Abstract
Automated planning often faces a dichotomy between declarative goals, which specify what to achieve, and procedural plans, which specify how to achieve it. In nondeterministic environments, relying on a single paradigm often leads to either computational intractability or brittle execution. This paper introduces a framework that fuses these approaches into a single Extended Goal Language (EGL). By allowing users to provide procedural "sketches" containing loops, conditionals, and failure handling, the system transforms complex goals into control automata that guide the planner efficiently. Experimental results in robot navigation and web service composition demonstrate that this hybrid approach can achieve orders of magnitude speedup and near-linear scalability compared to purely declarative methods.
Introduction
In classical AI planning, goals are typically expressed declaratively. While elegant, this approach often suffers from state-space explosion in nondeterministic domains where actions have uncertain outcomes. Conversely, purely procedural scripts are efficient but lack the flexibility to handle unexpected environmental changes. The core problem addressed in this research is the lack of a formal framework that allows for the seamless integration of high-level temporal requirements with procedural plan fragments.
Methodology: The Extended Goal Language
The authors propose an Extended Goal Language (EGL) that supports a rich set of constructs designed to bridge the gap between high-level intent and low-level execution:
- Primitive Actions and Control Structures: Standard sequences, conditionals (
if-else), and loops (while). - Failure Handling: A
try-catchconstruct designed specifically for nondeterministic outcomes, allowing explicit recovery behaviors for known edge cases. - Search Control: A
policyconstruct to prune the search space by restricting action choices for specific sub-goals. - Declarative Integration: The ability to embed temporal logic goals (e.g., CTL or EAGLE) within procedural flows.
To operationalize these goals, the EGL is transformed into a Control Automaton. This automaton serves as a state machine that guides the planner's search process. Instead of searching for any path to a goal state, the planner seeks a plan that satisfies the transitions defined by the goal's automaton.
Experimental Evaluation
The approach was evaluated in two primary domains to test its robustness and scalability:
- Robot Navigation Domain: A robot must navigate through $N$ rooms to find, disarm, or destroy bombs. This domain is specifically designed to test scalability as the number of rooms increases.
- Web Service (WS) Composition: Coordination of multiple services (e.g., bookstore, shipping) to fulfill complex user requests, testing the language's ability to handle intricate, message-based interactions.
Results and Discussion
The experimental results highlight several key insights regarding the fusion of planning paradigms:
- Scalability: In the robot domain, planning time for purely declarative goals increased exponentially with the number of rooms. The fused approach, however, scaled almost linearly, demonstrating the power of procedural guidance.
- Efficiency: In the Web Service domain, the hybrid method successfully managed 13+ services, whereas purely declarative reachability goals became impractical much earlier.
- Procedural Guidance as Search Control: Procedural fragments act as search guidance rather than rigid scripts. This allows the planner to solve smaller sub-problems independently, effectively turning exponential search into a linear one.
Conclusion
Fusing procedural and declarative goals provides a powerful mechanism for planning in complex, nondeterministic domains. While there is some overhead in constructing the control automaton for trivial problems, the benefits in realistic, large-scale scenarios are substantial. Future work includes integrating this framework with Hierarchical Task Networks (HTN) and further exploring the formal expressiveness of the hybrid language.
Summary updated