Why Would We Want a Multi-Agent System Unstable

Abstract

In everyday driving, many traffic maneuvers such as merges, lane changes, passing through an intersection, require negotiation between independent actors/agents. The same is true for mobile robots autonomously operating in a space open to other agents (humans, robots, etc.). Negotiation is an inherently difficult concept to code into a software algorithm. It has been observed in computer simulations that some “decentralized” algorithms produce gridlocks while others never do. It has turned out that gridlocking algorithms create locally stable equilibria in the joint inter-agent space, while, for those that don’t gridlock, equilibria are unstable – hence the title of the talk.

We use Control Barrier Function (CBF) based methods to provide collision avoidance guarantees. The main advantage of CBFs is that they provide easier to solve convex programs even for nonlinear systems and inherently non-convex obstacle avoidance problems. Six different CBF-based control policies were compared for collision avoidance and liveness (fluidity of motion, absence of gridlocks) on a 5-agent, holonomic-robot system. The outcome was then correlated with stability analysis on a simpler, yet representative problem. The results are illustrated by extensive simulations including an intersection example where the (in)stability insights are used to explain otherwise difficult to understand vehicle behaviors.