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.
国家科技期刊平台
NSTL
万方数据
