Steven Okamoto

Allocating Virtual and Physical Flows for Multiagent Teams in Mutable, Networked Environments Degree Type: Ph.D. in Computer Science
Advisor(s): Katia Sycara
Graduated: December 2012

Abstract:

The movement of information, agents, and resources is a crucial part of cooperative multiagent systems: decision makers must receive data in a timely manner to make good decisions, while agents and resources must be provided at appropriate locations for tasks to be completed. Flow allocation meets these conditions by computing paths through the environment, be it the communication network (for data or software agents) or the physical world (for embodied agents or physical resources). This thesis addresses the problem of allocating flows when the environment is mutable, either by the agents or by a malicious adversary.

In this thesis I represent the environment as a graph with agents and tasks represented by source and sink nodes, respectively. The agents are partitioned into groups, and the flows from members of a group must be sent to the same sink, reflecting cases where a task requires multiple agents to work together or a decision requires multiple inputs. Capacity and cost constraints on the graph reflect environmental factors affecting the feasibility and quality of allocations. I prove that even relatively simple problems of allocating flows for groups in graphs are not just hard to solve optimally, but also hard to approximate.

In some cases the agent team can add additional nodes and edges to the graph, for instance by deploying unmanned aerial vehicles (UAVs) as communication relays to supplement a ground-based wireless ad hoc network. I prove that augmenting the network optimally is intractable, and provide algorithms for solving it heuristically.

In other cases an adversary can impair the agents by choosing attacks that increase costs to the agents. Agents must then choose their paths through the network strategically, reasoning not just about the environmental costs but also about the behavior of the adversary. I formalize this interaction as a game between the agent team and the adversary, and provide polynomial time algorithms for computing equilibrium strategies in simultaneous zerosum games, simultaneous non-zero-sum games where each player unilaterally incurs costs to play their strategies, and sequential non-zero-sum games where the sender can commit to a strategy.

Thesis Committee:
Katia Sycara (Chair)
Srinivasan Seshan
Paul Scerri
Milind Tambe (University of Southern California)

Jeannette Wing, Head, Computer Science Department
Randy Bryant, Dean, School of Computer Science

Keywords:
Multiple source network flow, partial centralization, network augmentation, network security game