An efficient algorithm for multiagent decision making

作者：Jiang Dawei; Wang Yongli; Dong Yisheng

来源：Chinese Journal of Electronics, 2007, 16(2): 206-211.

• multiagent coordination
• simulated annealing
• coordination graphs
• variable elimination
• game theory

Coordination, as a key issue in fully cooperative multiagent systems, raises a number of challenges. Variable elimination offers a feasible solution to this problem. However the worst-case time complexity of this algorithm grows exponentially with the number of agents and it only reports an answer when the whole algorithm terminates. Therefore, it is unsuitable in real-time systems. In this paper, we propose an anytime algorithm, called the simulated annealing algorithm, as an approximation alternative to variable elimination. Experiments show that the algorithm can compute optimal results in small joint action spaces with lower cost and find near optimal solution with only a fraction of the time that variable elimination takes to solve the same coordination problems of large joint action space.

• 出版日期2007-4
• 单位东南大学