Incomplete Distributed Constraint Optimization Problems: Model, Algorithms, and Heuristics
Incomplete Distributed Constraint Optimization Problems: Model, Algorithms, and Heuristics
复制标题
不完全分布式约束优化问题：模型、算法和启发式
DOI：
10.1007/978-3-030-94662-3_5
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Zivan, Roie
中科院分区：
文献类型：
--
作者：
Tabakhi, Atena M.;Yeoh, William;Zivan, Roie
分布式约束优化问题(DCOP)是建模协作多智能体问题的有力工具，特别是当它们之间存在稀疏约束时。该模型的一个关键假设是，所有约束都是完全指定的或先验已知的，这在约束编码了人类用户偏好的应用中可能不成立。在本文中，我们将该模型扩展到不完全DCOP(I-DCOP)，其中一些约束可以部分地指定。在I-DCOP算法的执行过程中，可以得出用户对这些部分指定的约束的偏好，但它们会产生一些启发成本。此外，我们还扩展了完整的DCOP算法SyncBB和不完整的DCOP算法ALS-MGM来求解I-DCOP。我们还提出了参数启发式算法，这些算法可以用来权衡解决方案的质量，以换取更快的运行时间和更少的启发。当引出是免费的时，当SyncBB使用时，它们还提供理论上的质量保证。因此，我们的模型和启发式算法扩展了分布式约束推理的最新发展，以更好地建模和解决具有用户偏好的基于分布式代理的应用程序。
TheDistributed Constraint Optimization Problem(DCOP) formulation is a powerful tool to model cooperative multi-agent problems, especially when they are sparsely constrained with one another. A key assumption in this model is that all constraints are fully specified or known a priori, which may not hold in applications where constraints encode preferences of human users. In this paper, we extend the model toIncomplete DCOPs(I-DCOPs), where some constraints can be partially specified. User preferences for these partially-specified constraints can be elicited during the execution of I-DCOP algorithms, but they incur some elicitation costs. Additionally, we extend SyncBB, a complete DCOP algorithm, and ALS-MGM, an incomplete DCOP algorithm, to solve I-DCOPs. We also propose parameterized heuristics that those algorithms can utilize to trade off solution quality for faster runtime and fewer elicitation. They also provide theoretical quality guarantees when used by SyncBB when elicitations are free. Our model and heuristics thus extend the state-of-the-art in distributed constraint reasoning to better model and solve distributed agent-based applications with user preferences.
登录
查看更多内容
用于智能建筑中调度设备的 DCOP 中的优先诱导
DOI：
--
发表时间：
2017
期刊：
AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Atena M. Tabakhi
通讯作者：
Atena M. Tabakhi
在 DCOP 解决方案的搜索中嵌入偏好诱导
DOI：
--
发表时间：
2020
期刊：
Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS
影响因子：
--
作者：
Xiao, Yuanming;Tabakhi, Atena M;Yeoh, William
通讯作者：
Yeoh, William
开放约束规划
DOI：
10.1016/j.artint.2004.10.005
发表时间：
2005
期刊：
Artif. Intell.
影响因子：
--
作者：
B. Faltings;Santiago Macho
通讯作者：
Santiago Macho
DOI：
10.1613/jair.2849
发表时间：
2008-05
期刊：
--
影响因子：
--
作者：
W. Yeoh;Ariel Felner;Sven Koenig
通讯作者：
W. Yeoh;Ariel Felner;Sven Koenig
DOI：
--
发表时间：
2020
期刊：
Principles and Practice of Multi-Agent Systems
影响因子：
--
作者：
Tabakhi, Atena M.;Yeoh, William;Fioretto, Ferdinando
通讯作者：
Fioretto, Ferdinando