ARA*+算法：基于Anytime Repairing A*的改进路径规划算法

需积分: 21 152 浏览量更新于2024-09-14 1 收藏 609KB PDF 举报

ARA*+ 路径规划搜索算法 ARA*+ 路径规划搜索算法是基于 A* 算法的一种改进算法，旨在解决传统 A* 算法在度量地图内搜索路径时的缺陷。传统 A* 算法无法保证机器人的运动连续性，特别是在时间有限的情况下。为了解决这个问题，Anytime Repairing A* (ARA*) 算法被提出，该算法可以快速获取次优解，然后继续改进解直到时间耗尽。然而，ARA* 算法仍然存在一些缺陷，例如在搜索过程中，状态只能被扩展一次，无法重复使用以前的规划结果。为了克服这些缺陷，ARA*+ 算法被提出，该算法 executes 多个加权 A* 搜索以获取解决方案。在第一次搜索中，加权 A* 算法使用较大的膨胀因子，且不允许状态被扩展超过一次，这样可以显著缩短找到次优解的时间。然后，加权 A* 算法将被重新执行，以获取更好的路径，通过减小膨胀因子和重用以前的规划结果。 ARA*+ 算法的优点在于，它可以重用以前的规划结果，减少计算时间和空间的消耗。同时，ARA*+ 算法也可以 guarantee 机器人的运动连续性，提高路径规划的效率和可靠性。在实际应用中，ARA*+ 算法可以广泛应用于机器人领域，例如无人机、自动驾驶汽车、服务机器人等。这些机器人需要在复杂的环境中进行导航和避障，ARA*+ 算法可以提供快速和可靠的路径规划结果。 ARA*+ 路径规划搜索算法是一种高效和可靠的算法，能够解决传统 A* 算法的缺陷，提高机器人的运动连续性和路径规划效率。

ARA*+: Improved path planning algorithm based on ARA*

Bo Li, Jianwei Gong, and Yan Jiang, Hany Nasry, Guangming Xiong

Intelligent Vehicle Research Center

Beijing Institute of Technology

Beijing, China

gongjianwei@bit.edu.cn

Abstract—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 larger 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*+ is smaller than that in

ARA*, as a result, the time required to get the optimal

solution will be shorter.

Keywords-Path planning; Robot; ARA*; ARA*+;A*

I. INTRODUCTION

Path planning of a robot is to calculate a collision-free

path from the start state to the goal state, being satisfied with

some given environmental constraints and the robot’s own

mobility constraints, and a certain performance require-

ments as well [1]. The performance requirements are used to

evaluate the optimality of the solution, for instance, the

shortest path will be considered as the optimal solution if the

cost of the path is the evaluation indicator.

Two widely used path planning methods are

sampling-based algorithm [2] and heuristic search algorithm.

The sampling-based algorithm shows a very high efficiency

in high dimensional space, but it does not have any

optimality guarantees. A recent variation known as

improved randomly exploring randomized tree (RRT*) was

developed that adds an asymptotic optimality guarantee

without changing the computational overhead [3]. On the

other hand, A* [4], a typical heuristic search algorithm, can

significantly reduce the number of expanding states and

ensure the optimality of solutions as well. However, these

advantages will be weakened when the search area is too

large, or the robot moves at a higher speed.

A* can search the optimal solution if the value of

heuristic function from current state to the goal state is less

than the cost of the optimal path. Based on this, we can

come to a conclusion: the larger the value of heuristic

function is, the less the number of expanding states will be.

As a result, the searching efficiency will become higher. If

the value of heuristic function is larger than the cost of the

optimal solution, a feasible path can be searched out quickly,

though the optimality of the solution might not be ensured.

As an improved A*-based algorithm, Weighted A* [5],

which heuristic function, h(s), is multiplied by an inflation

factor ε (ε ≥ 1), can reduce the searching time and expand

less states. Although the optimality of the path has been

sacrificed, a sub-optimal path can be searched out quickly,

whose cost is no larger than ε times that of the optimal path

[6] [7], i.e., Weighted A* can search out a sub-optimal path

quickly. In this way, Weighted A* can solve the problem of

planning failure in limited time. If there is more time left,

Weighted A* will decrease ε and search again for a better

solution until the allocated time expires. However, this

method does not reuse the previous planning efforts and its

efficiency is not very high.

Anytime Weighted A* (AWA*) [8] executes Weighted

A* at the beginning of each iteration and quickly comes to a

sub-optimal solution. If there is more time left, it will keep

improving the result until the optimal solution is obtained or

take the current path as the output when the allocated time

expires. Although previous planning efforts have been

reused, it will expand too many states. Moreover, it will

keep expanding useless states even after the optimal solution

has been searched out.

Anytime Repairing A* (ARA*) [9] executes multiple

Weighted A*, and can effectively reduce the number of

states to be expanded by reusing the previous planning

efforts. ARA* restricts the re-expansion of states when

executing Weighted A* with the current ε, as a result, the

current Weighted A* can search for a feasible solution a bit

quickly. But more states will be expanded during another

search with a lower ε. Hansen [10] has queried the limitation

on expanding times of ARA*. He pointed out that this

method was flawed because it might expand more states

during the next search. Our experimental tests also support

Hansen's argument.

Considering the problems above, we proposed a

variation of ARA* algorithm (ARA*+). The first search of

this algorithm is the same as ARA* that executes Weighted

A* with given ε

to obtain a sub-optimal path quickly, here

no state is expanded more than once. Obviously the cost of

下载后可阅读完整内容，剩余4页未读，立即下载

l36179311

粉丝: 0
资源: 3

ARA+算法：基于Anytime Repairing A的改进路径规划算法

最新资源

ARA*+算法：基于Anytime Repairing A*的改进路径规划算法

ARA压缩算法库

ARA* AD*室内机器人导航算法研究

An Improved KNN Classification Algorithm based on Sampling

An improved collaborative recommendation algorithm based on optimized user similarity

[Practical Exercise] RRT Algorithm Based on MATLAB: UAV Path Planning

msft-yolo: improved yolov5 based on transformer for detecting defects of ste

The Improved Orthogonal Match Pursuit Algorithm Based on Image Characteristics

An improved iterative back projection algorithm based on ringing artifacts suppression

An improved ant colony algorithm for robot path planning.rar

An improved FCM medical image segmentation algorithm based on MMTD

最新资源

ARA+算法：基于Anytime Repairing A的改进路径规划算法