Time-optimal Coordination of Mobile Robots along Specified Paths

In this paper, we address the problem of time-optimal coordination of mobile robots under kinodynamic constraints along specified paths. We propose a novel approach based on time discretization that leads to a mixed-integer linear programming (MILP) formulation. This problem can be solved using gene...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-04
Main Authors: Altché, Florent, Qian, Xiangjun, Arnaud de La Fortelle
Format: Article
Language:English
Subjects:
Computer simulation
Constraint modelling
Discretization
Integer programming
Linear programming
Robots
Solvers
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we address the problem of time-optimal coordination of mobile robots under kinodynamic constraints along specified paths. We propose a novel approach based on time discretization that leads to a mixed-integer linear programming (MILP) formulation. This problem can be solved using general-purpose MILP solvers in a reasonable time, resulting in a resolution-optimal solution. Moreover, unlike previous work found in the literature, our formulation allows an exact linear modeling (up to the discretization resolution) of second-order dynamic constraints. Extensive simulations are performed to demonstrate the effectiveness of our approach.
ISSN:2331-8422
DOI:10.48550/arxiv.1603.04610