A logical measure of progress for planning
Aarati Parmar · 2002
Heuristic search planners are so far the most successful. Al-most all use as their heuristic an estimate of the distance to a goal state. We formalize a logical measure of progress, de-fined 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 iden-tify 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 en-tirely 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 func-tion 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. 1