AI Planning in PDDL-Descripted World

PDDL简介

PDDL是一种标准化的“规划域定义语言”，广泛用于描述规划域以及问题实例。它最初是为在1998年的国际计划竞赛（IPC）中使用而开发的，它允许所有竞争的规划人员使用相同的输入语言，并且从那时起逐步但显着地扩展和完善了它。当前，几乎所有新计划者都支持PDDL的某些子集。

https://en.wikipedia.org/wiki/Planning_Domain_Definition_Language 版本语言特征wiki介绍

http://users.cecs.anu.edu.au/~patrik/pddlman/writing.html 简短教程文档

Tutorial: Introduction to AI Planning, Part 1 (Amanda Coles, EASSS 2013) 慕课，简短的FF相关前向探索求解器启发式函数入门例解

  • The basics of propositional planning and search

  • Delete relaxation and the relaxed planning graph heuristic

  • Enforced Hill Climbing and Helpful Actions in the planner FF.

Writing Planning Domains and Problems in PDDL

古典计划使用从STRIPS建模语言[Richard E Fikes and Nils J Nilsson. Strips: A new approach to the application of theorem proving to problemsolving.Artificial intelligence, 2(3-4):189–208, 1971]派生而来的正式描述语言，称为计划领域定义语言（PDDL）[Drew McDermott, Malik Ghallab, Adele Howe, Craig Knoblock, Ashwin Ram, Manuela Veloso, Daniel Weld,and David Wilkins. Pddl-the planning domain definition language, 1998.]

关注的是令人满意的计划任务，它可以由集合（F，O，I，G）定义，其中F是一组命题（或谓词），它们描述任务实例中存在的对象的属性及其关系，O是一组运算符（或操作类型），ICF是初始状态，而GCF是目标状态的集合。

每个动作类型GO都由三元组（Pre（o），Add（o），Del（o））定义，其中前提为Pre（o）是一组谓词，这些谓词必须具有正确的值才能适用于该操作，Add（o）是一组谓词，在应用后该行为将变为真，而Del（o）是一组谓词，该行为将变为false根据申请。

Domain中定义abstract predicate definitions,actions，理解为定义一个符号代数推理系统，对象类型及其基本对象之上可执行的所有算子操作动作集

Problem中定义initial goal,goal state初始状态/目标状态。

一般基本状态都是用\<谓词(只有真假二值句子)向量集>来表征，每个动作则是标识为元组(pre condiction state动作适用前提谓词向量,effect动作使用后续状态)。

试图找到一个计划或一系列行动，这些行动或行动序列一旦应用，就会在一定时限或预定数量的步骤内导致状态为G C的状态。查找计划任务的计划通常是通过启发式搜索方法来完成的，但是，在这项工作中，专注于学习反应式计划策略，这些策略可以在特定领域的实例上进行训练，然后推广到同一领域中新的看不见的实例。

Components of a PDDL planning task:

•Objects: Things in the world that interest us.

•Predicates: Properties of objects that we are interested in; can be true or false.

•Initial state: The state of the world that we start in.

•Goal specification: Things that we want to be true.

•Actions/Operators: Ways of changing the state of the world.

为了防止别人看不懂你的pddl文件，推荐谓词和对象定义的时候，后方写注释说明当前pddl谓词描述的情景：

ROOM(x) ; – true iff x is a room

人工智能领域语言中PDDL 和Prolog

https://www.metalevel.at/prolog/showcases/turing.pl

简介：PDDL是一种用于表达计划任务的领域特定语言，而Prolog是一种成熟的编程语言，可让您表达所有可能的计算（包括解决计划任务）。

https://www.quora.com/What-is-difference-in-expressive-power-between-PDDL-and-Prolog

PDDL代表规划域定义语言。它是用于计划任务的标准编码。请注意，PDDL有不同版本，并且具有各种扩展名。

实际上，许多“ PDDL”求解器仅支持PDDL的某些子集。

通常，对计划任务的描述由特定组件组成，例如：

初始状态 一个目标 可以执行的动作 等

如果您的计划框架足够通用，那么这种特定于领域的计划语言实际上可以是**Turing-complete** ，因此与通用编程语言（例如Prolog）具有相同的计算能力：证明图灵机领域可以看作是经典的计划领域。

但是，PDDL并非如此：在PDDL中，通常需要对某些有限域（例如整数的有限间隔）进行推理。如果域是有限的，则无法建模无限的磁带，因此PDDL的表达能力**明显低于**Prolog。

此外，您通常只对多项式长度的计划感兴趣，甚至仅限于多项式长度的计划。在这种情况下，PDDL是PSPACE或EXPTIME完整的，具体取决于您使用的扩展名和变体。这尤其意味着**存在许多无法在PDDL中表达的计算任务**。

从实践的角度来看，即使PDDL在理论上足够强大，可以对所有计算任务进行建模，但在计划任务的预期应用领域之外使用它是否是方便或可取的仍值得商榷，所以用pddl描述自动机推演生成policy算法控制流图解子图"程序综合"可能需要PDDL的扩展版本或者基于其上做写framwork。

另一方面，Prolog是图灵完备的编程语言。这尤其意味着你可以表现一切任何编程语言，你可以也表达序言。您可以通过使用Prolog模拟图灵机来显示此信息：

prolog中的规划包 https://www.swi-prolog.org/pack/list?p=pddl_valoptic_api使用plasp 3将SAS和PDDL文件转换为统一的ASP事实格式。

本质上，plasp输出格式由状态变量组成，如果满足其前提条件，则可以通过操作对其进行修改。变量引用受操作影响的实体。与PDDL一样，目标是通过执行一系列操作来从初始状态开始实现特定目标。

plaspS变量对应于SAS中的多值变量。PDDL谓词被转换为布尔变量，以使输出格式一致。

动作的建模与PDDL动作和SAS运算符完全相同。

plasps变量表示计划问题的当前状态。变量链接到问题的对象和常量。

plasps变量是多值的，每个变量在每个时间点都只有一个值。

在PDDL中编写计划领域和问题

多大资料 https://www.cs.toronto.edu/~sheila/2542/s14/A1/introtopddl2.pdf

http://users.cecs.anu.edu.au/~thiebaux/papers/ijcai03.pdf In Defense of PDDL Axioms∗

在线 https://editor.planning.domains/# PDDL编辑器

The PDDL Resources page of IPC 2008:http://icaps-conference.org/ipc2008/deterministic/PddlResources.htmlCollects copies of most documents describing versions of PDDL up to 2008.

•PDDL Wikipedia page:https://en.wikipedia.org/wiki/Planning_Domain_Definition_Language

•Planning.Domains:http://planning.domains/Repository of planning domains and problems, on-line PDDL editor and planner, and collection of educational resources.

•PDDL 1.2 [Bacchus,2000]:http://ipc00.icaps-conference.org/pddl-subset.ps

PDDL1.2手册 http://homepages.inf.ed.ac.uk/mfourman/tools/propplan/pddl.pdf

•PDDL 2.1 [Fox and Long,2003]:https://www.jair.org/index.php/jair/article/view/10352

•PDDL 2.2 [Hoffmann and Edelkamp,2005]:https://www.jair.org/index.php/jair/article/view/10427

•PDDL 3.0 [Gerevini et al.,2009]:https://www.sciencedirect.com/science/article/pii/S0004370208001847

•PPDDL / FONDBryce and Buffet[2008]:http://icaps-conference.org/ipc2008/probabilistic/wiki/images/2/21/Rules.pdf

pddl版本迭代平衡复杂性和表现能力

通过例子介绍几种PDDL不同层次语言的表现力级别，通过:requirments实现。

STRIPS，ADL，多数solvers中常见的PDDL2.1，和添加非确定性后续状态描述的FOND/QNP抽象。

事实上很多pddl的parser都是solver定制的，通用的基本只有最基本的STRIPS，adl之类大概4个特性左右。其他不同版本各自特性可以看对应文档相关资料。

pddl中qnp2fond,FOND-SAT,myND 都是用的 pddl 转 sas+。qnp2fond看作DFA2NFA非确定性状态自动机。表现能力模仿程序设计语言的一段代码，能做到的事特定“任意层括号的正则动作序列行为”的特定通用规划问题。其实FOND/QNP类的抽象 就像输入一张抽象图(state transition system)，很直接的方法也更简短的甚至可以写一个json 文件输入这张图应有的内存中结构化数据类型。

为什么需要统一标准输入 pddl 文件写一个parser？

因为需要规范，一个模型领域 pddl 文件，各种遵循IPC规范求解器都能求解，社区共享 pddl 格式的benchmarks,相同输入格式的solver效率比较更为公平。

任何能构造皮亚诺算术的人造推理体系都可以用哥德尔文中的步骤构造不完备证明，一般保证完备的系统中常见都只有布尔状态，比如QNP中虽然有数值变量V_i ，但是就像程序设计一样 ，无法区分1，2，3，4等Nat仅仅知道V_i >0非零即真，V_i=0 就是假。

（简洁）。通用计划的简洁性是解 n 的大小。大小可以度量为算法中已编程的行数，FSC中的控制器数，策略规则的数量等等。

（复杂性）。通用计划的复杂性是关于用于描述计划实例的输入变量的时空函数的渐近分析。例如，在计算复杂性理论中使用big-O符号进行功能分析和复杂性类的研究。

PDDL版本不断wiki更新发展，实际功能插件版本也在不断变更，automated-programming-framework的Javier Segovia-Aguas在相关论文中总结过PDDL的版本迭代情况：

The Action Description Language (ADL) (Pednault, 1994) extended STRIPS al-lowing actions to have conditional effects, so some effects are triggered depending on the state. In contrast to STRIPS, ADL allows existential quantification, negative literals, goals with disjunctions, different object types, and while variables in STRIPS are either true or false, in ADL they can be true, false or undefined.

In the year 1998, with the aim to make a standard representation of planning languages, the Planning Domain Definition Language (PDDL) (McDermott et al.,1998) was published. The IPC has been used to compare planning solvers performance but also to include new features to the language. These are the different published versions:

  • PDDL1.2is the version used in the first international planning competition IPC-98 (Long et al., 2000) where the planning problem model is splitted into a domain and a problem description.-

  • PDDL2.1(Fox and Long, 2003) introduced numeric fluents so resources can be represented. In previous versions, actions were directly applied indiscrete time, but in this version actions can be described and performed in continuous space, so they are described as temporal or durative actions.数值 fluents 可以最短路寻址规划，推广来看硬约束可以保证尽量少用特定动作。

  • PDDL2.2(Edel kamp and Hoffmann, 2004) introduced derived predicates that can represent dependency among literals through transitive closures. This version also introduces timed initial literals where some literals are triggered by independent events at different times.传递闭包，描述更加精炼。时序网络建模。
  • PDDL3.0(Gere vini and Long, 2006) introduced hard constraints called state-trajectory constraints that must be true along the execution of a plan,and soft constraints called preferences where plans that satisfy them are considered of better quality.比如软约束。希望能实现少用new ListNode *动作防止O(n)空间复杂度新建临时指针而仅仅只需要(有限个ListNode * pre/cur/next或者for(int i ;i<n;i++))，时序刷新动态重复使用临时局部变量，这样直接用O(1)空间复杂度处理链表类似域LL domain希望学出来的“goto 汇编代码/控制流程/指令行数”尽量少。
  • PDDL3.1 introduced object-fluents where any function can be an object type. This feature is a reformulation of Functional STRIPS(Geffner, 2000).

https://planning.wiki/guide/whatis/pddl 规划wiki介绍PDDL各种版本

IPC官网对PDDL版本更新迭代的通知信息：

**PDDL2.1**分为不同的表达*水平*。级别1是ADL规划，级别2添加了数字构造，级别3添加了持续动作。（还有一个具有连续效果的第四层，但是尚未在IPC-3中使用，也不会在IPC-4中使用。）2002年竞赛语言PDDL2.1下载规范文档具有以下功能：

  • 处理（有限组）数值流利。
  • 时间和持续时间的明确表示。
  • 规划度量标准规范，作为问题实例的一部分。

与PDDL2.1一样，**PDDL2.2**分为三个级别，分别对应于ADL，数字和持续时间计划。除了PDDL2.1语言功能之外，还添加了两个新的构造：

  • 派生谓词，可以处理领域公理
  • 定时的初始文字，可以轻松表示确定性外生事件

新的**PDDL3.0**语言是与Derek Long合作开发的。该语言的主要新功能是“软目标”和“状态轨迹约束”，这些目标是有效计划不一定要实现的目标，而状态轨迹约束是对计划结构的约束。轨迹约束可以是硬约束或软约束。硬轨迹约束可用于表达控制知识或对计划域和/或特定计划问题的有效计划的约束。软目标和轨迹约束可用于表达影响计划质量的偏好，而不会限制有效计划的集合。

在PDDL3中，软目标或约束是具有与其在计划中的违规相关联的“惩罚权重”的“偏好”。计划的计划度量标准的规范包括必须最小化的这些违规罚款权重。通常，并非所有指定的偏好（可能具有不同的惩罚权重）都不能满足，并且确定可以实现的最佳偏好子集是在计划过程中要处理的额外困难。此外，如果有用于计划的CPU时间限制，为了产生高质量的解决方案，计划者还可以确定一组良好的（可能不是最优的）软目标/约束，这些目标可以在可用的计算资源量内实现。

对PDDL2.2（2004年竞赛的语言，IPC-4）的一些重要扩展，这些扩展在“ A. Gerevini，P.Haslum，D.Long，A.Saetti，Y， Dimopoulos， 第五届国际计划竞赛中的确定性计划：PDDL3和计划者的实验评估， 人工智能，第173（5-6）卷，第619-668页，2009年”。新语言（PDDL3.0）的BNF语法在另一个相关文档（Postscript版本， PDF版本）中给出。PDDL3.0在最近的“规划中的偏好和软约束研讨会（ICAPS 2006） ”上发表的论文中也得到了描述，其中包含了IPC-5中使用的一些基准示例。

上面提到的有关PDDL3的论文包含许多软目标以及硬和软轨迹约束的示例。

http://kcl-planning.github.io/ROSPlan//demos/robot_pages/komodo.html 视频讲解积木世界:durative-actions功能。

blocks-domiain_task_d.pddl

(define (domain blocks-domain)
(:requirements :strips :typing :fluents :disjunctive-preconditions :durative-actions)
(:types block_t)
(:predicates 
    (inhand ?block - block_t) 
    (emptyhand) 
    (not_emptyhand) 
    (on ?block ?on_block - block_t) 
    (clear ?block - block_t)
)

(:durative-action pick_up
    :parameters (?block ?from_block - block_t)
    :duration ( = ?duration 15)
    :condition (and 
        (at start (emptyhand))
        (over all (clear ?block))
        (at start (on ?block ?from_block)))
    :effect (and 
        (at end (inhand ?block))
        (at end (clear ?from_block))
        (at start (not (emptyhand)))
        (at start (not_emptyhand))
        (at start (not (on ?block ?from_block))))
)

(:durative-action put_down
    :parameters (?block ?on_block - block_t)
    :duration ( = ?duration 17)
    :condition (and 
        (at start (not_emptyhand))
        (over all (clear ?on_block))
        (at start (inhand ?block)))
    :effect (and 
        (at end (on ?block ?on_block))
        (at end (emptyhand))
        (at end (not (not_emptyhand)))
        (at start (not (inhand ?block)))
        (at start (not (clear ?on_block))))
  )
)

blocks-domiain_task_p.pddl

(define (problem blocks-domiain_task)
(:domain blocks-domain)
(:objects
    a b c d t1 t2 t3 t4 - block_t
)
(:init 
    (clear b)
    (clear t3)
    (clear t2)
    (clear c)
    (emptyhand)
    (on a t1)
    (on b a)
    (on d t4)
    (on c d)
)
(:goal (and
    (on d t2)
    (on a d)
    (on c a)
    (on b t4)
)))