Abstract
Multi-agent coordination often relies on social laws—predefined restrictions on agent behavior that ensure conflict-free operation. Traditionally, these laws are hand-crafted. This paper introduces an automated framework for synthesizing social laws by treating the task as a heuristic search problem. By incorporating pruning techniques based on counter-examples and infeasibility, and utilizing a novel heuristic ($h_{stat}$), the proposed system autonomously generates robust social laws for diverse multi-agent planning domains.
Introduction
In multi-agent environments, uncoordinated agents frequently encounter conflicts, such as collisions or deadlocks. While centralized control and online negotiation are common solutions, they suffer from single points of failure and high communication overhead, respectively. Social laws offer a robust alternative by establishing "traffic rules" offline. If agents adhere to these laws, they can plan independently while guaranteeing global coordination. This research addresses the challenge of automated synthesis: computationally deriving these laws to replace manual expert design.
Methodology
The synthesis of social laws is framed as a search through the space of possible action restrictions. Starting from an empty law, the algorithm incrementally adds restrictions to forbid specific actions.
Search and Pruning
The search space is exponentially large ($2^{|A|}$). To manage this, the authors implement two primary pruning strategies:
- Counter-example Pruning: When a conflict is detected by the robustness verifier, the search focuses only on restricting actions involved in that specific conflict.
- Infeasibility Pruning: If a law becomes so restrictive that an agent cannot reach its goal, any further restrictions are immediately discarded.
Heuristics
A key contribution is the $h_{stat}$ heuristic. Similar to clause learning in SAT solvers, $h_{stat}$ tracks "troublemaker" actions that frequently lead to failures across different search branches, prioritizing their restriction.
Experimental Evaluation
The approach was tested on 91 problems across five domains from the International Planning Competition (IPC): Rovers, Driverlog, Zenotravel, Taxi, and Fix.
Key Results
The experiments demonstrated that automated synthesis is viable for complex coordination tasks. As shown in the summary table, the Greedy Best-First Search (GBFS) configuration using the $h_{stat}$ heuristic was the most effective, solving up to 18 problems.
A significant trade-off was observed between search efficiency and the "quality" (length) of the social law. While Breadth-First Search (BFS) consistently found the shortest laws (minimal restrictions), it was significantly slower than heuristic-driven methods like GBFS. The detailed data in the table above highlights this disparity; for instance, in the ROVERS-2 problem, BFS found a law of length 2, while DFS and GBFS produced much longer laws, albeit often with faster search times.
Discussion and Future Work
The primary bottleneck in the synthesis process remains the robustness check, which relies on external classical planners. Future work aims to improve scalability and expressiveness. Current laws only delete actions; future iterations could include conditional "wait-for" rules, allowing for more nuanced coordination. Additionally, extending the framework to temporal planning would enable the synthesis of laws for agents with time-sensitive actions.
Conclusion
This work marks a significant step toward fully autonomous multi-agent systems. By automating the creation of social laws, the framework reduces the need for human intervention in complex planning scenarios, providing a scalable and complete method for ensuring agent harmony.
Summary updated