Multi-agent pathfinding with waypoints using Branch-Price-and-Cut

Bachelor thesis (2020)

Authors

A.C. Michels Electrical Engineering, Mathematics and Computer Science

Contributors

J. Mulderij Algorithmics - EEMCS (mentor)
M.M. de Weerdt Algorithmics - EEMCS (mentor)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2020 Andor Michels
More Info
expand_more

Published Date

22-06-2020

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

In the multi-agent pathfinding (MAPF) problem, agents have to traverse a graph to a goal location without running into each other. Currently, the Branch-and-Cut-and-Price-MAPF (BCP-MAPF) algorithm is the state-of-the-art algorithm for solving MAPF problems, which uses Branch-Price-and-Cut (BPC) to solve a linear minimization problem. The multi-agent pathfinding with waypoints (MAPFW) problem is a variation on the classical MAPF problem. MAPFW can be useful for e.g. navigating warehouses and scheduling trains. However, little to no research exists on MAPFW. This research proposes two extensions to the BCP-MAPF algorithm to incorporate waypoints and reviews their performance.