The Effects of Cooperation on Multiagent Search in Task-Oriented Domains

This talk summarizes the results that appear in

• José M. Vidal. The effects of cooperation on multiagent search in task-oriented domains. In Proceedings of the Autonomous Agents and Multi-Agent Systems Conference, 2002.
• José M. Vidal. The effects of cooperation on multiagent search in task-oriented domains. Technical report, USC, 2002. USC CSE TR-2002-013.

• The task allocation problem consists of:
  • T: tasks
  • A: agents
  • c_i : 2 ^T -> Reals. cost to agent i to do a subset of tasks.
  • (t₁, t₂,..., t_|A|): an initial allocation of tasks to agents.
• The cost function is monotonic.
• The cost of doing nothing is 0.
• A deal between two agents 1 and 2 re-allocates the tasks that they had: from (T₁, T₂) to (D₁, D₂).
• This is an instance of the multiagent search problem.

• Established by Stuart Kauffman. See The Origins of Order: Self-Organization and Selection in Evolution. [1] Oxford University Pres. 1993.
• Imagine a gene sequence as a number in binary format, each digit is a gene whose value is 0 or 1.
• In nature, we expect each gene sequence to have a particular fitness. More specifically, we can imagine that the fitness of a sequence depends on the values of the individual genes.
• At its simplest, the fitness of a gene could depend solely on its own state. At its most complex, the fitness of a gene could depend on the state of all others.
• There are N genes. Each gene's fitness depends of the state of K others.
• An NK landscape is generated by assigning these values randomly.
• For K=0 we get a single peak.
• For K=N we get a completely random landscape.

• This table does not show the individual gene utility tables (too long to list).
• It is a distributed search because each gene can change its own value, perhaps in an effort to increase its own utility.
• Of course, one gene's gain could be another one's loss (for K>0).
• This is an instance of a multiagent search problem.

• n variables x₁, x₂...x_n.
• Value of x₁ is taken from domain D₁.
• constraint p_k(x_k1, x_k2...x_kj)
• If all constraints are binary then we can draw a graph like above.
• Each variable is assigned an agent. Each agent tries to change its value so as to minimize the constraints it violates.
• This is another instance of the multiagent search problem.

• Hypothesis: Would it be better if agents, instead of acting completely selfishly, acted selfishly within a team? If so, what size teams are better?
• team(i) is the set of agents in i's team. i is one of them.
• u_i(S) is the utility that i receives at state S. S is the set of all agent's current states. The team's utility is then defined as
  teamUtil(i,S) = 1/|team(i)| Σ_{j ∈ team(i)} u_j(S)
• When two agents trade tasks they move the world from state S to S'. An agent i is willing to do this if
  willingToDo(i,S,S') = teamUtil(i,S) - teamUtil(i,S') ≥ L
  where L is the maximum loss.
• If L=0 the agents are not willing to lose anything.

    S ← Randomly chosen state
    for step = 1 to 500
      maxUtility ← - infinity
      maxState ← S
      i ←  chooseRandom(A)
      fort ∈ T
        if (st = i) // i is doing t
          for j ∈ A - {i}
            S' ← S
            s't ← i
            if (t ∈ mj ∧ willingToDo(j,S,S'))
              tmp ← teamUtil(i, S') - teamUtil(i,S) 
              if (tmp > maxUtility)
                maxUtility ← tmp
                maxState ← S'
              endif
            endif
          endfor
        else // i not doing t
          if (st = i) // i could do t
            j ← argj ∈ A sj = t // j is doing t
            S' ← S
            s'i ← t
            if (willingToDo(j,S,S'))
              tmp ← teamUtil(i, S') - teamUtil(i,S) 
              if (tmp > maxUtility)
                maxUtility ← tmp
                maxState ← S'
              endif
            endif
          endif
        endif
      endfor
      S ← maxState // Move to best state.
    endfor

• For 1 team all have the same value.
• Lowest cost seems to be for values of L around .4.
• L=0 is bad. Even team selfishness is bad.

• The final cost is reduced as the number of runs that converge to a fixed point strays away from 0.
• 0 is the stable regime. Larger numbers mean the system is more dynamic.
• Intuition a small degree of selflessness acts as "heat" in a simulated annealing problem, it makes the system continue to search so better answers are found.

• Much larger search space.
• Overall minimum is lower!
• De-coupling helps, I guess.