Anytime Coordination Using Separable Bilinear Programs
Anytime Coordination Using Separable Bilinear Programs
复制标题
使用可分离双线性程序进行随时协调
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
S. Zilberstein
中科院分区：
文献类型：
--
作者：
Marek Petrik;S. Zilberstein
为多智能体系统开发可扩展的协调算法是一个很难的计算挑战。一个有用的方法，证明了覆盖集算法（CSA），利用结构化的相互作用，以产生显着的计算增益。从经验来看，CSA表现出非常好的随时性能，但结果的误差范围尚未确定。我们重新制定的算法，并推导出在线和离线的近似解的误差界。此外，我们提出了一种有效的方法来自动降低交互的复杂性。我们的实验表明，这是一个很有前途的方法来解决广泛的分散决策问题。该算法使用的一般公式使其易于实现，并广泛适用于各种其他AI问题。
Developing scalable coordination algorithms for multi-agent systems is a hard computational challenge. One useful approach, demonstrated by the Coverage Set Algorithm (CSA), exploits structured interaction to produce significant computational gains. Empirically, CSA exhibits very good anytime performance, but an error bound on the results has not been established. We reformulate the algorithm and derive both online and offline error bounds for approximate solutions. Moreover, we propose an effective way to automatically reduce the complexity of the interaction. Our experiments show that this is a promising approach to solve a broad class of decentralized decision problems. The general formulation used by the algorithm makes it both easy to implement and widely applicable to a variety of other AI problems.