Research Paper:
Joint Path and Multi-Hop Communication Node Location Planning in Cluttered Environment
Lihua Li*, Zhihong Peng*,, Chengxin Wen*, Peiqiao Shang*, and Jinqiang Cui**
*School of Automation, Beijing Institute of Technology
5 South Street, Zhongguancun, Haidian District, Beijing 100081, China
Corresponding author
**Department of Mathematics and Theories, Peng Cheng Laboratory
2 Xingke 1st Street, Nanshan, Shenzhen 518055, China
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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] S. M. LaValle, “Rapidly-exploring random trees: A new tool for path planning,” No.TR 98-11, Iowa State University, 1998.
- [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] 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] M. Otte and E. Frazzoli, “RRTX: 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] 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] 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] 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] 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] T. S. Rappaport, “Wireless communications: Principles and practice,” Prentice Hall, 1996.
- [28] R. Bridson, “Fast Poisson disk sampling in arbitrary dimensions,” ACM SIGGRAPH 2007 Sketches (SIGGRAPH’07), 2007. https://doi.org/10.1145/1278780.1278807
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.