Anytime Truncated D*: Anytime Replanning with Truncation - Robotics Institute Carnegie Mellon University

Anytime Truncated D*: Anytime Replanning with Truncation

Sandip Aine and Maxim Likhachev
Conference Paper, Proceedings of 6th International Symposium on Combinatorial Search (SoCS '13), pp. 2 - 10, July, 2013

Abstract

Incremental heuristic searches reuse their previous search efforts to speed up the current search. Anytime search algorithms iteratively tune the solutions based on available search time. Anytime D* (AD*) is an incremental anytime search algorithm that combines these two approaches. AD* uses an inflated heuristic to produce bounded suboptimal solutions and improves the solution by iteratively decreasing the inflation factor. If the environment changes, AD* recomputes a new solution by propagating the new costs. Recently, a different approach to speed up replanning (TLPA*/TD* Lite) was proposed that relies on selective truncation of cost propagations instead of heuristic inflation. In this work, we present an algorithm called Anytime Truncated D* (ATD*) that combines heuristic inflation with truncation in an anytime fashion. We develop truncation rules that can work with an inflated heuristic without violating the completeness/suboptimality guarantees, and show how these rules can be applied in conjunction with heuristic inflation to iteratively refine the replanning solutions with minimal reexpansions. We explain ATD*, discuss its analytical properties and present experimental results for 2D and 3D (x, y, heading) path planning demonstrating its efficacy for anytime replanning.

BibTeX

@conference{Aine-2013-109540,
author = {Sandip Aine and Maxim Likhachev},
title = {Anytime Truncated D*: Anytime Replanning with Truncation},
booktitle = {Proceedings of 6th International Symposium on Combinatorial Search (SoCS '13)},
year = {2013},
month = {July},
pages = {2 - 10},
}