Robust communication connectivity for multi-robot path coordination using Mixed Integer Nonlinear Programming: Formulation and feasibility analysis

Mixed Integer Nonlinear Programming (MINLP) techniques are increasingly used to address challenging problems in robotics, especially Multi-Vehicle Motion Planning (MVMP). A particular challenge in using this framework is encoding stochastic phenomena such as communication connectivity in the form of MINLP constraints. The main contribution of this paper is an analytical formulation of communication connectivity constraints using stochastic physical layer communication models. These constraints account for the log-normal channel shadowing in noisy communication environments and specify inter-vehicle connectivity in terms of the outage probability of communication. A method is developed to provably accord robustness to communication failure by specifying an upper bound on the outage probability in terms of the inter-vehicle communication range. Finally, we demonstrate the utility of this formulation in the context of a realistic decentralized Multi-Vehicle Path Coordination (MVPC) scenario in which multiple robotic vehicles travel along predetermined fixed paths and are required to maintain communication connectivity during their transit. Conditions that affect the feasibility of the MVPC problem are formalized. Examples that assist in visualizing these conditions are provided.