基于黎曼流形的野外综合地形路径规划方法

doi:10.3778/j.issn.1002-8331.2207-0323

摘要/Abstract

摘要： 在野外综合地形上实现路径规划具有较大的现实意义，它需综合考虑高程、地表覆盖分类、植被密度和风向等多种行进阻力。针对此类多阻力要素下的全局路径规划问题，目前的方案由于欧式距离空间的限制，无法给出此类问题的统一数学表达，使得在各向同性、各向异性阻力并存的情况下，求解系统较为混乱。从黎曼流形的视角来看待大地表面，便可以导出能够反映局部信息的黎曼度量，并导出广义测地距离（综合寻路代价）形成距离空间，从而给出此类问题具备一定的推广性的统一数学表达形式，能够十分贴切地反映野外行进的现实情况与需求。以此为基础，使用改进热方法给出森林火灾逃生路径规划问题的求解，作为野外综合路径规划应用实例。

关键词: 黎曼流形, 测地距离, 路径规划, LiDAR点云

Abstract: It is of great practical significance to realize the path planning on the comprehensive wild terrain. It needs to consider various travel resistances such as elevation, land cover classification, vegetation density and wind direction. For the global path planning problem under such multi-resistance elements, the current solution cannot give a unified mathematical expression for this kind of problem due to the limitation of the Euclidean distance space. This makes the solution system chaotic, especially under the coexistence of isotropic and anisotropic resistances. Viewing the Earth’s surface from the perspective of a Riemannian manifold, the Riemannian metric that reflects local information and the generalized geodesic distance（comprehensive pathfinding cost） that helps form a distance spacecan be derived, thus giving a generalization for such problems. The unified mathematical expression reflects the actual situation and needs of field travelprecisely. Based on this, the improved heat method is used to solve the forest fire escape path planning problem as an application example of path planning on the comprehensive wild terrain.

Key words: Riemannian manifold, geodesic distance, path planning, LiDAR points cloud

王帅, 刘向阳. 基于黎曼流形的野外综合地形路径规划方法[J]. 计算机工程与应用, 2023, 59(7): 92-101.

WANG Shuai, LIU Xiangyang. Path Planning Method for Comprehensive Wild Terrain Based on Riemannian Manifold[J]. Computer Engineering and Applications, 2023, 59(7): 92-101.

参考文献

[1] YAN X P，WANG S W，MA F，et al.A novel path planning approach for smart cargo ships based on anisotropic fast marching[J].Expert Systems with Applications，2020，159：113558.
[2] LI H，XUE Z，CUI K，et al.Diffusion tensor-based fast marching for modeling human brain connectivity network[J].Computerized Medical Imaging and Graphics，2011，35（3）：167-178.
[3] DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerische Mathematik，1959，1（1）：269-271.
[4] KHATIB O.Real-time obstacle avoidance for manipulators and mobile robots[C]//Proceedings of International Conference on Robotics and Automation，1985：500-505.
[5] CRANE K，WEISCHEDEL C，WARDETZKY M.Geodesics in heat：a new approach to computing distance based on heat flow[J].ACM Transactions on Graphics，2013，32（5）：1-11.
[6] SETHIAN J A.Fast-marching level-set methods for three-dimensional photolithography development[C]//Proceedings of International Symposium on Microlithography，1996：262-272.
[7] SETHIAN J A，VLADIMIRSKY A.Ordered upwind methods for static Hamilton-Jacobi equations[J].Proceedings of the National Academy of Sciences，2001，98（20）：11069-11074.
[8] LEE J M.Introduction to riemannianmanifolds[M].Cham：Springer，2018.
[9] HOPF H，RINOW W.On the concept of the complete differential geometric surface[J].The Swiss Mathematician’s Commentaries，1931，3（1）：209-225.
[10] CRANDALL M G，LIONS P L.Two approximations of solutions of Hamilton-Jacobi equations[J].Mathematics of Computation，1984，43：1-19.
[11] CRANDALL M G，ISHII H，LIONS P L.User’s guide to viscosity solutions of second order partial differential equations[J].Bulletin of the American Mathematical Society，1992，27（1）：1-67.
[12] CRANDALL M G，LIONS P L.Viscosity solutions of Hamilton-Jacobi equations[J].Transactions of the American Mathematical Society，1983，277（1）：1-42.
[13] GARRIDO S，ALVAREZ D，MARTIN F，et al.An anisotropic fast marching method applied to path planning for mars rovers[J].IEEE Aerospace and Electronic Systems Magazine，2019，34（7）：6-17.
[14] WANG S，SU W.Hiking path planning algorithm based on dynamic parameters and heuristic information for complex field comprehensive terrain[J].Journal of Physics（Conference Series），2021，1961（1）：012038.
[15] 杨秀红，郭宝龙.基于结构张量的数字图像修复技术研究[D].西安：西安电子科技大学，2014.
YANG X H，GUO B L，Research on digital image restoration technology based on structure tensor[D].Xi’an：Xidian University，2014.
[16] TAN Q，WANG S.Hiking path planning algorithm based on dynamic parameters and anisotropy in field integrated terrain[C]//Proceedings of IEEE International Conference on Advances in Electrical Engineering and Computer Applications（AEECA），August 20-21，2022.
[17] VARADHAN S R S.On the behavior of the fundamental solution of the heat equation with variable coefficients[J].Communications on Pure and Applied Mathematics，1967，20（2）：431-455.
[18] SCHWARZ G.Hodge decomposition—a method for solving boundary value problems[M].Cham：Springer，2006.
[19] PINGEL T J，CLARKE K C，MCBRIDE W A.An improved simple morphological filter for the terrain classification of airborne LIDAR data[J].ISPRS Journal of Photogrammetry and Remote Sensing，2013，77：21-30.
[20] KIM H，ARROWSMITH R，CROSBY C，et al.An efficient implementation of a local binning algorithm for digital elevation model generation of LiDAR/ALSM dataset[C]//Proceedings of AGU Fall Meeting Abstracts，2006.
[21] 余文利，周明全，税午阳，等.基于曲率的点云自动配准方法[J].系统仿真学报，2015，27（10）：2374-2379.
YU W L，ZHOU M Q，SHUI W Y，et al.Automatic point cloud registration method based on curvature[J].Journal of System Simulation，2015，27（10）：2374-2379.