多agent系统作为分布式人工智能研究领域的重要分支,已被广泛应用于多个领域中复杂系统的建模.而分布式约束优化作为一种多agent系统求解的关键技术,已成为约束推理研究的热点.首先对其适用性进行分析,并基于对已有算法的研究,总结出采用该方法解决问题的基本流程,在此基础上,从解的质量保证、求解策略等角度对算法进行了完整的分类;其次,根据算法分类结果以及执行机制,对大量经典以及近年来的分布式约束优化算法进行了深入分析,并从通信、求解质量、求解效率等方面对典型算法进行了实验对比;最后,结合分布式约束优化技术的求解优势给出了分布式约束优化问题的实际应用特征,总结了目前存在的一些问题,并对下一步工作进行了展望.
Multi agent system, one of important branches of distributed artificial intelligence, has been widely applied to modeling a serious of complex systems in diverse research fields. Significant research effort has sought to solve constraint programming with distributed constraint optimization which is a popular framework for multi agent system. The contributions of this research proceed from previous work in the following ways. First, based on the existing research, the applicability of distributed constraint optimization is analyzed, and general process of distributed constraint optimization algorithms is extracted. Second, a relatively complete classification of algorithms is provided from the perspective of quality assurance and solving strategies. Next, considering execution mechanism, a thorough analysis of a large number of classic algorithms proposed in recent years is carried out. Moreover, the experimental analysis of some typical algorithms with the metrics of communication, solution quality and efficiency is provided. Finally, combining the advantage of distributed constraint optimization technology, the application characteristics of distributed constraint optimization problem are proposed, and future work is discussed.
多agent系统(multi-agent system,简称MAS)作为分布式人工智能(distributed artificial intelligence,简称DAI)的一个重要分支,利用分布式约束推理解决agent之间合作问题.MAS中每个agent是自主的,通过协调这些自治的agent行为,使这些agent达到共同或各自不同的目标.在MAS中,agent是一种可以感知环境变化并且通过内部执行机构反馈给环境的节点.在MAS的具体应用中,关键的一个问题是如何加强agent之间的有效合作,使agent与其他agent交换本地决策信息的同时能够根据其他agent的决策信息进行分析、推理,进而求得问题的最优解[
虽然将回溯搜索以及约束一致性检查两种基本思想引入到启发式方法中能够解决MAS问题,但是随着硬件和网络技术的发展以及分布式计算环境广泛地应用,越来越多支持agent自治性特点的建模、求解技术逐渐成为研究热点[
随着DCOP研究的深入,许多具备分布式求解特点的实际问题被建模成为DCOP进行求解.为了能够更直观地了解DCOP在实际问题中的应用特征,
3人3会议安排问题
Three meeting schedule problem with 3 participants
与会者档期时间
Schedule time of participants
与会者 | 会议 | 档期(时) |
|
|
8-9/10-11/11-12 |
|
|
9-10/10-11/13-14/17-18 |
|
|
9-10/11-12//13-14 |
会议安排问题具备如下特点:
· 每个与会者只关心个人会议安排情况,个人的档期与其他与会者无关.
· 会议时间的通信协商仅发生在同一会议与会者之间.
· 当部分与会者的档期发生变化时,需要及时获取新的会议安排.
结合该典型实例可以看出,DCOP求解技术解决的一类实际问题通常具备如下特征:
· 自治性强:难以建立全局模型求解.每个子系统由于固定地理位置等原因,只能根据自身信息或者局部信息进行决策,使得系统无法获取全局信息,难以建立全局模型进行求解,如无线传感器网络.
· 限制性通信:难以获取全局约束.在不同的实际应用领域中,由于通信代价、通信隐私、通信范围的局限,使得通信仅能发生在相邻子系统间.整个系统难以搜集全局的约束,如社交网络.
· 时效性强:难以适应环境动态变化.一类实际问题对于求解的实时性要求较高.一旦周围环境发生局部变化时,通过更新全局信息将延迟求解速度,如灾难救援等问题.
对于这类问题,集中式求解方法的处理方式是:设置中央处理节点,将各节点的信息直接或间接发送至中央处理节点进行处理;最后,通过集中决策得到问题的解.然而,集中式求解算法主要存在以下3个方面的缺点:
(1) 容易暴露个体内部的隐私信息.比如无线传感器网络在军事中的应用,每个传感器的感知内容通过集中式的传递,会造成信息泄露等安全性威胁.
(2) 难以适应个体内部环境的动态变化.比如在会议安排问题中,个别与会者的档期发生变化时,中央处理节点要重新利用更长时间进行全局会议时间分配的调整;相应地,更多的额外信息会在个体之间进行传递.
(3) 较差的鲁棒性.中央处理节点需要收集到所有节点的消息后才会进行集中决策,如果决策过程中发生错误,需要从全局方面变更个体的内部状态.
相应地,DCOP求解方法则适应于求解该类问题,其求解目的是获得问题的最优解或者次优解,并能使这些解在质量上得到一定的保证
本文第1节介绍DCOP的定义,并给出DCOP的求解流程.第2节根据DCOP求解流程对目前的DCOP算法进行分类,并结合具体的典型算法进行算法间的对比分析.第3节介绍DCOP相应的应用.最后,本文在总结中给出一些DCOP未来的扩展和研究工作.
MAS解决实际问题的方式可以理解为一种基于agent的协作问题,而分布式约束则可以描述领域对象的性质、相互关系、任务要求、目标,因此可以作为一种有效的方法表示这种agent间的协作关系.所以,研究者将分布式约束作为建模此问题的一个关键范式.分布式约束优化满足问题(distributed constraint satisfaction problem,简称DCSP)作为早期求解MAS的技术,从
集中式与DCSP算法比较
Comparison between centralized and DCSP algorithms
求解类型 | 集中式 | DCSP |
通信代价 | 全局通信 | 局部通信 |
隐私性 | 暴露隐私 | 保护隐私 |
容错性 | 局部错误对全局影响大 | 仅需调整局部错误 |
并行性 | 难以实现并行 | 易实现并行 |
求解质量 | 解的质量较好 | 无解、多解 |
通信代价 | 全局通信 | 局部通信 |
DCSP求得的解
Solutions of DCSP
会议 | 与会者 | 开会时间(时) | |
解1 | 解2 | ||
|
|
10-11 | 10-11 |
|
|
9-10 | 13-14 |
|
|
11-12 | 11-12 |
造成DCSP算法中无解或者多解的原因,是由于约束只有满足和不满足两种状态,DCSP相关解决方案的目的是找到满足所有约束的解.因此,多解之间不存在优劣比较,使算法无法在多个解中进行取舍.同理,只要一个约束是违反规则的,DCSP相关解决方案无法根据解的优劣选择次优解.DCOP在DCSP的基础之上,将约束状态从满足与不满足扩展到约束函数,约束函数是对约束更加具体的量化处理.DCOP定义存在若干形式上有细微差异的版本[
定义
·
·
·
·
·
定义
$F(x) = \sum\limits_{{x_i},{x_j} \in X} {{f_{ij}}({x_i},{x_j})} ,{x_i},{x_j} \in D$
(1)
定义
(2)
从DCOP的定义中我们可以看出,DCSP是DCOP的特殊情况.
· 在约束方面,变量和约束分布在不同自治的agent中,但DCSP的约束形态仅为满足或不满足.只要使DCOP中的约束函数代价值为0(不满足)或1(满足),即可代表这两种形态.
· 在目标函数方面,如果使DCOP中所有的约束代价值之积为1,则当前的变量赋值情况即为全局满足所有约束的一个解.
为便于研究,在目前的DCOP建模过程中,我们假设每个agent有且仅控制一个变量[
通过对DCOP求解算法执行过程的分析、总结,
DCOP求解方法基本流程
Basic process of solution method for DCOP
该流程主要分为3个阶段:第1阶段是将实际问题建模成为DCOP,在流程中主要体现为模型的建立;第2阶段是对建模的DCOP进行预处理,包含模型转化和搜索空间的构建;第3阶段是算法求解,在流程中包括求解策略的确定以及通信模式的设计.
在DCOP求解过程中,不同算法之间的差异主要体现在模型建立、模型转换、搜索空间构建、求解策略、通信方式等过程中的解决策略上,不同的求解算法在一个或几个流程中采取不同的策略,形成不同的求解效果.
在模型的建立阶段,一个实际问题首先被建模成为一个五元组模型.然而,同一个问题通常有若干建模方式,不同的建模方式导致问题在形成DCOP模型时所确定的问题的agent划分、变量从属情况、约束划分、目标建立有所不同.这些区别将直接导致模型转化后形成的问题规模有所差异,进而影响算法的求解效率.在目前的大部分DCOP算法中,模型的转化是必要的;但是在一些算法中,模型转化后的图结构可以直接作为搜索空间,不需要进行树形结构的建立.
在模型转化中,一个DCOP一般被转化成为一个图结构.根据DCOP算法求解策略的不同,目前大部分DCOP算法通常将一个DCOP模型转化为约束图或因子图.
DCOP的模型转化及搜索空间的确定
Transformation and the determination of search space based on DCOP model
搜索空间的构建,主要为了确定agent之间的次序关系,以满足消息传递的范围.目前,DCOP根据求解策略的不同,主要在图结构的基础上将其构建成一棵伪树或者(pseudo tree)与或树(AND/OR tree),
DCOP完备算法通常采用两种求解策略:一种是搜索方法,如最佳优先、深度优先、回溯和分支界限搜索等;另一种是基于推理的方法,基于推理的求解策略允许agent计算从相邻agent中聚合约束的代价值以逐步减少问题规模.在一些非完备算法中,为了更快地获得次优解,随机策略、约束问题求解中的求解框架也相应地运用到了DCOP的求解过程中.
为了支持不同的求解策略,agent之间的通信方式也有差异,在基于搜索的算法中,经常采用异步通信方式,而在基于推理的算法中,则常采用同步通信方式;此外,agent之间的通信范围也有所不同,比如部分集中式算法中,信息会传送至中央节点,而完全分散式的算法则常常采用局部通信等.针对目前DCOP算法在流程各个阶段采用的不同机制,本文对其中的关键策略进行了归纳总结,见
DCOP算法在求解流程中采用的关键策略
Critical strategies adopted in the solution progress of DCOP algorithms
求解流程 | 关键策略 |
模型建立 |
三元组模型:〈 |
模型转化 | 约束图/因子图 |
搜索空间 | 约束图/因子图/伪树/与或树 |
求解策略 | 基于搜索(最佳优先/深度优先/分支界限/回溯); 基于推理/随机策略/基于约束问题求解框架 |
通信模式 | 同步局部通信/异步局部通信/集中式通信 |
为了使算法能够解决DCOP,我们还需要让DCOP算法满足以下几个需求:
(1) 完备性.寻找满足所有约束或违反约束最少并且代价值最优的解.
(2) 分布性.支持agent分布性特点,保护agent的内部隐私.
(3) 异步性.保证各agent不必相互等待,确保系统的健壮性.
为了满足以上求解条件,提出了一系列优秀的DCOP算法,如ADOPT[
完备与非完备算法的最大区别在于求解质量的不同:完备算法求得的是全局最优解,而非完备算法求得的是最优解或是次优解.造成求解质量不同的主要原因在于算法选取的求解策略有所差异,这将直接影响agent的通信范围、消息传递的类型、数量以及消息处理的时间等执行过程,进而使agent根据局部信息给出的决策不同,最终影响agent内部变量的赋值情况.通常,为了能够找到问题的最优解,完备算法需要消耗过多的计算和通信资源,这些消耗的资源会随着问题规模的扩大而呈非线性增长.而非完备算法则能够有效地避免这些问题,又因为有些实际问题对于求解的实时需求高于精度需求,或因实际问题受物理条件的制约(如存储空间小),此时,采用拥有良好稳定性和健壮性的非完备算法可以在时间、资源代价较小的情况下求得次优解.
完备算法主要分为部分集中式算法和完全分散式算法.两类算法最大的区别在于通信的模式不同.
· 部分集中式算法融入了集中式求解特点,一些消息将会被传递至中央处理节点;而后,中央处理节点将会集中处理消息,并根据这些消息进行变量的赋值决策.
· 在完全分散式算法中,消息仅在相邻agent间进行传递;然后,每个agent根据局部消息进行决策.
因此,通信模式的不同导致消息传递的范围、agent对于消息的接收和处理方式不同,造成两种算法在求解效率上有所差异.虽然消息的集中处理会使agent提供的变量赋值决策更加准确,但消耗更多的时间;而分散式则与其相反.部分集中式求解算法的代表是OptAPO算法[
针对非完备算法,本文从质量保证角度进行了归类分析.非完备算法主要分为无质量保证和基于质量保证两类.两类算法最大的区别在于次优解的可靠程度和保障程度.虽然在两类算法的执行过程中,每个agent的变量赋值决策都基于局部相邻agent的赋值情况,但是无质量保证的非完备算法通常采用随机决策的方式,以一定的概率对变量进行赋值的变更;而基于质量保证的非完备算法则是通过上下界或局部最优等限制条件给出更严谨的赋值变更决策.虽然无质量保证算法会降低求解时间,但这种求解策略容易导致算法陷入局部最优,也使求得的解难以得到质量保证,在许多实际问题中,无质量保证的解的实
际意义不强,比如DSA[
DCOP算法的分类
Classification of DCOP algorithm
本文的第2.1节和第2.2节将对基于搜索以及推理类的算法进行详细的描述.本文的第2.3节和第2.4节将对基于质量保证的off-line算法和on-line算法进行详细的描述.
这类算法主要采用搜索的求解策略进行解的构建,不同的搜索策略将会影响算法的求解效率.同时,算法采用树形的搜索空间,使每个子树根节点之间不存在约束,便于子树中agent进行异步搜索.这类算法容易造成agent间传递大量消息,因此,很多算法的改进目标就是避免大量的消息传递.搜索效率较好的算法主要采用最佳优先搜索或者深度优先分支界限搜索策略.
最佳优先搜索可以看成是对宽度优先搜索的一种改进.与宽度优先一样,最佳优先也总是保留一组继续向下搜索的可选择路径.此外,最佳优先的一个重要原理就是根据评价函数的计算结果中代价最小的那条路径向下搜索.在搜索过程中,通过不断地放弃代价较大的路径,从而找到代价最小的问题求解答案.由于最佳优先搜索在寻找最优路径时采用的是最小下界,而最小下界的计算可以不依靠全局信息,因此,这种搜索策略更适合异步搜索.
然而,这种搜索策略带来的问题在于agent在搜索过程中无法保证当前得到的局部解是否会引导全局最优,因此,有可能会舍弃导致全局最优的局部解.在这种情况下,回溯搜索则必不可少,目的是探寻已经被舍弃的局部解.而这种回溯的频繁发生会导致异步搜索里agent之间传递的消息数量增加.
在DCOP算法中,ADOPT,ADOPT-ng[
分支界限法源于运筹学中的整数规划问题,是使用最为广泛的约束优化方法.其具体做法是:算法以深度优先的方式搜索解空间,而且如标准回溯方法一样执行,只是在为变量赋值时,需要计算一下当前的代价函数值,如果代价函数值越界,那么当前搜索路径以下的子树将被立刻修剪掉.开始时,算法通常先找到一个次优解,随着搜索过程的进行不断被修改.分支界限法的效率取决于代价函数值的大小以及是否能够更早地发现一个好的边界.
与最佳优先搜索策略相比,深度优先分支界限搜索可以有效地避免反复重建内存中已经舍弃的局部解,因此可以有效地降低agent之间由于回溯搜索而进行的大量消息传递,进而提高搜索效率.
在DCOP算法中,NCBB[
基于推理的DCOP算法主要采用动态规划求解策略进行解的构建,DPOP是最先采用这种思想进行求解的完备算法,后续算法均在DPOP基础上进行的改进,而求解策略仍然是动态规划.与搜索类算法相比,这类算法的消息数量是呈线性增长的,而消息容量却容易呈指数增长,因此,大部分基于DPOP的改进算法主要采用更合理的数据结构,减少消息对空间的占用.
利用动态规划进行求解的基本算法DPOP主要采用伪树结构,并且从小范围开始构建局部解,并适用到越来越大的范围,最终得到全局解.这类算法主要包含以下3个求解阶段:
· 伪树生成阶段:DPOP算法利用深度优先搜索方式,结合现有的分布式伪树构造算法将约束图转化成一棵伪树.
· UTIL消息传播阶段:UTIL消息是一系列值的矩阵,由子节点发送至父节点,矩阵中每一维代表一个agent的一个变量.UTIL消息在沿着树形结构至底向上传递的过程中,列出了和全局优化有关的所有子问题所有不同取值组合情况以及代价值.
· VALUE消息传播阶段:VALUE消息由父节点传送至子节点,包含父节点内部变量的最佳取值.在该阶段中,根节点率先根据获取的UTIL消息进行内部变量的最佳赋值,然后,子节点依次根据父节点传送的VALUE消息以及内部存储的UTIL消息,为节点内的变量进行最佳赋值,直到发送到叶子节点为止.
DPOP算法只需要线性的消息数,但消息的容量却随着约束图induced width的增加呈指数增长[
O-DPOP[
MB-DPOP(
H-DPOP[
·
·
·
大部分off-line算法主要根据定义的标准对搜索空间进行区域划分,形成若干独立区域,并在求解过程中保证这些独立区域内的变量赋值最优.这类算法的求解特点是,能够根据问题规模(变量、约束数量等)给出解的质量保证.
通常,off-line算法的求解过程主要分为以下3个阶段:
· 初始化阶段:agent之间通过传递初始信息确定在所给标准下所有独立划分区域的集合.
· 优化阶段:每个独立区域内的变量在保证边缘变量当前值的情况下,计算得到当前区域内的变量最优赋值.
· 执行阶段:独立区域间进行信息通信,并根据信息调整区域内赋值情况以获得全局.
其中,第2阶段和第3阶段循环执行,直到算法达到终止条件为止.结合
该类算法主要包括
定义
$$R({A_{kop}}) \geqslant \frac{{\left( {\matrix
{n - m} \\
{k - m} \\
\endmatrix } \right)}}{{\left( {\matrix
n \\
k \\
\endmatrix } \right) - \left( {\matrix
{n - m} \\
k \\
\endmatrix } \right)}}R({A^*})$$
(3)
定义
$R({A_{top}}) \geqslant \frac{{(m + t - 1)}}{n}R({A^*})$
(4)
$R({A_{cop}}) \geqslant \frac{{c{c_*}}}{{|c| - n{c_*}}}R({A^*})$
(5)
· 阶段1:通过移除伪树中的部分边,生成一棵子树,使该子树代表的子图的induced width在给定的参数
· 阶段2:借助任意完备算法,在该子树上求解问题的解.
若用
$R({A^*}) - R(A) \leqslant {r_{\max }} \times \sum\limits_k^{w(G,o) - p} {(|X| - (k + 1))} $
(6)
从以上次优解与最优解的关系中也可以看出:通过off-line算法得到的次优解仅与问题的划分标准和问题规模有关,与算法的运行过程无关.即,在算法运行前就可以确定解的质量范围.
On-Line算法的求解思想与完备算法类似,主要根据子问题的求解情况逐步构建更优的全局解,因此,算法每次循环的执行结果不仅用来寻找次优解,同时也在不断为次优解提供上下界.与完备算法不同的是,为了能让on-line算法适合快速求解大规模的DCOP,在求解过程中,不同的求解策略导致子问题的构建方式以及子问题间的通信方式会有所差异,因此,on-line算法对求解质量的保证也有一定的差别.
DaCSA[
· 分解阶段:以agent为单位分解原问题,使每个agent单独成为一个子问题.
· Divide阶段:每个agent并行独立地对内部变量的赋值情况进行协调,直到内部赋值最优.
· Coordinate阶段:agent之间通过信息的交换来改变子问题内变量的赋值.
在DCOP中,约束有两种存在方式:仅属于agent内部变量之间的约束为内部约束;连接agent之间的约束为接口约束.分解一个二元约束DCOP时,由于接口约束被两个来自不同agent的内部变量共享,因此,两种算法将接口约束平均分配到所属的两个不同agent中.这种分配方式会出现agent在Divid e阶段并行赋值调整时,由接口约束连接的两个变量因分属在不同agent中而产生赋值冲突.为了能使agent之间在Coordinate阶段更好、更快地达到赋值一致性,两种算法均采用了拉格朗日对偶分解以及次梯度方法.不同的是两种算法在分解前对问题进行线性转化时所采用的编码方式:DaCSA采用的是线性编码方式,而DaQED采用的是二次编码方式.
算法循环执行Divide阶段与Coordinate阶段,直到超过预定时间或求得的解落在一定误差范围内,在每次循环中,算法会根据所有子问题的解,进行上界值(
在ADOPT等完备算法中,每个agent都根据伪树中相邻agent内变量的赋值状况以及当前代价值等信息,更加精确地对其内部变量的取之空间进行有效的搜索.虽然更精确的信息有助于提高搜索质量,但往往搜集信息的过程以及赋值的决策都需要消耗大量时间.为了能够提高搜索效率,基于抽样的算法首先将每个变量的每个可能取值看成一个样本,然后,借助于有限的信息首先对样本进行筛选,最后再通过概率选取等手段在可取的样本空间内进行变量赋值,进而削弱了决策和信息搜集带来的时间消耗.DUCT[
DUCT是一种分布式UCT算法.该算法首先构建一棵伪树,伪树中的每个节点都包含该变量所有取值下的样本.从根节点开始,伪树中的每个节点都会选择一个样本,并将样本中变量的取值信息包含在CONTEXT消息中依次传递至孩子节点.每个节点都包含2个计数器,分别记录在当前CONTEXT消息下,样本
本
D-Gibbs是分布式的Gibbs算法.该算法是一种基于马尔可夫链的蒙特卡罗算法,用于联合概率分布的近似估计,主要应用在需要进行最大后验概率估计的问题中.为了能够利用Gibbs求解DCOP,D-Gibbs首先将DCOP映射成为一个最大后验概率估计问题.与DUCT相同的是,该算法仍然是将问题转换成伪树后,自上而下进行消息传递;不同的是,每个节点进行变量选
取的过程有所不同.在D-Gibbs算法中,伪树中的每个节点记录样本选取的次数
这类算法以max-sum算法为基础.Max-Sum算法是一类消息传递算法,通过将问题转化成为一个因子图(如
Bounded max-sum(BMS)[
· 松弛阶段:首先,算法在原有因子图的基础上为图中的每一个边分配一个权重,这个权重用来衡量一个因子对于最优解决方案的影响程度;然后,算法找到一棵该权重下的最大生成树;接下来,原问题被转化成了一个拥有最大生成树的无环因子图.
· 求解阶段:利用max-sum算法求解松弛阶段中转化成的无环因子图.
· 边界阶段:对获得的解进行边界限定.
Weak Improved BMS[
Weak Improved BMS通过计算上界值,提高算法性能:在松弛阶段,算法将属于因子图,但是不属于生成树的约束进行改造,然后再将因子图转化成一个无环图.RN-BMS在BMS的基础上,通过引入信任度的概念提高变量赋值的准确性.在具体执行过程中,RN-BMS对问题中每两个相邻变量之间设置信任度,表示一个变量对邻变量中每个取值是否导致最优解的可能程度.结合信任度及约束函数,算法在松弛阶段对因子图进行转化.
在DCOP算法的研究中,除了在求解效率、求解质量等方面对算法进行改进外,也有研究从实际应用、执行环境等角度给出了相关改进策略.比如P-DPOP[
从
几种典型完备算法的求解策略
Solution strategy of some typical complete algorithms
算法 | ADOPT | ADOPT-ng | DPOP | MB-DPOP |
模型建立 |
〈 |
〈 |
〈 |
〈 |
模型转化 | 约束图 | 约束图 | 约束图 | 约束图 |
搜索空间 | 伪树 | 伪树 | 伪树 | 伪树 |
求解策略 | 最佳优先搜索 | 最佳优先搜索 | 动态规划 | 动态规划 |
通信机制 | 异步局部通信 | 异步局部通信 | 同步局部通信 | 同步局部通信 |
几种典型非完备算法的求解策略
Solution strategy of some typical incomplete algorithms
算法 | DSA |
|
DaQED | D-Gibbs |
模型建立 |
〈 |
〈 |
〈 |
〈 |
模型转化 | 约束图 | 约束图 | 约束图 | 约束图 |
搜索空间 | 约束图 | 约束图 | 约束图 | 伪树 |
求解策略 | 随机搜索 | 区域最优 | DaC框架 | 抽样策略 |
通信机制 | 同步局部通信 | 异步局部通信 | 同步局部通信 | 同步局部通信 |
几种典型完备算法的定性比较
Qualitative comparison of some typical complete algorithms
算法 | ADOPT | ADOPT-ng | DPOP | MB-DPOP |
消息数量 | 多 | 较多 | 较少 | 少 |
消息容量 | 小 | 较小 | 大 | 较大 |
几种典型非完备算法的定性比较
Qualitative comparison of some typical incomplete algorithms
算法 | DSA |
|
DaQED | D-Gibbs |
求解质量 | 差 | 较高 | 较高 | 高 |
为了更准确地对比算法之间的求解优势和性能区别,针对
几种典型完备算法的性能比较
Performance comparison of some typical complete algorithms
非完备算法的性能比较
Performance comparison of incomplete algorithms
从
从
完备与非完备算法的运行时间比较
Runtime comparison of complete and incomplete algorithms
除了前文给出的会议安排问题实例,DCOP同时适用于其他agent间的协作问题.这类问题通常难以建立全局模型,或者难以获取全局约束,并且面临环境动态变化等问题.例如,在无线传感器追踪网络应用实例中,每个传感器可感知搜索范围内所有目标,但同一时间仅能追踪目标中的一个,一个目标的位置要由多个传感器共同确定.然而,因为每个传感器的地理位置是固定的,只能根据自身信息或者局部信息进行决策,使得系统无法获取全局信息,难以建立全局模型进行求解.此时,如果以被追踪的目标作为agent,将同时追踪到该目标的传感器作为变量集合从属于不同agent中,就初步形成了该实例的一个DCOP模型.
DCOP的另一个实际应用是分布式资源分配问题.资源分配中将任务或资源分配给agent,资源的有限性导致agent间存在约束关系.文献[
在多agent系统中,每个自治的agent之间通过约束相关联,DCOP的求解目的就是寻找到满足这些agent间约束一致行为的最优组合.求解大规模的组合问题通常是NP难问题,而这类问题作为一类模型被广泛应用在实际生活中.本文较为全面地评述了DCOP的相关研究,给出了DCOP的定义、求解流程、算法分析以及DCOP的实际应用等.
自DCOP提出以来,DCOP算法的研究成为一项研究热点,大部分算法的提出都是根据执行过程中的某一方面(诸如存储方面、通信方面)有针对性地提高求解性能.然而,虽然算法的求解效果可观,但这些算法更多地集中于完备类别.目前,虽然国内对DCSP及其算法的研究已取得了一定成果,但在DCOP方面仍有欠缺,影响力 较小.
另一方面,随着近年来多agent系统应用范围的拓宽,DCOP的实际应用需求也随之加强.目前,DCOP算法的测试主要采用模拟仿真形式,虽然效果可观,但应对条件严格的实际问题仍有很大不足;其次,如何更好地对实际问题进行DCOP建模以便于算法求解,如何解决问题中更复杂的软约束,如何平衡agent之间通信数量与质量,如何应对环境动态变化对模型的实时性的影响以及隐私性带给算法的安全隐患等实际问题也亟待解决.
最后,通过对近10年DCOP算法的统计可以看出,给予质量保证的非完备算法俨然正成为一项研究热点.这些问题都为我们未来的研究提供了方向.
国家自然科学基金(61572116, 61572117); 国家科技支撑计划(2014BAI17B00); 宁夏回族自治区自然科学基金(NZ 13265); 中央高校东北大学基本科研专项基金(N120804001, N120204003)