Multiple robot coordination: A mathematical programming approach

This thesis focuses on the optimal coordination of multiple robot systems with dynamics along specified paths using mathematical programming. These multiple robot coordination problems are motivated by wide applications, including automated guided vehicle coordination in industries, droplet coordination in digital microfluidic systems, and manipulator coordination in car assembly lines. Previous work on optimal coordination of robots either ignored robot dynamics or focused almost exclusively on dual robot systems.; Initially we assume that each robot's path is specified. We first develop a mixed integer nonlinear program (MINLP) model for coordinating multiple robots with double integrator dynamics. We demonstrate the convexity and differentiability of the nonlinear constraints in this MINLP and provide several global optimality conditions for multiple robot coordination with dynamics. We then develop two mixed integer linear program (MILP) models to approximate the MINLP model. In addition, we find the computational complexity and show a shortest path structure and a network flow structure for multiple robot coordination. To coordinate multiple manipulators with given initial trajectories, we exploit the time-scaling law to build MILP and MINLP models that uniformly scale the trajectories, minimize the system cost, satisfy complex manipulator dynamics, and avoid collisions. In addition, we develop a mixed integer conic program (MICP) model that is guaranteed to find the globally optimal design for time-scaled planar manipulator systems. We demonstrate our approaches for multiple robot coordination with extensive implementation results.; Computing collision zones and detecting collisions are crucial for coordinating multiple robots. The last topic of the thesis is concerned with collision detection and proximity queries for objects represented as superconics, which are a generalization of convex superellipsoids. We design an efficient algorithm for computing the minimum distance between two superconics using second order cone programs.