对neutral settings下的epistemic problem的规划逻辑的一个尝试2

先前有提出过一个解决代理猜测其他代理目标的方法，那个方法在时间之后以失败告终，因此此处再提出另一个可能的方法。

不过此方法目的并不是为了仅仅是猜出目标，还需要考虑如何解决代理之间出现死循环的情况。

事实上，从现实的角度来说，在其他人不告诉你他在做什么的情况下，你根本无法准确猜出对方的目的。这种情况在复杂问题的情况下尤为明显。因此，我们更应该想出一个方法，该方法只需要有如下功效即可：

• 能够帮助代理做判断
• 能够让代理距离他的目标更近
• 有实际意义

由于我们假设模型是一个partial observable且decentralized的设定，因此带来了很大限制的同时，也带来了更好地概括性。

接下来描述新的想法

Idea

考虑一个目标反向传递的方法

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

graph LR

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

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

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

假如先考虑a的视角，它可以不考虑b的目标，直接本地生成一套最优行为流程：

$\{a: stay, b: move(3,2), a: stay, b:move(2,4), a:move(1,2), b:stay, a:move(2,3)\}$

不难发现，a想要抵达3，至少需要抵达2，需要抵达2没至少需要在1或4中。当然，抵达目标不能有人。

再考虑b的视角，它不考虑a的目标，本地最优行为流程为：

$\{a:move(1,2),b:stay,a:move(2,4),b:move(3,2),a:stay,b:move(2,1)\}$

明显可以看出，在a的视角中，如果要用最优路径完成目标，则需要让b先动。而在b的视角中则需要让a先动。他们观念具备冲突，因此在规划过程中会出现死循环。

如果对于单一的MAPF问题来说，该问题还是很好解决的，然而现在需要考虑的是一个通用的，全面的解决方案。该解决方案中需要考虑：

• 代理无法观察到所有状态
• 代理的目标颇为复杂
• 代理的目标为认知目标，比如a的目标是让b有一个错误的信念

该问题最好的解决方案就是让代理去用某种方法猜其他代理的目标是什么，以达成合作行为。

假设问题中每一个代理的goals最终都必然可以完成，且所有代理都清楚这一点。在a的视角中，它可以想出b所有可能的goals

$$\{B_bat(b,1)\}\\ \{B_bat(b,2)\}\\ \{B_bat(b,4)\}\\ \{B_bat(a,3)\}\\ \{B_bat(b,1), B_bat(a,3)\}\\ \{B_bat(b,2), B_bat(a,3)\}\\ \{B_bat(b,4), B_bat(a,3)\}\\$$

由于模型在一开始就会定义最大信念深度，因此也许可以用如下方法

反选

在任何代理行动后，所有代理都会去尝试反选自己对其他所有代理的目标信念。比如说，现在b:move(3,2)，但是b的信号灯没有亮。这说明b没有完成目标。因此，a可以根据自己视角中b的视角来推断，对b来说当前世界状态有哪些状态机不是它的目标。比方说，在a的视角中，a相信b相信b在2，也相信a在1（只考虑与目标有关的状态）。因此，在将这两个状态进行超集转换后可以得到：

$$\{(B_bat(b,2)),(B_bat(a,1)), (B_bat(b,2), B_bat(a,1))\}$$

其中，与a对b的目标信念相同的仅有$\{B_bat(b,2)\}$因此，a可以将该信念排除，以后都不用再去考虑这个信念。

这是将目标信念最大深度设为1的情况，假如为2，则让推测更深一层。也就会变成a相信b相信a相信… $B_aB_bB_a...$，然后将其中与目标状态有关的内容超集转换后，排除错误目标。

不过，如果观察到b的完成信号亮起，比如a在4，b在1，此时，在a的视角中，$\{B_bat(b,1),B_bat(a,4)\}$都存在，但是由于a知道自己的目标是at(a,3)，并且a知道所有人的目标都能在最终完成，因此$B_bat(a,4))$将会被排除。（其实同样转化为超集后正选即可）。

难点

1. 也许会出现无法过滤掉任何目标而导致行为不断重复的现象：
   • 可以限制代理行为，避免它前往自己已知的世界状态。（该方法经过测试后会造成更多问题，故放弃该方法）
   • 也许可以参考Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity 论文中提到的方法，让代理通过观察其他代理的行为与自己预期的行为来对最终策略进行更新。（该方法与我们目前的研究方向和假设不匹配，故而不采用该方法）
2. 在一个代理做出行动后，其他代理将基于他们在当前世界状态下是否可以看见该代理来记录该代理的行为。比如，在之前提到的问题中，假如a一开始做出了stay行为，那么由于b能够看见a，因此b会记录下当前$f_b(w)$下a可能的行为。假设下一次a在当前状态下又move了，那么也会把move纳入行为集合中。
   • 在进行local BFS search时，代理行动的每一步之前都会去检查当前代理在初步代理的状态-行为集合中是否存在以往做过的行为，如果有，则初步代理会人外当前代理的行为依然会是其中之一。此处讲述的有些难懂，可以一步到另一篇文章中看详细内容：认知状态-行为集合以限制本地模拟时其他代理的可能动作