Distributed on-Line Multi-Agent Optimization under Uncertainty : Balancing Exploration and Exploitation
Distributed on-Line Multi-Agent Optimization under Uncertainty : Balancing Exploration and Exploitation
复制标题
不确定性下的分布式在线多智能体优化：平衡探索与利用
DOI：
10.1142/s0219525911003104
复制
发表时间：
2011
影响因子：
0.4
通讯作者：
Milind Tambe
中科院分区：
文献类型：
--
作者：
Matthew E.Taylor;Manish Jain;Prateek Tandon;Makoto Yokoo;Milind Tambe
在有效地允许多个代理进行协调以实现共同目标方面存在着大量的工作。特别是，分布式约束优化（DCOP）框架中越来越多的工作使得不同数量的团队合作能够进行这种协调。此类算法可以隐式或显式地权衡解决方案质量的提高与通信和计算要求的增加。然而，DCOP框架仅限于规划问题； DCOP 代理必须在计划时对奖励函数有完整而准确的了解。我们扩展了 DCOP 框架，定义了分布式探索和利用协调 (DCEE) 问题类，以通过多种新颖算法解决现实世界的问题，例如自组织无线网络优化。 DCEE 算法与 DCOP 算法的不同之处在于，它们 (1) 仅限于单次试验中的有限数量的操作，(2) 尝试最大化在线奖励，而不是最终奖励，(3) 无法详尽地探索所有可能的操作，以及 (4) 可能了解环境中奖励的分布，但不了解奖励本身。因此，DCEE 问题不是一种规划问题，因为 DCEE 算法必须仔细平衡和协调多个智能体的探索和利用。引入了两类算法：静态估计算法执行简单的计算，允许智能体留下或探索，平衡探索算法使用有关奖励分布和实验中剩余时间的知识来决定是否留下、探索或（在某些算法中）回溯到先前位置。在复杂的移动自组织无线网络设置中的模拟和物理机器人上对这两类 DCEE 算法进行了比较。与我们的预期相反，我们发现在 DCEE 算法中增加团队合作可能会降低团队绩效。相比之下，运行 DCOP 算法的代理会随着团队合作的增加而提高其奖励。我们将这种以前未知的现象称为团队不确定性惩罚，在模拟和机器人上对其进行分析，并提出改善惩罚的技术。
A significant body of work exists on effectively allowing multiple agents to coordinate to achieve a shared goal. In particular, a growing body of work in the Distributed Constraint Optimization (DCOP) framework enables such coordination with different amounts of teamwork. Such algorithms can implicitly or explicitly trade-off improved solution quality with increased communication and computation requirements. However, the DCOP framework is limited to planning problems; DCOP agents must have complete and accurate knowledge about the reward function at plan time.We extend the DCOP framework, defining theDistributed Coordination of Exploration and Exploitation(DCEE) problem class to address real-world problems, such as ad-hoc wireless network optimization, via multiple novel algorithms. DCEE algorithms differ from DCOP algorithms in that they (1) are limited to a finite number of actions in a single trial, (2) attempt to maximize the on-line, rather than final, reward, (3) are unable to exhaustively explore all possible actions, and (4) may have knowledge about the distribution of rewards in the environment, but not the rewards themselves. Thus, a DCEE problem is not a type of planning problem, as DCEE algorithms must carefully balance and coordinate multiple agents' exploration and exploitation.Two classes of algorithms are introduced:static estimationalgorithms perform simple calculations that allow agents to either stay or explore, andbalanced explorationalgorithms use knowledge about the distribution of the rewards and the time remaining in an experiment to decide whether to stay, explore, or (in some algorithms) backtrack to a previous location. These two classes of DCEE algorithms are compared in simulation and on physical robots in a complex mobile ad-hoc wireless network setting. Contrary to our expectations, we found that increasing teamwork in DCEE algorithms maylowerteam performance. In contrast, agents running DCOP algorithms improve their reward as teamwork increases. We term this previously unknown phenomenon theteam uncertainty penalty, analyze it in both simulation and on robots, and present techniques to ameliorate the penalty.