Kapadia et al. present a path planning method, mostly oriented to game applications such as non-player characters/autonomous agents, that is based on the anytime dynamic A* (AD*) planner [1]. The main improvements are related to the adoption of hybrid graphs to represent the environment, combining a coarse representation--the so-called “highways,” with few nodes and allowing fast planning--with a detailed representation--a dense graph with detailed triangulation of free spaces, and precise but slower planning. The authors also propose adding constraints that can influence the trajectories, with weights defining a multiplier field (continuous potential fields with attractors/repellants), generated from simple declarative prepositions (for example, In/Not In: Front, Between, LineOfSight). As the planner is based on AD*, it can deal with dynamic constraints and obstacles, interleaving planning with navigation execution. On the other side, as the planner uses constraints and hybrid graphs (with “highways”), the planned path is not guaranteed to be optimal.
The proposed approach improves the well-known path planning AD* algorithm, allowing it to define constraints and using an optimized hybrid representation of the environment, adding some interesting features to the original algorithm. The authors also present practical results that demonstrate the main advantages of their proposed approach.