Submodular Optimization for Risk-aware Coordination of Multi-robot Systems

Download or read book Submodular Optimization for Risk-aware Coordination of Multi-robot Systems written by Stefan Jorgensen and published by . This book was released on 2018 with total page pages. Available in PDF, EPUB and Kindle. Book excerpt: Robots are often designed for dangerous environments such as severe storms, but routing algorithms rarely are. This dissertation introduces a new class of routing problems with ``risky traversal'' where a robot may fail when travelling between two sites. Our key insight is that many objectives in the risky traversal model satisfy a diminishing returns property known as submodularity. We develop a set of tools based on submodular optimization which lead to efficient solutions for a wide variety of problems: 1. The "Team Surviving Orienteers" (TSO) problem, where the size of the team is fixed and we seek routes which maximize the expected rewards collected at nodes, subject to survival probability constraints on each robot. 2. The "On-line TSO" problem, where observations are incorporated to update the paths on-line in a parallel fashion (in response to survival events). 3. The "Heterogeneous TSO" problem, which allows robots to have different capabilities such as sensors (affecting rewards collected), actuation (affecting ability to traverse between sites), and robustness (affecting survival probabilities). 4. The "Matroid TSO" problem, where the set of routes must satisfy an `independence' constraint represented by a matroid, for example limits on the number of each type of robot available, traffic through regions of the environment, total risk budgets for the team, or combinations of these limits. 5. The "Risk Sensitive Coverage" problem, which is the dual to the TSO where the team must satisfy a coverage constraint (e.g., ensure that nodes are visited with specified probabilities) while using minimum resources (e.g., number of robots deployed, distance travelled, or expected number of failures). Our algorithms are based on the approximate greedy algorithm, where we iteratively select a path which approximately maximizes the expected incremental rewards subject to some constraints. Due to the submodular structure of the problems considered in this dissertation, we can prove bounds on the suboptimality of our algorithms. The approach developed in this dissertation provides a foundational set of tools for routing large scale teams in dangerous environments while explicitly planning for robot failure.