Anytime Truncated D* : Anytime Replanning with Truncation
| Autor: | Sandip Aine, Maxim Likhachev |
|---|---|
| Rok vydání: | 2021 |
| Zdroj: | Proceedings of the International Symposium on Combinatorial Search. 4:2-10 |
| ISSN: | 2832-9163 2832-9171 |
| DOI: | 10.1609/socs.v4i1.18295 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|