Document Open Access Logo

Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection

Authors Juan José Besa Vial, William E. Devanny, David Eppstein, Michael T. Goodrich

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2016.5.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Juan José Besa Vial
William E. Devanny
David Eppstein
Michael T. Goodrich

Cite As Get BibTex

Juan José Besa Vial, William E. Devanny, David Eppstein, and Michael T. Goodrich. Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/OASIcs.ATMOS.2016.5

Abstract

We study various versions of the problem of scheduling platoons of autonomous vehicles through an unregulated intersection, where an algorithm must schedule which platoons should wait so that others can go through, so as to minimize the maximum delay for any vehicle. We provide polynomial-time algorithms for constructing such schedules for a k-way merge intersection, for constant k, and for a crossing intersection involving two-way traffic. We also show that the more general problem of scheduling autonomous platoons through an intersection that includes both a k-way merge, for non-constant k, and a crossing of two-way traffic is NP-complete.

Subject Classification

Keywords
  • autonomous vehicles
  • platoons
  • scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. H. Ahn, A. Colombo, and D. Del Vecchio. Supervisory control for intersection collision avoidance in the presence of uncontrolled vehicles. In 2014 American Control Conf., pages 867-873, 2014. Google Scholar
  2. F. Altché, X. Qian, and A. de La Fortelle. Time-optimal coordination of mobile robots along specified paths. arXiv preprint arXiv:1603.04610, 2016. Google Scholar
  3. G. Antonelli and S. Chiaverini. Kinematic control of platoons of autonomous vehicles. IEEE Trans. on Robotics, 22(6):1285-1292, 2006. Google Scholar
  4. T. Au and P. Stone. Motion planning algorithms for autonomous intersection management. In AAAI Workshop on Bridging the Gap Between Task and Motion Planning, 2010. Google Scholar
  5. J. Baber, J. Kolodko, T. Noel, M. Parent, and L. Vlacic. Cooperative autonomous driving: intelligent vehicles sharing city roads. IEEE Robotics Automation Magazine, 12(1):44-49, 2005. Google Scholar
  6. F. Berger and R. Klein. A traveller’s problem. In 26th ACM Symp. on Computational Geometry (SoCG), pages 176-182, 2010. Google Scholar
  7. D. Carlino, S. D. Boyles, and P. Stone. Auction-based autonomous intersection management. In 16th Int. IEEE Conf. on Intelligent Transportation Systems (ITSC), pages 529-534, 2013. Google Scholar
  8. P. Dasler and D. Mount. On the complexity of an unregulated traffic crossing. In Frank Dehne, Jörg-Rüdiger Sack, and Ulrike Stege, editors, 14th Int. Symp. on Alg. and Data Struct. (WADS), pages 224-235, 2015. see also URL: http://arxiv.org/abs/1505.00874.
  9. K. Dresner and P. Stone. Multiagent traffic management: A reservation-based intersection control mechanism. In 3rd Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), pages 530-537, 2004. Google Scholar
  10. K. Dresner and P. Stone. Multiagent traffic management: An improved intersection control mechanism. In 4th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), pages 471-477, 2005. Google Scholar
  11. K. Dresner and P. Stone. A multiagent approach to autonomous intersection management. Journal of Artificial Intelligence Research, pages 591-656, 2008. Google Scholar
  12. E. Frazzoli and F. Bullo. Decentralized algorithms for vehicle routing in a stochastic time-varying environment. In 43rd IEEE Conf. on Decision and Control (CDC), volume 4, pages 3357-3363 Vol.4, 2004. Google Scholar
  13. M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1990. Google Scholar
  14. S. Ilgin Guler, M. Menendez, and L. Meier. Using connected vehicle technology to improve the efficiency of intersections. Transportation Research Part C: Emerging Technologies, 46:121-131, 2014. Google Scholar
  15. W. Hatzack and B. Nebel. The operational traffic control problem: Computational complexity and solutions. In Sixth European Conference on Planning, pages 113-119, 2014. Google Scholar
  16. R. A. Hearn and E. D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1):72-96, 2005. Google Scholar
  17. J. Lee and B. Park. Development and evaluation of a cooperative vehicle intersection control algorithm under the connected vehicles environment. IEEE Transactions on Intelligent Transportation Systems, 13(1):81-90, 2012. Google Scholar
  18. J. Levinson, J. Askeland, J. Becker, J. Dolson, D. Held, S. Kammel, J. Z. Kolter, D. Langer, O. Pink, V. Pratt, M. Sokolsky, G. Stanek, D. Stavens, A. Teichman, M. Werling, and S. Thrun. Towards fully autonomous driving: Systems and algorithms. In IEEE Intelligent Vehicles Symp. (IV), pages 163-168, 2011. Google Scholar
  19. G. Lu, L. Li, Y. Wang, R. Zhang, Z. Bao, and H. Chen. A rule based control algorithm of connected vehicles in uncontrolled intersection. In 17th Int. IEEE Conf. on Intelligent Transportation Systems (ITSC), pages 115-120, 2014. Google Scholar
  20. N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. J. ACM, 30(4):852-865, 1983. Google Scholar
  21. D. Miculescu and S. Karaman. Polling-systems-based control of high-performance provably-safe autonomous intersections. In 53rd IEEE Conf. on Decision and Control, pages 1417-1423, 2014. Google Scholar
  22. R. Naumann, R. Rasche, and J. Tacken. Managing autonomous vehicles at intersections. IEEE Intelligent Systems and their Applications, 13(3):82-86, 1998. Google Scholar
  23. R. Rajamani and S. E. Shladover. An experimental comparative study of autonomous and co-operative vehicle-follower control systems. Transportation Research Part C: Emerging Technologies, 9(1):15-31, 2001. Google Scholar
  24. D. J. Stilwell, B. E. Bishop, and C. A. Sylvester. Redundant manipulator techniques for partially decentralized path planning and control of a platoon of autonomous vehicles. IEEE Trans. on Systems, Man, and Cybernetics, Part B (Cybernetics), 35(4):842-848, 2005. Google Scholar
  25. M. VanMiddlesworth, K. Dresner, and P. Stone. Replacing the stop sign: Unmanaged intersection control for autonomous vehicles. In 7th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS), pages 1413-1416, 2008. Google Scholar
  26. C. Wuthishuwong, A. Traechtler, and T. Bruns. Safe trajectory planning for autonomous intersection management by using vehicle to infrastructure communication. EURASIP Journal on Wireless Communications and Networking, 2015(1):1-12, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact