Path Planning with D*Lite: Implementation and Adaption of the D*Lite Algorithm

PDF

Authors
  1. Mackay, D.
Corporate Authors
Defence R&D Canada - Suffield, Ralston ALTA (CAN)
Abstract
Incremental search methods reuse information from previous searches to find solutions to a series of similar tasks much faster than is possible by solving each search task from scratch. Heuristic search methods, such as A*, use task-specific information in the form of approximations of goal distances to focus the search and typically solve search problems much faster than uninformed search methods. In LPA*, incremental and heuristic search were combined to further reduce replanning times. D*Lite is an application of a modified LPA* to the goal-directed robot navigation task in unknown terrain. Conventional graph search methods, such as repeated applications of A*, could be used when replanning paths after discovering previously unknown obstacles; however, resulting planning times could be prohibitively long. D* uses a clever heuristic to speed up replanning by one or two orders of magnitude over repeated A* searches by modifying previous search results locally. D*Lite, building on LPA*, implements the same navigation strategy as D*, but is algorithmically different. It is an attractive alternative to D* which is simpler to understand, implement, and debug. It involves only a single tie-breaking criterion when comparing priorities and does not need the nested if statements with complex conditions required in D*. Furthermore, D*Lite has been demonstrated to be at least as efficient as D*. In this paper, an implementation of D*Lite is described and its performance is compared wi

Il y a un résumé en français ici.

Keywords
path planning;navigation;Autonomous navigation;Obstacle avoidance
Report Number
DRDC-SUFFIELD-TM-2005-242 — Technical Memorandum
Date of publication
01 Dec 2005
Number of Pages
42
DSTKIM No
CA026915
CANDIS No
524912
Format(s):
CD ROM

Permanent link

Document 1 of 1

Date modified: