一种基于简化可视图的建图和规划方法

doi:10.19562/j.chinasae.qcgc.2024.07.012

摘要/Abstract

摘要：

当前车辆路径规划大部分是基于栅格地图的规划方法，这种方法在搜索面积较大时计算量也会大幅增加。相比之下，基于可视图的方法能够在路径搜索时减小计算量，但是受到障碍物复杂程度的影响较大。针对这一问题，本文结合SLAM和可视图的方法，提出了一种简化可视图的建图和规划方法。首先使用改进的SLAM算法生成点云地图，并进行动态障碍物的剔除。接着生成可视图，并基于障碍物的大小和顶点处内凹角的大小对可视图中多边形的复杂边缘进行简化，剔除冗余的顶点。最后通过仿真和实车实验证明，该方法相对原有的算法，在保证建图精度的情况下，可视图中多边形的顶点数量减少20%~30%，地图更新时间和整体算法的运行时间减少30%以上。这表明本文方法能够有效减小建图和规划过程的计算量和算法的运行时间。

关键词: 可视图, 路径规划, SLAM, 智能车辆

Abstract:

Most of the current vehicle route planning is based on the grid map planning method， which will greatly increase the amount of calculation when the search area is large. In contrast， the method based on visibility graph can reduce the amount of calculation during path search， but is greatly affected by the complexity of obstacles. For this problem， combining the SLAM and visibility graph methods， a simplified visibility graph construction and planning method is proposed in this paper. Firstly， the improved SLAM algorithm is used to generate point cloud maps， and dynamic obstacles are removed. Then a visibility graph is generated， and the complex edges of polygons in the visibility graph are simplified based on the size of the obstacle and the size of the concave angle at the vertex to eliminate redundant vertices. Finally， through simulation experiments and real vehicle experiments， it is proved that compared with the original algorithm， this method can reduce the number of polygon vertices in the visibility graph by 20%-30% while ensuring the accuracy of mapping. The map update time and the running time of the overall algorithm are also reduced by more than 30%. It shows that the method in this paper can effectively reduce the amount of calculation and the running time of the algorithm in the mapping and planning process.

Key words: visibility graph, path planning, SLAM, intelligent vehicle

范晓临,张旭东,邹渊,尹鑫,刘颖群. 一种基于简化可视图的建图和规划方法[J]. 汽车工程, 2024, 46(7): 1249-1258.

Xiaolin Fan,Xudong Zhang,Yuan Zou,Xin Yin,Yingqun Liu. A Mapping and Planning Method Based on Simplified Visibility Graph[J]. Automotive Engineering, 2024, 46(7): 1249-1258.

图/表 17

图 1

图 2

图 3

图 4

图 5

图 6

图 7

图 8

图 9

图 10

表1

图 11

图 12

图 13

图 14

图 15

表2

参考文献 21

1	陈慧岩，熊光明，龚建伟，等. 无人驾驶汽车概论［M］.北京：北京理工大学出版社，2014.
	CHEN H Y， XIONG G M， GONG J W， et al. Introduction to self-driving car［M］. Beijing： Beijing Institute of Technology Press， 2014.
2	KHATIB O. Real-time obstacle avoidance for manipulators and mobile robots［J］. The International Journal of Robotics Research， 1986， 5（1）： 90-98.
3	LUMELSKY V， STEPANOV A. Dynamic path planning for a mobile automaton with limited information on the environment［J］. IEEE Transactions on Automatic Control， 1986， 31（11）： 1058-1063.
4	COLORNI A， DORIGO M， MANIEZZO V. Distributed optimization by ant colonies［C］. Proceedings of the first European Conference on Artificial Life， 1991： 134-142.
5	BREMERMANN H J. The evolution of intelligence： the nervous system as a model of its environment［M］. University of Washington， Department of Mathematics， 1958.
6	CHAN H， TAM K， LEUNG N. A neural network approach for solving the path planning problem［C］. 1993 IEEE International Symposium on Circuits and Systems （ISCAS）， 1993： 2454-2457.
7	KAVRAKI L E， SVESTKA P， LATOMBE J C， et al. Probabilistic roadmaps for path planning in high-dimensional configuration spaces［J］. IEEE Transactions on Robotics and Automation， 1996， 12（4）： 566-580.
8	LAVALLE S M， KUFFNER J J， DONALD B. Rapidly-exploring random trees： progress and prospects［J］. Algorithmic and Computational Robotics： New Directions， 2001， 5： 293-308.
9	JOHNSON D B. A note on Dijkstra's shortest path algorithm［J］. Journal of the ACM （JACM）， 1973， 20（3）： 385-388.
10	HART P E， NILSSON N J， RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths［J］. IEEE Transactions on Systems Science and Cybernetics， 1968， 4（2）： 100-107.
11	STENTZ A. Optimal and efficient path planning for partially-known environments［C］. Proceedings of the 1994 IEEE International Conference on Robotics and Automation， 1994： 3310-3317.
12	WANG B， LIU Z， LI Q， et al. Mobile robot path planning in dynamic environments through globally guided reinforcement learning［J］. IEEE Robotics and Automation Letters， 2020， 5（4）： 6932-6939.
13	LOZANO-PéREZ T， WESLEY M A. An algorithm for planning collision-free paths among polyhedral obstacles［J］. Communications of the ACM， 1979， 22（10）： 560-570.
14	黎萍，朱军燕，彭芳，等. 基于可视图与A*算法的路径规划［J］. 计算机工程， 2014， 40（3）： 193-195，200.
	LI P， ZHU J Y， PENG F， et al. Path planning based on visibility graph and A* algorithm［J］. Computer Engineering， 2014， 40（3）： 193-195，200.
15	李霜琳，何家皓，敖海跃，等. 基于鸽群优化算法的火星飞行器智能可视图法［J］. 飞行力学， 2020， 38（5）： 90-94.
	LI S L， HE J H， AO H Y， et al. Intelligent visibility graph algorithm of Mars aircraft based on pigeon-inspired optimization［J］. Flight Dynamics， 2020， 38（5）： 90-94.
16	OU J， HONG S H， SONG G， et al. Hybrid path planning based on adaptive visibility graph initialization and edge computing for mobile robots［J］. Engineering Applications of Artificial Intelligence， 2023， 126： 107110.
17	LV T， ZHAO C， BAO J. A global path planning algorithm based on bidirectional SVGA［J］. Journal of Robotics， 2017， 2017.
18	YANG F， CAO C， ZHU H， et al. FAR planner： fast， attemptable route planner using dynamic visibility update［C］. 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS）， 2022： 9-16.
19	LI Q， XIE F， ZHAO J， et al. FPS： fast path planner algorithm based on sparse visibility graph and bidirectional breadth-first search［J］. Remote Sensing， 2022， 14（15）： 3720.
20	SHAN T， ENGLOT B. LeGO-LOAM： lightweight and ground-optimized lidar odometry and mapping on variable terrain［C］. 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS）， 2018： 4758-4765.
21	DOUGLAS D H， PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature［J］. Cartographica： the International Journal for Geographic Information and Geovisualization， 1973， 10（2）： 112-122.

项目	原始程序	本文方法	优化效果
全局地图顶点数量	934	719	23%
平均算法运行时间/ms	10.68	7.02	34%

项目	原始程序	本文方法	优化效果
平均局部地图顶点数量	84.28	51.42	39.9%
全局地图顶点数量	957	675	29.5%
平均地图更新时间/ms	12.04	8.18	32.0%

[1]	陈吉清,车宇翔,田小强,兰凤崇,周云郊. 动态场景下基于3D多目标追踪的实时视觉SLAM方法研究[J]. 汽车工程, 2024, 46(5): 776-783.
[2]	赵树恩,王盛,冷姚. 智能汽车轨迹跟踪多目标显式模型预测控制[J]. 汽车工程, 2024, 46(5): 784-794.
[3]	丁志杰,王亚飞,章翼辰,邬明宇,王亦乐. 基于复合动态采样的自动驾驶矿车节能路径规划方法[J]. 汽车工程, 2024, 46(4): 588-595.
[4]	芦涛,金馨,廖毅霏,黄圣杰,杨依琳,谢国涛,秦晓辉. 基于雅克比域零空间边缘化的视觉SLAM[J]. 汽车工程, 2023, 45(8): 1457-1467.
[5]	胡满江,牟斌杰,杨泽宇,边有钢,秦晓辉,徐彪. 基于DBSCAN与二分法的混合A*路径规划方法[J]. 汽车工程, 2023, 45(3): 341-349.
[6]	胡杰,朱琪,陈锐鹏,张敏超,张志豪,刘昊岩. 引入必经点约束的智能汽车全局路径规划[J]. 汽车工程, 2023, 45(3): 350-360.
[7]	吕彦直,魏超,何元浩. 基于GCN和CIL的端到端自动驾驶换道方法[J]. 汽车工程, 2023, 45(12): 2310-2317.
[8]	任明辉,梁军,陈龙,张春,王云. 基于改进冲突搜索的智能车库多AGV路径规划[J]. 汽车工程, 2023, 45(10): 1933-1943.
[9]	胡杰,朱令磊,陈瑞楠,钟鑫凯,徐文才,张敏超. 狭小车位平行泊车路径规划方法研究[J]. 汽车工程, 2022, 44(7): 1040-1048.
[10]	黄圣杰,胡满江,周云水,殷周平,秦晓辉,边有钢,贾倩倩. 动态场景下基于语义分割与运动一致性约束的车辆视觉SLAM[J]. 汽车工程, 2022, 44(10): 1503-1510.
[11]	高强,陆洲,段晨东,徐婷. 汽车垂直泊车路径规划与路径跟踪研究[J]. 汽车工程, 2021, 43(7): 987-994.
[12]	张志勇,龙凯,杜荣华,黄彩霞. 自动驾驶汽车高速超车轨迹跟踪协调控制[J]. 汽车工程, 2021, 43(7): 995-1004.
[13]	张旭东,徐福康,邹渊,郭宁远,张宇. 融合TangentBug与Dubins曲线的智能轮式车辆局部路径规划算法[J]. 汽车工程, 2021, 43(6): 833-841.
[14]	李彩霞,卢少波,张博涵,吴文娟,陆嘉峰. 基于行人位置预测的人车转向避撞路径规划[J]. 汽车工程, 2021, 43(6): 877-884.
[15]	胡林,周登辉,黄晶,杜荣华,张新. 考虑信号灯和能耗的电动车最优路径规划[J]. 汽车工程, 2021, 43(5): 641-649.