Let's Learn Their Language? A Case for Planning with Automata-Network Languages from Model Checking

Jörg Hoffmann, Holger Hermanns, Michaela Klauck, Marcel Steinmetz, Erez Karpas, Daniele MagazzeniAAAI 2020 · DOI

Introduction

In the field of AI Planning (AIP), the Planning Domain Definition Language (PDDL) has long served as the standard for modeling how agents interact with their environments. However, as planning moves into more complex, real-world scenarios—such as robots collaborating with humans or navigating crowded airspaces—the limitations of PDDL are becoming increasingly apparent. This paper proposes a shift in perspective: adopting automata-network languages from the model-checking (MC) community, specifically Jani, to handle the intricacies of exogenous agents, probabilistic timing, and complex data structures natively.

The Limitations of PDDL

While PDDL is highly effective for goal-oriented agent actions, it struggles with environments containing exogenous agents—entities the planner does not control. Modeling a human worker who might take a coffee break or a third-party drone with its own trajectory requires awkward "hacks" in standard PDDL dialects. Researchers have attempted to address these gaps with extensions like PDDL+ or RDDL, but no single dialect currently offers a unified, robust solution for combining exogenous behavior, pre-defined plan structures, and advanced data structures like 3D occupancy grids.

The Automata-Network Paradigm

The authors advocate for using automata-network languages as a superior modeling front-end. Unlike the first-order logic basis of PDDL, these languages represent the world as a collection of interacting state machines. This approach offers several key advantages:

  • Agent-Centric Modeling: Every entity, whether the controlled robot or an external human, is modeled as its own automaton.
  • Synchronization: Automata communicate through shared labels or global variables, simplifying the modeling of reactive behaviors (e.g., "if the human signals 'next', the robot moves to 'inspect'").
  • Native Programming Constructs: Jani supports first-class data structures like arrays. In PDDL, a 3D grid might require thousands of individual predicates, leading to "grounding explosions." In Jani, it is a simple array.
  • Probabilistic Timing: Drawing from decades of formal methods research, these languages natively handle continuous-time Markov chains and complex probability distributions for action durations.

Case Study: Drone Navigation

To demonstrate the qualitative superiority of this approach, the authors present a drone control use case. Navigating a fleet through airspace with third-party traffic requires both collision avoidance and trajectory prediction.

Automata models for controlled and exogenous drones.

As shown in the figure above, both the controlled drone and the exogenous drone are modeled using the same state-machine formalism. The exogenous drone's non-deterministic movement is captured through probabilistic transitions (e.g., [1/9]), while spatial reasoning is handled via explicit array indexing (free[x+dx][y+dy]). This makes the model both more readable and computationally efficient compared to predicate-heavy PDDL versions.

Case Study: Human-Robot Collaboration

A second use case involves an aircraft assembly riveting process. Here, a robot must adapt to a human partner’s variable workflow and non-deterministic break times.

Synchronized automata for a robot and a human partner.

The automata-network approach allows for seamless synchronization between the two agents. As illustrated, the human automaton can transition to a break state with a specific probability, while shared labels like next! and next? ensure the robot reacts appropriately to human cues. This natural representation of "non-deterministic" choices allows the robot planner to adjust its strategy in real-time as these transitions occur.

Bridging the Gap

The paper emphasizes that AIP and MC should be viewed as complementary rather than redundant. While MC is traditionally used for offline verification of "safe regions," AIP excels at fast, online heuristic search. By adopting MC languages, the planning community can leverage sophisticated modeling tools while focusing on developing faster planning algorithms for these complex domains.

However, challenges remain. Current MC tools are designed for exhaustive verification rather than the "fast-forward" search typical of AI planning. Additionally, automata-network languages like Jani are currently less equipped to handle partial observability, a core strength of frameworks like POMDPs.

Conclusion

The authors propose a future vision where a hybrid architecture utilizes MC methods to prepare safe regions or heuristics offline, which are then utilized by planning algorithms for real-time execution. By "learning the language" of the model-checking community, AI planning can move beyond the constraints of PDDL and more effectively tackle the complexities of modern, multi-agent environments.

Summary updated

BibTeX
@inproceedings{hoffmann2020let,
  author = {Jörg Hoffmann and Holger Hermanns and Michaela Klauck and Marcel Steinmetz and Erez Karpas and Daniele Magazzeni},
  title = {{Let's Learn Their Language? A Case for Planning with Automata-Network Languages from Model Checking}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i09.7083},
}
Figure