Download PDFOpen PDF in browser

A New Model for Multi-Robot Path Planning on Graphs with Using Network Flow

EasyChair Preprint 2029

4 pagesDate: November 25, 2019

Abstract

In this study, we address the problem of optimal multi-robot path planning (MPP) on graphs, focusing on the makespan criteria (minimizing the maximum arrival time). We use network flows concept and present an Integer Linear Programming (ILP) approach to solve the problem. In contrast to previous studies that used gadgets to avoid the head-on collision, our model applies some constrains on the edges and vertices instead of using gadgets. These constraints significantly reduce the number of edges and vertices in our designed network compared to the presented networks flow in related studies. More precisely, the number of edges and vertices in our network are
(nT)+(2m-1)T and n(T+1), respectively, where T, m, and n are time-horizon, the number of main graph edges and vertices, respectively. Whereas these numbers in the case of using the gadgets are
5mT + 2nT and n(2T+1) + 2T(n-1).

Keyphrases: Integer Linear Programming, multi-robot path planning, network flows

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@booklet{EasyChair:2029,
  author    = {Samira Kashefi Biroon and Bahram Sadeghi Bigham and Salman Khodayifar},
  title     = {A New Model for Multi-Robot Path Planning on Graphs with Using Network Flow},
  howpublished = {EasyChair Preprint 2029},
  year      = {EasyChair, 2019}}
Download PDFOpen PDF in browser