Distributed_Submodular_Max

The problem of maximizing the utility of a team of agents with feasible decision sets has gained attention in recent years. Many important problems can be formulated and cast into this framework. Path planning of a team of drones monitoring wildfires to gain maximum information on the fire expansion, route selection of different vehicles to maximize the travel speed, and data selection of different computer centers to train a better artificial intelligence are some of the examples. In this framework, the decision of one agent directly affects the amount of gain other agents can acquire from their own decisions. Hence, to find the best combination of the decisions it is necessary to cross-test all the decision sets of the agents with each other. Therefore, as the number of agents and the size of the decision sets increases the need for computing power to find the optimal solution increases to the verge of not being computable by all the computers on earth. To use the resources efficiently and drop the dependency on a central computer, the distributed solutions depending on the computing power of the agents are of paramount importance. As it becomes impossible to find the optimal combination of the decisions, in this work we offer a fast and decentralized algorithm for finding a suboptimal solution with a guarantee on optimality bound. In our proposed algorithm, at every time step, each agent communicates with its reachable neighboring agents and based on the passed message they update their beliefs on the best decision to make. At the final stage of our algorithm, each agent decides on a decision to make based on the evolved belief over the repeated communication with the neighboring agents. A novelty of our work is that our algorithm offers a robust solution to changes happening in the communication graph where the previous works needed the communication graph to be static. For instance, as the mobile agents move in a field and their reachable neighboring agents change as they travel, our algorithm efficiently deals with these changes.