Planning safe motions for multi-robot systems is crucial for deploying them in real-world applications such as target tracking, environmental monitoring, and multi-view cinematography. Traditional approaches mainly solve the multi-robot motion planning problem in a deterministic manner, where the robot states and system models are perfectly known. Practically, however, many sources of uncertainty exist in real-world environments, such as noisy sensor measurements, motion disturbances, and uncertain behaviors of other decision-making agents. Reasoning about these uncertainties is of utmost importance for robust and safe navigation of multi-robot systems. To this end, this thesis aims to develop probabilistic methods for multi-robot motion planning under uncertainty.
The first main contribution of this thesis is a Chance-Constrained Nonlinear Model Predictive Control (CCNMPC) method for probabilistic multi-robot motion planning. Taking into account uncertainties in robot localization, sensing, and motion disturbances, the method explicitly considers the collision probability between each robot and obstacle and formulates a model predictive control problem with chance constraints. A tight upper bound of the collision probability is developed which makes the CCNMPC formulation tractable and solvable in real time. In addition, the CCNMPC is incorporated into multi-robot motion planning using three coordination strategies: a) centralized sequential planning, b) distributed planning in which robots communicate their future planned trajectories, and c) decentralized planning in which robots predict other robots' trajectories using the constant velocity model (CVM). Performances of the three strategies are analyzed and compared.
The CCNMPC method requires robots to know the future trajectories of other robots, either via communication or motion prediction using CVM. However, communication is not always available, and the CVM based motion prediction can lead to collisions among robots, especially in crowded environments. To achieve decentralized and communication-free multi-robot collision avoidance under uncertainty, this thesis then presents a method that relies on the introduced Buffered Uncertainty-Aware Voronoi Cell (B-UAVC). The B-UAVC defines a local safe region for each robot among other robots and obstacles, such that the collision probability between robots and obstacles is below a specified threshold if each robot's motion is constrained to be within its corresponding B-UAVC. An approach to constructing the B-UAVC is proposed, which leverages the techniques of computing a separating hyperplane between two Gaussian distributions and adding buffers for probabilistic collision avoidance. Based on B-UAVC, a set of reactive controllers are designed for single-integrator, double-integrator, and differential-drive robots, respectively; and a receding horizon planner is proposed for general nonlinear dynamical systems.
Instead of directly generating a control action for each robot to move towards its waypoint goal as in the CCNMPC and B-UAVC methods, this thesis further presents a method that can compute a safe control input by minimally modifying a given nominal controller, which may come from a high-level task-oriented planner. The method is decentralized and relies on the Chance-Constrained Safety Barrier Certificates (CC-SBC), which defines a probabilistic safe control space for each robot in a multi-robot system considering robot localization and sensing uncertainties. The CC-SBC chance constraints are reformulated into a set of deterministic quadratic constraints, based on which a quadratically constrained quadratic program (QCQP) can be formulated. By solving the QCQP, the robot can obtain a safe control action thanks to that the CC-SBC guarantees forward invariance of the robot's safety set in a probabilistic manner. Hence, the CC-SBC method can be used as a probabilistic safety filter for multi-robot systems.
While both the B-UAVC and CC-SBC methods are decentralized and communication-free, they typically lead to more conservative robot motions than the CCNMPC method with robots communicating their planner trajectories. The CCNMPC method can also be communication-free by letting each robot predict the other robots' trajectories using the constant velocity model, but it is unsafe in crowded environments. To address the issue, this thesis finally presents a novel trajectory prediction model based on Recurrent Neural Networks (RNN) that can learn multi-robot motion behaviors from demonstrated trajectories generated using a centralized motion planner. By incorporating the learned RNN-based trajectory prediction model within the MPC framework, efficient and communication-free multi-robot motion planning is achieved.
The motion planning methods developed in the thesis have been extensively evaluated and validated in simulations and real-world experiments with a team of quadrotors, showing safe navigation of robots under uncertainty.