1932

Abstract

Operating autonomous agents in unstructured space presents a difficult problem. The complexity of making decisions such as when to yield and when to go ahead increases exponentially with the number of agents. This is true for humans as well as for software that controls autonomous agents. With some practice, however, human operators are able to move efficiently in a maze of interacting agents in dense traffic. One recent result correlates the instability of equilibria in a multiagent system with an absence of gridlocks. These control barrier function–based algorithms do not include a decision-making component—the action is continuous, and negotiation happens through instability. This mechanism, referred to as instinctive negotiation, is contrasted with discontinuity-induced decisions arising from nonconvex optimization. Based on observed behavioral similarities and insights into human implicit and explicit learning, this article proposes a connection with human driving and suggests that humans may employ a mechanism similar to instinctive negotiation to navigate dense traffic.

Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-060923-025701
2024-07-10
2025-02-13
Loading full text...

Full text loading...

/deliver/fulltext/control/7/1/annurev-control-060923-025701.html?itemId=/content/journals/10.1146/annurev-control-060923-025701&mimeType=html&fmt=ahah

Literature Cited

  1. 1.
    Blondel VD, Tsitsiklis JN. 2000.. A survey of computational complexity results in systems and control. . Automatica 36:(9):124974
    [Crossref] [Google Scholar]
  2. 2.
    Boyd S, Vandenberghe L. 2004.. Convex Optimization. Cambridge, UK:: Cambridge Univ. Press
    [Google Scholar]
  3. 3.
    Busoniu L, Babuška R, De Schutter B. 2010.. Multi-agent reinforcement learning: an overview. . In Innovations in Multi-Agent Systems and Applications, ed. D Srinivasan, LC Jain , pp. 183221. Berlin:: Springer
    [Google Scholar]
  4. 4.
    Schwarting W, Alonso-Mora J, Rus D. 2018.. Planning and decision making for autonomous vehicles. . Annu. Rev. Control Robot. Auton. Syst. 1::187210
    [Crossref] [Google Scholar]
  5. 5.
    Wang W, Wang L, Zhang C, Liu C, Sun L. 2022.. Social interactions for autonomous driving: a review and perspectives. . Found. Trends Robot. 10:(3–4):198376
    [Crossref] [Google Scholar]
  6. 6.
    Fox D, Burgard W, Thrun S. 1997.. The dynamic window approach to collision avoidance. . IEEE Robot. Autom. Mag. 4:(1):2333
    [Crossref] [Google Scholar]
  7. 7.
    Conroy P, Barreiss D, Beall M, van den Berg J. 2014.. 3-D reciprocal collision avoidance on physical quadrotor helicopters with on-board sensing for relative positioning. . arXiv:1411.3794v1 [cs.RO]
  8. 8.
    Snape J, van den Berg J, Guy S. 2011.. The hybrid reciprocal velocity obstacle. . IEEE Trans. Robot. 27:(4):696706
    [Crossref] [Google Scholar]
  9. 9.
    van den Berg J, Guy S, Lin M, Manocha D. 2009.. Reciprocal n-body collision avoidance. . Robotics Research: The 14th International Symposium ISRR, ed. C Pradalier, R Siegwart, G Hirzinger , pp. 319. Berlin:: Springer
    [Google Scholar]
  10. 10.
    Trautman P, Krause A. 2010.. Unfreezing the robot: navigation in dense, interacting crowds. . In 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 797803. Piscataway, NJ:: IEEE
    [Google Scholar]
  11. 11.
    Paden B, Čáp M, Zheng Yong S, Yershov D, Frazzoli E. 2016.. A survey of motion planning and control techniques for self-driving urban vehicles. . IEEE Trans. Intell. Veh. 1:(1):3355
    [Crossref] [Google Scholar]
  12. 12.
    Vitelli M, Chang Y, Ye Y, Woyczyk M, Osiński B, et al. 2021.. SafetyNet: safe planning for real-world self-driving vehicles using machine-learned policies. . arXiv:2109.13602v1 [cs.RO]
  13. 13.
    Phan-Minh T, Howington F, Chu T-S, Lee S, Tomov M, et al. 2022.. Driving in real life with inverse reinforcement learning. . arXiv:2206.03004v1 [cs.RO]
  14. 14.
    Nageshrao S, Rahman Y, Ivanovic V, Jankovic M, Tseng E, et al. 2022.. Robust AI driving strategy for autonomous vehicles. . In AI-Enabled Technologies for Autonomous and Connected Vehicles, ed. YL Murphey, I Kolmanovsky, P Watta , pp. 161212. Cham, Switz.:: Springer
    [Google Scholar]
  15. 15.
    Tesla. 2022.. Tesla AI Day 2022. . YouTube. https://www.youtube.com/watch?v=ODSJsviD_SU
    [Google Scholar]
  16. 16.
    Wieland P, Allgöwer F. 2007.. Constructive safety using control barrier functions. . IFAC Proc. Vol. 40:(12):46267
    [Crossref] [Google Scholar]
  17. 17.
    Ames AD, Grizzle JW, Tabuada P. 2014.. Control barrier functions based quadratic programming with application to adaptive cruise control. . In 53rd IEEE Conference on Decision and Control, pp. 627178. Piscataway, NJ:: IEEE
    [Google Scholar]
  18. 18.
    Ames AD, Xu X, Grizzle JW, Tabuada P. 2017.. Control barrier function based quadratic programs for safety critical systems. . IEEE Trans. Autom. Control 62:(8):386176
    [Crossref] [Google Scholar]
  19. 19.
    Hobbs K, Mote M, Abate M, Coogan S, Feron E. 2023.. Runtime assurance for safety-critical systems. . IEEE Control Syst. Mag. 43:(2):2865
    [Crossref] [Google Scholar]
  20. 20.
    ODYS. 2023.. ODYS QP Solver. . ODYS. http://odys.it/qp
    [Google Scholar]
  21. 21.
    Blackmore L. 2017.. Autonomous precision landing of space rockets. . In Frontiers in Engineering: Reports on Leading-Edge Engineering from the 2016 Symposium, pp. 3342. Washington, DC:: Natl. Acad. Press
    [Google Scholar]
  22. 22.
    Alrifaee B, Maczijewski J, Abel D. 2017.. Sequential convex programming MPC for dynamic vehicle collision avoidance. . In 2017 IEEE Conference on Control Technology and Applications, pp. 22027. Piscataway, NJ:: IEEE
    [Google Scholar]
  23. 23.
    Schouwenaars T, De Moor B, Feron E, How J. 2001.. Mixed integer programming for multi-vehicle path planning. . In 2001 European Control Conference, pp. 26038. Piscataway, NJ:: IEEE
    [Google Scholar]
  24. 24.
    Borrmann U, Wang L, Ames AD, Egerstedt M. 2015.. Control barrier certificates for safe swarm behavior. . IFAC-PapersOnLine 48:(27):6873
    [Crossref] [Google Scholar]
  25. 25.
    Wang L, Ames AD, Egerstedt M. 2017.. Safety barrier certificates for collision-free multirobot systems. . IEEE Trans. Robot. 33:(33):66174
    [Crossref] [Google Scholar]
  26. 26.
    Santillo M, Jankovic M. 2021.. Collision free navigation with interacting, non-communicating obstacles. . In 2021 American Control Conference, pp. 163743. Piscataway, NJ:: IEEE
    [Google Scholar]
  27. 27.
    Jankovic M, Santillo M. 2021.. Collision avoidance and liveness of multi-agent systems with CBF-based controllers. . In 2021 60th IEEE Conference on Decision and Control, pp. 682228. Piscataway, NJ:: IEEE
    [Google Scholar]
  28. 28.
    Jankovic M, Santillo M, Wang Y. 2023.. Multi-agent systems with CBF-based controllers: collision avoidance and liveness from instability. . IEEE Trans. Control Syst. Technol. https://doi.org/10.1109/TCST.2023.3324531
    [Google Scholar]
  29. 29.
    Ashby FG, Valentin VV. 2017.. Multiple systems of perceptual category learning: theory and cognitive tests. . In Handbook of Categorization in Cognitive Science, ed. H Cohen, C Lefebvre , pp. 15788. Amsterdam:: Elsevier. , 2nd ed..
    [Google Scholar]
  30. 30.
    Roeder JL, Maddox WT, Filoteo JV. 2017.. The neuropsychology of perceptual category learning. . In Handbook of Categorization in Cognitive Science, ed. H Cohen, C Lefebvre , pp. 189225. Amsterdam:: Elsevier. , 2nd ed..
    [Google Scholar]
  31. 31.
    Smith JD, Berg ME, Cook RG, Murphy MS, Crossly MJ, et al. 2012.. Implicit and explicit categorization: a tale of four species. . Neurosci. Biobehav. Rev. 36:(10):235569
    [Crossref] [Google Scholar]
  32. 32.
    Garone E, Di Cairano S, Kolmanovsky I. 2017.. Reference and command governors for systems with constraints: a survey on theory and applications. . Automatica 75::30628
    [Crossref] [Google Scholar]
  33. 33.
    Nicotra MM, Garone E. 2018.. The explicit reference governor: a general framework for the closed-form control of constrained nonlinear systems. . IEEE Control Syst. Mag. 38:(4):89107
    [Crossref] [Google Scholar]
  34. 34.
    Kouvaritakis B, Cannon M. 2016.. Model Predictive Control: Classical, Robust, and Stochastic. Cham, Switz.:: Springer
    [Google Scholar]
  35. 35.
    Khatib O. 1986.. Real-time obstacle avoidance for manipulators and mobile robots. . Int. J. Robot. Res. 5:(1):9098
    [Crossref] [Google Scholar]
  36. 36.
    Gerdes C, Rossetter E. 1999.. A unified approach to driver assistance systems based on artificial potential fields. . J. Dyn. Syst. Meas. Control 123:(3):43138
    [Crossref] [Google Scholar]
  37. 37.
    Nguyen Q, Sreenath K. 2016.. Exponential control barrier functions for enforcing high relative-degree safety-critical constraints. . In 2016 American Control Conference, pp. 32228. Piscataway, NJ:: IEEE
    [Google Scholar]
  38. 38.
    Jankovic M. 2018.. Robust control barrier functions for constrained stabilization of nonlinear systems. . Automatica 96::35967
    [Crossref] [Google Scholar]
  39. 39.
    Kolathaya S, Ames AD. 2019.. Input-to-state safety with control barrier functions. . IEEE Control Syst. Lett. 3:(1):10813
    [Crossref] [Google Scholar]
  40. 40.
    Clark A. 2019.. Control barrier functions for complete and incomplete information stochastic systems. . In 2019 American Control Conference, pp. 292835. Piscataway, NJ:: IEEE
    [Google Scholar]
  41. 41.
    Xu X, Tabuada P, Grizzle JW, Ames AD. 2015.. Robustness of control barrier functions for safety critical control. . IFACPapers-OnLine 48:(27):5461 ( updated version available at https://doi.org/10.48550/arXiv.1612.01554 )
    [Crossref] [Google Scholar]
  42. 42.
    Seiler P, Jankovic M, Hellstrom E. 2022.. Control barrier functions with unmodeled input dynamics using integral quadratic constraints. . IEEE Control Syst. Lett. 6::166469
    [Crossref] [Google Scholar]
  43. 43.
    Liu C, Tomizuka M. 2014.. Control in a safe set: addressing safety in human-robot interactions. . In Proceedings of the ASME 2014 Dynamic Systems and Control Conference, Vol. 3, pap. V003T42A003 . New York:: Am. Soc. Mech. Eng.
    [Google Scholar]
  44. 44.
    Xiao W, Belta C. 2019.. Control barrier functions for systems with high relative degree. . In 2019 IEEE 58th Conference on Decision and Control, pp. 47479. Piscataway, NJ:: IEEE
    [Google Scholar]
  45. 45.
    Krstic M, Bement M. 2006.. Nonovershooting control of strict-feedback nonlinear systems. . IEEE Trans. Autom. Control 51:(12):193843
    [Crossref] [Google Scholar]
  46. 46.
    Fiorini P, Shiller Z. 1998.. Motion planning in dynamic environments using velocity obstacles. . Int. J. Robot. Res. 17:(7):76072
    [Crossref] [Google Scholar]
  47. 47.
    Everett M, Chen YF, How JP. 2018.. Motion planning among dynamic, decision-making agents with deep reinforcement learning. . In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 305259. Piscataway, NJ:: IEEE
    [Google Scholar]
  48. 48.
    Panagou D, Stipanovic D, Vulgaris P. 2016.. Distributed coordination control for multi-robot networks using Lyapunov-like barrier functions. . IEEE Trans. Autom. Control 61:(3):61732
    [Crossref] [Google Scholar]
  49. 49.
    Celi F, Wang L, Pallottino L, Egerstedt M. 2019.. Deconfliction of motion paths with traffic inspired rules in robot-robot and human-robot interactions. . IEEE Robot. Autom. Lett. 4:(2):222734
    [Crossref] [Google Scholar]
  50. 50.
    Grover J, Liu C, Sycara K. 2022.. The before, during and after of multi-robot deadlock. . Int. J. Robot. Res. 42:(6):31736
    [Crossref] [Google Scholar]
  51. 51.
    Chen Y, Zhang L, Merry T, Amatya S, Zhang W, Ren Y. 2021.. When shall I be empathetic? The utility of empathetic parameter estimation in multi-agent interactions. . In 2021 IEEE International Conference on Robotics and Automation, pp. 276167. Piscataway, NJ:: IEEE
    [Google Scholar]
  52. 52.
    Au T-C, Zhang S, Stone P. 2015.. Autonomous intersection management for semi-autonomous vehicles. . In Routledge Handbook of Transportation, ed. D Teodorovic , pp. 88104. London:: Routledge
    [Google Scholar]
  53. 53.
    Hassan A, Rakha H. 2014.. A fully-distributed heuristic algorithm for vehicle control of autonomous vehicle movement at isolated intersections. . Int. J. Transp. Sci. Technol. 3::297310
    [Crossref] [Google Scholar]
  54. 54.
    Verginis CK, Dimarogonas DV. 2019.. Closed-form barrier functions for multi-agent ellipsoidal systems with uncertain Lagrangian dynamics. . IEEE Control Syst. Lett. 3:(3):72732
    [Crossref] [Google Scholar]
  55. 55.
    Rajamani R. 2012.. Vehicle Dynamics and Control. New York:: Springer. , 2nd ed..
    [Google Scholar]
  56. 56.
    Albaba M, Yildiz Y. 2019.. Modeling cyber-physical human systems via an interplay between reinforcement learning and game theory. . Annu. Rev. Control 48::121
    [Crossref] [Google Scholar]
  57. 57.
    Kim C, Langari R. 2014.. Game theory based autonomous vehicles operation. . Int. J. Veh. Des. 65:(4):36083
    [Crossref] [Google Scholar]
  58. 58.
    Liu M, Kolmanovsky I, Tseng HE, Huang S, Filev D, Girard A. 2023.. Potential game-based decision-making for autonomous driving. . IEEE Trans. Intell. Transp. Syst. 24:(8):801427
    [Crossref] [Google Scholar]
  59. 59.
    Treiber M, Hennecke A, Helbing D. 2000.. Congested traffic states in empirical observations and microscopic simulations. . Phys. Rev. E 62:(2):180524
    [Crossref] [Google Scholar]
  60. 60.
    van Hasselt H, Guez A, Silver D. 2016.. Deep reinforcement learning with double Q-learning. . Proc. AAAI Conf. Artif. Intell. 30:(1). https://doi.org/10.1609/aaai.v30i1.10295
    [Google Scholar]
  61. 61.
    Black M, Jankovic M, Sharma A, Panagou D. 2023.. Future-focused control barrier functions for autonomous vehicle control. . In 2023 American Control Conference, pp. 332431. Piscataway, NJ:: IEEE
    [Google Scholar]
  62. 62.
    Khalil HK. 2002.. Nonlinear Systems. Upper Saddle River, NJ:: Prentice Hall
    [Google Scholar]
  63. 63.
    Censi A, Slutsky K, Wongpiromsarn T, Yershov D, Pendleton S, et al. 2019.. Liability, ethics, and culture-aware behavior specification using rulebooks. . arXiv:1902.09355v2 [cs.AI]
  64. 64.
    Lake BM, Ullman TD, Tenenbaum JB, Gershman SJ. 2017.. Building machines that learn and think like people. . Behav. Brain Sci. 40::e253
    [Crossref] [Google Scholar]
  65. 65.
    Franci A, Golubitsky M, Stewart I, Bizyaeva A, Leonard NE. 2023.. Breaking indecision in multiagent, multioption dynamics. . SIAM J. Appl. Dyn. Syst. 22:(3):1780817
    [Crossref] [Google Scholar]
/content/journals/10.1146/annurev-control-060923-025701
Loading
/content/journals/10.1146/annurev-control-060923-025701
Loading

Data & Media loading...

  • Article Type: Review Article
This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error