---
title: "Incremental Phi*: Incremental Any-Angle Path Planning on Grids"
authors:
  - "Alex Nash"
  - "Sven Koenig"
  - "Maxim Likhachev"
doi: ""
url: "https://ijcai.org/proceedings/2009/303"
pdf: "https://ijcai.org/proceedings/2009/0303.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "1824-1829"
track: ""
keywords:
---

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

Alex Nash, Sven Koenig, Maxim Likhachev

*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