Decentralized Epistemic Planning文档

Decentralized Epistemic Planning基础定义

Classic Planning

一个Classical Planning实例（Classical Planning问题）可以用一个元组表示

$$\mathcal{P} = \langle S, s_0, S_G, Act, A, f, c \rangle$$

其中$S$代表实例中所有可能的状态，$s_0 \subset S$代表初始状态的集合，$S_G\subseteq S$代表目标状态的集合，$A(s)\subseteq Act$代表在状态集$s\in S$下能够做出的行为集$A(s)$，$f$代表转移函数，$s' = f(a, s)$代表在状态$s$下通过行为$a\in A(s)$ 能够到达的下一个状态$s'$，$c(a,s)$代表在状态$s\in S$下采取行为$a$所需要的代价。

Classical Planning中的一个核心表达结构可以采取STRIPS中定义的基本行为模板，其中定义如下：

action action_name(params)
	prec (
		states...
	)
	effs(
		effects...
	)

以move为例子，假设现在要模拟一个代理a从一个房间r1移动到另一个房间r2，那么在状态空间中会有如下变化：

• agent_at(a, r1) = 1 -> agent_at(a, r1) = 0
• agent_at(a, r2) = 0 -> agent_at(a, r2) = 1

做出该行为的先决条件为：

• connected(r1, r2) = 1
• agent_at(a, r1) = 1

以上便表示了一个行为所需的基本内容，而定义move行为模板的方法如下：

action move(?a - agent ?from ?to - room)
	prec (and
			((agent_at ?a ?from) = 1)
			((connected ?from ?to) = 1)
	)
	effs(and
			((agent_at ?a ?from) = 0)
			((agent_at ?a ?to) = 1)
	)

实际上以上只是我在pddl中倾向的写法，实际上并不需要写成这样。但是这样会让模型逻辑变简单一些，因此就这么写了。

可以看出，一个行为可以用一个元组来表示$act \in Act = (par, pre, eff)$，分别代表了参数，先决条件和影响。

常规的Classical Planning的解决方案已经在AI界中广泛讨论，有各种解决方案能处理这类问题。然而，Classical Planning却无法解决代理的信念问题

Epistemic Planning

Epistemic Planning意为认知规划，通常用于讨论代理对其他代理的信念问题，用另一种方法说， 可以成为代理的现实世界的认知与嵌套认知问题。

一个Epistemic Planning可以被如下表示

$$\mathcal{P} = \langle S, Agt, s_0, S_G, O, Act, A, f, c\rangle$$

其中与Classical Planning中相同符号的也代表相同意思。此外，$\alpha \in Agt$表示代理，$O(\alpha, s)$代表观察函数，用于表示代理$\alpha \in Agt$在现实状态$s \subset S$下所能观察到的内容。

在继续讨论之前，需要先讲一下基本的Epistemic Logic（认知逻辑）

Epistemic Logic

在Fagin等人的研究中，他们提出了一套对认知逻辑的正式定义，其中数学表达如下

$$\varphi :== p \mid \varphi \wedge \varphi \mid \neg \varphi \mid K_i\varphi \mid B_i\varphi$$

其中，$p \in Prop = \{p_1,p_2,...\}$为有限的基本逻辑（事实）集合。$i \in Agt = \{a_1, a_2, ...\}$为代理集合。$K_i\varphi$表示代理$i$知道某个逻辑$\varphi$。$B_i\varphi$代表代理$i$相信某个逻辑$\varphi$。该数学表达中的连接符号可以用常规的逻辑符号理解。不难看出，这套认知逻辑中展示了信念有嵌套性，比如$K_aK_b\varphi$也是存在的，用于代表$a$知道$b$知道逻辑$\varphi$。

在这里解释一下$\varphi$。这个东西可以用于表示一个truth，比如某个人在某个地方：$\varphi ::= p = (agent\_at(a, r1))$，而$K_i\varphi$则可以被理解为代理$i$知道代理$a$在房间$r1$。然而，代理的理解并不一定正确，就好比你也许只是以前见过某个人在上海，就如今依然还是相信它在上海一样。这件事并不一定正确。

我们可以使用Kripke structure来表示逻辑系统，Kripke structure通用可以用一个元组表示

$$M = (W, \pi, R)$$

其中，$W$是一个非空的可能世界集合，在认知逻辑中，可能世界并不单单指的是现实世界中的状态，也同时表示代理的认知世界中的状态。$\pi(\varphi,w)$为一个二元评估函数，用于表示$\varphi$在世界$w$中是否为真。$R = \{R_1,R_2,...\}$表示可能世界$W$之间的二元可达性关系。如果$(w, w')\in R, w\in W$，则表示世界$w$和$w'$时双向可达的。

其余的有关于信念$B$和知识$K$的系统定义，分别名为$KD45_n$和$KT45_n$。其定义较为复杂，便不在此做赘述。

如上便基本讲完了认知规划中的基本逻辑，接下来讲认知规划的功能。

Motivation

Classical Planning中，所有的状态都是基于现实世界的，问题中代理个人的视角和信念的表示则需要使用额外的状态空间来表示。通常来说，Classical Planning也可以用于解决代理之间的信念问题，但是那通常会让问题的状态空间急剧变大，难以维护正常的运行。

Epistemic Planning采用认知逻辑对基本逻辑$\varphi$ 的表达方式进行了扩展。这解决了经典规划中添加信念逻辑导致状态空间剧增的问题。

在Epistemic Planning中，我们暂时不考虑$c(a,s)$的问题，即假设所有$c(a,s) = 0$。