Multi-agent robot motion planning respects legal rules and detects rule breakers
Auditable and Deployable Multi-Agent Motion Planning via Posetal Games from Legal Guidelines
Multiagent SystemsComputer Science and Game TheoryRobotics
Summary
When robots move around in places like sea lanes, they need to follow laws while achieving their goals alongside others. The authors created a way to turn legal rules into a kind of game where robots plan their movements with partially ranked preferences instead of fixed priorities. This method can find plans where robots follow the law as much as possible and also spot who breaks rules just from public information. They tested their approach with up to four ships navigating together and verified that any rule violations were either forced or clearly identified.
What this means in practice
- •For maritime navigation teams: Coordinate multiple vessels to follow traffic rules while planning safe paths and identify rule violations without direct communication.
- •For robot fleet operators: Plan coordinated movements of multiple robots that can adapt to evolving legal rules and private objectives while ensuring legality is preserved.
Authors
Florian Lercher, Karan Mahesh, Yujun Huang, Meshal Alharbi, Runyu Zhang, Hanna Krasowski, Michael R. Benjamin, Matthias Althoff, Gioele Zardini
Abstract
When robots are deployed in the real-world, they must interact with other agents and accomplish their own goals while adhering to legal constraints. These potentially conflicting objectives are often only partially prioritized, making scalarized objectives or fully specified hierarchies unsuitable. We present a framework for multi-agent motion planning under legal requirements based on games with partially ordered preferences (posetal games). Scenario-independent legal guidelines order abstract legal concerns, from which we automatically derive agent preferences and a legal game for any concrete scenario. Agents may refine their legal preferences with private objectives, and regulators may refine the guideline as laws evolve. We prove that such customizations can only remove equilibria and thus preserve legality. To coordinate agents without explicitly communicating private preferences, we introduce belief play, which provably recovers the true equilibria from conservative local games, and a distributed iterative best-response protocol requiring less information. We apply the framework to maritime navigation, systematically lifting pairwise traffic rules to multi-vessel encounters. On seven encounters with up to four vessels, every rule violation of the committed equilibria is certified as forced by the legal hierarchy or unsatisfiable, and defectors are identified from public information in all tested cases. These results indicate that guideline-based posetal games offer an auditable route from partially specified laws to multi-agent motion planning.