New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Path Planning for Groups

SpeakerHan Hoogeveen

Co-authorsMarjan van den Akker, Roland Geraerts, and Corien Prins

In computer games groups of characters have to move from one location to another as quickly as possible. If there is only one group, then it can be solved efficiently as a dynamic flow problem. If there are several groups with different origins and destinations, then the problem becomes NP-hard. In current games, these problems are solved by using greedy ad-hoc rules. We present a heuristic solution that is based on ILP techniques.