AI lecture seires - Vadim Bulitko - Dynamic Control in Real-Time Heuristic Search

The AI Lecture Series welcomes everyone to the following talk this Wednesday (September 3), 11:00-12:00 in room K5, Kringlan:

"Dynamic Control in Real-Time Heuristic Search"

Vadim Bulitko, University of Alberta

Abstract:

Real-time heuristic search is a challenging type of agent-centered search because the agent's planning time per action is bounded by a constant independent of problem size. A common problem that imposes such restrictions is pathfinding in modern computer games where a large number of units must plan their paths simultaneously over large maps. Common search algorithm (e.g., A*, IDA*, D*, ARA*,AD*) are inherently not real-time and may lose completeness when a constant bound is imposed on per-action planning time. Real-time search algorithms retain completeness but frequently produce unacceptably suboptimal solutions. In this paper, we extend classic and modern real-time search algorithms with an automated mechanism for dynamic depth and subgoal selection. The new algorithms remain real- time and complete. On large computer game maps, they find paths within 7% of optimal while on average expanding roughly a single state per action. This is nearly a three-fold improvement in suboptimality over the existing state-of-the-art algorithms and, at the same time, a 15- fold improvement in the amount of planning per action.

Short bio:

Vadim Bulitko is an associate professor at the Department of Computing Science at University of Alberta, Canada. He received his Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign in 1999. His interests are in strong Artificial Intelligence, creativity and cognition. Vadim's primary contributions are in the area of real-time heuristic search. He has also worked in emotion and culture modeling in virtual trainers, player modeling for adaptive story telling in role-playing video games, enemy prediction in tactical first-person shooters, hiding and seeking spatial patterns in human behavior and other areas. In doing so, Vadim has collaborated with Bioware Corp., Reykjavik University, Queensland University of Technology, Canadian Forestry Service, Syncrude Research and other institutions. He co-chaired an IJCAI'05 workshop on decision-making in uncertain environments, was a workshop and tutorial chair for ICML'06 and is a co-chair of the SARA'09 international symposium. In his free time Vadim enjoys photography, painting and sketching, hiking, martial arts, jogging, writing poetry, reading philosophy and playing video games.  He is spending this fall term at Reykjavik University as a part of his sabbatical.