PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Florian Lercher, Karan Mahesh, Yujun Huang, Meshal Alharbi, Runyu Zhang, Hanna Krasowski, Michael R. Benjamin, Matthias Althoff, Gioele Zardini

arXiv:2610.22277v1cs.MAcs.GTcs.ROcs.SYeess.SY

TL;DR

Multi-agent motion planning must handle legal objectives that may conflict and are only partially prioritized. The paper derives posetal games from scenario-independent legal guidelines and provides protocols for coordination under private preferences. In seven maritime encounters, rule violations were auditable and defectors were identifiable from public information.

  • Problem

    Legal multi-agent planning must reconcile conflicting, partially prioritized requirements while agents respond strategically and their private objectives are typically unknown.

    Source: §I · p. 1

  • Method

    The framework derives agent preferences and a legal game from scenario-independent guidelines, then coordinates agents through belief play or distributed iterative best-response.

    Source: §I · p. 2, §VII · p. 16

  • Results

    Across seven encounters involving two to four vessels, every rule violation was auditable as forced by legal priorities or unsatisfiable, and defectors were identifiable from public information.

    Source: B. Contributions · p. 3

  • Takeaways & Limitations

    Guideline-based posetal games offer an auditable route from partially specified laws to multi-agent motion planning.

    Source: §VII · p. 16

    Distributed best-response iteration is guaranteed to converge when the true game is a potential game; otherwise convergence is not guaranteed.

    Source: B. Distributed Iterative Best-Response · p. 10

Abstract

from arXiv · show

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.

I. INTRODUCTION

Legal multi-agent planning must reconcile potentially conflicting, partially ordered obligations while agents respond strategically and their private objectives remain unknown. Prior approaches leave gaps in representing these priorities, translating pairwise laws to multi-vessel encounters, and coordinating agents without complete preference information.

I. INTRODUCTION

1) Specifications for Robotic Interactions:

  • Formal specifications and rulebooks represent interaction requirements and prioritize objectives, but pairwise or fixed-priority structures can be incomplete for diverse multi-agent scenarios.Existing rulebooks permit lower-priority violations to satisfy higher-priority objectives, but do not fully resolve scenario-dependent strategic interactions.Source: 1) Specifications for Robotic… · p. 2

2) Motion Planning with Formal Objectives:

  • Scalar-cost multi-agent methods can obscure objective priorities, while formal-objective planning often assumes uncooperative surroundings or gives safety strict priority over performance.These formulations do not by themselves express the partial priorities that legal requirements may leave unspecified.Source: 2) Motion Planning with Formal… · p. 2

3) Games with Ordered Objectives:

  • Posetal games allow objectives to remain incomparable, unlike total-order games, but existing methods assume complete knowledge of every agent’s preferences.Prior approaches also lack a mechanism for translating general legal requirements into scenario-specific preferences.Source: 3) Games with Ordered Objectives · p. 2

4) COLREGS-Compliant Multi-Vessel Motion Planning:

  • Prior COLREGS formalizations support pairwise encounter monitoring and synthesis, but do not specify priorities among obligations in simultaneous multi-vessel encounters.Existing maritime approaches often monitor or model surrounding vessels rather than strategically coordinating heterogeneous preferences; scalarized or centralized methods also limit interpretability or private agent-specific preferences.Source: 4) COLREGS-Compliant Multi-Vessel… · p. 3

B. Contributions

The paper develops a framework that derives legal posetal games from scenario-independent guidelines and supports refinements and coordination under private preferences. Its preliminaries define posets, posetal games, preferences, and preference refinement.

B. Contributions

  • Scenario-independent guidelines automatically yield agents’ partially ordered preferences and a legal game for each concrete scenario.Agents may add private objectives and regulators may refine guidelines; these customizations restrict rather than expand legal behaviors.Source: B. Contributions · p. 3
  • Belief play recovers exactly the true game’s equilibria from conservative local beliefs, while distributed iterative best-response requires less information about other agents.The framework is instantiated for COLREGS encounters with two to four vessels, where violations can be audited and defectors identified from public information.Source: B. Contributions · p. 3

A. Games with Partially Ordered Preferences

  • A posetal game generalizes a classical scalar-utility game by evaluating outcomes with multiple metrics prioritized by a partial order.This allows some objectives to remain incomparable.Source: A. Games with Partially Ordered… · p. 3

1) Partially Ordered Sets:

  • A poset is a set equipped with a partial order, which can be visualized using a Hasse diagram.The order is reflexive, transitive, and antisymmetric.Source: 1) Partially Ordered Sets · p. 3

2) Preferences:

  • A preference is a finite poset of named metrics, with higher-ranked metrics indicating greater importance and inducing an ordering over actions.An action is at least as preferable when any metric on which it performs worse is dominated by a more important metric on which it performs better.Source: 2) Preferences · p. 4
  • Preference refinement preserves every strict action preference while making the induced ordering finer.Refinement can add priority relations, aggregate incomparable metrics, or replace multiple metrics with a strictly increasing aggregate.Source: 2) Preferences · p. 4
  • Replacing incomparable metrics with a strictly increasing aggregate yields a refinement that relates the new metric to other metrics as the replaced metrics were related.Disjoint preferences can also be composed by placing one below the other, so the added metrics break ties without compensating for losses under the original preference.Source: 2) Preferences · p. 4

3) Posetal Games:

Posetal games represent agents’ actions and preferences over joint action profiles, allowing best responses and Nash equilibria to be defined for partially ordered objectives. Refining agents’ preferences can only filter existing equilibria.

3) Posetal Games:

  • A posetal game consists of agents, individual action spaces, and preferences defined over joint action profiles.Source: 3) Posetal Games · p. 4
  • A Nash equilibrium is an action profile in which every agent plays a best response; no agent can unilaterally deviate to strictly improve its outcome.Source: 3) Posetal Games · p. 4
  • Refining every agent’s preference can only remove Nash equilibria, never introduce new joint behaviors.Source: 3) Posetal Games · p. 5

B. Problem Statement

The problem is to derive legally prioritized preferences for each scenario and find a socially optimal equilibrium without requiring agents to disclose private preferences. The proposed pipeline derives scenario-specific legal metrics, orders them through scenario-independent guidelines, and assembles a posetal game.

B. Problem Statement

  • The planning problem is to derive legally prioritized agent preferences and find a socially optimal Nash equilibrium through a distributed protocol that does not require disclosure of private preferences.Source: B. Problem Statement · p. 5

III. FROM LEGAL REQUIREMENTS TO POSETAL GAMES

  • The pipeline derives scenario-specific metrics and preferences from generic rules and guidelines, then uses them to construct a posetal game incorporating agents’ individual goals.The induced preference is well-defined as a partial order.Source: §III · p. 5, B. Guidelines · p. 6

A. Legally Required Metrics

  • Temporal-logic robustness turns pairwise legal rules into quantitative metrics, with violations penalized while satisfying behaviors are not distinguished by robustness magnitude.Rules applying only to the ego agent use one metric per rule rather than one per contact agent.Source: A. Legally Required Metrics · p. 5

B. Guidelines

  • Guidelines order abstract concerns, and the induced preference groups metrics by the concerns they address, prioritizing groups while leaving metrics within a group incomparable.A metric addressing multiple concerns appears in multiple groups; metrics addressing no concern are omitted.Source: B. Guidelines · p. 6, Figure 5 · p. 6

C. Deriving the Motion Planning Game

The legal game encodes each agent’s guideline-induced preference over legal metrics, while the true game refines those preferences with private objectives. This refinement ensures that true-game equilibria remain legal.

C. Deriving the Motion Planning Game

  • An agent’s true preference may add objectives where law leaves priorities unspecified, but it must refine rather than override the legal preference.Agents violating this condition are defectors; a defector whose action is not a legal best response can be identified from public information.Source: C. Deriving the Motion Planning Game · p. 7
  • The true game’s equilibria are exactly the legal-game equilibria where every agent also best-responds under its true preference.Source: C. Deriving the Motion Planning Game · p. 7
  • True-game equilibria are a subset of legal-game equilibria, so private objectives can select among legal behaviors but cannot make an illegal profile an equilibrium.Source: C. Deriving the Motion Planning Game · p. 7

D. Handling Regulatory Change

The framework supports regulatory revisions that refine legal behavior: the resulting guideline can only shrink the set of legal equilibria. Priority refinement adds required orderings, while injection splits a concern to prioritize its subconcerns.

D. Handling Regulatory Change

  • Refining a guideline preserves or strengthens its induced preferences, so the legal-equilibrium set can only shrink.This supports revisions that keep previously forbidden behavior forbidden.Source: D. Handling Regulatory Change · p. 7

1) Priority Refinement:

  • Adding required priorities yields the unique least-restrictive refinement when their transitive closure is antisymmetric; a cycle signals priorities that cannot be enforced consistently.The minimal refinement adds the required priorities and those implied by transitivity.Source: 1) Priority Refinement · p. 8

2) Injection:

  • Priority refinement adds orderings between existing concerns, but injection splits an existing concern so its more specific subconcerns can be prioritized individually.Source: 1) Priority Refinement · p. 7, 2) Injection · p. 8
  • Injection refines the original guideline when every metric addressing the split concern also addresses a concern in the injected guideline.The construction requires injected concerns to be new to avoid conflicting inherited priorities.Source: 2) Injection · p. 8

3) Augmentation:

Guidelines can be extended by placing one disjoint guideline below another, yielding a refinement. Under conservative beliefs, belief play recovers the true game’s equilibria by intersecting equilibria of agents’ local games.

3) Augmentation:

  • Appending a disjoint guideline below another makes the combined guideline a refinement of the higher-priority guideline.The added relations place every concern in G2 below every concern in G1.Source: 3) Augmentation · p. 8

IV. SOLUTION PROTOCOLS

  • With private preferences, belief play uses conservative local games, while distributed iterative best-response requires no information about others’ action spaces or preferences.A complete-information protocol is not deployable when agents do not know others’ true preferences.Source: §IV · pp. 8–9

A. Belief Play

  • Belief play recovers exactly the true-game equilibria as the action profiles that are equilibria in every agent’s local game.This result assumes each true preference refines the corresponding belief; conservative beliefs may omit another agent’s priorities but do not attribute priorities it lacks.Source: A. Belief Play · p. 9

1) Algorithm:

Belief play can be interrupted while preserving legality, and distributed best-response iteration offers a lower-information alternative with weaker guarantees. The case study applies the framework to multi-vessel COLREGS encounters.

1) Algorithm:

  • Agents broadcast local-game equilibria; their shared intersection contains exactly the true equilibria, from which they select the socially best profile.With a fixed tie-breaking rule, all agents commit to the same selected equilibrium.Source: 1) Algorithm · p. 9

2) Anytime Legality:

  • If interrupted, belief play can commit to a known true equilibrium when one has been found, or use a legal fallback while enumeration continues.The fallback is not incentive-stable under the true preferences; the social value of the committed true equilibrium is nondecreasing as candidates accumulate.Source: 2) Anytime Legality · p. 10

3) Complexity and Communication:

  • Belief play’s enumeration cost can grow exponentially with the joint action space, while finer conservative beliefs can reduce the number of candidates and messages.Brute-force enumeration requires O(|Γ|^n) best-response queries; when beliefs refine legal preferences, required messages are bounded by n|NE(Glegal)|.Source: 3) Complexity and Communication · p. 10

B. Distributed Iterative Best-Response

  • Distributed iterative best-response forwards an action profile agent to agent, with each agent replacing its own action by a best response until a fixed point.Agents need only know their own action spaces and preferences, but optimality is guaranteed only after exhaustive exploration; convergence is guaranteed when the true game is a potential game.Source: B. Distributed Iterative Best-Response · p. 10
  • About three best-response rounds sufficed for convergence in the tested COLREGS cases, and restarts recovered optimal social value in all tested scenarios, sometimes requiring up to 20 initializations.Distributed iterative best-response is not guaranteed to find the optimal equilibrium or provide a legal fallback if interrupted or non-convergent.Source: B. Distributed Iterative Best-Response · p. 10

V. CASE STUDY: COLREGS-COMPLIANT PLANNING

  • The framework lifts pairwise COLREGS rules to encounters involving any number of vessels, including cases where strict rule compliance yields to collision avoidance.The case study focuses on steering and sailing rules under good visibility.Source: §V · p. 10

A. Metrics Required by COLREGS

The COLREGS metrics represent collision, give-way, and stand-on concerns for each contact vessel. Their guideline prioritizes collision avoidance while leaving give-way and stand-on incomparable.

A. Metrics Required by COLREGS

  • Collision, give-way, and stand-on metrics are defined for each contact vessel, with collision severity quantified by maximum relative collision speed.The collision metric is zero when vessels remain outside the collision radius throughout the trajectory.Source: A. Metrics Required by COLREGS · p. 11

B. COLREGS Guideline

  • The guideline places collision above give-way and stand-on, while leaving give-way and stand-on incomparable.The metrics distinguish contacts by vessel class, and collisions involving different contacts remain incomparable.Source: B. COLREGS Guideline · p. 11, Figure 9 · p. 11

C. Legal and True Game

The legal and true games derive scenario-specific agent preferences from legal guidelines, then allow private objectives and regulatory updates to refine those preferences. The evaluation instantiates this framework for maritime encounters using finite trajectory sets and preferences that place performance below legal concerns.

C. Legal and True Game

  • The legal game uses preferences derived from the guideline, while the true game can refine them with performance objectives, new priorities, or aggregated incomparable metrics.Performance metrics are placed below legal preferences, so they cannot compensate for a worse legal outcome.Source: C. Legal and True Game · pp. 11–12, 3) True Preferences · p. 13

D. Regulatory Change

  • Regulatory refinements can prioritize give-way over stand-on duties, encode the Rule 18 vessel-class hierarchy, or make local rules take precedence over COLREGS.The class hierarchy is incorporated by splitting give-way and stand-on concerns according to the hierarchy and adding cross-priorities.Source: D. Regulatory Change · p. 12, Figure 11 · p. 12

VI. EVALUATION

  • The evaluation tests auditability, customization, and coordination protocols in one-shot COLREGS games, where each vessel commits to a complete trajectory before the encounter.It uses five geometric scenarios, including encounters with up to four vessels, and applies the vessel-class hierarchy in mixed-class scenarios.Source: §VI · p. 12, A. Experimental Setup · p. 12

1) Vessel Models:

  • Vessel trajectories use a yaw-constrained kinematic model with bounded acceleration and yaw rate, parameterized using two CommonOcean vessel types.The maximum yaw rate is set between 0.03 and 0.06 rad/s per vessel.Source: 1) Vessel Models · p. 13

2) Action Spaces:

  • Each agent receives a finite set of dynamically feasible trajectories that vary course, offset, and speed profile; the largest game has 164,934 joint profiles.Joint action spaces are exhaustively enumerated unless otherwise specified.Source: 2) Action Spaces · p. 13

3) True Preferences:

  • True preferences place goal-reaching and path-length performance metrics below the legal preference, making legal compliance prior to individual performance.Among trajectories that reach the goal, the preference favors shorter and faster paths; a give-way detour can therefore incur a path-length cost.Source: 3) True Preferences · p. 13

4) Social Metric:

The public social metric selects among true-game equilibria by respecting the legal hierarchy. Audits then classify each committed-equilibrium violation by whether it is forced by higher-priority concerns or unsatisfiable within the action space.

4) Social Metric:

  • The social metric prioritizes collision compliance over encounter compliance, weighs incomparable metrics within each level equally, and uses a fixed public rule to break remaining ties.Its components are nonpositive and reach zero when all vessels comply with the corresponding rules; every agent can evaluate the metric from public information.Source: 4) Social Metric · p. 13

1) Auditing Violations:

  • For each violation, the audit checks the violating vessel's unilateral deviations: a rule is unsatisfiable if no deviation satisfies it, and forced if improving it worsens a higher- or incomparable-priority metric.Source: 1) Auditing Violations · pp. 13–14
  • The audit finds that all lower-priority violations in the selected equilibria are forced, and none is unsatisfiable within the action space.Across seven scenarios, the crossing cases have no violations; the triangle, crossing–overtaking, priority encounter, and gauntlet contain forced violations explained by the legal hierarchy.Source: B. Auditability · p. 13, 1) Auditing Violations · p. 14, Figure 13 · p. 14

2) Identifying Defectors:

The protocols and customization experiments show how private preferences, regulatory changes, and limited communication affect equilibria and their selection. The case study also identifies the boundary of the audits and leaves real-time deployment and richer action spaces as open challenges.

2) Identifying Defectors:

  • A public-information test identifies a defector when its committed action is not a legal best response, succeeding in three of four tested cases.In the exception, Bravo's straight-to-goal action is itself a legal best response, so the behavior remains legal.Source: 2) Identifying Defectors · p. 14, Figure 14 · p. 15

1) Private Preference Refinements:

2) Guideline Refinements:

D. Solution Protocols

  • Distributed IBR reaches a true equilibrium in all four tested scenarios with far fewer messages than belief play, but does not always select the socially optimal equilibrium.Five initializations reach the optimum on triangle, and ten do so on crossing–overtaking and four-agent priority; on gauntlet, encounter compliance remains 0.08 below the optimum with 10 or 20 initializations.Source: D. Solution Protocols · pp. 15–16, Table II · p. 16, Figure 16 · p. 16

VII. CONCLUSION AND FUTURE WORK

  • The conclusion reports that belief play recovers the true game's equilibria from conservative local beliefs and remains legal if interrupted, while distributed IBR requires less information.Source: §VII · p. 16
  • Audits are relative to the finite action lattice, so a violation classified as unsatisfiable may become satisfiable with a richer action space.The paper also identifies real-time solvers as necessary for deployment and notes that exhaustive enumeration grows exponentially with the number of agents.Source: §VII · p. 16

APPENDIX

The appendix proves that preference refinements preserve strict comparisons and explains why aggregation and adding lower-priority metrics preserve the relevant ordering.

A. Proofs of the Preference Refinement Operations

Loading 2610.22277v1…