arXiv：cs.AI· Raziyeh Moghaddas, Fabio Caraffini·· 18 小时前
DCC-Incomplete：面向分布式约束满足的动态冲突聚类与轻量学习修复求解器
Dynamic Conflict Clustering with Lightweight Learning and Strategic Repair for Distributed Constraint Satisfaction
AI 导读
研究者提出基于修复的 DCSP 求解器 DCC-Incomplete，将未解部分划分为冲突簇，并通过协调层把通信限制在同一冲突区域内的 agent 之间。在带已知可满足解的分布式图着色基准上，其记忆引导重启将成功率从 37.50% 提升到 61.11%，中位运行时间从 0.565s 降至 0.367s，每条约束的中位通信量从 12.493 条降至 6.503 条。
正文
Abstract:Distributed Constraint Satisfaction Problems (DCSPs) model distributed decision-making in multi-agent systems, where agents assign values to local variables while satisfying shared constraints. However, many DCSP solvers still rely on broad, repeated peer-to-peer communication and are largely reactive, with limited support for strategic coordination or learning. This increases communication overhead, can lead to stagnation, and reduces the success of hard instances. Hence, we propose Dynamic Conflict Clustering-Incomplete (DCC-Incomplete), a repair-based solver that combines conflict-centred decomposition, structured coordination, strategic repair, and lightweight learning for stagnation recovery. DCC-Incomplete groups the unsolved part of the problem into conflict clusters and restricts communication via a coordination layer to agents within the same conflict region. It also introduces memory-guided restart, enabling agents and clusters to pause, revise, and adapt repairs based on neighbouring conflict states. A thorough evaluation of DCC-Incomplete on distributed graph-colouring benchmarks with planted satisfying assignments shows that its memory-guided restart improves the success rate from 37.50% to 61.11%, reduces median runtime from 0.565s to 0.367s, and cuts median communication from 12.493 to 6.503 messages per constraint. These results suggest that dynamic conflict clustering, combined with lightweight strategic and learning-guided repair, improves both communication efficiency and robustness in incomplete DCSP solving.
| Subjects: | Multiagent Systems (cs.MA); Artificial Intelligence (cs.AI); Discrete Mathematics (cs.DM) |
| Cite as: | arXiv:2610.15658 [cs.MA] |
| (or arXiv:2610.15658v1 [cs.MA] for this version) | |
| https://doi.org/10.48550/arXiv.2610.15658 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Fabio Caraffini PhD [view email]
[v1]
Sun, 11 Oct 2026 14:35:35 UTC (7,061 KB)
来源：arXiv：cs.AI · arxiv.org