When: Monday, May 05, 3:15 p.m.

Where: 1109Newell-Simon Hall

Geoffrey A. Hollinger

Thesis Proposal

Abstract:
In many real-world applications, a team of robots must locate a moving target. Prior work has explored limited instances of these problems, but these techniques scale poorly to large teams and complex environments. This proposal examines multi-robot search in the physical world. This includes three variations of robotic search: efficient search, guaranteed search, and constrained search. During efficient search, robots move to optimize the average-case performance of the search. In guaranteed search, robots coordinate in such a way to provide worst-case guarantees on search time. Finally, during constrained search, the team must consider secondary requirements such as maintaining communication range or a chain topology.

This thesis demonstrates that algorithms using implicit coordination can provide scalable solutions to these multi-robot search problems. Robotic searchers can implicitly coordinate by sharing information without explicitly planning the actions of their teammates. Avoiding explicit coordination directly leads to algorithms scalable to large teams and complex environments. This thesis presents a linearly scalable efficient search algorithm using implicit coordination and derives near-optimality bounds on its performance. Noisy measurements are incorporated into the algorithm to assist robots during search. Performance is verified both in simulation and using data from ultra-wideband ranging radios.

Implicit coordination algorithms can be augmented with a shared pre-preprocessing step to improve performance in difficult search instances. If robots agree to modify their environment representation before search, tightly coordinated search tasks can be simplified to require only implicit coordination. This thesis demonstrates a novel algorithm utilizing pre-search spanning tree generation that solves the guaranteed search problem. The algorithm is the first anytime algorithm for guaranteed search that improves its performance with increasing runtime. The speed at which this technique generates a feasible search path makes it well-suited for search in complex, physical environments.

Proposed work extends search algorithms utilizing implicit coordination to take into account team constraints, limited communication bandwidth, and dynamic environments. The complete framework will enable large teams of autonomous robots to successfully search large physical environments outside the scope of previous techniques in the literature.

Thesis Committee Members:
Sanjiv Singh, Chair
Geoff Gordon
Reid Simmons
Athanasios Kehagias, Aristotle University of Thessaloniki

<< Back