Navigation functions with moving destinations and obstacles
Abstract
Dynamic environments challenge existing robot navigation methods, and motivate either stringent assumptions on workspace variation or relinquishing of collision avoidance and convergence guarantees. This paper shows that the latter can be preserved even in the absence of knowledge of how the environment evolves, through a navigation function methodology applicable to sphere-worlds with moving obstacles and robot destinations. Assuming bounds on speeds of robot destination and obstacles, and sufficiently higher maximum robot speed, the navigation function gradient can be used produce robot feedback laws that guarantee obstacle avoidance, and theoretical guarantees of bounded tracking errors and asymptotic convergence to the target when the latter eventually stops moving. The efficacy of the gradient-based feedback controller derived from the new navigation function construction is demonstrated both in numerical simulations as well as experimentally.
References
[1]
Aiushita, S., Hisanobu, T., & Kawamura, S. (1993) Fast path planning available for moving obstacle avoidance by use of laplace potential. In Proceedings of the IEEE international conference on robotics and automation (pp. 673–678).
[2]
Ajanovic, Z., Lacevic, B., Shyrokau, B., Stolz, M., Horn, M. (2018). Search-based optimal motion planning for automated driving. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 4523–4530).
[3]
Alonso-Mora J, DeCastro JA, Raman V, Rus D, and Kress-Gazit H Reactive mission and motion planning with deadlock resolution avoiding dynamic obstacles Autonomous Robots 2017 42 4 801-824
[4]
Alsaab, A., & Bicker, R. (2014) Improving velocity obstacle approach for obstacle avoidance in indoor environments. In Proceedings of the UKACC international conference on control (pp. 325–330).
[5]
Arslan O and Koditschek DE Sensor-based reactive navigation in unknown convex sphere worlds The International Journal of Robotics Research 2019 38 2–3 196-223
[6]
Cai, K., Wang, C., Cheng, J., De Silva, C. W., Meng, M. Q.-H. (2018) Mobile robot path planning in dynamic environments: A survey. arXiv preprint arXiv:2006.14195
[7]
Chen, C., Li, C., & Tanner, H. G. (2020) Navigation functions with non-point destinations and moving obstacles. In Proceedings of the IEEE American control conference (pp. 2532–2537).
[8]
Chen PC and Hwang YK SANDROS: A dynamic graph search algorithm for motion planning IEEE Transactions on Robotics and Automation 1998 14 3 390-403
[9]
Connolly C Harmonic functions and collision probabilities The International Journal of Robotics Research 1997 16 4 497-507
[10]
Elbanhawi M and Simic M Sampling-based robot motion planning: A review IEEE Access 2014 2 56-77
[11]
Faust, A., Oslund, K., Ramirez, O., Francis, A., Tapia, L., Fiser, M., Davidson, J. (2018). PRM-RL: Long-range robotic navigation tasks by combining reinforcement learning and sampling-based planning. In Proceedings of the IEEE international conference on robotics and automation (pp. 5113–5120)
[12]
Ferguson D and Stentz A Using interpolation to improve path planning: The field D* algorithm Journal of Field Robotics 2006 23 2 79-101
[13]
Fernandes, L. C., Souza, J. R., Shinzato, P. Y., Pessin, G., Mendes, C. C. T., Osorio, F. S., Wolf, D. F. (2012) Intelligent robotic car for autonomous navigation: Platform and system architecture. In Proceedings of the second Brazilian conference on critical embedded systems (pp. 12–17).
[14]
Francis A, Faust A, Chiang H-TL, Hsu J, Kew JC, Fiser M, and Lee T-WE Long-range indoor navigation with PRM-RL IEEE Transactions on Robotics 2020 36 4 1115-1134
[15]
Fulgenzi, C., Spalanzani, A., & Laugier, C. (2009) Probabilistic rapidly-exploring random trees for autonomous navigation among moving obstacles. In Proceedings of the IEEE international conference on robotics and automation (pp. 4027–4033).
[16]
González D, Pérez J, Milanés V, and Nashashibi F A review of motion planning techniques for automated vehicles IEEE Transactions on Intelligent Transportation Systems 2015 17 4 1135-1145
[17]
Hasselt, H. v., Guez, A., Silver, D. (2016). Deep reinforcement learning with double Q-learning. In Proceedings of the thirtieth AAAI conference on artificial intelligence (pp. 2094–2100).
[18]
Iizuka, S., Nakamura, T., & Suzuki, S. (2014). Robot navigation in dynamic environment using navigation function APF with SLAM. In Proceedings of the IEEE 8th Europe-Asia congress on mecatronics (pp. 89–92).
[19]
Jaillet, L., Siméon, T. (2004) A PRM-based motion planner for dynamically changing environments. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (Vol. 2, pp. 1606–1611).
[20]
Karaman S and Frazzoli E Sampling-based algorithms for optimal motion planning The International Journal of Robotics Research 2011 30 7 846-894
[21]
Khalil HK Nonlinear systems 2002 Prentice Hall
[22]
Koditschek DE and Rimon E Robot navigation functions on manifolds with boundary Advances in Applied Mathematics 1990 11 4 412-442
[23]
Li C and Tanner HG Navigation functions with time-varying destination manifolds in star worlds IEEE Transactions on Robotics 2019 35 1 35-48
[24]
Loizou, S. G., Tanner, H. G., Kumar, V., Kyriakopoulos, K. (2003) Closed loop navigation for mobile robots in dynamic environments. In Proceedings of the IEEE/RSJ international conference on robots and systems (pp. 3769–3774).
[25]
Minguez J, Lamiraux F, and Laumond J-P Siciliano B and Khatib O Motion planning and obstacle avoidance Springer Handbook of Robotics 2008 Berlin, Heidelberg Springer 827-852
[26]
Mohanan MG and Salgoankar A A survey of robotic motion planning in dynamic environments Robotics and Autonomous Systems 2018 100 171-185
[27]
Montiel O, Orozco-Rosas U, and Sepúlveda R Path planning for mobile robots using bacterial potential field for avoiding static and dynamic obstacles Expert Systems with Applications 2015 42 12 5177-5191
[28]
Olunloyo VOS and Ayomoh MKO Autonomous mobile robot navigation using hybrid virtual force field concept European Journal of Scientific Research 2009 31 2 204-228
[29]
Pandey A, Pandey S, and Parhi DR Mobile robot navigation and obstacle avoidance techniques: A review International Robotics & Automation Journal 2017 2 3 96-105
[30]
Paternain S, Koditschek DE, and Ribeiro A Navigation functions for convex potentials in a space with convex obstacles IEEE Transactions on Automatic Control 2018 63 9 2944-2959
[31]
Pradhan, N., Burg, T., & Birchfield, S. (2011). Robot crowd navigation using predictive position fields in the potential function framework. In Proceedings of American control conference (pp. 4628–4633).
[32]
Prassler E, Scholz J, and Fiorini P A robotics wheelchair for crowded public environment IEEE Robotics & Automation Magazine 2001 8 1 38-45
[33]
Qi J, Yang H, and Sun H MOD-RRT*: A sampling-based algorithm for robot path planning in dynamic environment IEEE Transactions on Robotics 2021 68 8 7244-7251
[34]
Rimon E and Koditschek DE Exact robot navigation using artificial potential functions Transactions on Robotics and Automation 1992 8 5 501-518
[35]
Short, A., Pan, Z., Larkin, N., & van Duin, S. (2016) Recent progress on sampling based dynamic motion planning algorithms. In Proceedings of the IEEE international conference on advanced intelligent mechatronics (pp. 1305–1311).
[36]
Shvalb N and Hacohen S Kagan E, Shvalb N, and Ben-Gal I Motion in potential field and navigation function Autonomous mobile robots and multi-robot systems 2019 John Wiley & Sons 87-107
[37]
Sun J and Tanner HG Constrained decision-making for low-count radiation detection by mobile sensors Autonomous Robots 2015 39 4 519-536
[38]
Szulczyński P, Pazderski D, and Kozłowski K Harmonic functions and collision probabilities Journal of Automation Mobile Robotics and Intelligent Systems 2011 5 3 497-507
[39]
Tanner, H. G., & Kyriakopoulos, K. J. (2000). Nonholonomic motion planning for mobile manipulators. In Proceedings of the IEEE international conference on robotics and automation (Vol. 2, pp. 1233–1238).
[40]
Tanner, H. G., Jadbabaie, A., & Pappas, G. J. (2003). Stable flocking of mobile agents, Part I: Fixed topology. In Proceedings of the IEEE conference on decision and control (pp. 2010–2015).
[41]
Tanner HG, Jadbabaie A, and Pappas GJ Morse S, Leonard N, and Kumar V Flocking in teams of nonholonomic agents Cooperative control. Lecture notes in control and information sciences 2005 Springer 229-239
[42]
Tiseni L, Chiaradia D, Gabardi M, Solazzi M, Leonardis D, and Frisoli A UV-C mobile robots with optimized path planning: Algorithm design and on-field measurements to improve surface disinfection against SARS-CoV-2 IEEE Robotics Automation Magazine 2021 28 1 59-70
[43]
Van Den Berg, J.P., Nieuwenhuisen, D., Jaillet, L., & Overmars, M. H. (2005). Creating robust roadmaps for motion planning in changing environments. In Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (pp. 1053–1059).
[44]
Vasilopoulos V, Pavlakos G, Bowman SL, Caporale JD, Daniilidis K, Pappas GJ, and Koditschek DE Reactive semantic planning in unexplored semantic environments using deep perceptual feedback IEEE Robotics and Automation Letters 2020 5 3 4455-4462
[45]
Wang J, Meng MQ-H, and Khatib O EB-RRT: Optimal motion planning for mobile robots IEEE Transactions on Automation Science and Engineering 2020 17 4 2063-2073
[46]
Warnke, J., Shamsah, A., Li, Y., Zhao, Y. (2020). Towards safe locomotion navigation in partially observable environments with uneven terrain. In Proceedings of IEEE conference on decision and control (pp. 958–965).
[47]
Waydo, S., & Murray, R. M. (2003) Vehicle motion planning using stream functions. In Proceedings of the IEEE international conference on robotics and automation (pp. 2484–2491).
[48]
Wijmans, E., Kadian, A., Morcos, A., Lee, S., Essa, I., Parikh, D., Savva, M., Batra, D. (2019). DD-PPO: Learning near-perfect pointgoal navigators from 2.5 billion frames. arXiv preprint arxiv:1911.00357
[49]
Xu, D., Fang, Y., Zhang, Z., Meng, Y. (2017). Path planning method combining depth learning and Sarsa algorithm. In Proceedings of the international symposium on computational intelligence and design (Vol. 2, pp. 77–82).
[50]
Yadav, I., Eckenhoff, K., Huang, G., Tanner, H.G. (2018). Visual-inertial target tracking and motion planning for UAV-based radiation detection. arXiv preprint arXiv:1805.09061
[51]
Yadav, I., Tanner, H. G. (2021) Exact decentralized receding horizon planning for multiple aerial vehicles. In Proceedings of the IEEE conference on decision and control (pp. 5747–5752).
[52]
Yao P, Wang H, and Su Z Real-time path planning of unmanned aerial vehicle for target tracking and obstacle avoidance in complex dynamic environment Aerospace Science and Technology 2015 47 269-279
[53]
Zucker, M., Kuffner, J., & Branicky, M. (2007). Multipartite RRTs for rapid replanning in dynamic environments. In Proceedings of the IEEE international conference on robotics and automation (pp. 1603–1609).
Recommendations
Tangential Gap Flow (TGF) navigation
This paper presents a novel reactive collision avoidance method for mobile robots moving in dense and cluttered environments. The proposed method, entitled Tangential Gap flow (TGF), simplifies the navigation problem using a divide and conquer strategy ...
Reactive and the shortest path navigation of a wheeled mobile robot in cluttered environments
We determine the shortest minimal in length path on a unicycle-like mobile robot in a known environment with smooth possibly non-convex obstacles with a constraint on curvature of their boundaries. Furthermore, we propose a new reactive randomized ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2023. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 12 February 2023
Accepted: 12 January 2023
Received: 30 December 2021
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 06 Jan 2025