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

cs.MAOct 15, 2026

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

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

Organizations: Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, USA. · School of Computation, Information and Technology, Technical University of Munich, 85748 Garching, Germany. · Department of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139, USA. · Woods Hole Oceanographic Institution, Woods Hole, MA 02543, USA. ·

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.

Figures & tables

Panel of Figure 1 — Fig. 1: A vessel encounter with conflicting COLREGS rules for $V_{0}$ . The vessel is required to keep its current course and speed for the overtaking vessel $V_{1}$ and, simultaneously, give way to the crossing vessel $V_{2}$ by evading to starboard [ 5 , Rules 13 and 15] .

Panel of Figure 2 — Fig. 2: The Hasse diagram of the poset $\mathsf{P}=\langle\{p_{1},p_{2},p_{3},p_{4}\},\preceq_{\mathsf{P}}\rangle$ with $p_{4}\prec_{\mathsf{P}}p_{2}\prec_{\mathsf{P}}p_{1}$ and $p_{4}\prec_{\mathsf{P}}p_{3}\prec_{\mathsf{P}}p_{1}$ ; $p_{2}$ and $p_{3}$ are incomparable.

Panel of Figure 3 — Fig. 3: Two robots meet head-on in a narrow corridor. By regulation, robots have to avoid collisions, keep a sufficient clearance from other robots, and remain inside the operational area marked by the bold lines. Collision avoidance is the highest-priority objective, and the other two are incomparable. We take the perspective of the left robot and assume the trajectory of the right robot is fixed. Trajectories $a$ , $c$ , and $d$ are preferred over $b$ , since $b$ causes a collision; $a$ and $c$ are indifferent , as they have the same insufficient clearance but stay in the operational area; $d$ is incomparable to $a$ and $c$ , as it achieves sufficient clearance by leaving the operational area (adapted from [ 4 , Fig. 2] ).

Panel of Figure 4 — Fig. 4: Deriving legal preferences from a generic rule set $\Phi$ and a scenario-independent guideline $\mathsf{G}$ . For any concrete scenario, $\Phi$ yields the set of metrics that each agent is legally required to consider, denoted by $m_{k}$ and $m^{\prime}_{k}$ . The guideline $\mathsf{G}$ induces the legal preference for an agent over its legal metrics. The color of the clouds indicates the agent to which a set of metrics or a preference belongs.

Panel of Figure 5 — Fig. 5: Inducing a preference from a guideline. Arrows indicate which concerns a metric addresses; colors indicate the concern a metric was selected for. Since $m_{1}$ addresses both concerns from $\mathsf{G}$ , two copies of it appear in $\mathsf{P}(\mathcal{M},\mathsf{G})$ ; $m_{4}$ addresses no concern and is dropped. Metrics within a group are incomparable, and the groups are prioritized according to $\mathsf{G}$ . We abbreviate the labels $\mathtt{collision}$ , $\mathtt{high\text{-}vul}$ , and $\mathtt{low\text{-}vul}$ as $\mathtt{coll}$ , $\mathtt{hv}$ , and $\mathtt{lv}$ , respectively.

Panel of Figure 6 — Fig. 6: Propagation of a guideline refinement $\mathsf{G}\sqsubseteq\mathsf{G}^{\prime}$ through the pipeline. The horizontal maps take a guideline to its induced preference, the assembled legal game, and its equilibria. Induction and game construction preserve $\sqsubseteq$ (solid vertical arrows, monotone homomorphisms), whereas the equilibrium map is antitone (dashed arrow). Hence, a finer guideline can only shrink the set of joint behaviors, i.e., $\mathsf{NE}(G_{\mathtt{legal}}^{\prime})\subseteq\mathsf{NE}(G_{\mathtt{legal}})$ .

Panel of Figure 7 — Fig. 7: Visualization of guideline injection using Hasse diagrams. The colors indicate which parts of the refined guideline originate from which inputs. Continuing the example from Fig. 3 , $\mathcal{C}_{1}^{1}$ could be the $\{\mathtt{collision}\}$ concern, which is split according to a guideline prioritizing $\{\mathtt{high\text{-}vul}\}$ over $\{\mathtt{low\text{-}vul}\}$ .

Protocol	Known about others	Optimal?
Complete information	action space, true preference	✓
Belief play	action space, belief on preference	✓
Distributed IBR	none	after full search

TABLE I: Solution protocols, the information that each agent requires about the other agents, and whether the protocol is guaranteed to commit to the socially optimal equilibrium

Panel of Figure 9 — Fig. 8: COLREGS encounter situations (adapted from [ 22 , Fig. 2] ). (a) In an overtaking situation, the overtaking vessel evades to either direction, while the overtaken vessel stands on. (b) In a head-on situation, both vessels evade to starboard. (c) In a crossing situation, the vessel coming from the left evades to starboard, while the vessel coming from the right stands on.

Panel of Figure 10 — Fig. 9: The guideline $\mathsf{G}^{\mathtt{COLREGS}}$ representing the priorities over concerns specified by the COLREGS.

Panel of Figure 11 — Fig. 10: Modeling motion planning under COLREGS in an encounter of three vessels as a posetal game. We visualize the continuous action space of each vessel using a finite number of trajectories. In the legal game, every vessel would use its legal preference as shown for $V_{0}$ . In the true game, the vessels use refined preferences including their individual objectives and customized implementations of the COLREGS as shown for $V_{1}$ and $V_{2}$ .

Panel of Figure 12 — Fig. 11: Modifying $\mathsf{G}^{\mathtt{COLREGS}}$ to prioritize the encounter rule metrics according to the vessel class hierarchy. (a) The guideline $\mathsf{G}^{\mathtt{R18}}$ encoding the hierarchy. (b) The refined guideline after injection and priority refinement. The edges added via priority refinement are highlighted. We abbreviate some labels to keep the figure compact, e.g., $\mathtt{gw}$ is short for $\mathtt{give\text{-}way}$ .

Panel of Figure 13 — Fig. 12: Action spaces for all five geometric scenario configurations. Each colored curve represents a candidate trajectory for one agent, shaded from a pale tint at $t=0$ to the saturated hue at the horizon.

Fig. 13: Socially optimal equilibrium

\gamma^{*}

( 3 ) of the true game. The shading of the trajectories encodes time like in Fig. 12 .

Fig. 14: Defector trajectories for (a) the triangle scenario and (b)–(d) the crossing–overtaking scenario. The highlighted agent ignores legal requirements and always moves straight to its goal. The shading of the trajectories encodes time like in Fig. 12 .

Fig. 15: Customization of the private preferences via refinement of the legal preferences by adding (a) performance, (b) prioritization of give-way metrics over stand-on metrics for Bravo, and (c) stand-on metrics over give-way metrics for Charlie. Each plot shows one refinement step by drawing the trajectories occurring in at least one NE of the original game below those of the refined game.

Fig. 16: Communication cost of a single run of each solution protocol. The error bars indicate the standard deviation over 15 independently seeded distributed IBR runs.

Scenario	Distributed IBR				Belief play
	1 init.	5 inits.	10 inits.	20 inits.
triangle	$0.84$ / $1$	$0.0$ / $3$	$0.0$ / $5$	$0.0$ / $10$	$0.0$ / $17$
crossing–overtaking	$8.82$ / $1$	$8.82$ / $2$	$0.0$ / $4$	$0.0$ / $4$	$0.0$ / $5$
four-agent priority	$9.92$ / $1$	$4.05$ / $4$	$0.0$ / $9$	$0.0$ / $13$	$0.0$ / $29$
gauntlet	$15.59$ / $1$	$0.24$ / $3$	$0.08$ / $7$	$0.08$ / $8$	$0.0$ / $43$

TABLE II: Solution quality of IBR with restarts: optimality gap of the socially best equilibrium among those reached from

k

initializations / number of distinct equilibria reached. Each entry stems from one pool of

k

seeded runs.

Maritime Navigation

See all 21 papers

Legislating World-Model-Based Planning with Legal Reasoning
Sep 14, 2026Dylan Waldner, Yiannis Kantaros, Guido Governatori +2Logical Reasoning Robot Task Planning
Cognizant AI Lab, USA · Department of Electrical & Systems Engineering, Washington University, USA · School of Engineering and Technology, Central Queensland University, Australia +1
L-MAD: A Systematic Evaluation of Multi-Agent Debate Structures in Legal Reasoning
Jul 10, 2026Tan-Minh Nguyen, Hoang-Trung Nguyen, Huu-Dong Nguyen +3Legal NLP Multi-Agent Debate
Japan Advanced Institute of Science and Technology (JAIST), Ishikawa, Japan · VNU University of Engineering and Technology, Hanoi, Vietnam
Investigating Multi-Agent Deliberation in Law
Jun 29, 2026Cor Steging, Ludi van Leeuwen, Tadeusz ZbiegieńMulti-Agent Systems Multi-Agent Reasoning
Bernoulli Institute of Mathematics, Computer Science and Artificial Intelligence, University of Groningen The Netherlands · Department of Legal Theory, Jagiellonian University Poland

Sep 14, 2026J/K move · Enter open · S save

Legislating World-Model-Based Planning with Legal Reasoning

Dylan Waldner, Yiannis Kantaros, Guido Governatori, Risto Miikkulainen+1

Cognizant AI Lab, USA · Department of Electrical & Systems Engineering, Washington University, USA · School of Engineering and Technology, Central Queensland University, Australia+1

Logical Reasoning Robot Task Planning AI Agent Governance Deontic Logic

Open paper AskPDF arXiv

As robotic systems grow more general, legal norms are needed to integrate them into society. This paper extends the isomorphism problem of aligning legal source texts with their encodings, and measures two key challenges to robot normative control: (1) the grounding isomorphism gap, where perception error grounds false atoms for legal reasoning, and (2) the ontological isomorphism gap, where one legal conclusion admits many faithful translations into planning constraints. The paper introduces a legal planning stack that employs Defeasible Deontic Logic (DDL) to constrain a motion planner. The stack leverages learned world models to plan and to provide legal context, enabling ex ante governance that intervenes before an illegal action is executed. It was deployed on a simulated robot arm pushing a cube across a 3x3 grid. The findings were (1) the legislated agent abided substantially more often than the non-legislated one, and modeling perception uncertainty lifted abidance even further, (2) the legal reasoning ran efficiently at runtime and its verdicts were auditable, and (3) the stack adapted to exogenous signals and endogenous rule changes. Both gaps were measured: (4) world model and probe error corrupted the factual input for the DDL reasoner, and (5) a single law admitted several faithful metric interpretations yielding drastically different abidance. Thus, ex ante legislation functions as intended, and closing these gaps with a standardized mapping from the law to runtime constraints and improved fact grounding from perception will yield robust laws that align robot behavior with society's norms. Project page: https://dylanwaldner-cail.github.io/Legislated-Planner/.

Abstract

Maritime Navigation

Explore similar work

Legislating World-Model-Based Planning with Legal Reasoning

L-MAD: A Systematic Evaluation of Multi-Agent Debate Structures in Legal Reasoning

Investigating Multi-Agent Deliberation in Law