In this paper we consider the problem of collision avoidance among robots that follow pre-planned trajectories in a structured environment while minimizing the maximum traveling time among them. More precisely, we consider a discrete event formulation of this problem. Robots are modeled by automata, the environment is partitioned into a square grid where cells represent free space, obstacles and walls, which are modeled as shared resources among robots. The main contribution of this paper is twofold. First, we propose a problem formulation based on mixed integer linear programming to compute an optimal schedule for the pre-planned trajectories. Second, we propose a heuristic method to compute a sub-optimal schedule: the computational complexity of this approach is shown to be polynomial with the number of robots and the dimension of the environment. Finally, simulations are provided to validate performance and scalability of the proposed approach.

A Discrete Event Formulation for Multi-Robot Collision Avoidance on Pre-Planned Trajectories

DIEGO DEPLANO;MAURO FRANCESCHELLI;ALESSANDRO GIUA
2020-01-01

Abstract

In this paper we consider the problem of collision avoidance among robots that follow pre-planned trajectories in a structured environment while minimizing the maximum traveling time among them. More precisely, we consider a discrete event formulation of this problem. Robots are modeled by automata, the environment is partitioned into a square grid where cells represent free space, obstacles and walls, which are modeled as shared resources among robots. The main contribution of this paper is twofold. First, we propose a problem formulation based on mixed integer linear programming to compute an optimal schedule for the pre-planned trajectories. Second, we propose a heuristic method to compute a sub-optimal schedule: the computational complexity of this approach is shown to be polynomial with the number of robots and the dimension of the environment. Finally, simulations are provided to validate performance and scalability of the proposed approach.
2020
discrete event systems; heuristic solution; MILP problem; multi-robot path-planning; optimal solution; optimization; scheduling
File in questo prodotto:
File Dimensione Formato  
Deplano et al_ A Discrete Event Formulation for Multi-Robot Collision Avoidance on Pre-Planned Trajectories_2020.pdf

accesso aperto

Descrizione: articolo
Tipologia: versione editoriale
Dimensione 922.04 kB
Formato Adobe PDF
922.04 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/294637
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
social impact