1、分布式約束優(yōu)化是對多Agent系統(tǒng)的建模，廣泛應用于求解分布式計劃、分布式調度和分布式資源分配問題，典型應用有災難救援、多Agent小組合作、分布式機器人、會議調度、傳感器網絡等。DPOP算法是一種基于動態(tài)規(guī)劃思想的推理式算法，也是當前分布式約束優(yōu)化完備算法中效率最高的算法之一。DPOP算法的性能和效率遠遠高于許多搜索類算法，非常適合于實際應用問題的求解。本文基于DPOP算法，從通信結構的角度提出改進和優(yōu)化思路，并在自主開發(fā)的分布式約束

2、優(yōu)化算法實驗平臺DCOPSolver上實驗和證明思路的可行性，具體研究工作如下：
　?、俳榻B了分布式約束優(yōu)化的研究現(xiàn)狀和最新研究動態(tài)，詳細闡述了分布式約束優(yōu)化的基本概念和定義，包括約束圖、通信結構和圖著色、會議調度、隨機DCOP三類典型問題，并重點介紹了本文的主要研究對象DPOP算法。
　?、谔岢鲆环N新的以廣度優(yōu)先搜索偽樹為通信結構的BFSDPOP算法。相比DPOP采用的深度優(yōu)先搜索偽樹通信結構，BFSDPOP采用的廣度優(yōu)先

3、搜索偽樹通信結構具有分支多、通信路徑短的特點，使得BFSDPOP算法的并行運算性能和通信效率更優(yōu)。同時，本文提出ClusterRemoving算法通過合理分配偽樹中的交叉邊，很好地控制了算法中生成的最大消息大小。
　?、厶岢鲆环N新的以深度優(yōu)先搜索偽樹為通信結構的CVDPOP算法，它以最佳割點和最大度數(shù)優(yōu)先的策略構建其偽樹通信結構。CVDPOP算法的創(chuàng)新之處在于引入割點引導深度優(yōu)先搜索偽樹的構建，借助割點促進分支生成的特點構建分支更

4、多、質量更優(yōu)的深度優(yōu)先搜索偽樹，從而提高算法性能。
　　④鑒于已有實驗平臺的復雜性，本文自主開發(fā)了一套新的分布式約束優(yōu)化算法實驗平臺DCOPSolver，它具有功能模塊更加精簡，新算法擴展集成難度更小、速度更快的特點。本文的所有實驗均在DCOPSolver上實施，實驗比較了DPOP、BFSDPOP、CVDPOP三種算法分別求解圖著色問題、會議調度問題和隨機DCOP問題時的運行時間和最大消息維度。實驗結果顯示BFSDPOP和CVDP