Abstract:
In the wake of a natural disaster, locating and extracting victims quickly is critical because mortality rises rapidly after the first forty-eight hours. In order to assist search and rescue teams and improve response times, teams of aerial robots equipped with sensors and cameras can engage in sensing tasks such as mapping buildings, assessing structural integrity, and locating victims. We seek to enable large numbers of robots to cooperate to complete such sensing tasks more quickly and thereby to improve response times for first responders.

When formalized, such sensing tasks encapsulate numerous computationally difficult (at least NP-Hard) problems related to routing, sensor coverage, and decision processes. One way to simplify planning for these tasks is to focus on maximizing sensing performance over a short time horizon. Specifically, consider the problem of how to select motions for a team of robots to maximize a notion of sensing quality (the sensing objective) over the near future, say by maximizing the amount of unknown space in a map that robots will observe over the next several seconds. By repeating this process regularly (about once a second), the robots can react quickly to new observations as they work to complete the sensing task. In technical terms, this planning and control process forms an example of receding-horizon control. Fortunately, common sensing objectives for these problems benefit from well-known monotonicity properties (e.g. submodularity), and greedy algorithms can exploit these monotonicity properties to solve the receding-horizon optimization problems that we study near-optimally.

However, greedy algorithms typically force robots to make decisions sequentially. Thus, planning time grows with the number of robots and eventually exceeds time constraints to replan in real time. This is particularly important in distributed settings as the accumulation of communication latencies between robots in sequence can be significant on its own. Further, recent works that have begun to investigate sequential greedy planning, have demonstrated that reducing the number of sequential steps while retaining suboptimality guarantees can be hard or impossible.

This thesis demonstrates that halting such growth in planning time is possible for many sensing problems. To do so, we introduce new greedy methods, Randomized Sequential Partitioning (RSP) and Range-limited RSP. These methods enable planning with a fixed number of sequential steps that does not grow with the number of robots. Additionally, we prove that our algorithms approach the initial near-optimality guarantees for sequential planning for many sensing problems. In doing so, we develop new methods for quantifying redundancy between potential future observations and highlight the importance of a relatively unknown monotonicity property of some sensing objectives.

We apply our algorithms to autonomous mapping (known as exploration) and target tracking problems which serve as proxies for the variety of tasks and combinations of tasks that may arise in search and rescue scenarios. Simulation results demonstrate that our greedy planners often approach the performance of sequential planning (in terms of target position uncertainty) given only a few planning steps (2-4), even for very large numbers of robots (96). This amounts to a 25x reduction in the number of sequential steps and an equivalent or greater reduction in the duration of distributed planning.

With exploration, we apply our methods in the context of a complex system where robots equipped with depth cameras map unknown, three-dimensional environments such as an office space or a cave. Moreover, the analysis we present when applying our planning methods to mapping objectives also provides valuable insights into the design of such exploration systems. While improving completion times via greedy methods proves challenging, we demonstrate that sequential planning and RSP increase coverage rates early in simulation trials and reliably improve solution quality. Finally, we present a distributed implementation of RSP and simulation results for exploration of an office environment.

More Information

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