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

Preliminaries and Problem Statement

In this section, we recall the necessary background on games with partially ordered preferences and then state the problem addressed in this paper. In classical games, every agent possesses a scalar utility function to evaluate the outcomes of the game.

Games with partially ordered preferences, or posetal games , are more general in that they allow each agent to evaluate an outcome with respect to multiple metrics that are prioritized according to a partial order [ 4 ] .

From Legal Requirements to Posetal Games

$m_{1}$ $m_{2}$ $m_{3}$ … $m^{\prime}_{1}$ $m^{\prime}_{2}$ $m^{\prime}_{3}$ $m^{\prime}_{4}$ $m^{\prime}_{5}$ … … $m_{1}$ $m_{2}$ $m_{3}$ … $m^{\prime}_{1}$ $m^{\prime}_{2}$ $m^{\prime}_{3}$ $m^{\prime}_{4}$ $m^{\prime}_{5}$ … … Scenario Legal metrics Legal preferences $\Phi$ $\mathsf{G}$ Fig. 4: Deriving legal preferences from a generic rule set $\Phi$ and a scenario-independent guideline $\mathsf{G}$.

Solution Protocols

In this section, we address part (ii) of Problem 1 , which requires computing the socially optimal NE $\gamma^{*}$ ( 3 ) of the true game $G_{\mathtt{true}}$ derived in Sec. III . To this end, we propose the solution protocols summarized in Tab. I . The design of a solution protocol depends strongly on which information each agent has about the others.

If the agents have complete information about the others, every agent can independently compute $\gamma^{*}$ without communication as they can directly construct $G_{\mathtt{true}}$.

Case Study: COLREGS-Compliant Planning

G S Give-way vessel Stand-on vessel (a) G S (a) G G (b) G S (c) 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. In this section, we apply the modeling framework developed in Sec.

Evaluation

We evaluate the framework in one-shot COLREGS motion-planning games, in which each agent commits to a complete dynamically feasible trajectory before the encounter begins. Our goals are threefold. First, we verify that every rule violation at the committed equilibria can be audited and that defectors can be identified from public information.

Second, we confirm that private and regulatory customizations shrink the set of equilibria as predicted by Theorem 2 and Proposition 4 , and we quantify the efficiency cost of private preferences.

Sources and Demonstrations

Figures are reproduced from Lercher et al. See the full paper for experimental details and the project page, when the paper links one, for demonstrations and videos.