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

This talk summarizes the results that appear in

1 Task-Oriented Domains

2 NK Landscapes

2.1 NK Example

Gene 1 Gene 2 Gene 3 K=0 Fitness K=3 Fitness
0 0 0 0 3
0 0 1 1 1
0 1 0 1 5
0 1 1 2 8
1 0 0 1 0
1 0 1 2 2
1 1 0 2 14
1 1 1 3 9

3 Constraint Satisfaction

Constraint Satisfaction graph

4 Teaming

5 Search Algorithm

    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

6 Random Landscape Shared Cost Results

7 Optimality at the Edge of Chaos

8 Random Landscape Individual Cost Results

URLs

  1. The Origins of Order: Self-Organization and Selection in Evolution., http://www.amazon.com/exec/obidos/ASIN/0195079515/multiagentcom

This talk available at http://jmvidal.cse.sc.edu/talks/coopintod/
Copyright © 2009 José M. Vidal . All rights reserved.

26 October 2002, 12:21PM