一种基于改进可视图构造的路径规划算法

摘要

本发明公开了一种基于改进可视图构造的路径规划算法，该算法在搜索过程借助A*算法向目标点进行扩展，当起点和目标点之间没有障碍物时，可视为两点之间存在可达的可视线，将其添加到A*算法的Open表中，若之间存在障碍物，则根据连线向障碍物顶点进行搜索，将其最近的两个顶点加入拓展表中，直至搜索出一条可行路径。该算法由函数初始化和路径搜索两部分组成，第一步分：在初始化过程中分别记录起点和终点，并将障碍物的可视边考虑到可视图中；第二步分：在对路径进行搜索时从起点向外扩展，构建穿越线，从而完成路径的搜索。本发明有益效果：有效的结合了可视图和A*算法，在地图构建和搜索上效率较高，时间复杂度较小，具有很强的可行性。