Proceedings of the International Conference on Systems, Man and Cybernetics
Institute of Electronics Engineers
953-957
No
New York
NY
International Conference on Systems, Man and Cybernetics
2004
[en] Coordinationgraphsprovideatractableframe- work for cooperative multiagent decision making by decom- posing the global payoff function into a sum of local terms. In this paper we review some distributed algorithms for ac- tion selection in a coordination graph and discuss their pros and cons. For real-time decision making we emphasize the need for anytime algorithms for action selection: these are algorithms that improve the quality of the solution over time. We describe variable elimination, coordinate ascent, and the max-plus algorithm, the latter being an instance of the be- lief propagation algorithm in Bayesian networks. We discuss some interesting open problems related to the use of the max- plus algorithm in real-time multiagent decision making.