Auditable and Deployable Multi-Agent Motion Planning via Posetal Games from Legal Guidelines

The gist: This work presents a framework for multi-agent motion planning under legal requirements based on games with partially ordered preferences (posetal games) that automates the translation of practical scenarios into posetal games from scenario-independent legal guidelines.

Framework for Legal Posetal Games

The framework systematically derives agent preferences and a legal game from abstract legal concerns, which are specified as a partial order over abstract legal concerns, resulting in posetal games The key idea is to separate what the law prescribes from what a scenario instantiates Regulators specify a guideline, i.e., a partial order over abstract legal concerns such as collision avoidance, and every concrete scenario inherits the preferences of its agents by matching their legal metrics to these concerns. Since every customization of the resulting preferences is a refinement, and refining preferences can only remove equilibria, legality is preserved by construction

Customization with Legality Guarantees

The framework enables agents to incorporate private objectives and regulators to refine legal guidelines, and it is proven that such refinements can only restrict the set of legal behaviors rather than introduce new ones. This sharply contrasts with scalarization methods (e.g., [28]–[31]), in which changing even a single weight can alter the resulting behavior in ways that are to predict and audit.

Deployable Solution Protocols

To coordinate agents without explicitly communicating private preferences, the authors introduce two protocols:

1. Belief play recovers the true equilibria from conservative local approximations The protocol relies on agents constructing their local game G i based on beliefs P i j about other agents' true preferences, and then intersecting the NEs of these local games to find the socially optimal Nash equilibrium γ∗ = arg max γ∈NE(G) (s(γ))

2. Distributed iterative best-response (IBR) requires even less information about other agents This protocol involves agents assembling an initial action profile, forwarding it, and having each agent replace its action with a best response under its true preference until a fixed point is reached

Auditability and Case Study Application

The framework is applied to maritime navigation, systematically lifting pairwise traffic rules to multivessel 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. This demonstrates that agents can audit every rule violation and justify it in terms of conflicting higher-priority requirements

Regulatory Change Handling

The framework accommodates regulatory change through guideline refinement operations, such as Priority Refinement, Injection, and Augmentation. These operations ensure that a finer guideline can only shrink the set of legal equilibria, as the equilibrium map is antitone The authors show how adding an edge to the partial order over metrics can enforce new priorities between concerns while preserving legality

Evaluation Results

The evaluation in one-shot COLREGS motionplanning games verified that every rule violation at the committed equilibria can be audited and that defectors can be identified from public information. The comparison between belief play and distributed IBR showed that distributed IBR exchanges solution quality for communication efficiency and weaker information assumptions compared to belief play Distributed IBR converges to a true equilibrium in all four considered scenarios while communicating far fewer action profiles than belief play

Conclusion

The framework successfully provides an auditable route from partially specified laws to multi-agent motion planning via posetal games. The authors conclude that private objectives can only select among legal behaviors and never turn an illegal action profile into an equilibrium. The work demonstrates the practical applicability of guideline-based posetal games for complex, real-world scenarios like maritime navigation

How it works

The authors introduce partially ordered sets and preferences to formalize the evaluation of outcomes with respect to multiple metrics prioritized according to a partial order A preference P is defined as a finite poset of metrics, where m ⪯P m′ indicates that m′ is at least as important as m Posetal games G are then constructed using these preferences, where rational agents strive to play their best response to the actions of the others

Legal Metrics and Guidelines

Legal metrics are derived from temporal logic specifications of pairwise rules, where the metric for agent i in scenario S is Mlegal i:= m φi,j φ ∈ Φ, j ∈ A−i (γ) = min(ρφi,j (γ), 0) (4) Guidelines G are introduced to represent abstract legal concerns as a poset G:= ⟨CG, ⪯G⟩ Definition 2 shows that the induced preference P(M, G) picks, for each concern in CG, all metrics from M addressing that concern; if a metric addresses multiple concerns, several copies of it appear in the preference

Game Construction and Legality Proof

The true game Gtrue is constructed by augmenting the legal preference with individual objectives using Proposition 3 to incorporate private objectives while never overriding a priority prescribed by the law The set of all legal action profiles precisely corresponds to the NEs of the legal game Glegal:= ⟨A, Γi, P(Mlegal i, G legal)⟩ Theorem 1 proves that NE(Gtrue) ⊆ NE(Glegal), meaning private objectives can only select among legal behaviors and never turn an illegal action profile into an equilibrium

Solution Protocols in Detail

The belief play protocol assumes that agent i has a belief P i j about the true preference of agent j, and it solves Gtrue by intersecting the NEs of the local games G i:= ⟨A, Γ j, P i j⟩ The distributed IBR protocol performs best-response iteration where an agent replaces its action with a best response under its true preference until a fixed point is reached

Evaluation Metrics

The social metric s(γ) is defined as s(γ):= s coll(γ), s enc(γ), where these components respect the priority of the guideline, meaning no improvement in encounter compliance can compensate for a worse collision outcome The performance metrics P perf i are placed below the legal preference using Proposition 3 to ensure that compliance is never free

Refinement Operations

Three refinement operations support regulatory changes: Priority Refinement, Injection, and Augmentation. Priority Refinement allows regulators to clarify priorities between concerns by adding an edge to the partial order over metrics Injection allows splitting a concern into several more specific ones that can be prioritized individually via the injection operator ⋉Cˆ Augmentation combines two guidelines by appending one below the other, which is analogous to Proposition 3 for preferences

Future Work

Several directions remain open, including extending the framework into a receding-horizon scheme where agents repeatedly re-solve the game as the encounter evolves and refine their beliefs about the preferences of others. Deploying such a scheme on real vessels requires realtime capable solvers, and establishing conditions under which the COLREGS game is a potential game would guarantee convergence of distributed IBR The auditability results are relative to the finite action lattice, and characterizing how the audit outcome depends on this discretization would strengthen legal interpretation The authors also suggest applying the framework to other domains in which regulators specify only partial priorities, like autonomous driving or airborne collision avoidance

References

[1] J. Tumova, G. C. Hall, S. Karaman, E. Frazzoli, and D. Rus, “Leastviolating control strategy synthesis with safety rules,” in Proc. of the Int. Conf. on Hybrid Systems: Computation and Control (HSCC), 2013

[2] T. Wongpiromsarn, K. Slutsky, E. Frazzoli, and U. Topcu, “Minimumviolation planning for autonomous systems: Theoretical and practical considerations,” in Proc. of the American Control Conf. (ACC), 2021

[3] A. Censi, K. Slutsky, T. Wongpiromsarn, D. Yershov, S. Pendleton, J. Fu, and E. Frazzoli, “Liability, ethics, and culture-aware behavior specification using rulebooks,” in Proc. of the IEEE Int. Conf. on Robotics and Automation (ICRA), 2019

[4] A. Zanardi, G. Zardini, S. Srinivasan, S. Bolognani, A. Censi, F. Dorfler, ¨ and E.

1. The system can perform Systematic construction of legal posetal games, which means it can automatically derive agent preferences and a legal game for any concrete scenario from abstract legal guidelines, removing the need to specify preferences by hand for every scenario.

2. The system can handle regulatory evolution by implementing Guideline refinement operations, such as Priority Refinement (adding an edge) or the injection operator, allowing regulators to update priorities while guaranteeing that legality is preserved by construction because refinements can only remove equilibria and thus preserve legality.

3. The system can coordinate agents without explicit communication using the belief play protocol, which leverages conservative local beliefs to recover the true equilibria from local games, as proven by Theorem 2: NE(Gtrue) = i∈A NE(Gi).

4. The system can perform auditability on motion plans, where it can audit every rule violation and certify it as either forced by the legal hierarchy or unsatisfiable within the action space, allowing for the identification of defectors from public information alone.

5. The system can solve complex multi-agent problems under uncertainty using a distributed iterative best-response (IBR) protocol, which is more communication-efficient than belief play, although it does not guarantee to find the socially optimal equilibrium and requires restarts to recover optimality.