Abstract:
Teams of aerial sensing robots can provide valuable situational awareness to first responders during disasters and emergencies by locating victims, mapping environments, identifying hazards, and locating gas sources. While individual sensing tasks may feature a variety of goals, many tasks will be time-sensitive such as after a widespread disaster or due to imminent danger of a fire and involve operation in unknown and cluttered environments due to recent changes and lack of information. When the environment is unknown, the subset that is safe to traverse as well as the distribution of information sources are revealed incrementally as robots move through the environment. Consequently, robots must adapt and replan often in response to new information. Because these tasks are time-sensitive robots should also operate rapidly both individually and collectively. To address these challenges, this thesis will demonstrate that near-optimal distributed sensor planning over receding horizons is possible for arbitrary numbers of robots and can improve completion times in relevant time-sensitive sensing tasks.

Deployments of large numbers of robots must contend with close proximity between robots and overlapping sensor ranges. Existing techniques can extend single-robot sensor planners to multi-robot settings and provide guarantees for teams in terms of performance of individual robots. However, planning times generally scale at least linearly with the number of robots which conflicts with the desire to replan rapidly. This impedes performance for large teams of robots and limits applications in time-sensitive domains.

We describe two algorithms that seek to mitigate these challenges. The first is a heuristic variation on existing sequential algorithms that takes advantage of parallel computation and approaches existing guarantees in practice. We apply this algorithm in a multi-robot exploration task with a team of aerial robots. The second is similar and obtains constant-factor performance with a constant number of sequential steps that is independent of the number of robots for spatially local sensor coverage objectives.

We propose three further contributions: extension of the analysis of the second planning approach to other sensing tasks such as for localizing targets and inspecting objects; implementation and evaluation of the proposed planning approach in a distributed setting with constrained communication and receding-horizon planning; and development and evaluation of a planning system for time-sensitive sensing tasks.

More Information

Thesis Committee Members:
Nathan Michael, Chair
Anupam Gupta
Katia Sycara
Mac Schwager, Stanford University