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

You are here: Homepage > Search

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

Free access

DIEGO DEPLANO / MAURO FRANCESCHELLI / SIMON WARE / SU RONG / ALESSANDRO GIUA

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.

Access

Download

Export, share and cite

Document information

Title :

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

Contributors:

DIEGO DEPLANO (author) / MAURO FRANCESCHELLI (author) / SIMON WARE (author) / SU RONG (author) / ALESSANDRO GIUA (author) / Deplano, Diego / Franceschelli, Mauro / Ware, Simon / Rong, Su / Giua, Alessandro

Publication date :

2020-01-01

DOI :

https://doi.org/10.1109/ACCESS.2020.2994472

Type of media :

Article (Journal)

Type of material :

Electronic Resource

Language :

English

Keywords :

discrete event system , heuristic solution , MILP problem , multi-robot path-planning , optimal solution , optimization , scheduling