A Logical Measure of Progress for Planning

Aarati Parmar, Stanford University

Heuristic search planners are so far the most successful. Almost all use as their heuristic an estimate of the distance to a goal state. We formalize a logical measure of progress, defined as a predicate P(x,s) true of objects x at a situation s. Actions which increase P’s extension are guaranteed to move closer to a goal situation, so that P enables us to form plans without search. One example of a measure of progress is the concept of final position used in BlocksWorld. It is not clear how to find a P for an arbitrary domain, so instead we identify three different classes of domains and conditions which allow us to construct a measure of progress. An obvious P will not deliver optimal plans, but it should encode plans which are "good enough." Our paradigm is entirely within first-order logic, allowing us to extend our results to concurrent domains and those containing non-trivial state constraints. It turns out P not only encodes goal orderings, but subgoal orderings. P also gives rise to a strategy function a(s) which can be used to create a universal (complete) teleo-reactive (TR) program. Given the fact that P-increasing actions will never require backtracking, this TR program can be a powerful on-line planner.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.