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 two essential properties. The first property is safety which encompasses aspects relating to kinodynamic feasibility and collision-avoidance. The second property is reliability which relates to the successful handling of multi-robot motion planning queries in a wide variety of uncertain three-dimensional environments with varying topologies and spatiotemporal characteristics, varying team sizes, and inter-robot communication constraints. This thesis aims to develop such a safe and reliable motion-planning and coordination framework in order to enable distributed navigation of multi-robot teams in uncertain 3D workspaces.

To this end, 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. Finally, we extend the planning framework to a decentralized formulation and, via simulation, show safe operation in uncertain dynamic 3D workspaces.

The remainder of the thesis proposes to develop a distributed planning and coordination framework to enable efficient multi-robot navigation in partially known or unknown, and potentially dynamic environments. To this end, we first propose a distributed global planning methodology leveraging incremental construction and sharing of sparse topological graphs over bandwidth constrained communication networks in order to improve navigation efficiency of the multi-robot team over time. Second, we formulate a distributed local coordination methodology for cluttered and dynamic workspaces which balances long term deliberative coordination with short-term reactive planning to enable deadlock free navigation. Finally, we propose to conceptualize, implement, and evaluate a distributed navigation algorithm combining the aforementioned global and local planning methods applied to a building clearance scenario.

More Information

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