Graph-Based Deadlock Analysis and Prevention for Robust Intelligent Intersection Management
Journal
ACM Transactions on Cyber-Physical Systems
Journal Volume
8
Journal Issue
3
Start Page
1
End Page
22
ISSN
2378-962X
2378-9638
Date Issued
2024-07-13
Author(s)
Abstract
Intersection management systems, with the assistance of vehicular networks and autonomous vehicles, have the potential to perform traffic control more precisely than contemporary signalized intersections. However, as infrastructural intersection management controllers do not directly activate motions of vehicles, it is possible that the vehicles fail to follow the instructions from controllers, undermining system properties such as deadlock-freeness and traffic performance. In this article, we consider a class of robustness issues, the time violations, which stem from possible discrepancies between scheduled orders and real executions. We refine a graph-based intersection model to build our theoretical foundations and analyze potential deadlocks and their resolvability. We develop solutions that mitigate negative effects of time violations. In particular, we propose a Robustness-Aware Greedy Scheduling algorithm for robust scheduling and evaluate the deadlock-free robustness of different intersection models and scheduling algorithms. Experimental results show that the Robustness-Aware Greedy Scheduling algorithm is able to significantly improve robustness and keep a good balance with traffic performance.
SDGs
Publisher
Association for Computing Machinery (ACM)
Type
journal article