Are We Stuck? Modeling and Detecting Deadlocks in Multi-autonomous Vehicle Systems

Autonomous driving system (ADS) testing is essential to ensure the safety and reliability of autonomous vehicles (AVs) prior to deployment. As ADSs are increasingly deployed in multi-AV traffic environments, it becomes crucial to assess their cooperative performance, particularly with respect to deadlock, a fundamental liveness issue in concurrent systems that can lead to traffic congestion and prolonged stalling. However, the analysis and testing of ADSs’ cooperative capabilities with respect to deadlock remain largely underexplored. In this work, we present the first systematic study of deadlock in multi-AV systems. We formalize deadlock in autonomous driving using a time-indexed wait-for relation grounded in vehicles’ planned trajectories and road-region occupancy. Building on this formalization, we propose WaitWatch, a wait-for-oriented testing framework that steers scenario generation via spatio-temporal intersection alignment of executed trajectories to induce circular wait patterns. WaitWatch integrates a Deadlock Judge, Intersection Alignment Feedback, and Intersection Oriented Mutation to efficiently uncover latent deadlock scenarios. We conduct an extensive evaluation on three representative ADSs. Experimental results show that, on average, WaitWatch generates 2.28× as many deadlock scenarios (DLSs) as the best-performing baseline. By shifting the focus from single- AV evaluation to multi-AV cooperation, our approach identifies a range of previously unknown deadlock behaviors, revealing significant limitations in the cooperative and liveness capabilities of current ADSs. Our findings highlight a fundamental safety–liveness trade-off in deadlock resolution and demonstrate the need for systematic deadlock-aware testing in the development and validation of autonomous driving systems.