证明：使用代理单步行为后的状态差异无法让分布式代理找出合理策略

对代理状态差异方法的解释

我们把一个代理$a$在世界状态序列为$\vec{w}$的justified perspective world写为$f_a(\vec{w})$，在代理$a$的观点中，代理$b$在世界状态为$w$的justified perspective world写为$f_b(f_a(\vec{w}))$。另外，一个问题模型的所有时间戳下的世界状态集合为$\vec{w_n} = \{w_0, w_1, w_2, ..., w_n\}$。

在某个代理$a$执行一个行为$act \in A(a,w)$后，所带来的下一个世界状态$w'=f(act, w)$。此处$w'$代表在$w$世界下进行$act$行为后所抵达的世界状态。

所谓代理状态差异，便是其他代理在代理$a\in Agt$做出行为$act$后，根据$diff_{w,w'}(f_{i,a}) \subseteq f_a(f_{i}(\vec{w'})) - f_a(f_{i}(\vec{w})) \subset G, i \in Agt$的内容来判断代理$i$相信$a$做出行为$act$的目的有哪些，并以此让代理$i$在下一次轮到自己的行动回合时所纳入考虑的$B(G_i)$。

证明

假如当前问题中有四个房间

graph LR

a(1) <--> b(2)
b <--> c(3)
b <--> d(4)

代理a在1，b在3，a要去3，b要去1。假设代理知道环境中的所有内容，但是不知道对方要去哪里。思考如何用去中心化的方式解决这个问题，要求：

• 代理之间不能沟通，交换任何信息
• 代理在完成目标时可以发出完成的信号

首先例举出$a$认为的所有可能的目标组合：

$$G_a: B_a loc(a) = 3\\ G_b: \left \{ \begin{array}{} B_bloc(b) = 1 \\ B_bloc(b) = 2 \\ B_bloc(b) = 4 \\ B_bloc(a) = 3 \end{array}\right.$$

以上通过组合后，会得到7个不同的Goal settings：

$$G_a: B_aloc(a) = 3\\ G_b: \left \{ \begin{array}{} 1. \left\{\begin{array}{} B_bloc(b) = 1 \end{array}\right.\\ 2. \left\{\begin{array}{} B_bloc(b) = 2 \end{array}\right.\\ 3. \left\{\begin{array}{} B_bloc(b) = 4 \end{array}\right.\\ 4. \left\{\begin{array}{} B_bloc(a) = 3 \end{array}\right.\\ 5. \left\{\begin{array}{} B_bloc(b) = 1 \\ B_bloc(a) = 3\end{array}\right.\\ 6. \left\{\begin{array}{} B_bloc(b) = 2 \\ B_bloc(a) = 3\end{array}\right.\\ 7. \left\{\begin{array}{} B_bloc(b) = 4 \\ B_bloc(a) = 3\end{array}\right.\\ \end{array}\right.$$

b认为所有的目标组合与a的类似：

$$G_b: B_b loc(b) = 1\\ G_a: \left \{ \begin{array}{} B_aloc(a) = 2 \\ B_aloc(a) = 3 \\ B_aloc(a) = 4 \\ B_aloc(b) = 1 \end{array}\right.$$

同样会有7个不同的Goal settings：

$$G_b: B_bloc(b) = 1\\ G_a: \left \{ \begin{array}{} 1. \left\{\begin{array}{} B_aloc(a) = 2 \end{array}\right.\\ 2. \left\{\begin{array}{} B_aloc(a) = 3 \end{array}\right.\\ 3. \left\{\begin{array}{} B_aloc(a) = 4 \end{array}\right.\\ 4. \left\{\begin{array}{} B_aloc(b) = 1 \end{array}\right.\\ 5. \left\{\begin{array}{} B_aloc(a) = 2 \\ B_aloc(b) = 1\end{array}\right.\\ 6. \left\{\begin{array}{} B_aloc(a) = 3 \\ B_aloc(b) = 1\end{array}\right.\\ 7. \left\{\begin{array}{} B_aloc(a) = 4 \\ B_aloc(b) = 1\end{array}\right.\\ \end{array}\right.$$

推演步骤

1. 首先是$a$行动，由于a对b的目标没有信念，所以a只会将b的目标设为与自己相同，因此，此时a在进行local planning的时候使用的goal set为：

G_a: &B_a loc(a) = 3\\ G_b: &B_b loc(a) = 3

​ 此时，a在经过BFS算法之后得出自己此时最优的策略为$stay$，故，a会选择$stay$

2. $a$在$stay$之后，其他代理会本地地算出$diff(f_{i,a})$，由于本问题只有a和b两个代理，因此只需要算$diff_{w,w'}(f_{b,a})$。很明显可以看到，$stay$没有将世界状态发生任何变化，因此b没有更新本地的目标信念。

3. 现在是$b$行动，b对a的目标同样没有信念，因此接下来的方法与a相同，b此时的goal set为：

   G_a: &B_aloc(b) = 1\\ G_b: &B_bloc(b) = 1

   此时b在经过BFS算法后也得出自己此时最优的策略为$stay$，故，b会选择$stay$

4. 不难看出，该过程会一直循环下去，卡主不动。

因此，该方法并无法保证能够找到目标路径，会出现死循环的现象。