Using the max-plus algorithm for multiagent decision making in coordination graphs

Jelle R. Kok and Nikos Vlassis. Using the max-plus algorithm for multiagent decision making in coordination graphs. In RoboCup-2005: Robot Soccer World Cup IX, Osaka, Japan, July 2005. Best Scientific Paper Award. To appear

Download

pdf [176.1kB]  ps.gz [166.5kB]  

Abstract

Coordination graphs offer a tractable framework for cooperative multiagent decision making by decomposing the global payoff function into a sum of local terms. Each agent can in principle select an optimal individual action based on a variable elimination algorithm performed on this graph. This results in optimal behavior for the group, but its worst-case time complexity is exponential in the number of agents, and it can be slow in densely connected graphs. Moreover, variable elimination is not appropriate for real-time systems as it requires that the complete algorithm terminates before a solution can be reported. In this paper, we investigate the max-plus algorithm, an instance of the belief propagation algorithm in Bayesian networks, as an approximate alternative to variable elimination. In this method the agents exchange appropriate payoff messages over the coordination graph, and based on these messages compute their individual actions. We provide empirical evidence that this method converges to the optimal solution for tree-structured graphs (as shown by theory), and that it finds near optimal solutions in graphs with cycles, while being much faster than variable elimination.

BibTeX Entry

@InProceedings{Kok05robocup,
  author =       {Jelle R. Kok and Nikos Vlassis},
  title =        {Using the max-plus algorithm for multiagent decision
                  making in coordination graphs},
  address =      {Osaka, Japan},
  booktitle =    {RoboCup-2005: Robot Soccer World Cup IX},
  year =         2005,
  month =        jul,
  note =         {Best Scientific Paper Award. To appear},
  abstract =     { Coordination graphs offer a tractable framework for
                  cooperative multiagent decision making by
                  decomposing the global payoff function into a sum of
                  local terms. Each agent can in principle select an
                  optimal individual action based on a variable
                  elimination algorithm performed on this graph. This
                  results in optimal behavior for the group, but its
                  worst-case time complexity is exponential in the
                  number of agents, and it can be slow in densely
                  connected graphs. Moreover, variable elimination is
                  not appropriate for real-time systems as it requires
                  that the complete algorithm terminates before a
                  solution can be reported. In this paper, we
                  investigate the max-plus algorithm, an instance of
                  the belief propagation algorithm in Bayesian
                  networks, as an approximate alternative to variable
                  elimination. In this method the agents exchange
                  appropriate payoff messages over the coordination
                  graph, and based on these messages compute their
                  individual actions. We provide empirical evidence
                  that this method converges to the optimal solution
                  for tree-structured graphs (as shown by theory), and
                  that it finds near optimal solutions in graphs with
                  cycles, while being much faster than variable
                  elimination.}
}

---

Generated by bib2html.pl (written by Patrick Riley) on Tue Oct 31, 2006 19:33:42 UTC