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

EasyChair Preprint 2029

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

@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}}