DCSP和DCOP求解研究进展

摘要

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