Submodular Optimization for Coupled Task Allocation and Intermittent Deployment Problems
This addresses coupled optimization challenges in multi-robot systems for applications like environmental monitoring, though it appears incremental as an extension of submodular methods to coupled problems.
The paper tackles coupled optimization problems in robotics, specifically task allocation and intermittent deployment for environmental monitoring, by proposing a greedy algorithm for submodular maximization with matroid constraints that achieves near-optimal solutions with provable bounds.
In this paper, we demonstrate a formulation for optimizing coupled submodular maximization problems with provable sub-optimality bounds. In robotics applications, it is quite common that optimization problems are coupled with one another and therefore cannot be solved independently. Specifically, we consider two problems coupled if the outcome of the first problem affects the solution of a second problem that operates over a longer time scale. For example, in our motivating problem of environmental monitoring, we posit that multi-robot task allocation will potentially impact environmental dynamics and thus influence the quality of future monitoring, here modeled as a multi-robot intermittent deployment problem. The general theoretical approach for solving this type of coupled problem is demonstrated through this motivating example. Specifically, we propose a method for solving coupled problems modeled by submodular set functions with matroid constraints. A greedy algorithm for solving this class of problem is presented, along with sub-optimality guarantees. Finally, practical optimality ratios are shown through Monte Carlo simulations to demonstrate that the proposed algorithm can generate near-optimal solutions with high efficiency.