Domain Compilation for Embedded Real-Time Planning

NASA Tech Briefs, Jan 2005

Robustness is increased at the price of a moderate increase in complexity.

NASA's Jet Propulsion Laboratory, Pasadena, California

A recently conceived approach to automated real-time control of the actions of a robotic system enables an embedded real-time planning algorithm to develop plans that are more robust than they would otherwise be, without imposing an excessive computational burden. This approach occupies a middle ground between two prior approaches known in the art as the universal-plan and hybrid approaches.

Ever since discovering the performance limitations of taking a sense-plan-act approach to controlling robots, the robotics community has endeavored to follow a behavior-based approach in which a behavior includes a rapid feedback loop between state estimation and motor control. Heretofore, system architectures following this approach have been based, variously, on algorithms that implement universal plans or algorithms that function as hybrids of planners and executives. In a typical universal-plan case, a set of behaviors is merged into the plan, but the system must be restricted to relatively small problem domains to avoid having to reason about too many states and represent them in the plan. In the hybrid approach, one implements actions as small sets of behaviors, each applicable to a limited set of circumstances. Each action is intended to bring the system to a subgoal state. A planning algorithm is used to string these actions together into a sequence to traverse the state space from an initial or current state to a goal state. The hybrid approach works well in a static environment, but it is inherently brittle in a dynamic environment because a failure can occur when the environment strays beyond the region of applicability of the current activity.

In the present approach, a system can vary from the hybrid approach to the universal-plan approach, depending on a single integer parameter, denoted n, which can range from 1 to a maximum domain-dependent value of M. As illustrated in the figure, n = 1 represents the hybrid approach, in which each linked action covers a small part of the state space of the system. As n increases, the portion of state space associated with each action and its subgoal grows. When n reaches M, coverage extends over the full state space, so that the system contains a universal plan.

Through incorporation of an embedded real-time planning algorithm that follows this middle-ground approach, a hybrid system can be made much more robust in a dynamic environment. In such a system, the planning algorithm passes the current subgoals (instead of activities) to an executive algorithm. The executive algorithm then uses the real-time planning algorithm to determine when to perform which action until it determines either that the current subgoals have been reached or that, they cannot be reached within n steps. If the current subgoals have been reached, the planning algorithm gives new subgoals to the executive algorithm. If it has been determined that the current subgoals cannot be reached, the planning algorithm must alter the sequence of actions.

A structure for finding the next step on an n or fewer step path to a subgoal is called a universal(n) plan. Because complexity increases sharply with n, it is necessary to choose n small enough to avoid an excessive computational burden but large enough that it is possible to make a universal (n) plan that makes the system robust in the sense that it can reach each given subgoal state from any state in a large region of the state space.

This approach involves utilizing knowledge compilation research by implementing an off-line compiler that generates a universal (n) plan from a system description. In the first step of a two-step process, the system description is converted into a logical expression, in what is known as a conjunctive normal form (CNF) that is based on the effects and preconditions of actions in an n-step plan. In the second step, the aforementioned research results are used to convert the CNF representation into a decomposable negation normal form (DNNF) representation. It turns out that the computation time needed to evaluate a DNNF expression to compute an optimal n-step plan increases only linearly with the DNNF representation size.

This work was done by Anthony Barrett of Callech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Information Sciences category.

The software used in this innovation is available for commercial licensing. Please contact Don Hart of the California Institute of Technology at (818) 393-3425. Refer to NPO-40296.