D*算法：机器人探索与路径规划的优化策略
4星 · 超过85%的资源 需积分: 19 11 浏览量
更新于2024-10-07
收藏 251KB PDF 举报 D*算法是一种经典的机器人路径规划方法，首次在1994年国际机器人与自动化会议（IEEE International Conference on Robotics and Automation）上发表，由Anthony Stentz提出，他当时在卡内基梅隆大学的机器人研究所工作。该算法的设计初衷是为了应对移动机器人在部分未知环境中的路径规划问题，这对于探索性机器人或者那些没有预先获取地形图或布局信息的机器人特别重要，比如火星探测器。
在传统研究中，大部分路径规划假设机器人对环境有完整且精确的认知，一旦开始行动。然而，现实情况下，机器人往往只能逐步了解其周围的环境，这导致了部分未知环境路径规划的挑战。现有的解决方案通常分为两类：一类是基于已知信息规划初始路径，然后随着机器人传感器发现障碍物时局部调整路径，尽管能够应对不确定性，但可能牺牲优化性和计算效率；另一类是完全重新规划路径，虽然保持了最优性，但处理动态变化环境时效率较低。
D*算法的创新之处在于它提供了一种既能保持高效又能确保全局最优的路径规划策略。它能够在未知、部分已知以及不断变化的环境中实现路径规划，这在面对不确定性和环境适应性方面具有显著优势。该算法的核心在于它结合了搜索算法和最佳优先级扩展的思想，通过建立一个增量式的搜索树，不断更新目标节点的最短路径估计，并在每次迭代中优化路径，从而达到在有限时间内找到最优路径的目标。
具体来说，D*算法的运作过程包括以下几个关键步骤：
1. **初始化**：创建一个起点到所有可能目标的启发式搜索图，初始状态下，所有边的长度估计都是无穷大，表示未知区域。
2. **搜索过程**：从起点开始，利用A*或Dijkstra算法进行搜索，每次选择具有最低“估价函数”（即预计到达目标的成本加上通过未知区域的估计成本）的节点进行扩展。
3. **路径改进**：当机器人遇到新的环境信息（如障碍物）时，更新目标节点的最短路径估计，可能需要回溯搜索树并重新计算某些路径。
4. **递归优化**：算法不断优化搜索树，直到找到一条从起点到当前已知目标的最佳路径，即使在未知区域也能保证路径的渐进最优性。
5. **动态适应**：D*算法能适应环境的变化，因为它会根据新的信息实时更新路径规划，使得在未知环境中仍能保证路径的优化。
D*算法以其高效性、优化性和完整性，成为了解决部分未知环境中机器人路径规划问题的重要工具，特别是在火星探测等复杂应用场景中展现出了强大的实用性。
In Proceedings IEEE International Conference on Robotics and Automation, May 1994.
Optimal and Efficient Path Planning for Partially-Known Environments
Anthony Stentz
The Robotics Institute; Carnegie Mellon University; Pittsburgh, PA 15213
Abstract
The task of planning trajectories for a mobile robot has
received considerable attention in the research literature.
Most of the work assumes the robot has a complete and
accurate model of its environment before it begins to
move; less attention has been paid to the problem of
partially known environments. This situation occurs for
an exploratory robot or one that must move to a goal
location without the benefit of a floorplan or terrain map.
Existing approaches plan an initial path based on known
information and then modify the plan locally or replan the
entire path as the robot discovers obstacles with its
sensors, sacrificing optimality or computational efficiency
respectively. This paper introduces a new algorithm, D*,
capable of planning paths in unknown, partially known,
and changing environments in an efficient, optimal, and
complete manner.
1.0 Introduction
The research literature has addressed extensively the
motion planning problem for one or more robots moving
through a field of obstacles to a goal. Most of this work
assumes that the environment is completely known before
the robot begins its traverse (see Latombe [4] for a good
survey). The optimal algorithms in this literature search a
state space (e.g., visibility graph, grid cells) using the dis-
tance transform [2] or heuristics [8] to find the lowest cost
path from the robot’s start state to the goal state. Cost can
be defined to be distance travelled, energy expended, time
exposed to danger, etc.
Unfortunately, the robot may have partial or no
information about the environment before it begins its
traverse but is equipped with a sensor that is capable of
measuring the environment as it moves. One approach to
path planning in this scenario is to generate a “global”
path using the known information and then attempt to
“locally” circumvent obstacles on the route detected by
the sensors [1]. If the route is completely obstructed, a
new global path is planned. Lumelsky [7] initially assumes
the environment to be devoid of obstacles and moves the
robot directly toward the goal. If an obstacle obstructs the
path, the robot moves around the perimeter until the point
on the obstacle nearest the goal is found. The robot then
proceeds to move directly toward the goal again. Pirzadeh
[9] adopts a strategy whereby the robot wanders about the
environment until it discovers the goal. The robot
repeatedly moves to the adjacent location with lowest cost
and increments the cost of a location each time it visits it to
penalize later traverses of the same space. Korf [3] uses
initial map information to estimate the cost to the goal for
each state and efficiently updates it with backtracking costs
as the robot moves through the environment.
While these approaches are complete, they are also
suboptimal in the sense that they do not generate the
lowest cost path given the sensor information as it is
acquired and assuming all known, a priori information is
correct. It is possible to generate optimal behavior by
computing an optimal path from the known map
information, moving the robot along the path until either it
reaches the goal or its sensors detect a discrepancy
between the map and the environment, updating the map,
and then replanning a new optimal path from the robot’s
current location to the goal. Although this brute-force,
replanning approach is optimal, it can be grossly
inefficient, particularly in expansive environments where
the goal is far away and little map information exists.
Zelinsky [15] increases efficiency by using a quad-tree
[13] to represent free and obstacle space, thus reducing the
number of states to search in the planning space. For
natural terrain, however, the map can encode robot
traversability at each location ranging over a continuum,
thus rendering quad-trees inappropriate or suboptimal.
This paper presents a new algorithm for generating
optimal paths for a robot operating with a sensor and a map
of the environment. The map can be complete, empty, or
contain partial information about the environment. For
下载后可阅读完整内容，剩余7页未读，立即下载
4109 浏览量
2024-10-28 上传
2427 浏览量
164 浏览量
1125 浏览量
2021-06-18 上传
