一种改进搜索的A-star算法

针对移动机器人在大规模复杂环境中规划速度慢、计算量大等问题,提出一种改进A-star路径规划算法。引入双向跨节点搜索机制,从原始起点和终点开始,分别以对向当前节点作为目标点进行搜索,优化寻路方向并缩减搜索节点数量;改进遇到障碍物时的搜索方法引入跳变概念,当扩展节点处于障碍物内时该节点认作无效节点,发生跳变,从无效节点处向垂直于无效节点扩展方向的两个方向搜索,直至搜索至非障碍物区,使快速脱离障碍物区域;改进节点评价方法采用分段评价方式,正常扩展阶段将扩展节点加入open表,并对open表中节点评价,当发生跳变时将跳变节点加入jump表并清空open表,然后对jump中节点表进行评价,该操作使得评价节点始终保持在一定数量,减少不必要节点的计算,节约内存占用,使得搜索效率不会因为扩展节点增多而降低。算法有效性在Matlab中仿真实现,通过对比不同算法在不同障碍物栅格地图中的仿真结果,论文改进算法计算节点更少,效率更高。