代理在neutral settings下如何推测其他代理的goals

Decentralized Epistemic Planning构成

$$\mathcal{P}_D = <S, Agt, s_0, G, O, Act, f, c>\\ \alpha \in Agt = <S_G>\\ \Rightarrow \mathcal{P}_D = <S, \{S_G^1, S_G^2, ... , S_G^n\},S_0, G, O, Act, f, c>\\ \text{where}\ S_G^n \subseteq G \subset S,\quad S_0 \subset S$$

简单来说，基本构造就是在基本Decentralized Planning的基础上加入了一个$G$用于限制可能的goal集合。在实践中，这个$G$用于存储可被接受为Goal的状态名。

检验Goal Set是否可被解决

通常来说，可以设计一个BFS算法，然后验证该Goal Set是否有解，如果有解，则代表可解，反之代表不可解。

寻常的BFS可以判断当前现实世界状态是否在以前出现过。然而，在DEP问题中，这有些许不同。

在DEP中，我们呈一个代理对当前世界的认知为$f_a(\vec{w})$，即代表代理$a$对世界序列$\vec{w}$的justified perspective。该理论认为，一个代理会相信他最近看见的事物。比方说，如果代理a现在看见了桌上有一个苹果，接下来他离开了房间。如果过程中没有任何证据可以说明这个苹果已经不在那个桌上了，则该代理依然会 认为苹果在那个桌上。

DEP中检测当前世界状态对于当前执行行为的代理来说是否在以往出现过的机制如下：假设世界状态序列为$\vec{w}$，世界中有{a,b}两个代理。

• 算法会为每一个代理维护一个独立的已观察世界集合$\mathcal{W_{a}}$，其中包括了在他的回合时，所有代理的$f_{agt}(\vec{w})$。
• 如果当前$\forall_{agt \in Agt} {f_{agt}(\vec{w})} \in \mathcal{W_{a}}$，则代表代理a以前见过当前世界，则不会被算法继续expand。

推测其他代理的goals

找到所有可能的goals设定

由于代理知道自己的goals，因此在生成全局goal set时，只需考虑其他agent可能的goals。在初始化模型时，每个Agent都会为所有可能的goals set。

过滤goals

这便是研究的难点所在了。现有思路如下：

• 每当一个代理行动，程序便会让所有其他代理观察该代理：
  • 如果能看见该代理的行为，则根据上一次看见该代理时其信念状态和这一次的信念状态的差异，判断该代理可能想要做什么。
  • 如果看不见该代理的行为，则不做更新。

现考虑一个世界状态：两个连通的房间，两个代理，一个物品。代理只能看见与自己在同一个房间的其他代理的行为，但是他们总是能知道其他代理和所有物品的所在位置。goal set中只会存在holdby

假设a的目标为a相信b拿着物品，b的目标是b相信自己没拿物品。

现在的世界状态为：a与b在同一房间内，a拿着物品，b没拿物品。

假设现在是a行动的轮次，a的局部bfs会判断a当前需要做的是把物品放下来。

此时，b观察到a把东西放了下来，b对a的信念状态会更新一个$holdby(i,a) = 1 \rightarrow holdby(i,a) = 0$。但是b却观察到a的goal complete信号灯没有亮，因此b首先会知道此时a并没有完成自己的任务，因此b会生成在此状态下，下一次轮到a前，所有可能的未来状态。其中对a有信念更新的状态便是b认为a可能的goals。

比如说，a放下东西后，在下一次轮到a前，b会行动一下。而b的行动中有pick_up, move 和stay三种。其中，move和stay都对a来说没什么帮助：

• stay就不会对世界状态带来改变，因此对a的信念也不会有任何改变

• move虽然会对b的所在位置带来改变，但这并不在goal set的考虑中，所以对a的goal相关信念也不会有任何改变

• pick up会让b拿起物品，这对a的goal相关信念发生了改变

所以b会认为pick up后的某些更新状态是a的goal。其中包括了$holdby(i,b)=1$，至此，b会在生成虚拟世界时，将所有包含了$B_aholdby(i,b)=1$的goal set统一进行考虑，最后应当得出结论为pick up。

因此，经过一回合行动后，变成了：a没拿物品，b拿着物品。

然而，在b拿起物品后，他的goal complete信号被关闭了。a也可以发现这个现象，因此a可以判断是b的上一个行为带来的改变让b无法完成任务。

而pick up带来的变化为:$holdby(i,b) = 0 \rightarrow holdby(i,b) = 1$

因此，a会以b上一个世界中的状态作为a对b的goal信念。因此a的goal set中会加入一个$B_bholby(i,b)=0$

如果该问题设定的max belief depth为2，则可能会多一个$B_bB_aholdby(i,b)=0$，但这都是后话。

此时轮到了a的回合，a此时的goal set中有$B_aholdby(i,b)=1, B_bholdby(i,b) = 0$。根据现有条件，a应该做的是move。

b观察到a离开了房间，由于b无法再看到a，所以b不知道a的信号状态，因此b不对goal set进行更新。此时，b的goal set中有$B_bholdby(i,b)= 0, B_aholdby(i,b) = 1$。要完成这个目标，只需放下物品即可。

至此，问题解决。

两个方案

上面一个部分是在代理一开始就能够观察到其他代理行为的情况。假设代理没有观察到其他代理的行为，此时该怎么办？

现有两个方案：

1. 将其他代理的goals设为自己的Goal，但是做一下转换
2. 对所有可能的goal set都做一次模拟，统计模拟数据，得出结果。

现在先试一下第一种方案。

结果证明该方法会出现一些问题，在某些极端情况下，代理可能会陷入死循环。（比如多智能体寻路的情况）