ARA*+算法：基于Anytime Repairing A*的改进路径规划算法
需积分: 21 118 浏览量
更新于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 ε
0
to obtain a sub-optimal path quickly, here
no state is expanded more than once. Obviously the cost of
下载后可阅读完整内容，剩余4页未读，立即下载
2018-07-16 上传
2021-02-07 上传
2021-02-07 上传
点击了解资源详情
2023-09-18 上传
2021-02-11 上传
2021-02-09 上传
2021-04-08 上传
l36179311
- 粉丝: 0
- 资源: 3
我的内容管理
展开
最新资源
- JHU荣誉单变量微积分课程教案介绍
- Naruto爱好者必备CLI测试应用
- Android应用显示Ignaz-Taschner-Gymnasium取消课程概览
- ASP学生信息档案管理系统毕业设计及完整源码
- Java商城源码解析：酒店管理系统快速开发指南
- 构建可解析文本框：.NET 3.5中实现文本解析与验证
- Java语言打造任天堂红白机模拟器—nes4j解析
- 基于Hadoop和Hive的网络流量分析工具介绍
- Unity实现帝国象棋：从游戏到复刻
- WordPress文档嵌入插件：无需浏览器插件即可上传和显示文档
- Android开源项目精选：优秀项目篇
- 黑色设计商务酷站模板 - 网站构建新选择
- Rollup插件去除JS文件横幅：横扫许可证头
- AngularDart中Hammock服务的使用与REST API集成
- 开源AVR编程器：高效、低成本的微控制器编程解决方案
- Anya Keller 图片组合的开发部署记录
