Article 2010 Fluctuated peer selection policy and its performance in large-scale multi-agent systems
(First author) 大規模マルチエージェントシステムにおけるゆらぎのある仲間選択政策とその性能
Toshiharu Sugawara, Kensuke Fukuda, Toshio Hirotsu, Shin Ya Sato, Osamu Akashi, Satoshi Kurihara
Web Intelligence and Agent Systems
【抄録】This paper describes how, in large-scale multi-agent systems, each agent's adaptive selection of peer agents for collaborative tasks affects the overall performance and how this performance varies with the workload of the system and with fluctuations in the agents' peer selection policies (PSP). An intelligent agent in a multi-agent system (MAS) often has to select appropriate agents to assign tasks that cannot be executed locally. These collaborating agents are usually chosen according to their skills. However, if multiple candidate peer agents still remain a more efficient agent is preferable. Of course, its efficiency is affected by the agent' workload and CPU performance and the available communication bandwidth. Unfortunately, as no agent in an open environment such as the Internet can obtain such data from any other agent, this selection must be done according to the available local information about the other known agents. However, this information is limited, usually uncertain and often obsolete. Agents' states may also change over time, so the PSP must be adaptive to some extent. We investigated how the overall performance of MAS would change under adaptive policies in which agents selects peer agents using statistical/reinforcement learning. We particularly focused on mutual interference for selection under different workloads, that is, underloaded, near-critical, and overloaded situations. This paper presents simulation results and shows that the overall performance of MAS highly depends on the workload. It is shown that when agents' workloads are near the limit of theoretical total capability, a greedy PSP degrades the overall performance, even after a sufficient learning time, but that a PSP with a little fluctuation, called fluctuated PSP, can considerably improve it. © 2010 - IOS Press and the authors. All rights reserved.
【抄録日本語訳】本論文では、大規模なマルチエージェントシステムにおいて、各エージェントが協調タスクのために仲間エージェントを適応的に選択することが全体のパフォーマンスにどのように影響するか、またこのパフォーマンスがシステムの作業負荷やエージェントの仲間選択ポリシー(PSP)の変動によってどのように変化するかを説明する。マルチエージェントシステム(MAS)内の知的エージェントは、ローカルに実行できないタスクを割り当てるために、しばしば適切なエージェントを選択する必要がある。これらの協力エージェントは、通常、そのスキルに応じて選択される。しかし、複数の候補となる同業者がまだ残っている場合、より効率的なエージェントを選択することが望ましい。もちろん、その効率はエージェントの作業負荷やCPU性能、利用可能な通信帯域幅に影響される。残念ながら、インターネットのようなオープンな環境では、どのエージェントも他のエージェントからそのようなデータを取得できないため、この選択は他の既知のエージェントに関する利用可能なローカル情報に従って行わなければならない。しかし、この情報は限られており、通常は不確かで、時代遅れになることが多い。また、エージェントの状態は時間とともに変化するため、PSPはある程度適応的でなければならない。我々は、統計的/強化学習を用いてエージェントが仲間を選択する適応的なポリシーのもとで、MASの全体的な性能がどのように変化するかを調査した。特に、低負荷、ニアクリティカル、過負荷という異なる作業負荷の下での選択における相互干渉に注目した。本論文では、シミュレーション結果を示し、MASの全体的な性能が作業負荷に大きく依存することを示す。エージェントの作業負荷が理論的な総能力の限界に近い場合、貪欲なPSPは十分な学習時間を経ても全体の性能を低下させるが、揺らぎPSPと呼ばれる少しの揺らぎを持つPSPはかなり改善できることが示された。© 2010 - IOS Pressと著者たち。All rights reserved.