ARA*+: Improved path planning algorithm based on ARA

B Li, J Gong, Y Jiang, H Nasry… - 2012 IEEE/WIC/ACM …, 2012 - ieeexplore.ieee.org
B Li, J Gong, Y Jiang, H Nasry, G Xiong
2012 IEEE/WIC/ACM International Conferences on Web Intelligence …, 2012ieeexplore.ieee.org
A* path planning algorithm cannot always guarantee the continuity of a robot's movements
when the allocated time is limited, however Anytime Repairing A*(ARA*) can get a sub-
optimal solution quickly, and then work on improving the solution until the allocated time
expires. This paper proposes a variation of ARA* algorithm (ARA*+) which executes multiple
Weighted A* to search the solution. During the first search of ARA*+, Weighted A* with a
bigger inflation factor is applied and no state is expanded more than once, in this way, the …
A* path planning algorithm cannot always guarantee the continuity of a robot's movements when the allocated time is limited, however Anytime Repairing A*(ARA*) can get a sub-optimal solution quickly, and then work on improving the solution until the allocated time expires. This paper proposes a variation of ARA* algorithm (ARA*+) which executes multiple Weighted A* to search the solution. During the first search of ARA*+, Weighted A* with a bigger inflation factor is applied and no state is expanded more than once, in this way, the time needed for finding a sub-optimal solution can be remarkably shortened. Then, Weighted A* will be executed again for better path, by decreasing the inflation factor and reusing the previous planning efforts. Here, with the same inflation factor the expanded states can be used again, and this is different from ARA*, which forbids the expanded states to be expanded again. If the allocated time does not expire, this process will not stop until the optimal solution is found, or the current sub-optimal solution will be regarded as the output. According to our robot path planning experiments, in most cases the number of expanded states in ARA*+ was smaller than that in ARA*, as a result, the time spent to get the optimal solution will be shorter.
ieeexplore.ieee.org
以上显示的是最相近的搜索结果。 查看全部搜索结果