利用规划图提高经典人工智能规划复杂度

作者 | Debby Nirwan

编译 | VK 来源 | Towards Data Science

利用一个新的搜索空间，规划图可以提高经典的规划方法的表达能力和复杂性的问题。

介绍

人工智能规划的经典方法是利用状态空间和规划空间来寻找解决规划问题的方案。

在状态空间搜索中，初始世界状态通过应用适当的操作进行多次转换，直到找到一个解决方案以达到目标或搜索算法终止并返回失败。我们可以使用诸如BFS、DFS、Dijkstra、A*等搜索算法。

得到的解决方案是一系列操作(action)，当应用这些操作时，会在一个或多个步骤中将初始世界状态转换为目标状态。

另一个搜索空间是规划空间，我们将规划作为我们的节点，试图解决开放（未解决）目标和缺陷。

这种方法本身就相当复杂，我们这里不讨论细节，如果你有兴趣了解更多，可以阅读以下文章：

https://medium.com/swlh/plan-space-search-2d877b4ab231

改善空间大小

在《Automated Planning: Theory and Practice》一书中，Malik、Dana和Paolo提到，由于表现力和复杂性的原因，经典方法的研究停滞不前，规划图-一个新的搜索空间，允许改进搜索空间的大小，从而为解决更复杂的规划问题开辟了一条途径。

我们将在下面的小节中详细介绍，以了解它是如何改进经典规划方法中发现的问题的。

码头工人机器人规划领域

对于我们的示例，我们将使用简化的Dock Worker Robots（DWR）域和问题，这在AI规划教程中经常使用。

在这个领域，我们有两个机器人，robr和robq，两个容器conta和contb，以及两个位置loc1和loc2。

有三种可能的操作：

• load(location, container, robot)：将容器装载到机器人上
• move(location, location)：从一个位置移动到另一个位置
• unload(location, container, robot)：从机器人上卸载容器

操作的前提条件和效果的详细信息可以在下面的pddl文件中看到。

我们还有五个谓词来表示状态：

• adjacent(loc1, loc2)-这是关于位置的静态信息
• atl(robot, location)）-描述机器人的位置
• loaded(robot, container)-机器人是否装载以及机器人上的容器
• unloaded(robot)-机器人已卸载
• iin(container, location)-描述容器的位置

我们使用PDDL（planningdomaindefinitionlanguage）来表示我们的规划域和规划问题。下面是我们感兴趣的领域的pddl文件。

;; Specification in PDDL1 of the DWR domain

(define (domain dock-worker-robot-simple)
 (:requirements :strips :typing )
 (:types
  location      ; there are several connected locations in the harbor
  robot         ; holds at most 1 container, only 1 robot per location
  container)

 (:predicates
   (adjacent ?l1  ?l2 - location)       ; location ?l1 is adjacent ot ?l2
   (atl ?r - robot ?l - location)       ; robot ?r is at location ?l
   (loaded ?r - robot ?c - container )  ; robot ?r is loaded with container ?c
   (unloaded ?r - robot)                ; robot ?r is empty
   (in ?c - container ?l - location)    ; container ?c is within location ?l
   )

;; there are 3 operators in this domain:

;; moves a robot between two adjacent locations
 (:action move
     :parameters (?r - robot ?from ?to - location)
     :precondition (and (adjacent ?from ?to) (atl ?r ?from) )
     :effect (and (atl ?r ?to)
                    (not (atl ?r ?from)) ))

;; loads an empty robot with a container held by a nearby crane
 (:action load
     :parameters (?l - location ?c - container ?r - robot)
     :precondition (and (atl ?r ?l) (in ?c ?l) (unloaded ?r))
     :effect (and (loaded ?r ?c)
                    (not (in ?c ?l)) (not (unloaded ?r)) ))

;; unloads a robot holding a container with a nearby crane
 (:action unload
     :parameters (?l - location ?c - container ?r - robot)
     :precondition (and (atl ?r ?l) (loaded ?r ?c) )
     :effect (and (unloaded ?r) (in ?c ?l)
                    (not (loaded ?r ?c)) )) )

现在让我们开始深入研究规划图及其规划器。

规划图

规划图是基于可达性分析的思想，即从一组初始状态计算一组状态是否可达的过程。

让我们一步一步地通过一个例子来理解这个概念。首先，这是我们的初始状态：

我们使用谓词来表示我们的世界状态（为了简单起见，我们省略了相邻的谓词）：

• in(conta, loc1)
• in(contb, loc2)
• atl(robr, loc1)
• atl(robq, loc2)
• unloaded(robr)
• unloaded(robq)

我们想知道这个状态是否可以到达：

我们没有展示图片中的机器人，因为我们不关心它们的位置，我们只对容器的位置感兴趣。我们是这样表示的：

• in(contb, loc1)
• in(conta, loc2)

可达树

现在，最简单的方法是使用可达性树。我们从初始状态（根节点）开始，搜索状态的适用操作（边），然后生成预测状态（子节点），并对所有子节点重复该过程，直到达到指定的深度。

这是深度为1的可达树。

这是深度为2的可达树。

我们可以看到，这并不能很好地扩展，当我们增加深度时，节点的数量会爆炸。而且，我们还没有找到这个深度的目标，我们需要进一步扩大它。

可达图

我相信你会认为，我们可以用一个图来改进它，因为有些节点确实是重复的。这是depth=2的图形版本。

虽然略有改进，但要达到我们的目标（红色节点），我们需要depth=6，如下所示：

很可怕，不是吗？它的规模确实很大，因为当我们增加深度时，复杂程度会增加，如果我们想解决更复杂的问题，这在某些时候变得不切实际。

规划图的可达性

规划图的思想是带松弛的可达图。在每一个深度（或者称为层次）它不使用单个状态，而是使用状态的并集，因此我们可以认为每个层次只有一个节点。

与可达图不同，在可达图中，我们通过应用可应用的操作来生成节点，所有的操作都用于生成状态的并集。

另一个区别是在可达图中，状态是一组一致的命题，而在规划图中，状态不是。例如，在图中的前提条件1中，robr的位置可以同时在loc1和loc2中。

同样，这些操作并不总是兼容的，它们可能会抵消彼此的效果。

在规划图中，为了跟踪这些命题的不一致性和不兼容的操作，我们使用了所谓的互斥（mutex）。在每个层面上，我们都有：

• 一组命题互斥
• 一组操作互斥

创建规划图

现在，让我们看看如何一步一步地构建规划图。最初，我们有级别0，其中只有前提条件0，它等于初始状态。

接下来，我们构建下一个级别，级别1。从一组操作开始：

这个等式的意思是A1是一组操作，其：

• 当前状态满足前提条件
• 在命题互斥对象中没有前提条件

下一步是构建一组命题：

我们采用先前构建的A1，并将所有操作的积极影响结合起来。

接下来的两个步骤是构建互斥体，从A1的互斥体开始：

A1中的两个操作是互斥对象，如果它们是相互依赖的(它们会抵消彼此的影响)，或者它们的前置条件在P0的互斥对象中。如果有一个负面影响会抵消一个正面影响的前提条件，那么这两个行为是相互依赖的:

最后一步是为P1构建互斥：

P1中的一对命题是互斥的，如果：

• A1中所有具有积极效果的一对操作中，这对操作是互斥的
• A1中没有一个操作可以同时产生这两种效果

现在，这是相当复杂的，但是这个步骤可以简单地重复到下一个级别。这是深度为3的规划图的结果。

此时，我们可以看到，与可达树和可达图相比，规划图的构建要复杂得多，但正如你所看到的，它将在搜索时间上更快，并且在大小上更小，更重要的是更易于我们分析或调试。

在构建规划图时，另一个重要的一点是，经过一些深度之后，它将是固定的，这意味着操作集和命题集不会再发生任何变化。

我们的目标达到了3级，我们可以看到两个命题：

• in(contb, loc1)
• in(conta, loc2)

在P3（见上图）。

搜索规划图

现在我们有了规划图-数据结构，我们可以使用搜索算法来找到规划问题的解决方案。

这种方法中的规划不是一系列操作，而是操作集合。一个级别的集合中的所有操作都可以独立执行，这意味着它们之间没有顺序约束。

在我们的例子中，搜索从P3向后执行到P0，递归地求解目标中的所有命题。在我们解决它们之后，我们递归地使用操作的前提条件作为子目标，直到我们达到P0。

我们跳过的一件重要的事情是，在每一个级别上，我们都有不做任何事情的虚拟操作—它们的前提条件和效果是相同的。这使得算法能够顺利地处理那些在较低层次上已经满足的命题。

例如，我们的解决方案规划是：

• Level 1: {load(loc2, contb, robq), load(loc1, conta, robr)}
• Level 2: {move(robq, loc2, loc1), move(robr, loc1, loc2)}
• Level 3: {unload(loc1, contb, robq), unload(loc2, conta, robr)}

结论

我们希望现在能够理解如何通过使用规划图方法来提高经典规划方法的复杂性。与可达树和可达图相比，规划图的构建更加复杂，但是它节省了我们搜索解决方案的大小和时间，如分步示例所示。

我希望你理解这个概念，在下一篇文章中，我们将用Python实现这个方法，以证明它是有效的，并帮助我们进一步理解它。