M.Sc Thesis

M.Sc StudentRevach Guy
SubjectPlanning for Cooperative Multiple Agents with Sparse
DepartmentDepartment of Electrical and Computer Engineering
Supervisor PROF. Nahum Shimkin
Full Thesis textFull thesis text - English Version


We consider the problem of planning for cooperative multiple agents in a deterministic world, and under a finite time horizon.

In a fully cooperative multi-agent system, all agents share a common goal, where the

decision making of an individual agent depends on the actions of the other agents. The main aspect in such systems is coordination; i.e., the process ensuring that the individual decisions of the agents result in jointly optimal decisions for the group. Planning in this case is a hard search and optimization problem in terms of computational complexity. Since there is growing interest in this problem both in theory and practice, there is need for an efficient mechanism for coordinating the agents' actions.

We present a model that aims to partially decouple the agents in the group using the

notation of soft cooperation constraints.  We consider a group of agents that are subject to a set of soft cooperation constraints, where each constraint is associated with a context and a discounted cost. A constraint may be chosen to be satisfied by a designated affecting agent, in which case the discounted cost is applied to the context for a designated affected agent. By minimizing the joint additive total cost for the group, agents are driven to cooperative behavior only in case of need. This model explicitly couples only the affecting and affected agents that are subject to the same cooperation constraint and forming dependency only in a specific context.

Our model is followed by a two-step, dynamic programming-based planning algorithm, which decouples a K multi-agent problem to K independent single-agent problems, such that the aggregation of the single-agent plans is optimal for the group.

The algorithm is both complete and optimal, and efficient in cases when the interactions among agents are sparse.

In step one, each agent plans independently, and computes its response function to the associated constraints. Step two is a centralized global plan merging, in which an optimal assignment is found under the minimum-sum objective. A factor graph, which captures dependencies among cooperative agents and utilizes the internal structure of the problem, is applied to the problem with a variable elimination algorithm for efficient min-sum optimization.

Analysis shows that the overall algorithm is linear in the number of agents, polynomial in the span of the time horizon, and dependent on the number of interactions among agents. For this particular multi-agent setup, it is robust for different sizes of graphs and numbers of agents when compared to a standard solution.