Path Planning for Groups using Column Generation
Files
Publication date
2010
Authors
van den Akker, Marjan
Geraerts, R.J.
Hoogeveen, Han
Prins, C.
Editors
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
Abstract
In computer games, one or more groups of units need 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 -hard. In current games, these problems are solved by using greedy ad hoc rules, leading to long traversal times or congestions and deadlocks near narrow passages. We present a centralized optimization approach based on Integer Linear Programming. Our solution provides an efficient heuristic to minimize the average and latest arrival time of the units.
Keywords
Theoretical Computer Science, General Computer Science
Citation
van den Akker, J M, Geraerts, R J, Hoogeveen, J A & Prins, C 2010, Path Planning for Groups using Column Generation. in Motion in Games - Third International Conference, MIG 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6459 LNCS, Springer, pp. 94-105, 3rd International Conference on Motion in Games, MIG 2010, Utrecht, Netherlands, 14/11/10. https://doi.org/10.1007/978-3-642-16958-8_10, conference