计算机应用研究

作者：王天琦,杨丽英,黄朝雄,何玉庆,

单位：1.中国科学院沈阳自动化研究所机器人学国家重点实验室,沈阳110016；2.中国科学院大学,北京100049；

关键词：Delaunay,路径规划,拓扑地图,图搜索算法,

基金：新疆自治区重点研发计划资助项目(2023B01029-3)；辽宁省科技厅资助项目(2023020427-JH1/104)；中科院青促会优秀会员项目(Y2022065)；；

为解决在大尺寸、复杂环境栅格地图上搜索路径时，存在的搜索时间长和计算资源消耗急剧上升等问题，提出了一种基于计算机几何学的拓扑地图提取方法，并基于图搜索的方法进行路径搜索。首先对地图进行预处理，将障碍物使用多边形表示，并从地图中提取出一组点集；然后将应用点集于Delaunay分割算法从而对地图进行分割，得到一组几何图形集合；之后将障碍物内的几何图形从集合中去除，并将新的集合转换为拓扑地图；最后将拓扑图用于A*的路径搜索算法。利用MATLAB和GAZEBO设置多种仿真环境进行测试，结果表明基于Delaunay分割的拓扑地图的A*算法搜索时间比基于栅格地图的A*算法的搜索时间显著减少，在50×50的地图中减少73.27%，并与其他拓扑地图的研究进行比较。因此，在仿真环境中运用计算机几何学的方法来生成拓扑地图，使用离散的点和不重叠的边来表达空间中的环境信息，可以有效解决A*路径搜索算法在栅格地图中搜索时间长、计算资源消耗多的问题。

来源：2025年第9期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2025年第9期