TL;DR
This paper introduces a novel logical framework for defining "progress" in AI planning, moving beyond purely numeric heuristics. By formalizing progress as a predicate that must strictly increase with each action, the authors guarantee deadlock-free planning and provide a foundation for generating "good enough" plans that are never backtracked.
What Problem Does This Paper Address?
Modern AI planners, particularly those using heuristic search, rely heavily on estimating the distance to a goal state. While incredibly successful, these heuristics often lack interpretability – they tell us how far we are, but not why a particular action moves us closer or what structure in the domain makes planning efficient. This paper aims to bridge this gap by defining a logical measure of progress that not only guides planning but also explains the reasoning behind it, drawing inspiration from human intuition and domain structure. The authors are interested in understanding what properties of domains lead to efficient planning, rather than just finding faster algorithms.
Methods
The core contribution is the formalization of a "strong measure of progress" (P) as a predicate over objects and situations. A predicate P is considered a strong measure of progress if:
- If the goal is not met, there always exists an action that strictly increases the extension of P.
- If P is true for all relevant objects, the goal is met.
This definition guarantees that any action increasing P moves the system closer to the goal without undoing previously achieved subgoals. The paper then explores different ways to construct such measures:
- Strong Measure of Progress: A direct generalization of the "final position" heuristic in BlocksWorld.
- Tiered Uniformity: A characteristic of domains where goals can be broken down into a sequence of stages (e.g., moving a package through different transport modes). This leads to a "tiered" measure of progress.
- Orthogonal Measures of Progress: For domains where progress might involve two types of actions (P-increasing and C-increasing), where C-increasing actions might be necessary to clear obstacles for P-increasing actions. This is visualized with a contour map analogy.
The paper also introduces theorems proving that the existence of a strong measure of progress implies a deadlock-free domain, and conversely, deadlock-free domains possess such measures.
Datasets
Not discussed in the paper. The paper focuses on formalizing concepts and demonstrating them with abstract domain examples like BlocksWorld, Kitchen Cleaning, and Logistics World.
Key Insights and Ideas
- Logical Progress vs. Numeric Heuristics: The paper argues for the power of logical predicates over numeric distance estimates for understanding and guiding planning.
- Guaranteed Progress and No Backtracking: The strict increase in the predicate's extension ensures forward progress and eliminates the need for backtracking, leading to more interpretable and potentially more efficient plans.
- Domain Structure is Key: The research emphasizes that obvious measures of progress arise from inherent domain structures, making planning intuitive for humans and potentially automatable for AI.
- Deadlock-Free Planning: The existence of a strong measure of progress is shown to be equivalent to a domain being deadlock-free.
- "Good Enough" Plans: While not guaranteeing optimality, these measures aim to produce plans that are "good enough" by ensuring subgoals are never undone and progress is always made.
Key Results
- Formal definition of a "strong measure of progress" (P) and theorems establishing its equivalence to deadlock-free planning.
- Demonstration of how to construct strong measures of progress for specific domain types:
- Kitchen Cleaning Domain: A measure Pkc is derived based on a <P ordering.
- Logistics World: A "tiered uniformity" characteristic is identified, leading to a Ptiered measure.
- A method for combining orthogonal measures of progress (P and C) to handle more complex scenarios.
- The paper shows that the strategy function derived from a strong measure of progress can be used to create a universal, complete, teleo-reactive (TR) program.
Limitations and Future Work
- Automatic Construction: The paper acknowledges that automatically discovering a strong measure of progress for an arbitrary domain is a difficult (at least PSPACE-hard) problem, which is left as future work.
- Deadlock-Prone Domains: The current formalization of a "strong measure of progress" requires domains without deadlocks. Weakening this definition for domains with deadlocks is suggested.
- Concurrency: The current framework is primarily within the situation calculus, which doesn't inherently handle concurrency. Extending the framework to handle parallel actions is proposed.
- Expressive Ramifications: While the framework can adapt to some ramifications, handling domains with more complex or circular ramifications might require further work.
- Combining Measures: While Theorem 6 shows how to combine measures, the paper suggests developing more elaborate ways to combine them and construct better actions that might move multiple objects simultaneously.
Summary updated