A Logical Measure of Progress for Planning

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Planning

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.