- 學位論文
分散式智慧路口管理中基於移除環之通過順序控制策略協調
Cycle-Removal-Based Priority Policies Coordination for Distributed Intelligent Intersection Management
若您是本文的作者，可授權文章由華藝線上圖書館中協助推廣。
摘要
能在無號誌路口中對車輛進行排程的通過順序控制策略（priority policy）隨著聯網自動駕駛車輛的發展已經成為一個重要的研究主題。然而，現今的通過順序控制策略缺少了能互相協調的能力，使得路口管理系統缺乏處理現實世界中複雜而且動態的場景的能力。此類場景的成因可能是無法預期的緊急狀況、來自製造商或服務提供者的特殊需求、不一致的運算環境，以及控制上的錯誤。在這篇論文中，我們為了解決因通過順序控制策略之間的不相容性而產生的死結（deadlock），提出了一個基於移除環的協調策略。這個策略包含去解決一個與最小回饋邊集問題（Minimum Feedback Arc Set Problem）相似的最佳化問題。雖然這個問題並未有前人研究過，但由於它和最小回饋邊集問題的相似性，使得它可以被許多現有的演算法解決。我們研究並改編了兩個確切方法以及兩個啟發式方法，並設計了數值實驗去評估它們的表現。實驗結果顯示了它們能有效達成我們的目標，即是讓通過順序控制策略之間能夠互相協調，並改善路口管理系統處理複雜需求的能力。
並列摘要
Priority policies, which schedule vehicles' passing order in non-signalized intersection management systems, have been a critical research topic since the development of connected autonomous vehicles. However, current priority policies lack the ability to coordinate with each other in the same intersection, leaving little flexibility to handle the complex and dynamic scenarios in the real world such as unexpected emergencies, special requirements from manufacturers or service providers, nonuniform computing environments, and faulty control. In this work, a cycle-removal-based coordination strategy is proposed to resolve the deadlock created by the incompatibility between different priority policies. This strategy involves solving an optimization problem similar to the minimum feedback arc set problem. Despite being newly proposed, this problem can be solved by various existing algorithms thanks to this similarity. Particularly, two exact methods and two heuristics are studied and adapted with numerical experiments designed to evaluate their performance. The experimental results show their effectiveness in achieving our goals, which enables the coordination of priority policies and improves an intersection management system's capability for handling complicated requirements.
參考文獻
[1] H. Aujac, “La hi´erarchie des industries dans un tableau des ´echanges interindustriels: et ses cons´equences sur la mise en œuvre d’un plan national d´ecentralis´e,”Revue ´economique, pp. 169–238, 1960.
[2] S. Azimi, G. Bhatia, R. Rajkumar, and P. Mudalige, “Reliable intersectionprotocols using vehicular networks,” in Proceedings of the ACM/IEEE International Conference on Cyber-Physical Systems, pp. 1–10, 2013.
[3] A. Baharev, H. Schichl, A. Neumaier, and T. Achterberg, “An exact method for the minimum feedback arc set problem,” Journal of Experimental Algorithmics (JEA), vol. 26, pp. 1–28, 2021.
[4] B. Berger and P. W. Shor, “Approximation alogorithms for the maximum acyclic subgraph problem,” in Proceedings of the annual ACM-SIAM symposium on Discrete algorithms, pp. 236–243, 1990.
[5] F. J. Brandenburg and K. Hanauer, “Sorting heuristics for the feedback arc set problem,” 2011.