Agent Design Consistency Checking via Planning

Nitin Yadav, John Thangarajah, Sebastian SardiñaIJCAI 2017 · DOI

TL;DR

This paper introduces a novel approach to automatically verify the consistency between an agent's design and its requirements using automated planning. By framing consistency checking as a search problem, their method offers higher coverage, faster execution, and the ability to handle complex design elements like loops, outperforming previous model-checking techniques.

What Problem Does This Paper Address?

Developing intelligent agent systems, particularly those based on the Belief-Desire-Intention (BDI) architecture, involves a multi-stage process from initial requirements specification to detailed design and finally implementation. A critical challenge in this process is ensuring that the detailed design accurately reflects the initial requirements. Inconsistencies at this early design stage can lead to significant costs and effort to fix later in the development lifecycle.

Previous work has attempted to address this by either formally verifying implemented agent code or by testing designs prior to implementation. While some approaches have focused on checking designs, they often lacked formal semantics, were incomplete, or struggled with scalability as designs grew in complexity. Specifically, handling loops in agent designs and unbounded subgoal reasoning presented significant hurdles for existing methods. This paper aims to bridge this gap by providing a formal, scalable, and more comprehensive method for checking design consistency against requirements.

Methods

The core innovation of this paper lies in framing agent design consistency checking as an automated planning problem. Instead of traditional trace extraction or model checking, the authors leverage classical planning techniques.

Here's a breakdown of their approach:

  • Formalization: They define a "requirement specification" as a pair of a scenario (a sequence of goals, percepts, and actions) and a goal tree (defining goal hierarchies). A "detailed design" is represented as a set of plans, where each plan has a trigger and a set of outputs.
  • Planning Domain Construction: They construct a planning domain (using a PDDL-like language) that encodes the agent's detailed design and the requirements.
  • Types: Objects are categorized into goal, plan, and step.
  • Predicates: These capture relationships like can-handle (plan to goal), sub-goal (plan to subgoal), goal-and/goal-or (goal types), child-goal (goal hierarchy), step-goal (scenario step to goal), and next (scenario step ordering).
  • Actions: Three core actions are defined:
  • handleGoal: Activates a plan when a goal is pending and can be handled.
  • generateGoal: Creates sub-goals for an active plan.
  • progressStep: Advances the scenario when a goal is met.
  • Handling Loops: To address loops in agent designs, they introduce a pending-goal metric and modify the handleGoal and generateGoal actions (renamed to executePlan). This allows the planner to manage multiple instances of pending goals, effectively handling cyclic dependencies.
  • Inconsistency Identification: For debugging, they introduce two "repair" actions, skipStep and swapStep, with associated costs. By minimizing the total cost in a planning problem with these actions, the planner can suggest modifications to resolve inconsistencies.

Datasets

The paper does not explicitly mention using pre-existing datasets. Instead, they generated a large benchmark of over 16,000 random instances. These instances were created by:

  1. Building Agent Details: Randomly generating agent designs based on three parameters: height (h), maximum goals per plan (g/p), and maximum plans per goal (p/g).
  2. Generating Scenarios: For each agent detail, multiple scenarios of varying lengths were constructed.

This generated benchmark allowed them to perform extensive empirical evaluation and comparison with previous methods.

Key Insights and Ideas

  • Planning as a Unified Solution: The most significant insight is that agent design consistency checking can be elegantly solved using automated planning. This shifts the paradigm from complex trace analysis or model checking to a well-established search problem.
  • Handling Loops is Crucial: The ability to handle loops in agent designs is a major advantage. Many real-world agent systems exhibit cyclic behaviors, and previous methods struggled to accommodate this. Their planning-based approach naturally handles these complexities.
  • Efficiency Gains: By framing the problem as planning, the authors demonstrate significant improvements in efficiency (lower run-time) and scalability compared to model-checking approaches, especially as agent designs become larger.
  • Debugging as Planning with Repair: The introduction of skipStep and swapStep actions with costs is a clever way to integrate debugging and inconsistency identification directly into the planning framework. This provides actionable feedback to designers.

Key Results

The paper presents strong empirical results from their benchmark of over 16,000 random instances:

  • Coverage: Their planning-based approach achieved significantly higher coverage (solved more instances within the 10-minute time limit) compared to previous model-checking approaches (MCMAS and NuSMV). For example, in one category, their approach solved 100% of cases, while model checkers solved significantly fewer.
  • Efficiency: The planning approach was considerably more time-efficient. For a specific complex category, fast-downward (their planner) averaged 0.298s, while MCMAS took 1.27s and NuSMV took 22.329s.
  • Scalability: The planning approach scales better with the size of the agent design. While model checkers' performance was heavily influenced by both branching factors (goals per plan, plans per goal), the planner's performance was more affected by the length of the scenario than the size of the design.
  • Loop Handling: The approach successfully handles designs with loops, a capability lacking in prior methods.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that while their approach is more scalable than previous ones, it can still be computationally intensive for very large and complex designs.
  • The current approach focuses on consistency between requirements and detailed design. Extending it to cover the entire development lifecycle, from initial specification to implementation, would be valuable.
  • Future Work:
    • The authors suggest exploring more advanced planning techniques to further improve efficiency and scalability.
  • Investigating how to automatically generate test cases from the identified inconsistencies could be a valuable extension.
  • Extending the framework to handle other agent architectures or design methodologies beyond BDI and Prometheus is also a potential direction.

Summary updated

BibTeX
@inproceedings{yadav2017agent,
  author = {Nitin Yadav and John Thangarajah and Sebastian Sardiña},
  title = {{Agent Design Consistency Checking via Planning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/65},
}
Figure