Skip to main content
SpringerLink
Log in

Robust Supervisors for Intersection Collision Avoidance in the Presence of Legacy Vehicles

  • Regular Papers
  • Control Theory and Applications
  • Published:
International Journal of Control, Automation and Systems Aims and scope Submit manuscript

Abstract

Vehicle coordination at road intersections to prevent collisions has recently drawn a lot of research attention, but still remains challenging due to a large volume of traffic composed of autonomous and human-driven vehicles. In this paper, we present the design and validation of a supervisory algorithm for collision avoidance at road intersections, in the simultaneous presence of measurement errors, unmodeled dynamics, and vehicles that are not equipped with autonomous driving features. We design a supervisor that takes control of vehicles that are capable of communication and autonomous actions, only when necessary to avoid a collision, or otherwise leaves control to their drivers. This supervisor is least restrictive, that is, it takes control away from drivers only when necessary to avoid future collisions. Since the complexity of the supervisor algorithm is combinatorial with the number of vehicles, we also design an approximate supervisor that can handle more realistic scenarios with a larger number of vehicles in polynomially bounded time at the expense of an additional, yet quantified, restrictiveness. The least restrictive supervisor is validated through experimental testings using three small-scale vehicles, and the approximate supervisor is validated through computer simulations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. “Waymo racks up 10 million test miles ahead of launching its robotaxi business,” https://www.forbes.com/sites/alanohnsman/2018/10/10/waymo-racks-up-10-milliontest-miles-ahead-of-launching-its-robotaxi-business/, 2018.

  2. A. Colombo and D. Del Vecchio, “Efficient algorithms for collision avoidance at intersections,” Proc. of the Int. Conf. Hybrid Systems: Computation and Control, pp. 145–154, 2012.

    Google Scholar 

  3. L. Bruni, A. Colombo, and D. Del Vecchio, “Robust multiagent collision avoidance through scheduling,” Proc. of the IEEE Conf. Decision and Control, pp. 3944–3950, 2013.

    Chapter  Google Scholar 

  4. H. Ahn, A. Colombo, and D. Del Vecchio, “Supervisory control for intersection collision avoidance in the presence of uncontrolled vehicles,” Proc. of the American Control Conference, p. 867–873, 2014.

    Google Scholar 

  5. A. Colombo and D. Del Vecchio, “Least restrictive supervisors for intersection collision avoidance: A scheduling approach,” IEEE Trans. on Automatic Control, vol. 60, no. 6, pp. 1515–1527, June 2015.

    Article  MathSciNet  Google Scholar 

  6. H. Ahn, and D. Del Vecchio, “Semi-autonomous intersection collision avoidance through job-shop scheduling,” Proc. of the Int. Conf. Hybrid Systems: Computation and control, pp. 185–194, 2016.

    Google Scholar 

  7. F. Altché, X. Qian, and A. de La Fortelle, “Least restrictive and minimally deviating supervisor for safe semi-autonomous driving at an intersection: An MIQP approach,” Proc. of the Int. Conf. Intelligent Transportation Systems, pp. 2520–2526, 2016.

    Google Scholar 

  8. F. Altché, X. Qian, and A. de La Fortelle, “An algorithm for supervised driving of cooperative semi-autonomous vehicles,” IEEE Trans. on Intelligent Transportation Systems, vol. 18, no. 12, pp. 3527–3539, September 2017.

    Article  Google Scholar 

  9. A. Colombo, G. R. De Campos, and F. Della Rossa, “Control of a city road network: Distributed exact verification of traffic safety,” IEEE Trans. on Automatic Control, vol. 62, no. 10, pp. 4933–4948, October 2017.

    Article  MathSciNet  Google Scholar 

  10. H. Ahn and D. Del Vecchio, “Safety verification and control for collision avoidance at road intersections,” IEEE Trans. on Automatic Control, vol. 63, no. 3, pp. 630–642, March 2018.

    Article  MathSciNet  Google Scholar 

  11. L. Chen and C. Englund, “Cooperative intersection management: a survey,” IEEE Trans. on Intelligent Transportation Systems, vol. 17, no. 2, pp. 570–586, September 2015.

    Article  Google Scholar 

  12. N. Murgovski, G. R. de Campos, and J. Sjöberg, “Convex modeling of conflict resolution at traffic intersections,” Proc. of the IEEE Conf. Decision and Control, pp. 4708–4713, 2015.

    Google Scholar 

  13. A. Richards, T. Schouwenaars, J. P. How, and E. Feron, “Spacecraft trajectory planning with avoidance constraints using mixed-integer linear programming,” J. Guidance, Control, and Dynamics, vol. 25, no. 4, pp. 755–764, July 2002.

    Article  Google Scholar 

  14. J. Omer, “A space-discretized mixed-integer linear model for air-conflict resolution with speed and heading maneuvers,” Computers & Operations Research, vol. 58, pp. 75–86, June 2015.

    Article  MathSciNet  Google Scholar 

  15. L. Pallottino, E. Feron, and A. Bicchi, “Conflict resolution problems for air traffic management systems solved with mixed integer programming,” IEEE Trans. on Intelligent Transportation Systems, vol. 3, no. 1, pp. 3–11, August 2002.

    Article  Google Scholar 

  16. M. Kamal, J. Imura, T. Hayakawa, A. Ohata, and K. Aihara, “A vehicle-intersection coordination scheme for smooth flows of traffic without using traffic lights,” IEEE Trans. on Intelligent Transportation Systems, vol. 16, no. 3, pp. 1136–1147, June 2015.

    Article  Google Scholar 

  17. H. Ahn, A. Rizzi, A. Colombo, and D. Del Vecchio, “Experimental testing of semi-autonomous multi-vehicle control for collision avoidance at intersections,” Proc. of the IEEE/RSJ Int. Conf. Intelligent Robots and Systems, pp. 4834–4839, 2015.

    Google Scholar 

  18. C. Cassandras and S. Lafortune, Introduction to Discrete Event Systems, Springer Science & Business Media, 2009.

    MATH  Google Scholar 

  19. P. J. Ramadge and W. M. Wonham, “Supervisory control of a class of discrete event processes,” SIAM J. Control and Optimization, vol. 25, no. 1, pp. 206–230, January 1987.

    Article  MathSciNet  Google Scholar 

  20. P. Falcone, M. Tufo, F. Borrelli, J. Asgari, and H. E. Tseng, “A linear time varying model predictive control approach to the integrated vehicle dynamics control problem in autonomous systems,” Proc. of the IEEE Conf. Decision and Control, pp. 2980–2985, 2007.

    Google Scholar 

  21. D. Bresch-Pietri and D. Del Vecchio, “Estimation for decentralized safety control under communication delay and measurement uncertainty,” Automatica, vol. 62, pp. 292–303, December 2015.

    Article  MathSciNet  Google Scholar 

  22. D. Angeli and E. Sontag, “Monotone control systems,” IEEE Trans. on Automatic Control, vol. 48, no. 10, pp. 1684–1698, October 2003.

    Article  MathSciNet  Google Scholar 

  23. M. R. Garey, D. S. Johnson, B. B. Simons, and R. E. Tarjan, “Scheduling unit-time tasks with arbitrary release times and deadlines,” SIAM J. Computing, vol. 10, no. 2, pp. 256–269, May 1980.

    Article  MathSciNet  Google Scholar 

  24. R. Verma, D. Del Vecchio, and H. K. Fathy, “Development of a scaled vehicle with longitudinal dynamics of an HMMWV for an ITS testbed,” IEEE/ASME Trans. on Mechatronics, pp. 46–57, February 2008.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mitsubishi Electric Research Laboratories, 8th floor, 201 Broadway, Cambridge, MA, 02139, USA

    Heejin Ahn

  2. Tri-Institutional Program in Computational Biology and Medicine, Weill Cornell Medical College, 1300 York Avenue, New York, NY, 10065, USA

    Andrea Rizzi

  3. Department of Electronics, Information, and Bioengineering, Politecnico di Milano, via Ponzio 34/5, 20133, Milano, Italy

    Alessandro Colombo

Authors
  1. Heejin Ahn
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andrea Rizzi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Alessandro Colombo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Heejin Ahn.

Additional information

Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Recommended by Associate Editor Vu Nguyen under the direction of Editor Won-jong Kim. This work was done while Heejin Ahn was a Ph.D. candidate at the Massachusetts Institute of Technology.

Heejin Ahn received her B.S. degree from Seoul National University in 2012, and her S.M. and Ph.D. degrees from the Massachusetts Institute of Technology (MIT), in 2014 and 2018, respectively. She is currently a visiting research scientist at Mitsubishi Electric Research Laboratories. Her research interests include the analysis and control of networked dynamical systems with application to transportation systems.

Andrea Rizzi obtained both his Laurea and Laurea Magistrale in Engineering of Computing Systems from Politecnico di Milano, in 2010 and 2014, respectively. He is currently a Ph.D. candidate in the Tri-Institutional Ph.D. Program in Computational Biology & Medicine in Dr. Chodera’s lab at Memorial Sloan Kettering Cancer Center. His research is centered on improving molecular models for the prediction of small molecule-protein binding.

Alessandro Colombo received his Diplôme D’Ingénieur from ENSTA in Paris in 2005, and a Ph.D. from Politecnico di Milano in 2009. He was a Postdoctoral Associate at the Massachusetts Institute of Technology in 2010–2012, and is currently an associate professor in the Department of Electronics, Information and Bioengineering at Politecnico di Milano. His research interests are in the analysis and control of discontinuous and hybrid systems with applications, among others, to transportation networks.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ahn, H., Rizzi, A. & Colombo, A. Robust Supervisors for Intersection Collision Avoidance in the Presence of Legacy Vehicles. Int. J. Control Autom. Syst. 18, 384–393 (2020). https://doi.org/10.1007/s12555-018-0768-4

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12555-018-0768-4

Keywords

Search

Navigation