Incremental Phi*: Incremental Any-Angle Path Planning on Grids
Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 1824-1829.
Abstract
We study path planning on grids with blocked and unblocked cells. Any-angle path-planning algorithms find short paths fast because they propagate information along grid edges without constraining the resulting paths to grid edges. Incremental path-planning algorithms solve a series of similar path-planning problems faster than repeated single-shot searches because they reuse information from the previous search to speed up the next one. In this paper, we combine these ideas by making the any-angle path-planning algorithm Basic Theta* incremental. This is non-trivial because Basic Theta* does not fit the standard assumption that the parent of a vertex in the search tree must also be its neighbor. We present Incremental Phi* and show experimentally that it can speed up Basic Theta* by about one order of magnitude for path planning with the freespace assumption.Alex Nash, Sven Koenig, Maxim Likhachev
@inproceedings{ijcai2009p303,
title = {Incremental Phi*: Incremental Any-Angle Path Planning on Grids},
author = {Nash, Alex and Koenig, Sven and Likhachev, Maxim},
booktitle = {Proceedings of the Twenty-First International Joint Conference on
Artificial Intelligence, {IJCAI-09}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Hiroaki Kitano},
pages = {1824--1829},
year = {2009},
url = {https://ijcai.org/proceedings/2009/303},
}
TY - CPAPER TI - Incremental Phi*: Incremental Any-Angle Path Planning on Grids AU - Nash, Alex AU - Koenig, Sven AU - Likhachev, Maxim T2 - Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence, IJCAI-09 PB - International Joint Conferences on Artificial Intelligence PY - 2009 SP - 1824 EP - 1829 UR - https://ijcai.org/proceedings/2009/303 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
