DCSP和DCOP求解研究进展

A Research on Solving DCSP and DCOP

分布式约束满足问题(DCSP)和分布式约束最优问题(DCOP)的研究是分布式人工智能领域的基础性工作。本文首先介绍了DCSP和DCOP的形式化描述及对实际应用问题的建模方法。在DCSP和DCOP的求解中,通常对问题要进行限制和要求,同时要满足分布性、异步性、局部性、完备性的原则。异步回溯(ABT)、异步弱承诺搜索(AWC)和分布式逃逸(DB)算法是求解DCSP的有代表性的算法;DCSP算法对DCOP求解产生了影响,但由DCSP一般化到DCOP的算法,仅适用于解决部分特定的问题,DCOP的最优、异步算法有异步分布式约束最优算法(A- dopt)和最优异步部分交叉算法(OptAPO)。本文讨论了上述算法的性能。相关的研究工作在多局部变量的处理、超约束DCSP、算法性能度量、通信的保密等方面进行了扩充,在对问题本身的研究、建模方法学、算法、与其他方法的结合以及拓展应用领域等方面仍有许多问题需要进一步研究。

The research of Distributed Constraint Satisfaction Problem（DCSP） and Distributed Constraint Optimization Problem （BCOP） have already became one of the most important basic research topic in distributed artificial intelligence domain. Formal description of DCSP and DCOP, as well as the modeling method to practical problem are introduced at the beginning. In order to solve DCSP and DCOP, there are some limitation and restriction in problem itself, and problem solving process needs to satisfy the principle of distributing, asynchronism, locality and completeness. Asynchronous Backtracking （ABT）, Asynchronous Weak-Commitment search（AWC） and Distributed Breakout（DB） are representative algorithms for solving DCSP, which have some affect to solving DCOP Due to the DCOP algorithm generalized by DCSP can only used to some special problem, there need asynchronous distributed constraint optimization （Adopt） and Optimal Asynchronous Partial Overlay（OptAPO） to provide optimal and asynchronous solution of DCOP. The performances of the above algorithms are discussed also. The relative work expanded in multi-local variability, over constraint DCSP, matrix of algorithms performance, privacy in communication, and etc. As the future work, progress should be made in DCSP and DCOP themselves, modeling methodology, algorithm, combination with other method and extending the application area.