Path Planning for Groups using Column Generation

J.M. van den Akker; R.J. Geraerts; J.A. Hoogeveen; C. Prins

doi:10.1007/978-3-642-16958-8_10

Path Planning for Groups using Column Generation

J.M. van den Akker, R.J. Geraerts, J.A. Hoogeveen, C. Prins

extern

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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.

Original language	English
Title of host publication	Motion in Games - Third International Conference, MIG 2010, Proceedings
Publisher	Springer
Pages	94-105
Number of pages	12
ISBN (Print)	3642169570, 9783642169571
DOIs	https://doi.org/10.1007/978-3-642-16958-8_10
Publication status	Published - 2010
Event	3rd International Conference on Motion in Games, MIG 2010 - Utrecht, Netherlands Duration: 14 Nov 2010 → 16 Nov 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6459 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd International Conference on Motion in Games, MIG 2010
Country/Territory	Netherlands
City	Utrecht
Period	14/11/10 → 16/11/10

Bibliographical note

Funding Information:
This work was partially supported by the itea2 Metaverse1 (www.metaverse1.org) Project.

Access to Document

10.1007/978-3-642-16958-8_10

MIG2010
Open Access (free)
Final published version, 432 KB

Cite this

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 (pp. 94-105). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6459 LNCS). Springer. https://doi.org/10.1007/978-3-642-16958-8_10

@inproceedings{818496557452473bafa4998fdccdee08,

title = "Path Planning for Groups using Column Generation",

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.",

author = "{van den Akker}, J.M. and R.J. Geraerts and J.A. Hoogeveen and C. Prins",

note = "Funding Information: This work was partially supported by the itea2 Metaverse1 (www.metaverse1.org) Project.; 3rd International Conference on Motion in Games, MIG 2010 ; Conference date: 14-11-2010 Through 16-11-2010",

year = "2010",

doi = "10.1007/978-3-642-16958-8_10",

language = "English",

isbn = "3642169570",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "94--105",

booktitle = "Motion in Games - Third International Conference, MIG 2010, Proceedings",

}

van den Akker, JM , Geraerts, RJ , Hoogeveen, JA & 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

Path Planning for Groups using Column Generation. / van den Akker, J.M.; Geraerts, R.J.; Hoogeveen, J.A. et al.
Motion in Games - Third International Conference, MIG 2010, Proceedings. Springer, 2010. p. 94-105 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6459 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Path Planning for Groups using Column Generation

AU - van den Akker, J.M.

AU - Geraerts, R.J.

AU - Hoogeveen, J.A.

AU - Prins, C.

N1 - Funding Information: This work was partially supported by the itea2 Metaverse1 (www.metaverse1.org) Project.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=78649677084&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-16958-8_10

DO - 10.1007/978-3-642-16958-8_10

M3 - Conference contribution

SN - 3642169570

SN - 9783642169571

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 94

EP - 105

BT - Motion in Games - Third International Conference, MIG 2010, Proceedings

PB - Springer

T2 - 3rd International Conference on Motion in Games, MIG 2010

Y2 - 14 November 2010 through 16 November 2010

ER -

van den Akker JM , Geraerts RJ , Hoogeveen JA, Prins C. Path Planning for Groups using Column Generation. In Motion in Games - Third International Conference, MIG 2010, Proceedings. Springer. 2010. p. 94-105. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-16958-8_10

Path Planning for Groups using Column Generation

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this