Introduction
In automated planning, a solution is typically a sequence of actions leading from an initial state to a goal. For complex domains, these sequences can grow exponentially, making them difficult to store, communicate, or verify. Traditional compression techniques like macros (fixed action sequences) are often too rigid, while Hierarchical Task Networks (HTNs), though expressive, are computationally expensive to verify (often PSPACE-hard). This paper introduces automaton plans, a novel representation using hierarchies of Mealy machines that bridges the gap between simple macros and complex HTNs.
Methods: Hierarchies of Mealy Machines
The core of an automaton plan is the Mealy machine—a finite-state transducer that produces an output for every input symbol. In this framework, the output can be a primitive action or a call to another automaton within an acyclic hierarchy.
By using input strings to drive the machine, a single automaton can represent a family of plans. For instance, different input symbols can trigger different branches, allowing the plan to adapt to specific parameters (e.g., choosing between a truck or a plane in a logistics task) without needing a separate macro for every variation. To ensure efficient "random access" to specific actions, the authors identify a "uniform expansion" subclass where every call results in a sequence of the same length.
Complexity and Expressiveness
Automaton plans occupy a unique position in the expressiveness hierarchy. They are strictly more powerful than macros but less expressive than full HTNs. Crucially, the authors prove that verifying an automaton plan—checking if the generated sequence actually solves the planning problem—is $\Pi^p_2$-complete. This complexity is significantly lower than the PSPACE-completeness associated with general STRIPS planning or HTNs, representing a "sweet spot" for practical verification.
Unlike HTNs, which often branch based on the dynamic state of the world, automaton plans branch based on static input symbols. This state-agnostic expansion is key to their lower verification complexity and allows for polynomial-time sequential access to actions.
Key Results and Benchmarks
The representational efficiency was evaluated using classic planning benchmarks:
- Towers of Hanoi: A linear number of small automata can represent the optimal $2^n - 1$ action plan.
- LOGISTICS & GRID Domains: Parameterization allows a single structure to solve various problem instances by varying the input string.
Furthermore, the authors demonstrate that for the uniform expansion subclass, one can jump to any arbitrary $i$-th action in polynomial time (random access), a property not generally shared by HTNs.
Conclusion and Future Work
Automaton plans provide a compact, verifiable, and flexible way to represent complex planning solutions. While the current model requires an acyclic hierarchy to avoid PSPACE-hard verification, it offers a powerful alternative to traditional plan formats. Future research will focus on developing planners that natively synthesize these automaton structures and extending the framework to handle contingent planning where agents react to environmental observations.
Summary updated