Motion coordination for large multi-robot teams in obstacle-rich environments

2019-04-29Using multiple robots is important for search-and-rescue, mining, entertainment, and warehouse automation, where robots must operate in constrained, perhaps even maze-like environments frequently. Motion coordination, which plans and executes the movement of robots, is a fundamental building block in such scenarios. Ideally, motion coordination should be capable of coordinating hundreds of robots efficiently even in obstacle-rich environments, of being executed on real physical robots, and of handling unforeseen dynamic changes. ❧ Two components of motion coordination are considered: motion planning and motion execution, both of which are coupled. Motion planning assumes that the environment is known a priori, and produces motion plans with theoretical guarantees such as completeness or optimality. On the other hand, motion execution provides safety guarantees even in the case of unforeseen dynamic changes. In this thesis, we extend the state-of-art in motion planning by providing a planning solution that can plan for hundreds of heterogeneous robots within minutes. We also introduce motion execution frameworks that can be used for robust (with respect to dynamically appearing obstacles, imperfect motion execution, etc.) and persistent execution. ❧ For motion planning, ideas from the artificial intelligence (AI) and robotics communities are combined. AI solvers are capable of computing plans for hundreds of robots in minutes with suboptimality guarantees. However, these solvers' simplified and unrealistic agent model assumptions make it challenging to execute the computed plans safely on real robots. Robotics solutions typically include richer kinodynamic models during planning, but are very slow when many robots and obstacles are taken into account. In this work, we combine the advantages of the two methods by using a two-step approach. First, we use and extend solvers from the AI community to solve a simplified coordination problem. The output is a discrete plan that, in its original form, cannot be executed on a real robot. Second, we apply a computationally efficient post-processing step that creates a smooth continuous plan, taking relevant kinematic constraints into account. ❧ For motion execution, we couple motion planning and traditional motion execution methods by adding a feedback term. In warehouse applications, this feedback term overlaps planning and execution, enabling uninterrupted robot motions. In distributed settings, such a feedback term can be used to avoid livelocks of robots in many cases. ❧ The approaches are demonstrated on different teams of robots, including ground robot teams, UAV teams, and heterogeneous teams