Truncated Incremental Search: Faster Replanning by Exploiting Suboptimality - Robotics Institute Carnegie Mellon University

Truncated Incremental Search: Faster Replanning by Exploiting Suboptimality

Sandip Aine and Maxim Likhachev
Conference Paper, Proceedings of 27th AAAI Conference on Artificial Intelligence (AAAI '13), pp. 16 - 24, July, 2013

Abstract

Incremental heuristic searches try to reuse their previous search efforts whenever these are available. As a result, they can often solve a sequence of similar planning problems much faster than planning from scratch. State-of-the-art incremental heuristic searches such as LPA*, D* and D* Lite all work by propagating cost changes to all the states on the search tree whose gvalues (the costs of computed paths from the start) are no longer optimal. While such a complete propagation of cost changes is required to ensure optimality, the propagations can be stopped much earlier if we are looking for solutions within a given suboptimality bound. We present a framework called Truncated Incremental Search that builds on this observation, and uses a target suboptimality bound to efficiently restrict the cost propagations. Using this framework, we develop two algorithms, Truncated LPA* (TLPA*) and Truncated D* Lite (TD* Lite). We discuss their analytical properties and present experimental results for 2D and 3D (x, y, heading) path planning that show significant improvement in runtime over existing incremental heuristic searches when searching for close-to-optimal solutions. In addition, unlike typical incremental searches, Truncated Incremental Search is much less dependent on the proximity of the cost changes to the goal of the search due to the early termination of the cost change propagation.

BibTeX

@conference{Aine-2013-109541,
author = {Sandip Aine and Maxim Likhachev},
title = {Truncated Incremental Search: Faster Replanning by Exploiting Suboptimality},
booktitle = {Proceedings of 27th AAAI Conference on Artificial Intelligence (AAAI '13)},
year = {2013},
month = {July},
pages = {16 - 24},
}