A multi-scale path-planning method for large-scale scenes based on a framed scale-elastic grid map

References

• Bailey ,James, Craig Tovey, Tansel Uras, Sven Koenig, and Alex Nash. 2015. “Path Planning on Grids: The Effect of Vertex Placement on Path Length.” Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 11 (1): 108–114. https://doi.org/10.1609/aiide.v11i1.12808.
   Google Scholar
• Chen, Jinchao, Chenglie Du, Ying Zhang, Pengcheng Han, and Wei Wei. 2021. “A Clustering-Based Coverage Path Planning Method for Autonomous Heterogeneous UAVs.” IEEE Transactions on Intelligent Transportation Systems 23 (12): 25546–25556. https://doi.org/10.1109/TITS.2021.3066240.
   Web of Science ®Google Scholar
• Chen, Jianhua, Xu Liu, Bingqian Wang, and Jian Lu. 2023. “A Clipping Algorithm for Real-Scene 3D Models.” International Journal of Digital Earth 16 (1): 464–485. https://doi.org/10.1080/17538947.2022.2159079.
   Web of Science ®Google Scholar
• Chen, D. Z., R. J. Szczerba, and J. J. Uhran. 1995. “Planning Conditional Shortest Paths through an Unknown Environment: A Framed-Quadtree Approach.” Proceedings 1995 IEEE/RSJ International Conference on Intelligent Robots and Systems. Human Robot Interaction and Cooperative Robots 3: 33–38.
   Google Scholar
• Chen, D. Z., R. J. Szczerba, and J. J. Uhran. 1997. “A Framed-Quadtree Approach for Determining Euclidean Shortest Paths in a 2-D Environment.” IEEE Transactions on Robotics and Automation 13 (5): 668–681. https://doi.org/10.1109/70.631228.
   Google Scholar
• Cormen, T. H., C. E. Leiserson, R. L. Rivest, and Clifford Stein. 2022. Introduction to Algorithms. Cambridge, MA, USA: MIT Press.
   Google Scholar
• Daniel, K., A. Nash, S. Koenig, and A. Felner. 2010. “Theta*: Any-Angle Path Planning on Grids.” Journal of Artificial Intelligence Research 39 (October): 533–579. https://doi.org/10.1613/jair.2994.
   Google Scholar
• Gibb, Robert G., Matthew B.J. Purss, Zoheir Sabeur, Peter Strobl, and Tengteng Qu. 2022. “Global Reference Grids for Big Earth Data.” Big Earth Data 6 (3): 251–255. https://doi.org/10.1080/20964471.2022.2113037.
   Google Scholar
• Han, Bing, Tengteng Qu, Xiaochong Tong, Jie Jiang, Sisi Zlatanova, Haipeng Wang, and Chengqi Cheng. 2022. “Grid-Optimized UAV Indoor Path Planning Algorithms in a Complex Environment.” International Journal of Applied Earth Observation and Geoinformation 111:102857. https://doi.org/10.1016/j.jag.2022.102857.
   Web of Science ®Google Scholar
• Harabor, Daniel Damir, Alban Grastien, Dindar Öz, and Vural Aksakalli. 2016. “Optimal Any-Angle Pathfinding in Practice.” Journal of Artificial Intelligence Research 56:89–118. https://doi.org/10.1613/jair.5007.
   Google Scholar
• Hauer, Florian, Abhijit Kundu, James M. Rehg, and Panagiotis Tsiotras. 2015. “Multi-Scale Perception and Path Planning on Probabilistic Obstacle Maps.” 2015 IEEE International Conference on Robotics and Automation (ICRA), 4210–4215.
   Google Scholar
• Hormazábal, Nicolás, Antonio Díaz, Carlos Hernández, and Jorge Baier. 2021. “Fast and Almost Optimal Any-Angle Pathfinding Using the 2k Neighborhoods.” Proceedings of the International Symposium on Combinatorial Search 8 (1): 139–143. https://doi.org/10.1609/socs.v8i1.18442.
   Google Scholar
• ISO 19170-4. 2023. Geographic Information – Discrete Global Grid Systems Specifications – Part 4: Axis-Aligned DGGS RS. https://committee.iso.org/sites/tc211/home/projects/projects—complete-list/iso-19170-4.html.
   Google Scholar
• Ivanov, Rosen. 2018. “An Algorithm for On-the-Fly K Shortest Paths Finding in Multi-Storey Buildings Using a Hierarchical Topology Model.” International Journal of Geographical Information Science 32 (12): 2362–2385. https://doi.org/10.1080/13658816.2018.1510126.
   Web of Science ®Google Scholar
• Jordan, S., J. Moore, S. Hovet, J. Box, J. Perry, K. Kirsche, D. Lewis, and Z. T. H. Tse. 2018. “State-of-the-art technologies for UAV inspections.” IET Radar, Sonar & Navigation 12 (2): 151–164. https://doi.org/10.1049/iet-rsn.2017.0251.
   Google Scholar
• Lei, Yi, Xiaochong Tong, Tengteng Qu, Chunping Qiu, Dali Wang, Yuekun Sun, and Jiayi Tang. 2022. “A Scale-Elastic Discrete Grid Structure for Voxel-Based Modeling and Management of 3D Data.” International Journal of Applied Earth Observation and Geoinformation 113:103009. https://doi.org/10.1016/j.jag.2022.103009.
   Google Scholar
• Li, Y., W. Zhao, and Z. Zhou. 2014. “An Accelerated Method for Multiscale Path Planning.” Information and Control 43 (2): 211–216. https://doi.org/10.3724/SP.J.1219.2014.00211.
   Google Scholar
• Liu, Tao, Ruiqi Shen, Zhengling Lei, Yuchi Huo, Jiansen Zhao, and Xiaogang Xu. 2022. “Wind Resistance Aerial Path Planning for Efficient Reconstruction of Offshore Ship.” International Journal of Digital Earth 15 (1): 1881–1904. https://doi.org/10.1080/17538947.2022.2140852.
   Web of Science ®Google Scholar
• Namdari, M. H., S. R. Hejazi, and M. Palhang. 2016. “Cornered Quadtrees/Octrees and Multiple Gateways Between Each Two Nodes; A Structure for Path Planning in 2D and 3D Environments.” 3D Research 7 (2): 1–18. https://doi.org/10.1007/s13319-016-0092-9.
   Google Scholar
• Nelson, Erik, Micah Corah, and Nathan Michael. 2018. “Environment Model Adaptation for Mobile Robot Exploration.” Autonomous Robots 42 (2): 257–272. https://doi.org/10.1007/s10514-017-9669-2.
   Google Scholar
• Pai, D. K., and L.-M. Reissell. 1998. “Multiresolution Rough Terrain Motion Planning.” IEEE Transactions on Robotics and Automation 14 (1): 19–33. https://doi.org/10.1109/70.660835.
   Google Scholar
• Pun-Cheng, L. S. C., M. Y. F. Tang, and I. K. L. Cheung. 2007. “Exact Cell Decomposition on Base Map Features for Optimal Path Finding.” International Journal of Geographical Information Science 21 (2): 175–185. https://doi.org/10.1080/13658810600852206.
   Web of Science ®Google Scholar
• Quan, Lun, Luxin Han, Boyu Zhou, Shaojie Shen, and Fei Gao. 2020. “Survey of UAV Motion Planning.” IET Cyber-Systems and Robotics 2 (1): 14–21. https://doi.org/10.1049/iet-csr.2020.0004.
   Google Scholar
• Radmanesh, Mohammadreza, Manish Kumar, Paul H. Guentert, and Mohammad Sarim. 2018. “Overview of Path-Planning and Obstacle Avoidance Algorithms for UAVs: A Comparative Study.” Unmanned Systems 06 (02): 95–118. https://doi.org/10.1142/S2301385018400022.
   Google Scholar
• Rivera, Nicolás, Carlos Hernández, Nicolás Hormazábal, and Jorge A. Baier. 2020. “The 2^k Neighborhoods for Grid Path Planning.” Journal of Artificial Intelligence Research 67:81–113. https://doi.org/10.1613/jair.1.11383.
   Web of Science ®Google Scholar
• Sun, Yuekun, He Li, Xiaochong Tong, Yi Lei, Dali Wang, Congzhou Guo, Jiayi Tang, and Yanfa Shang. 2023. “A Multi-Unmanned Aerial Vehicle Fast Path-Planning Method Based on Non-Rigid Hierarchical Discrete Grid Voxel Environment Modeling.” International Journal of Applied Earth Observation and Geoinformation 116:103139. https://doi.org/10.1016/j.jag.2022.103139.
   Google Scholar
• Szczerba, Robert J., Danny Z. Chen, and John J. Uhran. 1998. “Planning Shortest Paths among 2D and 3D Weighted Regions Using Framed-Subspaces.” The International Journal of Robotics Research 17 (5): 531–546. https://doi.org/10.1177/027836499801700505.
   Google Scholar
• Tanzmeister, Georg, Martin Friedl, Dirk Wollherr, and Martin Buss. 2014. “Efficient Evaluation of Collisions and Costs on Grid Maps for Autonomous Vehicle Motion Planning.” IEEE Transactions on Intelligent Transportation Systems 15 (5): 2249–2260. https://doi.org/10.1109/TITS.2014.2313562.
   Google Scholar
• Tsatcha, Dieudonné, Éric Saux, and Christophe Claramunt. 2014. “A Bidirectional Path-Finding Algorithm and Data Structure for Maritime Routing.” International Journal of Geographical Information Science 28 (7): 1355–1377. https://doi.org/10.1080/13658816.2014.887087.
   Web of Science ®Google Scholar
• Tsouros, Dimosthenis C., Bibi Stamatia, and Panagiotis G. Sarigiannidis. 2019. “A Review on UAV-Based Applications for Precision Agriculture.” Information 10 (11): 349. https://doi.org/10.3390/info10110349.
   Google Scholar
• Wang, Wenxin, Bin Jiang, Jian Yang, and Chao Li. 2021. “Research on UAV Application in Mountain Anti-Terrorism Combat.” Journal of Physics: Conference Series 1792 (1): 012079. https://doi.org/10.1088/1742-6596/1792/1/012079.
   Google Scholar
• Xie, Ronglei, Zhijun Meng, Lifeng Wang, Haochen Li, Kaipeng Wang, and Zhe Wu. 2021. “Unmanned Aerial Vehicle Path Planning Algorithm Based on Deep Reinforcement Learning in Large-Scale and Dynamic Environments.” IEEE Access 9:24884–24900. https://doi.org/10.1109/ACCESS.2021.3057485.
   Web of Science ®Google Scholar
• Xu, Minrui, Jiajie Xu, Rui Zhou, Jianxin Li, Kai Zheng, Pengpeng Zhao, and Chengfei Liu. 2023. “Empowering A* Algorithm with Neuralized Variational Heuristics for Fastest Route Recommendation.” IEEE Transactions on Knowledge and Data Engineering 35 (10): 10011–10023. https://doi.org/10.1109/TKDE.2023.3269084.
   Google Scholar
• Yan, Jinjin, Sisi Zlatanova, and Abdoulaye Diakité. 2021. “A Unified 3D Space-Based Navigation Model for Seamless Navigation in Indoor and Outdoor.” International Journal of Digital Earth 14 (8): 985–1003. https://doi.org/10.1080/17538947.2021.1913522.
   Web of Science ®Google Scholar
• Yoon, Sangyol, Sung-Eui Yoon, Unghui Lee, and David Hyunchul Shim. 2015. “Recursive Path Planning Using Reduced States for Car-Like Vehicles on Grid Maps.” IEEE Transactions on Intelligent Transportation Systems 16 (5): 2797–2813. https://doi.org/10.1109/TITS.2015.2422991.
   Web of Science ®Google Scholar
• Zhang, Songyi, Zhiqiang Jian, Xiaodong Deng, Shitao Chen, Zhixiong Nan, and Nanning Zheng. 2022. “Hierarchical Motion Planning for Autonomous Driving in Large-Scale Complex Scenarios.” IEEE Transactions on Intelligent Transportation Systems 23 (8): 13291–13305. https://doi.org/10.1109/TITS.2021.3123327.
   Google Scholar
• Zhang, Han-Ye, Wei-Ming Lin, and Ai-Xia Chen. 2018. “Path Planning for the Mobile Robot: A Review.” Symmetry 10:450. https://doi.org/10.3390/sym10100450.
   Google Scholar