\input zb-basic
\input zb-ioport
\iteman{io-port 06001718}
\itemau{Ding, Bo; Wang, Huaimin; Shi, Dianxi; Tang, Yangbin}
\itemti{An algorithm for distributed constraint optimization problems with low constraint density.}
\itemso{J. Softw. 22, No. 4, 625-639 (2011).}
\itemab
Summary: Many challenges in multi-agent coordination can be modeled as distributed constraint optimization problems (DCOPs). Aiming at DCOPs with low constraint density, this paper proposes a distributed algorithm. In this algorithm, each agent makes decisions according to a greedy principle and the backjumping mechanism among the agents ensures the success of this algorithm even if the greedy principle leads to a local optimum. In contrast with existing mainstream DCOP algorithms, this algorithm can solve problems with low constraint density with fewer messages while keeping polynomial message length and space complexity. The correctness of the key mechanisms in this algorithm is proved, and the advantages in performance are verified by experiments.
\itemrv{~}
\itemcc{}
\itemut{distributed constraint optimization problem; multi-agent coordination}
\itemli{doi:10.3724/SP.J.1001.2011.03765}
\end