UC Irvine

This dissertation contributes toward distributed strategy selection for networked mobile agents (robots, humans, unmanned aerial vehicles, etc.) for problems where the goal is to maximize the overall utility of the agents. The objective is the design of an infrastructure-free decentralized cooperative decision-making algorithm that can have a robust performance in encountering uncertainties of the system. The main driving application of this work is cooperative strategy selection solutions for tasks such as dynamic area patrolling, persistent monitoring, sensor placement, and area coverage where avoiding action overlaps and maximizing the performance of the agents is challenging. This dissertation work is an effort to design a decentralized strategy selection algorithm relying on the local processing power of the agents and the communication network among them. To address this problem, we tie a utility function to the combined set of decisions made by the team of agents. By showing that the utility function is a monotone increasing and submodular function, we formulate a general utility maximization problem as maximizing a submodular set function subject to partition matroid. We then proceed to propose a suboptimal strategy selection algorithm with known optimality bound. We work in the value oracle model where the only access of the agents to the utility function is through a black box that returns the utility function value and where the agents can communicate over a connected undirected graph and have access only to their own strategy set. Our proposed algorithm is based on a distributed stochastic gradient ascent scheme built on the multilinear-extension of the submodular set function. We use a maximum consensus protocol to minimize the inconsistency of the shared information over the network caused by a delay in the flow of information while solving for the fractional solution of the multilinear extension model. Furthermore, we propose a distributed framework for finding a set solution using the fractional solution. However, our proposed communication protocol informs adversarial elements on the selected strategies by the agents. Our next contribution is to design a distributed algorithm that enables each agent to find a suboptimal policy locally with a guaranteed level of privacy. We base our modified algorithm's privacy preservation characteristic on our proposed stochastic rounding method and tie the level of privacy to a privacy variable. That is, the policy choice of an agent can be determined with at most a certain probability. We also show that there is an interplay between the level of optimality gap and the guaranteed level of privacy.