GRAVITAS: A Model Checking Based Planning and Goal Reasoning Framework for Autonomous Systems

Hadrien Bride, Jin Song Dong, Ryan Green, Zhe Hou, Brendan P. Mahony, Martin Oxenham

TL;DR

This paper introduces GRAVITAS, a novel framework for autonomous systems that leverages model checking to achieve trustworthy planning and goal reasoning. By translating complex mission objectives into a formal model, GRAVITAS ensures that generated plans are not only efficient but also verifiable and explainable, addressing a critical gap in current autonomous system development.

What Problem Does This Paper Address?

Autonomous systems, particularly in complex environments like underwater exploration, often face uncertainty and dynamic events. While AI planning techniques have advanced, many struggle with providing interpretable, reliable, and verifiable behaviors. This leads to a "black box" problem where understanding why a system makes a certain decision is difficult, and guaranteeing its safety and correctness is challenging. The authors aim to bridge this gap by integrating model checking, a formal verification technique, into the planning and goal reasoning process, thereby enhancing trustworthiness and explainability.

Methods

The core of GRAVITAS is its use of model checking to solve planning and goal reasoning problems. The authors propose a new formalism called Goal Task Networks (GTNs), which are adapted to be compatible with the Process Analysis Toolkit (PAT), a model checker that supports concurrent, probabilistic, and timed systems.

Here's a breakdown of their approach:

  • GTN Formalism: GTNs are extended to incorporate guarded state transitions, making them directly translatable into CSP# (Communicating Sequential Processes), the modeling language used by PAT.
  • Model Checking for Planning: Planning problems are formulated as reachability properties within PAT. The model checker's ability to perform exhaustive search and provide witness traces allows for the generation of plans.
  • Goal Reasoning: The framework supports dynamic goal selection and re-planning. When unexpected events occur, GRAVITAS can assess the validity of the current plan and, if necessary, formulate a new one. This is achieved by modeling inconsistencies and incompatibilities as LTL properties.
  • Resource Constraints and Rewards: The system can incorporate resource constraints (e.g., energy levels) and goal priorities (rewards/penalties) into the planning process. This is done by extending GTN guards and transitions and by introducing a common currency (variable 'A') to evaluate overall resource consumption and goal achievement.
  • Hybrid Approach: To balance performance and guarantees, GRAVITAS employs a hybrid approach. Critical high-level decisions are made using model checking, while low-level plan execution might rely on external programs or heuristic planners, with verification of the translation.

Datasets

Not discussed in the paper. The paper focuses on a simulated AUV survey mission as a motivating example and experimental setup.

Key Insights and Ideas

  • Verification as Planning: The paper champions the idea that planning and verification are not separate concerns but can be integrated. Model checking provides a formal basis for ensuring the correctness of plans.
  • Trustworthy Autonomous Systems: By making plans verifiable and explainable, GRAVITAS directly addresses the need for trustworthy autonomous systems, especially in safety-critical applications.
  • GTNs for Model Checking: The adaptation of GTNs to be directly model-checkable in PAT is a key contribution, enabling the formal analysis of complex planning and goal reasoning scenarios.
  • Economic Framework for Goals: Using a common currency ('A') to represent rewards and resource consumption provides an intuitive and powerful way to handle multi-objective optimization and trade-offs in planning.
  • Handling Uncertainty: The model checking approach inherently handles uncertainty and non-determinism, making it well-suited for dynamic environments.

Key Results

The paper demonstrates the feasibility and effectiveness of GRAVITAS through a simulated AUV survey mission.

  • Performance: Testing on an NVIDIA Jetson TX2 showed that for two levels of planning detail, the system could produce plans within reasonable timeframes (around 1 second for re-planning in the case study). Level 1 planning (area order) was feasible for up to 5 survey areas, while Level 2 (entry/exit points) was feasible for fewer than 3 areas.
  • Verification: The framework successfully verified key properties, such as the AUV not running into obstacles, not running out of battery, and not surfacing near hostile vessels.
  • Dynamic Re-planning: The simulation showcased GRAVITAS's ability to dynamically re-plan in response to unexpected events like strong water currents, adjusting the mission to optimize for remaining energy and rewards.

Limitations and Future Work

  • Scalability: The paper acknowledges that model checking's state-space explosion can limit scalability, especially for more complex scenarios (Level 2 planning).
  • Low-Level Translation: While the framework generates high-level plans, translating these into low-level, executable commands for the AUV's actuators is an ongoing challenge. The paper mentions using algorithms like piecewise Bezier curves and future work with FMT* for continuous path planning.
  • In-Situ Experimentation: The current work is primarily based on simulations. The authors plan to conduct more realistic simulations and eventually in-situ demonstrations.
  • Extending Verification: Future work aims to extend verification from high-level plans to low-level plans to further enhance trustworthiness.

Summary updated

Abstract

While AI techniques have found many successful applications in autonomous systems, many of them permit behaviours that are difficult to interpret and may lead to uncertain results. We follow the "verification as planning" paradigm and propose to use model checking techniques to solve planning and goal reasoning problems for autonomous systems. We give a new formulation of Goal Task Network (GTN) that is tailored for our model checking based framework. We then provide a systematic method that models GTNs in the model checker Process Analysis Toolkit (PAT). We present our planning and goal reasoning system as a framework called Goal Reasoning And Verification for Independent Trusted Autonomous Systems (GRAVITAS) and discuss how it helps provide trustworthy plans in an uncertain environment. Finally, we demonstrate the proposed ideas in an experiment that simulates a survey mission performed by the REMUS-100 autonomous underwater vehicle.
BibTeX
@article{bride2019gravitas,
  author = {Hadrien Bride and Jin Song Dong and Ryan Green and Zhe Hou and Brendan P. Mahony and Martin Oxenham},
  title = {{GRAVITAS: A Model Checking Based Planning and Goal Reasoning Framework for Autonomous Systems}},
  journal = {Engineering Applications of AI},
  year = {2019},
  doi = {10.1016/j.engappai.2020.104091},
}
Figure