Abstract:
Disaster relief scenarios require rapid and persistent situational awareness to inform first-responders of safe and viable routes through a constantly shifting environment. Knowing what roads have become flooded or are suddenly obstructed by debris can significantly improve response time and ease the distribution of resources. In a sufficiently large environment, deploying and maintaining fixed camera stands would be ineffective and prohibitively expensive, so we look to deploying teams of robots equipped with sensors to persistently cover the region of interest. In this case, the main challenge is determining how to distribute the robots to cover the entire region with limited travel speed and duration.

Basic multi-robot coverage and exploration methods take a passive approach that direct robots to evenly cover the space and populate a map of the environment with the observations the robots acquire as they move. More reactive frontier-based approaches will continuously guide robots towards unobserved regions until the environment is fully known. These approaches, however, are less effective when the environment changes over time. When the number of robots are limited and can only operate for finite durations, the planner must prioritize which regions to visit in order to provide the most accurate map possible.

In this thesis, we propose to plan deployments of teams of quadrotors equipped with range sensors to cooperatively cover an environment such that a map can be persistently updated as the environment topography evolves. Here, we present a systems-based approach that breaks up planning into stages and computes feasible plans over a sliding-window horizon. These plans are extended over subsequent horizons up to the limit that each robot’s battery capacity will allow, ending with robots returning to home base and recharging. We initially show that the proposed planner is able to outperform greedy frontier assignment in terms of map accuracy and confidence. We then show how the objective function we initially used to distribute robots can be modified to incorporate the ‘goodness-of-fit’ of our environment dynamics model by biasing robots towards regions whose dynamics are less understood. The updated objective results in a system that quickly converges to robots revisiting regions only as often as they are expected to change.

While there is a physical limitation to how much area a team of energy-constrained robots can cover persistently, the system we present leverages an understanding of environment dynamics to maximize model improvement over time in a computationally tractable fashion. This is shown with a comprehensive study of the computational complexity of each component of our system and an evaluation of how overall performance evolves over time relative to the choice of system parameters and environment conditions. We additionally show that the system can be tuned to better address environments experiencing changes of greatly varying magnitudes and scale. The result is a complete system that enables perpetual deployment and efficient distribution of robots throughout the environment to ensure no changes go unobserved for too long.

More Information

Thesis Committee Members:
Nathan Michael, Chair
Katia Sycara
Maxim Likhachev
Stephen L. Smith, University of Waterloo