Adapting CBM to optimize the Sum of Costs

Title

Adapting CBM to optimize the Sum of Costs

 Author

Baauw, Robbin (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Intelligent Systems)

Contributor

Mulderij, J. (mentor)
de Weerdt, M.M. (mentor) ORCID 0000-0002-0470-6241
Zuniga, Marco (graduation committee) ORCID 0000-0003-3544-9169

 Degree granting institution

Delft University of Technology

 Programme

Computer Science and Engineering

 Project

CSE3000 Research Project

 Date

2021-07-01

 Abstract

In the Multi-Agent Pathfinding with Matching (MAPFM) problem, agents from a team are matched with and routed towards one of their team's goals without colliding with other agents. The sum of path costs of all agents is minimized. In prior works, Conflict Based Min-Cost-Flow (CBM) has been proposed. This algorithm solves a similar problem that instead minimizes the maximum path length. In this paper, an extension upon CBM is presented, called CBMxSOC. It consists of several changes to CBM that allow it to minimize the sum of path costs. CBMxSOC is experimentally compared to other MAPFM solvers and is shown to be able to scale to many agents when there are few conflicts between different teams.

 Subject

MAPF
Matching
CBS

 To reference this document use:

http://resolver.tudelft.nl/uuid:e73165e6-d60b-43cc-8abd-c6046f0ab638

 Part of collection

Student theses

 Document type

bachelor thesis

 Rights

© 2021 Robbin Baauw
Files
PDF RobbinBaauw_RP_2021.pdf 501.58 KB
Close viewer