ARA* AD*：机器人动态环境导航算法探索

3星 · 超过75%的资源需积分: 48 174 浏览量更新于2024-09-08 3 收藏 2.72MB PDF 举报

"ARA* AD*室内机器人导航算法研究" 这篇研究主要探讨了ARA*（Anytime A* with Provable Bounds on Sub-Optimality）算法在室内机器人导航中的应用，特别是在处理动态和高维度状态空间的路径规划问题。ARA*算法是一种适应性实时搜索策略，特别适合于那些思考时间有限的规划问题。它能在短时间内找到可行解，并随着可用时间增加逐步优化解决方案，直至达到最优。 1. ARA*算法原理： ARA*是基于A*搜索算法的扩展，A*算法通过结合启发式信息和代价估计来寻找从起点到终点的最优路径。ARA*则更进一步，它能够在有限的时间内调整其性能边界。初始阶段，ARA*使用宽松的边界快速找到次优解，随后随着时间的增加逐渐收紧边界，最终在足够的时间下能够找到一条被证明是全局最优的路径。 2. 实时规划：在现实世界中，机器人的决策时间往往受到限制。任何时间（Anytime）规划器如ARA*能够在快速提供可行解的同时，持续优化路径直到时间结束。这种特性使得ARA*特别适合于动态环境中的导航任务，例如移动机器人在部分已知的室外环境中的路径规划，需要考虑到速度等因素。 3. 效率提升： ARA*的一个关键优势是它能够有效地重用之前的搜索努力，这意味着在优化过程中它比其他任何时间搜索方法都更加高效。通过不断迭代和调整，ARA*可以在不牺牲效率的情况下逐步接近最优解。 4. 应用实验：论文通过模拟的机器人臂动力学问题和室外漫游车的动态路径规划问题，展示了ARA*在实际应用中的有效性。实验结果证实了ARA*不仅在理论上具有优势，而且在实践中也能提供显著的性能提升。总结，ARA* AD*室内机器人导航算法是解决复杂、动态环境中的机器人路径规划问题的有效工具，它兼顾了快速响应和最优路径寻优的需求，尤其适用于时间敏感的室内导航场景。通过理论分析和实验验证，ARA*展示了其在实际应用中的潜力和效率。

ARA*: Anytime A* with Provable Bounds on

Sub-Optimality

Maxim Likhachev, Geoff Gordon and Sebastian Thrun

School of Computer Science

Carnegie Mellon University

Pittsburgh, PA 15213

{maxim+, ggordon, thrun}@cs.cmu.edu

Abstract

In real world planning problems, time for deliberation is often limited.

Anytime planners are well suited for these problems: they ﬁnd a feasi-

ble solution quickly and then continually work on improving it until time

runs out. In this paper we propose an anytime heuristic search, ARA*,

which tunes its performance bound based on available search time. It

starts by ﬁnding a suboptimal solution quickly using a loose bound, then

tightens the bound progressively as time allows. Given enough time it

ﬁnds a provably optimal solution. While improving its bound, ARA*

reuses previous search efforts and, as a result, is signiﬁcantly more efﬁ-

cient than other anytime search methods. In addition to our theoretical

analysis, we demonstrate the practical utility of ARA* with experiments

on a simulated robot kinematic arm and a dynamic path planning prob-

lem for an outdoor rover.

1 Introduction

Optimal search is often infeasible for real world problems, as we are given a limited amount

of time for deliberation and want to ﬁnd the best solution given the time provided. In

these conditions anytime algorithms [9, 2] prove to be useful as they usually ﬁnd a ﬁrst,

possibly highly suboptimal, solution very fast and then continually work on improving

the solution until allocated time expires. Unfortunately, they can rarely provide bounds

on the sub-optimality of their solutions unless the cost of an optimal solution is already

known. Even less often can these algorithms control their sub-optimality. Providing sub-

optimality bounds is valuable, though: it allows one to judge the quality of the current

plan, decide whether to continue or preempt search based on the current sub-optimality, and

evaluate the quality of past planning episodes and allocate time for future planning episodes

accordingly. Control over the sub-optimality bounds helps in adjusting the tradeoff between

computation and plan quality.

A* search with inﬂated heuristics (actual heuristic values are multiplied by an inﬂation

factor  > 1) is sub-optimal but proves to be fast for many domains [1, 5, 8] and also pro-

vides a bound on the sub-optimality, namely, the  by which the heuristic is inﬂated [7].

To construct an anytime algorithm with sub-optimality bounds one could run a succession

of these A* searches with decreasing inﬂation factors. This naive approach results in a se-

ries of solutions, each one with a sub-optimality factor equal to the corresponding inﬂation

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

hechaowei2017

粉丝: 0
资源: 1

ARA* AD*：机器人动态环境导航算法探索

ARA压缩算法库

ara文件修复

ARA*+:Improved path planning algorithm based on ARA

A*算法和ARA*算法的区别

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

java ARA*算法 请写注释

java ARA*算法 请写注释 并实现

ARA*算法：兼顾效率与优化的实时搜索

ARA* java实现

使用Matlab 进行Spectral Factorization：找到问题ara* +cqc* = dd* 的频谱因子多项式d-matlab开发

最新资源

A算法和ARA算法的区别

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

java ARA*算法请写注释

java ARA*算法请写注释并实现