<div class="csl-bib-body">
<div class="csl-entry">Deligkas, A., Eiben, E., Ganian, R., Kanj, I., & Ramanujan, M. S. (2025). Parameterized Algorithms for Multiagent Pathfinding on Trees. In <i>AAMAS ’25 : Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems</i> (pp. 584–592). International Foundation for Autonomous Agents and Multiagent Systems. https://doi.org/10.5555/3709347.3743574</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/220013
-
dc.description.abstract
The classical Multiagent Pathfinding problem has been extensively studied not only within the artificial intelligence research community, but also by scholars in the areas of theoretical computer science and computational geometry. The problem asks for a minimum-makespan schedule that routes k agents (or robots) from their starting points to their destinations in a graph, while avoiding collisions, and is known to be NP-hard even on the fundamental class of trees. In this article we present two fixed parameter algorithms parameterized by k: the first yields a collision-free schedule on trees whose makespan deviates from the optimum by at most an additive polynomial function of k, and the second solves Multiagent Pathfinding optimally on the class of irreducible trees, i.e., trees with no vertices of degree 2. Both results rely on novel tools and insights into the properties of optimal schedules.
en
dc.language.iso
en
-
dc.relation.ispartofseries
AAMAS
-
dc.subject
Multiagent Pathfinding
en
dc.subject
Trees
en
dc.subject
Parameterized Complexity
en
dc.title
Parameterized Algorithms for Multiagent Pathfinding on Trees
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.affiliation
Royal Holloway University of London, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.contributor.affiliation
Royal Holloway University of London, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.contributor.affiliation
DePaul University, United States of America (the)
-
dc.contributor.affiliation
University of Warwick, United Kingdom of Great Britain and Northern Ireland (the)
-
dc.relation.isbn
979-8-4007-1426-9
-
dc.description.startpage
584
-
dc.description.endpage
592
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
AAMAS '25 : Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems
-
tuw.peerreviewed
true
-
tuw.book.ispartofseries
AAMAS
-
tuw.relation.publisher
International Foundation for Autonomous Agents and Multiagent Systems
-
tuw.relation.publisherplace
Richland, SC, USA
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publication.orgunit
E056-13 - Fachbereich LogiCS
-
tuw.publisher.doi
10.5555/3709347.3743574
-
dc.description.numberOfPages
9
-
tuw.author.orcid
0000-0003-2628-3435
-
tuw.author.orcid
0000-0002-7762-8045
-
tuw.author.orcid
0000-0003-1698-8829
-
tuw.author.orcid
0000-0002-2116-6048
-
tuw.event.name
AAMAS '25: 24th International Conference on Autonomous Agents and Multiagent Systems
en
tuw.event.startdate
19-05-2025
-
tuw.event.enddate
23-05-2025
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Detroit, MI
-
tuw.event.country
US
-
tuw.event.presenter
Deligkas, Argyrios
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.languageiso639-1
en
-
item.grantfulltext
none
-
item.openairetype
conference paper
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.cerifentitytype
Publications
-
item.fulltext
no Fulltext
-
crisitem.author.dept
Royal Holloway University of London, United Kingdom of Great Britain and Northern Ireland (the)
-
crisitem.author.dept
TU Wien
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
DePaul University, United States of America (the)
-
crisitem.author.dept
University of Warwick Science Park, United Kingdom of Great Britain and Northern Ireland (the)