Theory for designing rules to manage identical autonomous agent systems
Towards a Theory for the Design of Rules in Multi-Agent Systems: the case of Homogeneous Fleets
Multiagent Systems
Summary
Managing many automated agents that interact can be tricky, especially when trying to make sure they behave well together. The authors study how to design rules that guide groups of identical agents to achieve good overall system outcomes. They present a simpler version of the problem that can be solved more easily and propose an algorithm called Rule Branch and Bound for finding these best rules. They also show how this approach can help manage autonomous cars safely in traffic.
What this means in practice
- •For autonomous vehicle engineers: Design rules that coordinate identical self-driving cars to improve traffic flow and safety without central control.
- •For network protocol developers: Create regulations for identical devices sharing communication channels to ensure fair and efficient resource use.
Tested on simulated data.
Authors
Matteo Penlington, Lorenzo Fiaschi, Raj Kiriti Velicheti, Andrea Censi, Emilio Frazzoli
Abstract
The regulation of systems composed of many interacting decentralised agents is a long-standing problem. This problem has typically been resolved by the imposition of rules. Rules resolve the limitations of sub-optimal agents whilst simultaneously aligning the behaviour of the agents with the demands of society. Traffic laws, for example, let a driver cross a junction without seeing around the corner, and transport protocols such as TCP let applications share a network without knowing of one another. The problem is more pressing today, as autonomous systems are deployed in society. In this work, we establish the basis of a system-agnostic theory of rule design for multi-agent systems. We first state the rule design problem (RDP) in its generality. It relates a rule to the set of system performances, defined by the regulator, that the agents deployed under it can attain. However, it is not yet possible to solve the RDP in full generality. As such, we introduce the homogeneous rule design problem (HRDP), in which the agents in each environment are identical, and among other interesting properties, show that under worst-case aggregation the two problems have the same solution, bypassing the combinatorial complexity of the RDP. To solve the RDP under worst-case aggregation we propose Rule Branch and Bound (RuleBnB), an anytime branch-and-bound algorithm. Finally, we illustrate the value of solving the RDP on an autonomous driving case study.