Advances in Path Planning

In this talk, I will give an overview of two of our current research projects on path planning for video games, namely, any-angle path planning and fast replanning for moving-target search.

Any-Angle Path Planning: Grids with blocked and unblocked cells are often used to represent terrain in video games. However, paths formed by grid edges can be sub-optimal and unrealistic looking since the possible headings are artificially constrained. I will present Theta*, a variant of A* that propagates information along grid edges without constraining the paths to grid edges. I will then demonstrate that Theta* is simple, fast and finds short and realistic looking paths.

Fast Replanning for Moving-Target Search: Consider a game character that has to catch a moving target. It does not necessarily know the terrain initially but can observe it within a certain sensor range around itself. It uses the strategy to always move on the shortest presumed unblocked path toward the target, which is a reasonable strategy for video games. I will present MT-Adaptive A*, an incremental variant of A* that updates the heuristics between searches. I will then demonstrate that MT-Adaptive A* is faster than isolated A* searches and, in many situations, also D* Lite, a state-of-the-art incremental variant of A*.

This is joint work with K. Daniel, A. Felner, M. Likhachev, A. Nash and X. Sun.

Speaker Bio

Sven Koenig is an associate professor in computer science at the University of Southern California. Most of his research centers around techniques for decision making (planning and learning) that enable single situated agents (such as robots or decision-support systems) and teams of agents to act intelligently in their environments and exhibit goal-directed behavior in real-time, even if they have only incomplete knowledge of their environment, imperfect abilities to manipulate it, limited or noisy perception or insufficient reasoning speed. Additional information about Sven can be found on his web pages: idm-lab.org.