Handling non-local dead-ends in Agent Planning Programs

Lukás Chrpa, Nir Lipovetzky, Sebastian SardiñaIJCAI 2017 · DOI

TL;DR

This paper introduces a novel approach to improve the performance of Agent Planning Programs (APPs) by incorporating "global reasoning" about potential future dead-ends. By identifying and avoiding states that could lead to unsolvable future planning problems, the authors significantly increase the success rate of both online and offline APP execution.

What Problem Does This Paper Address?

Agent Planning Programs (APPs) are a powerful framework for representing complex, long-term agent behaviors that involve sequences of goals, user interaction, and continuous operation. Unlike traditional planning problems, APPs are essentially directed graphs where nodes represent program states and edges represent planning problems. The challenge arises because solving each individual planning problem (a "local" problem) in isolation doesn't guarantee a solution for the entire APP. This is because a plan chosen for one step might lead to a world state from which a future goal in the APP becomes impossible to achieve – a "non-local dead-end." Existing methods often rely on expensive backtracking when such dead-ends are encountered, significantly hindering performance. This paper aims to mitigate this by proactively identifying and avoiding these non-local dead-ends.

Methods

The core contribution is the integration of "global dead-end reasoning" into APP solving. This is achieved by leveraging recent work on identifying "dead-end traps" – formulas that characterize states from which a goal is unreachable.

  • Dead-end Traps: The paper utilizes k-DNF dead-end traps, which are disjunctions of partial states that capture regions of the search space from which a goal is unattainable. These traps can be computed as a preprocessing step.
  • Offline Approach Enhancement: For existing offline APP solvers, the dead-end traps are used to prune states that would lead to future unsolvable problems. This information is encoded as global knowledge to inform the solving of local planning problems.
  • Online Approach: A new online execution model for APPs is proposed. In this model, after each planning step, the system identifies dead-end traps for all potential future goals. These traps are then incorporated as maintenance goals for the current planning problem, effectively preventing the agent from entering states that would jeopardize future success. This is a key innovation as online execution typically lacks the ability to backtrack extensively.

Datasets

The evaluation was conducted using 20 APPs generated for each of the following six planning domains from the International Planning Competition:

  • Airport
  • Floortile
  • Glued-Bw
  • Matching-Bw
  • Logistics
  • Woodworking

No new benchmarks were introduced; instead, existing domains were used to test the proposed techniques.

Key Insights and Ideas

  • Non-local dead-ends are the Achilles' heel of APPs: The paper convincingly argues that the primary reason for the difficulty in solving APPs lies in the interdependencies between planning steps, specifically how a choice in one step can preclude solutions for future steps.
  • Global reasoning can be localized: The key insight is that global information about future dead-ends can be effectively encoded into local planning problems, transforming a global challenge into a series of more manageable local constraints.
  • Online execution benefits immensely from proactive dead-end avoidance: While offline methods can sometimes recover through backtracking, online execution, which is more akin to real-world agent behavior, critically needs to avoid dead-ends upfront. The proposed online approach directly addresses this.
  • Dead-end traps are a modular enhancement: The technique is designed to be incorporated into existing planning systems, making it a flexible and valuable addition.

Key Results

The experimental evaluation demonstrated significant improvements:

  • Increased Robustness: Reasoning about non-local dead-ends consistently increased the number of solved APPs across various domains for both online and offline approaches.
  • Online Approach Performance: The "dead-end traps" enhanced online approach significantly outperformed the naive online approach, which lacked global reasoning.
  • Offline Approach Performance: The "dead-end traps" enhanced offline approach also showed improvements over the state-of-the-art offline method, particularly in domains where backtracking is costly.
  • Trade-off: While dead-end reasoning improves success rates, it does introduce a computational "tax," leading to longer execution times in cases where both approaches succeed. However, this tax is often outweighed by the ability to solve previously unsolvable problems.

Limitations and Future Work

  • Computational Cost of Traps: The computation of k-DNF dead-end traps can be exponential in k, and for domains with a very large number of atoms, this preprocessing step can become computationally expensive, leading to timeouts in some cases (e.g., the Airport domain).
  • Completeness of Traps: While the paper uses 2-DNF traps and notes their reasonable performance/cost ratio, it acknowledges that for sufficiently large k, all dead-ends are captured. Future work could explore theoretical guarantees of k-DNF traps for specific domains to improve robustness.
  • Hybrid Offline Approach: The use of a "hybrid" offline approach (combining LPG with other planners) limited the full exploitation of the "trapper" tool in some experiments.
  • Future Work: The authors suggest exploring theoretical guarantees of k-DNF traps, and also investigating the use of APP dead-end reasoning to solve classical planning problems by decomposing them into sub-goals, mitigating backtracking when subsequent goals become unachievable.

Summary updated

BibTeX
@inproceedings{chrpa2017handling,
  author = {Lukás Chrpa and Nir Lipovetzky and Sebastian Sardiña},
  title = {{Handling non-local dead-ends in Agent Planning Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/135},
}
Figure