Incremental Phi*: Incremental Any-Angle Path Planning on Grids

July 2009

Incremental Phi*: Incremental Any-Angle Path Planning on Grids

Authors:

Alex Nash, Sven Koenig, and Maxim Likhachev

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.

Notes:

@conference{Nash-2009-109721,
author = {Alex Nash And Sven Koenig And Maxim Likhachev},
title = {Incremental Phi*: Incremental Any-Angle Path Planning on Grids},
booktitle = {Proceedings of 21st International Joint Conference on Artificial Intelligence (IJCAI '09)},
year = {2009},
month = {July},
pages = {1824 - 1830},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.