Inductive verification and validation of multi agent systems

Nico Jacobs, Kurt Driessens, Luc De RaedtEUROVAV 1998 · OpenReview

Introduction

Traditional software Verification and Validation (V&V) typically relies on deductive reasoning. In this paradigm, developers write a formal specification of how a system should behave and then use automated tools to check if the implementation matches that specification. However, for Multi-Agent Systems (MAS)—such as teams of autonomous robots—this approach often fails. MAS are reactive, proactive, and operate in noisy, uncertain environments. Writing a complete, formal specification for such systems is frequently as difficult as writing the code itself. Furthermore, the "emergent behavior" resulting from the interaction of multiple agents is notoriously difficult to predict or specify upfront.

This paper proposes a paradigm shift toward inductive V&V. Instead of treating the specification as a prerequisite, the authors use machine learning to "reverse engineer" the specification from the code's actual behavior. By observing the system in action, they generate a human-readable map of its logic, allowing developers to identify discrepancies between intended and actual behavior.

Methodology: Inductive Logic Programming

The core technique employed is Inductive Logic Programming (ILP). ILP sits at the intersection of machine learning and logic; it takes behavioral logs (examples) and domain rules (background knowledge) to produce hypotheses in the form of logic programs (Prolog). This symbolic approach is chosen specifically because the resulting rules are readable by human experts, unlike the "black box" nature of neural networks.

The researchers utilized two specific ILP systems:

  • Tilde: Used for predictive induction. It generates logical decision trees to classify agent actions based on the state of the world.
  • Claudien: Used for descriptive induction. It identifies general regularities or "clausal theories" that hold true across the data, helping to describe the relationships between different agents' beliefs.

Experimental Setup and Data

The researchers used the RoboCup simulator as their primary testbed. They logged the behavior of 11 software agents during a 10-minute game, resulting in a dataset of approximately 17,000 models (snapshots of the environment and agent states). The logs captured player positions, ball coordinates, and internal agent variables, such as "bucket" values—a mechanism used to force agents back to their home positions to maintain formation.

Key Insights

The Specification as an Output

The most significant conceptual contribution is the idea that the specification is the result of the learning process. If the induced rules look "wrong" to the developer, they have discovered a bug. This allows for a form of human-in-the-loop debugging where the ILP tool highlights the actual logic the agents are following.

Identifying Emergent Bugs

The authors discovered that agents were behaving inconsistently due to the aforementioned "bucket" mechanism. The ILP tool highlighted that agents were returning to their home positions even when they should have been tracking the ball. This was an emergent flaw that was not obvious from the raw code but became clear once the high-level logic was induced.

Consistency of Beliefs

In a multi-agent system, agents often have different "opinions" on the state of the world. Using the Claudien system for descriptive induction, the authors found that agents' beliefs about player positions were generally consistent only when players were within 10 units of each other. This provided a quantitative measure of how well the agents were "syncing" their worldviews.

Results

The inductive approach led to measurable improvements in system performance and understanding:

  • Bug Discovery & Optimization: Initial analysis showed the watch_ball action was only predictable with 73.4% accuracy. By using the induced rules to identify and remove the faulty home-position mechanism, the researchers improved the consistency of the agent's behavior, raising the accuracy of the predicted action to 99.6%.
  • Validation of Coordination: The system discovered a rule with 78% accuracy stating that if two agents are within 10 units of a player, their beliefs about that player's position will differ by less than 2 units. This served as a formal validation of the team's coordination capabilities.

Limitations and Future Work

While promising, the method currently depends on human experts to judge the correctness of the induced rules. Furthermore, the quality of the output is heavily reliant on the "background knowledge" provided to the ILP system; if the high-level concepts are poorly defined, the system may produce rules that are too low-level to be useful. Future research will focus on testing this framework on other complex MAS architectures and exploring the automatic generation of decision tables from existing knowledge bases.

Summary updated

BibTeX
@inproceedings{jacobs1998inductive,
  author = {Nico Jacobs and Kurt Driessens and Luc De Raedt},
  title = {{Inductive verification and validation of multi agent systems}},
  booktitle = {EUROVAV},
  year = {1998},
  url = {https://openreview.net/forum?id=VkLVHAIPTIU},
}
Figure