Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Planning with Incrementally Created Graphs



Stephen B. Balakirsky, Otto H. Herzog


A framework for planning algorithms that is both optimal and complete will be presented that allows for the planning of optimal paths through a multi-level hierarchy of annotated graph spaces. A rich world model that contains multi-resolution attributes, costs, and predicates controls the integrated incremental construction and evaluation of the planning graph in dynamic environments. The properties of this framework are proven and a number of example problem domains are presented that show how this framework can incorporate both hard and soft constraints during both graph construction and arc evaluation.
NIST Interagency/Internal Report (NISTIR) - 6895
Report Number


optimal plan, planning, planning graph, world model


Balakirsky, S. and Herzog, O. (2002), Planning with Incrementally Created Graphs, NIST Interagency/Internal Report (NISTIR), National Institute of Standards and Technology, Gaithersburg, MD (Accessed April 21, 2024)
Created June 30, 2002, Updated October 12, 2021