  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.
