This paper proposes an improved RRT^* formation path planning algorithm based on goal bias and node rejection strategy to solve UAVs’ formation path planning problems in a complex environment. Aiming at the position constraint problem of multi-UAV in the planning process, the leader–follower structure among UAVs and the formation configuration model are established. Furthermore, aiming at node redundancy and slow planning speed caused by the RRT^* algorithm in a complex environment, this paper sets the goal bias information so that the random tree could find the initial path quickly. At the same time, this paper proposes a node rejection strategy to prevent the nodes that do not meet the pre-set conditions from participating in the subsequent expansion. Compared to the standard RRT-related algorithms, the proposed improved algorithm can shorten the planning time, reduce the number of algorithm iterations and improve the algorithm’s applicability in the formation path planning problem.

This paper was recommended for publication in its revised form by editorial board member, Shiyu Zhao.

Keywords:

References

1. A. Mohiuddin et al., A survey of single and multi-UAV aerial manipulation, J. Unmanned Syst. 8(2) (2019) 119–147. Link, Google Scholar
2. S. B. Amarat and P. Zong, 3D path planning, routing algorithms and routing protocols for unmanned air vehicles: A review, J. Aircraft Eng. Aerosp. Technol. 91(9) (2019) 1245–1255. Crossref, Google Scholar
3. H. Zhang et al., A review of cooperative path planning of an unmanned aerial vehicle group, J. Front. Inf. Technol. Electron. Eng. 21(12) (2020) 1671–1694. Crossref, Google Scholar
4. W. Wu and N. Cui, A distributed and integrated method for cooperative mission planning of multiple heterogeneous UAVs, J. Aircraft Eng. Aerosp. Technol. 90(9) (2018) 1403–1412. Crossref, Google Scholar
5. F. Samaniego, S. Javier and G. N. Sergio, UAV motion planning and obstacle avoidance based on adaptive 3D cell decomposition: Continuous space vs discrete space, in Proc. 2017 IEEE Second Ecuador Technical Chapters Meeting, IEEE, Salinas, Ecuador, pp. 1–6. Google Scholar
6. Y. Chen et al., Three-dimensional unmanned aerial vehicle path planning using modified wolf pack search algorithm, J. Neurocomput. 266 (2017) 445–457. Crossref, Google Scholar
7. Y. Liu et al., Adaptive sensitivity decision based path planning algorithm for unmanned aerial vehicle with improved particle swarm optimization, J. Aerosp. Sci. Technol. 58 (2016) 92–102. Crossref, Google Scholar
8. L. Kavraki et al., Probabilistic roadmaps for path planning in high-dimensional configuration spaces, J. IEEE Trans. Robot. Automat. 12(4) (1996) 566–580. Crossref, Google Scholar
9. S. M. Lavalle and J. J. Kuffner, Randomized kinodynamic planning, J. Int. J. Robot. Res. 20(5) (2001) 378–400. Crossref, Google Scholar
10. J. Wang et al., Neural RRT^∗: Learning-based optimal path planning, J. IEEE Trans. Automat. Sci. Eng. 17(4) (2020) 1748–1758. Crossref, Google Scholar
11. A. R. Pedram et al., Rationally inattentive path-planning via RRT, in Proc. 2021 American Control Conf. (IEEE, New York), pp. 3440–3446. Google Scholar
12. C. Yuan et al., An efficient RRT cache method in dynamic environments for path planning, J. Robot. Autonom. Syst. 131 (2020) 1–12. Google Scholar
13. J. J. Kuffner and S. M. Lavalle, RRT-connect: An efficient approach to single-query path planning, in Proc. 2000 ICRA. Millennium Conf., IEEE Int. Conf. Robotics and Automation (IEEE, San Francisco, USA, 2000), pp. 473–479. Crossref, Google Scholar
14. Y. Li et al., PQ-RRT^∗: An improved path planning algorithm for mobile robots, J. Expert Syst. Appl. 152 (2020) 1–11. Crossref, Google Scholar
15. R. Mashayekhi et al., Informed RRT^∗-connect: An asymptotically optimal single-query path planning method, J. IEEE Access. 8 (2020) 19842–19852. Crossref, Google Scholar
16. I. Noreen, A. Khan and Z. Habib, Optimal path planning using RRT based approaches: A survey and future directions, J. Int. J. Adv. Comput. Sci. Appl. 7(11) (2016) 97–107. Google Scholar
17. S. Karaman and E. Frazzoli, Sampling-based algorithms for optimal motion planning, J. Int. J. Robot. Res. 30(7) (2011) 846–894. Crossref, Google Scholar
18. C. Li et al., Complete coverage path planning for an Arnold system based mobile robot to perform specific types of missions, J. Front. Inf. Technol. Electron. Eng. 20(11) (2019) 1530–1542. Crossref, Google Scholar