Canonical Ordering Tree Adaptive A*

Agents, such as robots and video game characters, have to be able to navigate from a given start location to a known goal location in initially unknown or partially known terrains. These agents are usually able to sense obstacles around them. Under the free-space assumption, the agent assumes the entire terrain is traversable except the blocked areas. The agent's knowledge may change and the current plan will be invalid. Therefore, re-planning is needed. A common approach is that the agent repeatedly searches and finds the cost-minimal path from its location to the goal location and follows the path until it reaches the goal location. These searches need to be fast otherwise the agent cannot move smoothly. Incremental heuristic search algorithms use previous and current searches to solve future similar search problems faster than heuristic search algorithms that solve the individual search problems in isolation such as Repeated A*. We propose Canonical Ordering Tree Adaptive A* algorithm which is one of the incremental heuristic search algorithms in the context of goal-directed navigation in unknown terrain represented by grids.