Reference : Using the max-plus algorithm for multiagent decision making in coordination graphs
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Engineering, computing & technology : Computer science
Using the max-plus algorithm for multiagent decision making in coordination graphs
Kok, Jelle R. [> >]
Vlassis, Nikos mailto [University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB) > >]
Proc. RoboCup Int. Symposium, Osaka, Japan
Proc. RoboCup Int. Symposium, Osaka, Japan
[en] 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.

File(s) associated to this reference

Fulltext file(s):

Open access
download.pdfAuthor postprint176.15 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.