Mixed Integer Nonlinear Programming (MINLP) techniques are increasingly used to address challenging problems in robotics, especially Multi-Vehicle Motion Planning (MVMP). The main contribution of this paper is a discrete time-distributed Receding Horizon Mixed Integer Nonlinear Programming (RH-MINLP) formulation of the underwater multi-vehicle path coordination problem with constraints on kinematics, dynamics, collision avoidance, and acoustic communication connectivity, and the application of state-of-the-art MINLP solution techniques. Each vehicle robot starts from a fixed start point and moves toward a goal point along a fixed path, so as to avoid collisions and remain in communication connectivity with other robots. Acoustic communication connectivity constraints account for the attenuation due to signal propagation and delays arising from multi-path propagation in noisy communication environments, and specify inter-vehicle connectivity in terms of a signal-to-noise ratio (SNR) threshold. Scenarios including up to 4 robots are simulated to demonstrate (i) the effect of communication connectivity requirements on robot velocity profiles, and (ii) the dependence of the solution computation time on the communication connectivity requirement. Typically the optimization improved connectivity at no appreciable cost in journey time (as measured by the arrival time of the last-arriving robot). Results also demonstrate the responsive nature of robot trajectories to safety requirements with collision avoidance being achieved at all times despite overlapping and intersecting paths.
Report Number: DFLJOEV1, Drexel University, June, 2013, 3141 Chestnut Street, Philadelphia, PA