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

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

José M. Vidal .

6 of 9