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

An Improved A-star Search Algorithm

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

In order to solve the problems of slow planning speed and large computation in large-scale complex environment,an improved A-star path planning algorithm is proposed.The two-way cross node search mechanism is introduced.From the original starting point and the end point,the target point to the current node is searched respectively,and the search direction is optimized and the number of search nodes is reduced.The concept of jump is introduced in the improved search method when the obstacle is encountered.When the extended node is in the obstacle,the node is recognized as invalid node,and the jump occurs.It searches from the invalid node to two directions perpendicular to the direction of the invalid node expansion until it is searched to the non ob-stacle area,so as to quickly get rid of the obstacle area.The improved node evaluation method adopts the method of segmented eval-uation.In normal expansion stage,the extended nodes are added to the open table,and the nodes in the open table are evaluated.When the jump occurs,the jump nodes are added to the jump table and the open table is cleared.Then,the node table in the jump is evaluated.This operation keeps the evaluation nodes in a certain amount,reduces the calculation of unnecessary nodes and saves memory consumption,The search efficiency will not be reduced by the increase of extended nodes.The algorithm is simulated in Matlab.By comparing the performance of different algorithms in different grid maps with obstacles,the improved algorithm has few-er nodes and higher efficiency.