Independently developed autonomous agents, such as autonomous vehicles, must guarantee joint compatibility, such as safety and task-completion requirements, when they operate in a shared environment. Existing methods require a centrally designed specification, or interaction mechanism before any agent is deployed. However, such centralized design is unrealistic when agent designs are confidential to their developers, and it is not flexible enough to accommodate future agent designs. We study a bi-level structure in which a regulator coordinates developers by publishing seed agents, and each developer independently tests its agent to ensure that it is compatible with every seed-compatible agent, a property we call future-proofness. Under this structure, joint compatibility is guaranteed for any agents that are designed and tested independently, without any coordination with each other. In this work, we first formulate compatibility for general multi-agent systems and show why it is not trivially implied by seed-compatibility. We then characterize the future-proof agents as the closure of the seed and show that this closure is monotone in the seed. Finally, we study a class of executable tests that involve interaction with the seed alone, and we ask to what extent such tests can distinguish the future-proof agents.
Figures & tables
Fig. 1 : Scheme of future-proof testing. A regulator publishes the seed agents (top). Each developer tests its own agents against the seed alone (sides), with no communication between developers. Any agent that passes joins the compatible agent set (centre). It is compatible with every passing agents, although they are never tested against each other.
Fig. 2 : Motivating example. Left. Two points that are each safe with the seed can be unsafe with each other, and only p0 itself is future-proof. Middle. A second seed point shrinks the seed-safe region but enlarges the future-proof region. Right. In the extreme case, the seed-safe region coincides with the future-proof region.
Fig. 3 : Vehicles following one another on a straight road at uniform gap g0 and speed v0 . The outcome generator triggers an emergency stop of the leading vehicle (red) and monitors for rear-end collisions between adjacent vehicles.
Fig. 4 : Seed-compatible, maximal compatible, and future-proof agents in the single-lane example. (a) The green region depicts all agents that are individually compatible with the seed π∗ . The pair (π2,π1) demonstrates that the set is not itself compatible. (b) Each outline shows a maximal compatible set, and the purple region depicts their intersection, namely the future-proof closure. (c) Extending the seed (red box) from π∗ in (b) admits more future-proof agents, so the purple region grows. (d) Further extending the seed (larger red box) collapses all maximal compatible sets to a unique one, and all seed-compatible agents become future-proof.
Fig. 5 : Warehouse delivery setup. Left. An example configuration. The yielding zone of the blue robot at the center is shown, and the dashed cells are the candidate starts and goals. Right. An encounter can lead to three outcomes, namely the conflict is resolved, the agents collide, or both agents yield.
Fig. 6 : The 38 self-compatible agents, each drawn as a robot with its yielding zone, arranged by the side they yield to. The outlines mark the largest compatible set among the left-yielding agents (five agents) and among the right-yielding agents (four agents). No maximal compatible set contains more than five agents.
Fig. 7 : Maximal compatible sets containing agent 5, one per column. Agents 1–5 form the only compatible set of five, and a–d are other agents. With F0={5} , the closure is the seed itself. Adding agent 2 leaves two maximal sets and Cl(F0)={2,5} , whereas adding agent 1 leaves only the five-agent set, so Cl(F0)={1,…,5} .