读书笔记 （二） ———Fundamentals of Multiagent Systems with NetLogo Examples by Prof. Jose M Vidal

chapter 2 分布式约束
1 分布式约束满足
1.1 过滤算法
1.2 基于归结的调和算法 consistency
1.3 异步回溯
1.4 异步弱承诺？
1.5 分布式突破？
2 分布式受限优化
2.1 Adopt
2.2 OptAPO

多智能体系统（MAS）为一组自主智能体具有局部认知，通过彼此协调完成全局目标。MAS目标在于每个个体根据局部信息调整局部状态保证系统的整体状态效能最大。
每个agent只能局部通信，并且各自的行为取决于其他agent的行为，如分布式传感器，儿童排队等。众多多智能体问题可以被归结为分布式受限问题。

这一章研究分布式搜索。

1 分布式约束
约束满足问题（CSP）：给定一组变量x1,x2,...,xn,分别属于定义域D1,D2,...Dn。一组布尔限制P满足pk(xk1,xk2,...,xkj)->{0,1},找到一组变量的分配保证满足所有布尔限制条件为真。
一个全局的算法：深搜

分布式约束满足问题（DCSP）: 假定每个agent负责CSP中的一个变量，每个agent负责寻找其他agent的值，通过通信获得其他人的值
一般DCSP中，
a) agent只能和邻居（共享同一约束的agent）通信，个别算法要求完全通信
b) agent知道所有与其相关的约束。

1.1 过滤算法
每个agent与邻居交换信息，如果成功消除其取值范围中的一个或多个值，通知邻居他的新值域。
过滤算法一定可以停止，因为只有有限个值，每消除一个就会发布一个信息。但是FA不一定会给出结果，可能会进入一个谁也无法消除的尴尬境地，也就无法得到结果。
（个人理解就是可以做初级数独，做不了高级数独或错误的数独）

1.2 基于超归结的调和算法
k-调和： 给定任意k-1个满足所有约束的变量实例，可以找到任意第k个变量实例保证所有k个变量满足约束。（k-1个确定好后，剩余的任选一个都可以找到值满足约束）
强k-调和： 若其是j-调和，j<=k。

超归结规则
union(A1,A2,A3,...Am)
~(intersection(A1,A11,A12,...))
.
.
.
~(intersection(Am,Am1,Am2,...))
_______________________________________
~(intersection(A11,...,A21,...Am1,...))

A1,A2等可以代表agent可取的状态 A11，A12代表约束 归结后的约束成为nogood

将过滤算法中两两比较算法的方式转换为交换规则，通过推理得到新的nogood

该算法的缺点在于慢慢慢，缺少nogood分析顺序的指导，同时该问题的停止条件十分缓慢，需要等待所有智能体都无法再生成新的nogood

1.3 异步回溯 ABT
回溯算法： 深度优先，遇到冲突后退回一步，更正后继续执行。 （不断递归）
ABT是集中深搜算法的分布式异步版本（yokoo 2000）。ABT对深搜本身进行了一定修正，保证搜索顺序是经过适当调整的，有利于减少回溯的次数。具体来说，通常希望对树顶元素的变量取值为包含在多个约束条件内的值。

每个agent被分配一个全局优先序列，分别负责一个局部变量xi，同时不断监控邻居的变量（local-view）。算法初始邻居定义为共享相同约束条件的agents，但会随着算法进行不断增加。agent通过交互的方式获得邻居的消息。
ABT中各agent只进行三类消息的交互：
a) HANDLE-OK?(J,xi) 询问agent J选择值xj是否冲突
b) HANDLE-NOGOOD (j,nogood) j报告无法找到满足约束的值，受到nogood限制
c) HANDLE-ADD-NEIGHBOR (j) 要求增加j为邻居

算法：。。。。。。。

ABT算法完整：ABT或者给出存在的解，或者无解时给出适当的信息。

缺点：
a) 优先级固定后，下等agent干活多，上等干活少。
b) 上层的取错值后导致下层穷举才可以。

两个变种：
a) 生成nogood的时候，只生成可能得到结果的nogood
b) kernel ABT，无法改变邻居的情况

1.4 异步弱承诺？

AWC算法即ABT的一个变种，通过不断修改优先级顺序，实现计算任务的平均分配。

1.5 分布式突破？

采用登山算法 hill-climbing 初始随机分配给各agent值，随后不断降低约束的违反。
分布式的hill-climbing要求各agent并行更改值，同时向邻居发送新值。但会出现局部极小值的情况，类似nash均衡，无法通过修改单个agent的值进行进一步优化。当出现极小值的情况时，需要各agent广播这一情况，同时还要判断所有agent都处于这种情况，解决这一问题需要更复杂的算法与大量的通信。

分布式突破（distributed breakout）绕过这一方法，通过辨识半-局部极小值（quasi-local minimum）的情况。
定义：agent xi处于quasi-local minimum情况意味着他当前违反了某些限制条件，同时他与他的邻居无法通过修正使得系统总体代价函数更低。
意思就是某个个体发现当前的状态不满足要求，同时自己与邻居都无能为力。

quasi-local minimum ~=> local minimum
local minimum => quasi-local minimum for1 agent at least

分布式突破不是完整算法，可能会卡在某个极小点无法进一步执行，无法找到解

2 分布式受限优化 COP NP-complete

与约束满足问题类似，但是限制条件返回值不是“满足”或“不满足”，而是一个实数。目标在于降低约束函数的返回值，使得违反约束的值最低。

定义： （受限优化问题 COP） 给定一组属于定义域D1,D2,...Dn的变量x1,x2,...,xn以及一组约束P,pk(xk1,xk2,...,xkj) -> R, 寻找所有变量的分配使得约束函数值之和最小

最主要的方法是分枝定界的方法（branch and bound）

定义：（DCOP） agent各负责一个变量，通过局部通信找到使得值最小的方法。

2.1 Adopt

将智能体根据受约束的关系形成自上而下类似树的图结构，但并不是树，只是要求每个节点都只有一个parent节点多个son节点。初始给定各节点初值，以及对代价函数上下限的估计，估计包括该节点在内的所有子节点的代价之和。
然后主要循环如下三步
a) 每个节点向子节点发布自身状态。子节点根据收到parent的状态决定自己的局部最优值（使得局部代价最小）。
b) 各子节点向父节点回馈自己估计的代价上下界限，下届好估计，但上届不好判断。
c) 所有节点根据收到的回馈进行判断，如果有的上界不等于下届，需要进行调整回溯

真正的Adopt算法还有Threshold来约束回溯，比文中所述要麻烦许多。

2.2 OptAPO

就是当agent之间出现冲突的时候，将冲突的agent放到一起，并推举一个协调官（mediator）。协调官负责根据所有冲突的人进行计算，找到一个你好我好大家好的办法。
最坏的情况就是全局集中搜索。