Efficient Navigation in Dynamic Multi-Agent Environments

Intelligent terrain navigation is one of the more fundamental AI problems that the game industry faces. In typical computer-game worlds tens or hundreds of human and computer controlled agents are simultaneously navigating and interacting with each other in a dynamically changing environment. Although path-finding is a well-studied problem in computer science, existing methods generally assume a single moving agent, a static known world, and/or non-real-time response requirements. Unfortunately, none of these assumptions hold in complex game worlds.

The main objective of this research project is to develop more efficient algorithms for real-time terrain navigation in large dynamic environments with multiple moving agents. The immediate focus will be on applications to commercial computer games, although such techniques may also prove useful in other domains that require real-time decisions making using limited computing and memory resources.