Planning with Loops

Hector J. LevesqueIJCAI 2005

Introduction

In the field of AI planning, specifying sequential actions (e.g., "pick up the block") or conditional branches (e.g., "if the light is red, stop") is relatively straightforward. However, representing iterative tasks—such as "chop the tree until it falls"—presents a significant challenge. Traditional approaches to iterative planning often rely on heavy-duty theorem proving and mathematical induction to guarantee loop correctness, which are notoriously difficult to automate.

Hector J. Levesque's work introduces a pragmatic alternative: KPLANNER. Instead of seeking a universal proof of correctness, KPLANNER generates a plan for a small instance of a problem and tests its robustness against larger instances.

The KPLANNER Methodology

KPLANNER utilizes a "generate-and-test" strategy built upon the situation calculus. The process is decoupled into generation and verification phases:

  1. Identify the Planning Parameter ($F$): The user defines an unknown quantity, such as the number of actions required to reach a goal.
  2. Establish a Generating Bound ($N_1$): The planner searches for a conditional plan that succeeds when $F$ is very small (e.g., $F \le 1$).
  3. Loop Discovery via Unwinding: KPLANNER analyzes the small conditional plan for repetitive structures that resemble "unwound" loops. It then "rewinds" these structures into a formal iterative plan.
  4. Verification via Testing Bound ($N_2$): The proposed iterative plan is tested against a significantly larger bound (e.g., $F \le 100$). If the plan holds, it is accepted as a solution.

This approach bypasses the need for loop invariants by leveraging symbolic pattern matching in Prolog to identify iterative structures efficiently.

Benchmarks and Evaluation

The system was evaluated on several classic logic-based planning problems:

  • Tree Chopping: Repeatedly chopping a tree until it falls.
  • Counting: Synchronizing accumulators based on integer inputs.
  • Binary Tree Search: Navigating an unbounded tree for a target node.
  • The Egg Problem: A sensing-heavy task requiring a specific number of "good eggs" to be placed in a bowl while filtering out bad ones.

Results and Scalability

KPLANNER demonstrates remarkable speed for small, complex problems. For instance, it found the correct iterative plan for tree chopping in 0.11 seconds and solved a nested loop binary tree search in 0.07 seconds.

However, the system encounters a "performance cliff" when the complexity of the required plan increases. This is most evident in the "Egg Problem." As the target number of good eggs increases, the search space for the initial conditional plan expands exponentially.

Performance of KPLANNER on the Egg Problem, showing the exponential increase in search time as the goal complexity grows.

As shown in the table above, while finding a plan for one or two eggs is nearly instantaneous, the computational cost for four eggs reaches approximately 28 minutes (1681 seconds). For five eggs, the search time is projected to exceed three weeks, highlighting a significant limitation in the current search control mechanisms.

Conclusion

KPLANNER offers a foundational perspective on trading off absolute formal perfection for practical, automated plan generation. By decoupling generation from verification and focusing on compact iterative structures, it provides a viable path for cognitive robotics, provided the initial search space remains manageable. Future work may involve improving forward filtering to mitigate the scalability issues observed in more complex sensing tasks.

Summary updated

BibTeX
@inproceedings{levesque2005planning,
  author = {Hector J. Levesque},
  title = {{Planning with Loops}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
}
Figure