Automaton Plans

Christer Bäckström, Anders Jonsson, Peter Jonsson

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.

A Mealy machine transducer used in an automaton plan 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

Abstract

Macros have long been used in planning to represent subsequences of operators. Macros can be used in place of individual operators during search, sometimes reducing the effort required to find a plan to the goal. Another use of macros is to compactly represent long plans. In this paper we introduce a novel solution concept called automaton plans in which plans are represented using hierarchies of automata. Automaton plans can be viewed as an extension of macros that enables parameterization and branching. We provide several examples that illustrate how automaton plans can be useful, both as a compact representation of exponentially long plans and as an alternative to sequential solutions in benchmark domains such as Logistics and Grid. We also compare automaton plans to other compact plan representations from the literature, and find that automaton plans are strictly more expressive than macros, but strictly less expressive than HTNs and certain representations allowing efficient sequential access to the operators of the plan.
BibTeX
@article{backstrom2014automaton,
  author = {Christer Bäckström and Anders Jonsson and Peter Jonsson},
  title = {{Automaton Plans}},
  journal = {J. Artif. Intell. Res.},
  year = {2014},
  doi = {10.1613/jair.4391},
}
Figure