基于成本的行动概率逻辑程序查询解答

### 基于成本的行动概率逻辑程序查询解答 在逻辑与概率的交叉领域中，基于成本的查询解答在行动概率逻辑程序里有着重要的应用。下面将详细介绍相关的基础概念、语义、问题定义以及算法。 #### 1. 基础概念 在开始之前，先明确一些基本的语法定义。我们假定存在一个逻辑字母表，其中包含： - 一个有限的常量符号集合 \(L_{cons}\)。 - 一个有限的谓词符号集合 \(L_{pred}\)，每个谓词符号都有其对应的元数。 - 一个无限的变量符号集合 \(L_{var}\)，不过不允许出现函数符号。 术语、原子和文字的定义遵循常规方式。同时，将 \(L_{pred}\) 划分为两个不相交的集合：行动符号集合 \(L_{act}\) 和状态符号集合 \(L_{sta}\)。 下面是一些重要的定义： 1. **行动公式**： - 一个（基）行动原子是一个（基）行动公式。 - 如果 \(F\) 和 \(G\) 是（基）行动公式，那么 \(\neg F\)、\(F \land G\) 和 \(F \lor G\) 也是（基）行动公式。 所有可能的行动公式集合记为 \(formulas(B_{L_{act}})\)，其中 \(B_{L_{act}}\) 是与 \(L_{act}\)、\(L_{cons}\) 和 \(L_{var}\) 相关联的 Herbrand 基。 2. **带注释的行动公式（ap - 公式）**：如果 \(F\) 是一个行动公式，且 \(\mu = [\alpha, \beta] \subseteq [0, 1]\)，那么 \(F : \mu\) 被称为带注释的行动公式（或 ap - 公式），\(\mu\) 被称为 \(F\) 的 ap - 注释。 3. **世界/状态**： - 世界是任何有限的基行动原子集合。 - 状态是任何有限的基状态原子集合。 4. **ap - 规则**：如果 \(F\) 是一个行动公式，\(B_1, \ldots, B_n\) 是状态原子，\(\mu\) 是一个 ap - 注释，那么 \(F : \mu \leftarrow B_1 \land \ldots \land B_m\) 被称为 ap - 规则。若该规则名为 \(r\)，则 \(Head(r)\) 表示 \(F : \mu\)，\(Body(r)\) 表示 \(B_1 \land \ldots \land B_n\)。 5. **ap - 程序**：一个行动概率逻辑程序（简称 ap - 程序）是一个有限的 ap - 规则集合。如果 \(\Pi'\subseteq\Pi\)，则 \(\Pi'\) 被称为 \(\Pi\) 的子程序。 下面是世界和状态的示例： - 世界示例：\(\{kidnap(1)\}\)、\(\{kidnap(1), tlethciv(1)\}\)、\(\{\}\)。 - 状态示例：\(\{forstpolsup(0), elecpol(0)\}\)、\(\{demorg(1)\}\)、\(\{extsup(1), elecpol(1)\}\)。 #### 2. ap - 程序的语义 使用 \(W\) 表示所有可能的世界集合，\(S\) 表示所有可能的状态集合。下面定义状态对规则体的满足情况以及世界对行动公式的满足情况： 1. **状态对规则体的满足**：设 \(\Pi\) 是一个 ap - 程序，\(s\) 是一个状态。当且仅当 \(\{B_1, \ldots, B_M\} \subseteq s\) 时，称 \(s\) 满足规则 \(F : \mu \leftarrow B_1 \land \ldots \land B_m\) 的体。 2. **世界对行动公式的满足**：设 \(F\) 是一个基行动公式，\(w\) 是一个世界。当且仅当以下条件满足时，称 \(w\) 满足 \(F\)： - 若 \(F \equiv a\)，其中 \(a \in B_{L_{act}}\)，则 \(a \in w\)。 - 若 \(F \equiv F_1 \land F_2\)，其中 \(F_1, F_2 \in formulas(B_{L_{act}})\)，则 \(w\) 满足 \(F_1\) 且 \(w\) 满足 \(F_2\)。 - 若 \(F \equiv F_1 \lor F_2\)，其中 \(F_1, F_2 \in formulas(B_{L_{act}})\)，则 \(w\) 满足 \(F_1\) 或 \(w\) 满足 \(F_2\)。 - 若 \(F \equiv \neg F'\)，其中 \(F' \in formulas(B_{L_{act}})\)，则 \(w\) 不满足 \(F'\)。 3. **ap - 程序相对于状态的约简**：设 \(\Pi\) 是一个 ap - 程序，\(s\) 是一个状态。\(\Pi\) 相对于 \(s\) 的约简，记为 \(\Pi_s\)，是集合 \(\{F : \mu | s\) 满足 \(Body\) 且 \(F : \mu \leftarrow Body\) 是 \(\Pi\) 中某个规则的基实例 \(\}\)。该集合中的规则在状态 \(s\) 中被认为是相关的。 ap - 程序的语义基于可能世界的概念。给定一个 ap - 程序 \(\Pi\) 和一个状态 \(s\)，可以定义一个与 \(s\) 相关联的线性约束集合 \(LC(\Pi, s)\)。每个能用语言 \(L_{act}\) 表达的世界 \(w_i\) 都有一个相关联的变量 \(v_i\)，表示其实际发生的概率。\(LC(\Pi, s)\) 包含以下约束： 1. 对于 \(\Pi_s\) 中形式为 \(F : [\ell, u]\) 的每个 \(Head(r)\)，\(LC(\Pi, s)\) 包含约束 \(\ell \leq \sum_{w_i \in W \land w_i \models F} v_i \leq u\)。 2. \(LC(\Pi, s)\) 包含约束 \(\sum_{w_i \in W} v_i = 1\)。 3. 所有变量都是非负的。 4. \(LC(\Pi, s)\) 仅包含上述 1 - 3 描述的约束。 当且仅当 \(LC(\Pi, s)\) 在实数域 \(\mathbb{R}\) 上可解时，\(\Pi_s\) 是一致的。 下面是一个关于 \(LC(\Pi, s)\) 和 ap - 公式蕴含的示例： 考虑一个 ap - 程序 \(\Pi\) 和状态 \(s_2\)。所有可能的世界为：\(w_0 = \{\}\)、\(w_1 = \{kidnap(1)\}\)、\(w_2 = \{tlethciv(1)\}\)、\(w_3 = \{kidnap(1), tlethciv(1)\}\)。假设 \(p_i\) 表示世界 \(w_i\) 的概率，那么 \(LC(\Pi, s_2)\) 包含以下约束： - \(0.5 \leq p_1 + p_3 \leq 0.56\) - \(0.49 \leq p_2 + p_3 \leq 0.55\) - \(p_0 + p_1 + p_2 + p_3 = 1\) 一个可能的解是 \(p_0 = 0\)、\(p_1 = 0.51\)、\(p_2 = 0.05\)、\(p_3 = 0.44\)。对于公式 \(kidnap(1) \land tlethciv(1)\)，它仅被世界 \(w_3\) 满足，该公式以概率区间 \([0, 0.55]\) 被蕴含。 #### 3. 基于成本的有界查询解答问题 假设 \(s\) 是一个状态（当前状态），\(G\) 是一个目标（行动公式），\([\ell, u] \subseteq [0, 1]\) 是一个概率区间。我们感兴趣的是找到一个新的状态 \(s'\)，使得 \(\Pi_{s'}\) 蕴含 \(G : [\ell, u]\)。不过，\(s'\) 必须可以从 \(s\) 到达。在本文中，假设将当前状态转换为另一个状态存在成本，并且这种转换有相应的成功概率。为了对其进行建模，将使用三个函数： 1. **转移函数**：任何函数 \(T : S \times S \to [0, 1]\)。 2. **成本函数**：任何函数 \(cost : S \to [0, \infty)\)。 3. **转移成本函数**：相对于转移