D*算法：机器人探索与路径规划的优化策略

4星 · 超过85%的资源需积分: 19 165 浏览量更新于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 Efﬁcient 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, sacriﬁcing optimality or computational efﬁciency

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 ﬁeld 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 ﬁnd the lowest cost

path from the robot’s start state to the goal state. Cost can

be deﬁned 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 efﬁciently 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页未读，立即下载

darwen2008

粉丝: 0
资源: 11

D*算法：机器人探索与路径规划的优化策略

D星路径搜索算法

A*和D*算法源代码(c文件)

ompl一些示例

matlab多机器人路径规划

基于D*与动态窗口法的动态路径规划

点对点的路径规划算法

matlab内置哪些路径规划算法

如何用MATLAB进行路径规划

谈一谈传统路径规划算法的研究现状

实时避障的路径规划算法有哪些

最新资源

A和D算法源代码(c文件)