Exploiting temporal coherence in nonlinear plan construction

Publisher Website
Google Scholar
Abstract
Correct conventional nonlinear planners operate in accordance with Chapman's modal truth criterion (MTC). The MTC characterizes the conditions under which an assertion will be true at a point in a nonlinear plan. However, the MTC is not all one requires in order to build a realistic planning system: it merely sanctions the use of a number of plan modifications in order to achieve each assertion in a developing plan. The number of modifications that can be made is usually very large. To avoid breadth‐first search a planner must have some idea of which plan modification to consider. We describe a domain‐independent search heuristic called temporal coherence, which helps guide the search through the space of partial plans defined by the MTC. Temporal coherence works by suggesting certain orderings of goal achievement as more appealing than others, and thus by finding bindings for plan variables consistent with the planner's overall goals. Our experience with a real nonlinear planner has highlighted the need for such a heuristic. In this paper, we give an example planning problem and use it to illustrate how temporal coherence can speed the search for an acceptable plan. We also prove that if a solution exists in the partial plan search space defined by the MTC, then there exists a path to that solution which is sanctioned by temporal coherence.

This publication has 6 references indexed in Scilit: