In the communication-constrained operating environment, a unmanned aerial vehicle (UAV) needs to plan a feasible path from the starting point to the endpoint while planning the node deployment location for multi-hop communication to establish an information pathway. In this study, a new algorithm was designed for joint path and multi-hop communication node location planning in cluttered environments based on rapidly-exploring random trees star (RRT*) algorithm. The maximum communication distance constraint between nodes was obtained based on the signal-free propagation model, whereas the communication node loss and path loss were established as joint optimization objectives. In bidirectional random tree growth, the structure of the trees was optimized according to the value of the loss function, and optimal path and node location planning were finally achieved through continuous growth and iteration. When tested in different complexity-barrier environments and compared to RRT*, Informed-RRT*, and IB-RRT* algorithms, the paths in the planning results of the new algorithm are close to those of the comparison algorithms; however, the number of nodes decreases significantly, which proves the effectiveness of the newly proposed algorithm.

1. [1] T. Wang et al., “Time and energy efficient data collection via UAV,” Science China Information Sciences, Vol.65, No.8, Article No.182302, 2022. https://doi.org/10.1007/s11432-021-3343-7
2. [2] Q. Song et al., “A survey of prototype and experiment for UAV communications,” Science China Information Sciences, Vol.64, No.4, Article No.140301, 2021. https://doi.org/10.1007/s11432-020-3030-2
3. [3] J. Delmerico et al., “The current state and future outlook of rescue robotics,” J. of Field Robotics, Vol.36, No.7, pp. 1171-1191, 2019. https://doi.org/10.1002/rob.21887
4. [4] N. Michael et al., “Collaborative mapping of an earthquake-damaged building via ground and aerial robots,” J. of Field Robotics, Vol.29, No.5, pp. 832-841, 2012. https://doi.org/10.1002/rob.21436
5. [5] C. Shen et al., “Collaborative air-ground target searching in complex environments,” 2017 IEEE Int. Symp. on Safety, Security and Rescue Robotics (SSRR), pp. 230-237, 2017. https://doi.org/10.1109/SSRR.2017.8088168
6. [6] K. Kannadasan et al., “M-Curves path planning model for mobile anchor node and localization of sensor nodes using Dolphin Swarm Algorithm,” Wireless Networks, Vol.26, No.4, pp. 2769-2783, 2020. https://doi.org/10.1007/s11276-019-02032-4
7. [7] C. Cadena et al., “Past, present, and future of simultaneous localization and mapping: Toward the robust-perception age,” IEEE Trans. on Robotics, Vol.32, No.6, pp. 1309-1332, 2016. https://doi.org/10.1109/TRO.2016.2624754
8. [8] E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, Vol.1, No.1, pp. 269-271, 1959. https://doi.org/10.1007/BF01386390
9. [9] P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Trans. on Systems Science and Cybernetics, Vol.4, No.2, pp. 100-107, 1968. https://doi.org/10.1109/TSSC.1968.300136
10. [10] J. Lovinger and X. Zhang, “Enhanced Simplified Memory-Bounded A Star (SMA*+),” C. Benzmüller, C. Lisetti, and M. Theobald (Eds.), “GCAI 2017. 3rd Global Conference on Artificial Intelligence,” pp. 202-212, EasyChair, 2017. https://doi.org/10.29007/v7zc
11. [11] D. Ferguson and A. Stentz, “Field D*: An interpolation-based path planner and replanner,” S. Thrun, R. Brooks, and H. Durrant-Whyte (Eds.), “Robotics Research: Results of the 12th International Symposium ISRR,” pp. 239-253, Springer, 2007. https://doi.org/10.1007/978-3-540-48113-3_22
12. [12] A. Nash et al., “Theta*: Any-angle path planning on grids,” Proc. of the 22nd AAAI Conf. on Artificial Intelligence (AAAI’07), pp. 1177-1183, 2007.
13. [13] A. Nash, S. Koenig, and M. Likhachev, “Incremental Phi*: Incremental any-angle path planning on grids,” Int. Joint Conf. on Artificial Intelligence (IJCAI), pp. 1824-1830, 2009.
14. [14] A. Nash, S. Koenig, and C. Tovey, “Lazy Theta*: Any-angle path planning and path length analysis in 3D,” Proc. of the AAAI Conf. on Artificial Intelligence, Vol.24, No.1, pp. 147-154, 2010. https://doi.org/10.1609/aaai.v24i1.7566
15. [15] D. Dolgov et al., “Path planning for autonomous vehicles in unknown semi-structured environments,” The Int. J. of Robotics Research, Vol.29, No.5, pp. 485-501, 2010. https://doi.org/10.1177/0278364909359210
16. [16] L. E. Kavraki et al., “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. on Robotics and Automation, Vol.12, No.4, pp. 566-580, 1996. https://doi.org/10.1109/70.508439
17. [17] R. Bohlin and L. E. Kavraki, “Path planning using lazy PRM,” Proc. 2000 IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 521-528, 2000. https://doi.org/10.1109/ROBOT.2000.844107
18. [18] A. Dobson and K. E. Bekris, “Improving sparse roadmap spanners,” 2013 IEEE Int. Conf. on Robotics and Automation, pp. 4106-4111, 2013. https://doi.org/10.1109/ICRA.2013.6631156
19. [19] S. M. LaValle, “Rapidly-exploring random trees: A new tool for path planning,” No.TR 98-11, Iowa State University, 1998.
20. [20] S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” The Int. J. of Robotics Research, Vol.30, No.7, pp. 846-894, 2011. https://doi.org/10.1177/0278364911406761
21. [21] J. D. Gammell, S. S. Srinivasa, and T. D. Barfoot, “Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic,” 2014 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 2997-3004, 2014. https://doi.org/10.1109/IROS.2014.6942976
22. [22] M. Otte and E. Frazzoli, “RRT^X: Asymptotically optimal single-query sampling-based motion planning with quick replanning,” The Int. J. of Robotics Research, Vol.35, No.7, pp. 797-822, 2016. https://doi.org/10.1177/0278364915594679
23. [23] A. H. Qureshi and Y. Ayaz, “Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments,” Robotics and Autonomous Systems, Vol.68, pp. 1-11, 2015. https://doi.org/10.1016/j.robot.2015.02.007
24. [24] S. Karaman and E. Frazzoli, “Optimal kinodynamic motion planning using incremental sampling-based methods,” 49th IEEE Conf. on Decision and Control (CDC), pp. 7681-7687, 2010. https://doi.org/10.1109/CDC.2010.5717430
25. [25] D. J. Webb and J. van den Berg, “Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics,” 2013 IEEE Int. Conf. on Robotics and Automation, pp. 5054-5061, 2013. https://doi.org/10.1109/ICRA.2013.6631299
26. [26] S. Choudhury et al., “Regionally accelerated batch informed trees (RABIT*): A framework to integrate local information into optimal path planning,” 2016 IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 4207-4214, 2016. https://doi.org/10.1109/ICRA.2016.7487615
27. [27] T. S. Rappaport, “Wireless communications: Principles and practice,” Prentice Hall, 1996.
28. [28] R. Bridson, “Fast Poisson disk sampling in arbitrary dimensions,” ACM SIGGRAPH 2007 Sketches (SIGGRAPH’07), 2007. https://doi.org/10.1145/1278780.1278807