Abstract:
A fundamental requirement for realizing scalable and responsive real-world multi-robot systems for time-sensitive critical applications such as search and rescue or building clearance is a motion-planning and coordination framework that exhibits three essential properties. The first property is safety that encompasses aspects relating to kinodynamic feasibility and collision-avoidance. The second property is reliability that relates to the successful handling of multi-robot motion planning queries in a wide variety of uncertain three-dimensional workspaces with varying topologies and spatiotemporal characteristics, varying team sizes, and inter-robot communication constraints. Finally, the third property is decentralized operation that seeks to leverage onboard planning and inter-robot communication in order to safely navigate the robots towards their respective goals. This thesis aims to develop such a safe, reliable, and decentralized motion-planning and coordination framework in order to enable navigation of multi-robot teams in uncertain 3D workspaces.

To this end, in the first part of the thesis, we first introduce a planning representation and a centralized decoupled search algorithm for kinodynamic multi-robot motion planning in known and static two-dimensional workspaces. The representation, by virtue of invariance, allows for offline preprocessing and abstraction of kinodynamic feasibility evaluations and collision-checking into fast lookup operations thus enabling online planning for large teams of robots. We then extend the planning framework to known and static three-dimensional workspaces and incorporate optimizations that exploit the invariant nature of the planning representation to improve scalability.

In the second part of the thesis, we relax the static workspace assumption and introduce stochastic dynamic obstacles into the problem formulation. To handle the presence of these dynamic obstacles, we propose an efficient collision-avoidance methodology, extend the planning framework to a decentralized formulation and, via simulation, show safe operation in various dynamic workspaces. We then address the primary limitations of myopic decentralized planning methods, i.e., increased likelihood of deadlocks with an increase in the density of robots or workspace clutter, by proposing a hierarchical local planner composed of deliberative and reactive components. The advantages of the proposed hierarchical local planner over state-of-the-art decentralized frameworks are shown via various simulation studies. Finally, we demonstrate that the proposed algorithms in this thesis enables efficient multi-robot navigation in cluttered and dynamic 3D workspaces, exhibiting needed planning capabilities to enable multi-robot deployments for complex applications such as search and rescue and building clearance.

More Information

Thesis Committee Members:
Nathan Michael, Chair
Maxim Likhachev
George Kantor
Sanjiban Choudhury, Aurora Innovation