Multi-Agent Pathfinding with Matching using Increasing Cost Tree Search

Multi-Agent Pathfinding with Matching using Increasing Cost Tree Search

van der Woude, Thom (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Software Technology)

Mulderij, J. (mentor)
de Weerdt, M.M. (mentor)
Zuniga, Marco (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2021-07-01

Both the assignment problem and the multi-agent pathfinding problem are common problems in the fields of robotics and transportation. The joint problem of multi-agent pathfinding extended with the assignment of goals to agents, matching, is something that has not been studied much; few methods exist today that solve it. In this work, two types of algorithms based on the Increasing Cost Tree Search (ICTS) algorithm for multi-agent pathfinding are presented that can optimally solve this joint problem: exhaustive algorithms that reduce the problem to solving many multi-agent pathfinding problems using regular ICTS, and algorithms that search a generalized increasing cost tree. These are compared to each other experimentally on a set of grid maps, and it is shown that exhaustive methods typically outperform the generalized ICTS. Lastly, an exhaustive ICTS algorithm is compared to alternative algorithms based on other multi-agent pathfinding approaches to put its performance into the broader context of algorithms for multi-agent pathfinding with matching.

Multi-Agent Pathfinding
Matching
Increasing Cost Tree Search
Exhaustive Search
Assignment

http://resolver.tudelft.nl/uuid:6065df0a-51e4-46a3-9727-b0ab68cec8fd

Student theses

bachelor thesis

© 2021 Thom van der Woude