Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

10-2026

Abstract

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.

Keywords

Deadlock, Multi-Autonomous Vehicle

Discipline

Software Engineering | Transportation

Research Areas

Software and Cyber-Physical Systems

Publication

Proceedings of the ACM on Software Engineering

First Page

1973

Last Page

1996

Identifier

10.1145/3832177

Publisher

ACM

City or Country

New York

Additional URL

https://doi.org/10.1145/3832177

Download

Share

COinS