Distributed submodular maximization on partition matroids for planning on large sensor networks

Abstract

Many problems that are relevant to sensor networks such as active sensing and coverage planning have objectives that exhibit diminishing returns and specifically are submodular. When each agent selects an action local space of actions, sequential maximization techniques for submodular function maximization obtain solutions within half of optimal even though such problems are often NP-Hard. However, adapting methods for submodular function maximization to distributed computation on sensor networks is challenging as sequential execution of planning steps is time-consuming and inefficient. Further, prior works have found that planners suffer severely impaired worst-case performance whenever large numbers of agents plan in parallel. This work develops new tools for analysis of submodular maximization problems which we apply to design of randomized distributed planners that provide constant-factor suboptimality approaching that of standard sequential planners. These bounds apply when the objective satisfies a higher-order monotonicity condition and when cumulative interactions between agents are proportional to the optimal objective value. Problems including generalizations of sensor coverage satisfy these conditions when agents have spatially local sensing actions and limited sensor range. We present simulation results for two such cases.