Stanford Seminar - Why would we want a multi-agent system unstable

Mrdjan Jankovic of Ford Research January 13, 2023 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 (e.g., 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 result in relatively easier to solve convex programs even for nonlinear system dynamics 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 and a vehicle experiment with stationary obstacles. 0:00 Introduction 0:49 Objective - unstable feedback loop? ord 2:43 Why CBFs? Short answer - convex QP 6:31 CBF based safety filter 7:58 Barrier margin for robustness 9:14 Robust Control Barrier Functions 10:32 Turning obstacles into barriers 12:16 CBF based obstacle avoidance 13:42 Traffic flow and gridlocks 14:42 Avoiding interacting obstacles 17:26 Decentralized multi-agent controllers 19:07 Centralized CBF Controller 20:06 Co-optimization and CCS 23:19 PCCA algorithm guarantees 24:00 5 agents Monte Carlo Simulations 24:52 Comparison of CBF based methods 26:08 Deadlock resolution 26:51 Cause