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

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

Michels, Andor (TU Delft Electrical Engineering, Mathematics and Computer Science)

Mulderij, J. (mentor)
de Weerdt, M.M. (mentor)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2020-06-22

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.

Multi-Agent Pathfinding
Branch-Price-and-Cut
Integer Linear Programming

http://resolver.tudelft.nl/uuid:d3deaccc-db8b-4fe0-8328-faaf4fa6b598

Student theses

bachelor thesis

© 2020 Andor Michels