Boundary-RRT* Algorithm for Drone Collision Avoidance and Interleaved Path Re-planning
0
조회
0
다운로드
4
인용
0
참고문헌
키워드
초록
Various modified algorithms of rapidly-exploring random tree (RRT) have been previously proposed. However, compared to the RRT algorithm for collision avoidance with global and static obstacles, it is not easyto find a collision avoidance and local path re-planning algorithm for dynamic obstacles based on the RRTalgorithm. In this study, we propose boundary-RRT*, a novel-algorithm that can be applied to aerial vehiclesfor collision avoidance and path re-planning in a three-dimensional environment. The algorithm not onlybounds the configuration space, but it also includes an implicit bias for the bounded configuration space. Therefore, it can create a path with a natural curvature without defining a bias function. Furthermore, theexploring space is reduced to a half-torus by combining it with simple right-of-way rules. When defining thedistance as a cost, the proposed algorithm through numerical analysis shows that the standard deviation (σ)approaches 0 as the number of samples per unit time increases and the length of epsilon ε (maximum length ofan edge in the tree) decreases. This means that a stable waypoint list can be generated using the proposedalgorithm. Therefore, by increasing real-time performance through simple calculation and the boundary of theconfiguration space, the algorithm proved to be suitable for collision avoidance of aerial vehicles and replanningof local paths.
Abstract
Various modified algorithms of rapidly-exploring random tree (RRT) have been previously proposed. However, compared to the RRT algorithm for collision avoidance with global and static obstacles, it is not easyto find a collision avoidance and local path re-planning algorithm for dynamic obstacles based on the RRTalgorithm. In this study, we propose boundary-RRT*, a novel-algorithm that can be applied to aerial vehiclesfor collision avoidance and path re-planning in a three-dimensional environment. The algorithm not onlybounds the configuration space, but it also includes an implicit bias for the bounded configuration space. Therefore, it can create a path with a natural curvature without defining a bias function. Furthermore, theexploring space is reduced to a half-torus by combining it with simple right-of-way rules. When defining thedistance as a cost, the proposed algorithm through numerical analysis shows that the standard deviation (σ)approaches 0 as the number of samples per unit time increases and the length of epsilon ε (maximum length ofan edge in the tree) decreases. This means that a stable waypoint list can be generated using the proposedalgorithm. Therefore, by increasing real-time performance through simple calculation and the boundary of theconfiguration space, the algorithm proved to be suitable for collision avoidance of aerial vehicles and replanningof local paths.
참고문헌 (30)
- P. Fiorini, "Motion planning in dynamic environments using velocity obstacles", The International Journal of Robotics Research, 17(7), pp.760~772 (1998)
- J. A. Douthwaite, "Velocity obstacle approaches for multi-agent collision avoidance", Unmanned Systems, 7(1), pp.55~64 (2019)
- Y. I. Jenie, "Three-dimensional velocity obstacle method for uncoordinated avoidance maneuvers of unmanned aerial vehicles", Journal of Guidance, Control, and Dynamics, 39(10), pp.2312~2323 (2016)
- X. Yang, "Obstacle avoidance method of three-dimensional obstacle spherical cap", Journal of Systems Engineering and Electronics, 29(5), pp.1058~1068 (2018)
- 박현상, "분할된 RRT 공간을 이용한 Simulink", Stateflow모델 테스트케이스 생성, 2013, pp.2(7), 471~478[DOI]
- M. Cap, "Multi-agent RRT : sampling-based cooperative pathfinding", Proceedings of International conference on Autonomous Agents and Multi-Agent Systems(AAMAS), pp.1263~1264 (2013)
- J. Nasir, "RRT*-SMART : a rapid convergence implementation of RRT", International Journal of Advanced Robotic Systems, 10(7), pp.299~ (2013)
- C. Urmson, "Approaches for heuristically biasing RRT growth", Proceedings 2003IEEE, 2003, 1178~1183
- J. D. Gammell, "Informed RRT* : optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic", Proceedings of 2014 IEEE, 2014, 2997~3004
- X. Wu, "Biased sampling potentially guided intelligent bidirectional RRT∗algorithm for UAV path planning in 3D environment", Mathematical Problems in Engineering, 2019, pp.5157403~ (2019)
- K. Naderi, "RT-RRT* a real-time path planning algorithm based on RRT", Proceedings of the 8th ACM SIGGRAPH Conference on Motion in Games, pp.113~118 (2015)
- P. Yao, "Hybrid UAV path planning based on interfered fluid dynamical system and improved RRT", Proceedings of the 41st Annual Conference of the IEEE Industrial Electronics Society(IECON), pp.000829~000834 (2015)
- S. Karaman, "Sampling-based algorithms for optimal motion planning", The International Journal of Robotics Research, 30(7), pp.846~894 (2011)
- J. Munkres, "Algorithms for the assignment and transportation problems", Journal of the Society for Industrial and Applied Mathematics, 5(1), pp.32~38 (1957)
- Z. Shi, "A collision-free path planning algorithm for unmanned aerial vehicle delivery", Proceedings of 2018 International Conference on Unmanned Aircraft Systems(ICUAS), pp.358~362 (2018)
- S. M. LaValle, "Randomized kinodynamic planning", Proceedings of 1999 IEEE International Conference on Robotics and Automation, pp.473~479 (1999)
- S. M. LaValle, "Rapidly-exploring random trees: a new tool for path planning", Department of Computer Science, pp.1998
- Y. B. Chen, "UAV path planning using artificial potential field method updated by optimal control theory", International Journal of Systems Science, 47(6), pp.1407~1420 (2016)
- M. U. Farooq, "Quadrotor UAVs flying formation reconfiguration with collision avoidance using probabilistic roadmap algorithm", Proceedings of 2017 International Conference on Computer Systems, pp.866~870 (2017)
- L. G. D. Veras, "systematic literature review of sampling process in rapidly-exploring random trees", IEEE Access, 7, pp.50933~50953 (2019)
- D. Alejo, "The velocity assignment problem for conflict resolution with multiple aerial vehicles sharing airspace", Journal of Intelligent & Robotic Systems, 69(1-4), pp.331~346 (2013)
- J. J. Rebollo, "Collision avoidance among multiple aerial robots and other noncooperative aircraft based on velocity planning", Proceedings of the 7th Conference on Mobile Robots and Competitions (2007)
- J. Van den Berg, "Reciprocal velocity obstacles for real-time multi-agent navigation", Proceedings of 2008 IEEE International Conference on Robotics and Automation, pp.1928~1935 (2008)
- Federal Aviation Administration, "Pilot’s Handbook of Aeronautical Knowledge", pp.5~38 (2016), Federal Aviation Administration
- "Section 91.113: Right-of-way rules: except water operations" (2004)[URL]
- Y. I. Jenie, "Selective velocity obstacle method for deconflicting maneuvers applied to unmanned aerial vehicles", Journal of Guidance, Control, and Dynamics, 38(6), pp.1140~1146 (2015)
- J. Farmer, "The volume of a torus using cylindrical and spherical coordinates", Australian Senior Mathematics Journal, 19(2), pp.49~58 (2005)
- L. Liu, "Path planning for UAVS based on improved artificial potential field method through changing the repulsive potential function", Proceedings of 2016 IEEE Chinese Guidance, pp.2011~2015 (2016)
- L. Wang, "Improved ant colony optimization for ground robot 3D path planning", Proceedings of 2018 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery(CyberC), pp.106~1066 (2018)
- M. Radmanesh, "Flight formation of UAVs in presence of moving obstacles using fastdynamic mixed integer linear programming", Aerospace Science and Technology, 50, pp.149~160 (2016)