低阶语言2高阶语言¶

低阶语言STRPIPS/ADL/SituationCalculus存在任意量化​的逻辑符号公式表示： a STRIPS instance is a quadruple\(<P,O,I,G>\),P is a set of conditions (i.e., propositional variables;I 初始状态，以初始为真的条件集合（所有其他条件均假定为假）给出；G 目标状态的规范是一对\(<N,M>\)，它们分别指定哪些条件为真和为假，以便将一个状态视为目标状态。O是运算符集，本身就是一个四元组\((\alpha,\beta ,\gamma ,\delta)\)：状态之间的转换由转换函数建模，转换函数是一种将状态映射到由于执行动作而导致的新状态的函数。由于状态由条件集表示，因此相对于STRIPS实例的转移函数。

高阶语言可判定的抽象如QNP看作DFA，FOND看作NFA，本质都是相同的状态迁移图。

总结两者最主要的区别是：高阶语言QNP/FOND巧妙设计量化值解决实例数量/参数未定CP问题更简单的描述，不需要像递阶语言STRPIPS逻辑公式中层层嵌套forall/exists等效表示临界状态(异或后继状态展开一阶逻辑公式不唯一已经很要命了)。

• 低阶语言们，一阶逻辑剩最后一个临界状态用量词(forall\(\forall\) condition effect)和(exists\(\exist\) condition effect)实现**临界**值更新后继状态的变化。

• 高阶抽象如，QNP看作DFA量化循环判断值X 临界剩最后一个变成两个后继状态>0或=0，FOND看作NFA直接两条边假设都能走且公平性假设保证最后一步一定能跳出循环。这里一般看作FOND，用(oneof 几个候选后继状态)表示*互斥或*(**xor**每次只有一个后继状态满足a⊕b = (¬a ∧ b) ∨ (a ∧¬b)=(a ∧ b) ∨ (¬a ∧¬b)=(a ∧ b) ∨ ¬(a ∨ b) a⊕b =(a ∨ b) ∧ (¬a ∨ ¬b)=(a ∨ b) ∧ ¬ (a ^ b)但是不会出现两者都假的后续状态，xor二元运算符经过柯里化就能实现任意元switch case选择后继状态语句功能)，而不是逻辑中**or**的*相容或*不可以cnt既大于零又等于零。

所以我们关心给定batches of CP经典规划实例（用递阶语言描述） 能不能 可靠完备转换 设计给定的QNP类程序设计语言输入输出的高阶语言抽象，CP_STRIPS和GP_QNP是n:1关系，同时想输入高低阶抽象描述pddl文件之后计算机自动证明给定两者是可靠抽象转换。

block clear¶

问题描述：清空桌面上的积木数量，cnt>0变成cnt=0

• 低阶表示形式化\(<P,O,I,G>\)

预定义对象实例 A B C D E F earth − physob

Init: (clear A) (on A B) (on B C) (ontable C) (ontable D) (ontable F) (on E D) (clear E) (clear F)

Goal：(onearth A) (onearth B)(onearth C) (onearth D) (onearth E) (onearth F)

表征全局状态snapshot的谓词集

 (:predicates; 
​    (ontable ?x ); − physob)
​    (clear ?x );− physob)
​    (on ?x ?y );− physob)
​    (onearth ?x) )

O动作集

    (:action move
        :parameters (?x ?y );− physob)
        :precondition (and( clear ?x) ( clear ?y) )
        :effect (and(on ?x ?y) (not( clear ?y) )
                (when( ontable ?x) 
                    (not( ontable ?x) ) )
                (forall (?z − );physob) 
                    (when(on ?x ?z) 
                        (and(not(on ?x ?z) ) (clear ?z) ) ))))

    (:action moveToTable
        :parameters (?x );− physob)
        :precondition (and( clear ?x) (not( ontable ?x) ) )
        :effect (and(not( clear ?x) ) ( ontable ?x)
        ( forall (?z );− physob) 
                (when(on ?x ?z) 
                    (and(not(on ?x ?z) ) (clear ?z) ) ) )))

    (:action pickUpandputaside ;move to earth
        :parameters (?x );− physob)
        :precondition (and( clear ?x) (not( onearth ?x) ) )
        :effect (and(not( clear ?x) ) ( onearth ?x)
        ( forall (?z );− physob) 
                (when(on ?x ?z) 
                    (and(not(on ?x ?z) ) (clear ?z) ) ) )))

• 高阶表示形式化

state presentation with Predicates vector

Init: \(\{!BlockOnHand \wedge cnt>0\}\)

Goal: \(\{cnt=0\}\)补完缺省谓词表示0/1均有可能成立但不关心这个谓词真假,即\(\{--缺省,cnt>0\}\)表示两个目标状态都能满足题目要求。

Opearators：

1. pick-up:从桌上捡起积木

[pre]:\(\{!BlockOnHand\}\)

[eff]:\(\{ oneof( ((! BlockOnHand) \wedge (cnt = 0)) ((! BlockOnHand) \wedge (cnt > 0)) ) \}\)

1. put-away:积木扔开一边

[pre]: \(\{BlockOnHand\}\)

[eff ]: \(\{!BlockOnHand\}\)

block X on Y¶

问题描述：X上方n块，y上方m块，积木世界把X放在Y上(隐含先清空X/Y上方积木)

• 低阶表示形式化\(<P,O,I,G>\)

预定义对象实例 A B C D X Y − physob

Init: (clear X) (on X B) (on B C) (ontable C) (ontable Y) (ontable D) (on A Y) (clear A) (clear D)

Goal：(and(clear D) (on D X) (on X C) (ontable C) (clear A)(on A B) (on B Y) (ontable Y))

表征全局状态snapshot的谓词集

    (:predicates;
        (ontable ?x )
        (clear ?x )
        (on ?x ?y ))

O动作集

    (:action move
        :parameters (?x ?y );− physob)
        :precondition (and( clear ?x) ( clear ?y) )
        :effect (and(on ?x ?y) (not( clear ?y) )
                (when( ontable ?x) 
                    (not( ontable ?x) ) )
                (forall (?z − );physob) 
                    (when(on ?x ?z) 
                        (and(not(on ?x ?z) ) (clear ?z) ) ))))

    (:action moveToTable
        :parameters (?x );− physob)
        :precondition (and( clear ?x) (not( ontable ?x) ) )
        :effect (and(not( clear ?x) ) ( ontable ?x)
        ( forall (?z );− physob) 
                (when(on ?x ?z) 
                    (and(not(on ?x ?z) ) (clear ?z))))))

• 高阶表示形式化\(Q=〈F, V, I, O, G〉\)

state presentation with Predicates vector\(<F_i,V_i>\)

\(F = \{ E空手,X手持积木'x',D 达成目标积木'x'放在积木'y'上方\}\)

\(V = {积木'x'上方有n块积木,积木'y'上方有非负整数m块积木}\)

Init: \(\{E,!X,!D,n>0,m>0\}\)

Goal: \(\{E,!X,D,n=0,m>0\}\)

Opearators：

1. Pick-above-x:捡起来x上方积木:

[pre]:\(\{E,!X,!D,n>0,m>0\}\)

[eff ]: \(\{!E,n\darr\},\)考虑不变的谓词和pre值相同就不写在eff加上就能保证问题是Fully Observable，其后继n=0/n>0都有可能\(\{!E,!X,!D,--,m>0\}\)。

1. Pick-above-y:捡起来y上方积木:

[pre]:\(\{E,!X,!D,n=0,m>0 \}\)这里原则上建模qnp的时候还要考虑n>0也有一种情况，这里简单起见建模时不考虑先清空y上m块积木再清空x上n酷爱，这动作已经要求学出来的结果必然是先清空x上n快再清空y上m块积木。

[eff ]:\(\{ !E,m\darr\}\)

1. put-aside-1:已经拿起x上方积木放一边到桌面Table

[pre]:\(\{!E,!X,!D,n=0 \}\)

[eff ]:\(\{ E\}\)

1. put-aside-2 :已经拿起y上方积木放一边到桌面Table

[pre]:\(\{!E,!X,!D,n>0,m>0 \}\)

[eff ]:\(\{ E\}\)

1. pick-x：拿起来x石头

[pre]:\(\{E,!X,!D,n=0,m=0 \}\)

[eff ]:\(\{ !E,X\}\)

1. put-x-aside,

[pre]:\(\{!E,X,!D,n=0,m>0 \}\)

[eff ]:\(\{ E,!X\}\)

1. put-x-on-y,把手中的x放在y上方

[pre]:\(\{!E,X,!D,n=0,m=0 \}\)

[eff ]:\(\{E,!X,D,m\uarr\}\)

build a tower¶

问题描述：把所有的积木堆成一座高塔the task is building a tower with all the blocks

• 低阶表示形式化\(<P,O,I,G>\)，

ADL语言版本

预定义对象实例 (:objects a b c - block table)

Init:

  (:init
     (on b table) (on a table) (on c a)
     (clear b) (clear c) (clear table)
  )

Goal：

  (:goal
     (and (on a b) (on b c) (on c table)))

表征全局状态snapshot的谓词集

 (:predicates (on ?x ?y) (clear ?x))

O动作集

  (:action move
     :parameters (?b - block ?x ?y)
     :precondition (and
                (clear ?b) (on ?b ?x) (clear ?y))
     :effect (and (on ?b ?y)
                  (not (on ?b ?x))
          (clear ?x)
          (when (not (= ?y table))
            (not (clear ?y))))
  )

STRIPS语言版本

预定义对象实例 (:objects a b c table)

Init:

  (:init
     (on b table) (on a table) (on c a)
     (clear b) (clear c) (clear table)
     (block a) (block b) (block c))

Goal：

  (:goal
     (and (on a b) (on b c) (on c table)))

表征全局状态snapshot的谓词集

 (:predicates
    (on ?x ?y) (clear ?x) (block ?x))

O动作集

  (:action move
    :parameters (?b ?x ?y)
    :precondition (and (block ?b) (clear ?b) (on ?b ?x) (block ?y) (clear ?y))
    :effect (and (not (on ?b ?x)) (clear ?x)
           (not (clear ?y)) (on ?b ?y)))

  (:action move-to-table
    :parameters (?b ?x)
    :precondition (and (block ?b) (on ?b ?x) (clear ?b))
    :effect (and (not (on ?b ?x)) (clear ?x) (on ?b table)))

• 高阶表示形式化\(Q=〈F, V, I, O, G〉\)

state presentation with Predicates vector\(<F_i,V_i>\)

\(F = \{ X, H,Z\}\)，H应该是手持物品 ? X Z 未知

\(V = \{n(X)>0,m(X)>0\}\),m应该是不在X上方堆塔的其他积木数量，n可能是X上方积木数量

Init: \(\{!X ,!H,Z,n(X)>0,m(X)>0\}\)

Goal: \(\{!X,!H,m(X) = 0\}\)

Opearators：

1. Pick-other:

[pre]:\(\{!X,!H,m>0\}\)

[eff ]: \(\{!X,H,m>0\}\)

1. Pick-above-x:放到x上方积木:

[pre]:\(\{!X,H,m>0\}\)

[eff ]: \(\{!X,!H,m>0\}\)

gripper¶

问题描述：一个带有夹子的机器人将若干个球从某个房间移动到目标房间.

• 低阶形式化\(<P,O,I,G>\)

预定义对象实例 rooma roomb ball1 ball2 left right

Init:

    (:init (room rooma)
           (room roomb)
           (ball ball1)
           (ball ball2)
           (gripper left)
           (gripper right)
           (at-robby rooma)
           (free left)
           (free right)
           (at ball1 rooma)
           (at ball2 rooma))

Goal：

(:goal (and (at ball1 roomb)(at ball2 rooma)))

表征全局状态snapshot的谓词集

(:predicates (room ?r) 
             (ball ?b) 
             (gripper ?g)
             (at-robby ?r)
             (at ?b ?r) 
             (free ?g)
             (carry ?o ?g))

O动作集

  (:action move
   :parameters (?from ?to)
   :precondition (and (room ?from)
                      (room ?to)
                      (at-robby ?from))
   :effect (and (at-robby ?to)
                (not (at-robby ?from))))

  (:action pick
   :parameters (?obj ?room ?gripper)
   :precondition (and (ball ?obj)
                      (room ?room)
                      (gripper ?gripper)
                      (at ?obj ?room)
                      (at-robby ?room)
                      (free ?gripper))
   :effect (and (carry ?obj ?gripper)
                (not (at ?obj ?room))
                (not (free ?gripper))))

  (:action drop
   :parameters (?obj ?room ?gripper)
   :precondition (and (ball ?obj)
                      (room ?room)
                      (gripper ?gripper)
                      (carry ?obj ?gripper)
                      (at-robby ?room))
   :effect (and (at ?obj ?room)
                (free ?gripper)
                (not (carry ?obj ?gripper))))

• 高阶形式化QNP/FOND等

QNP的形式化\(Q=〈F, V, I, O, G〉\).state presentation Predicates with vector$ $

X:机器人是否在目标房间; B:不在目标房间的球的数量C:机器人夹住球的数量G:空的夹子的数量

Init:\(\{ !T,b>0,c=0,g>0\}\)

Goal:\(\{ b=0,c=0\}\)

Opearators： 1. drop-ball-at-x:把夹住的球放到目标房间

[pre]:\(\{ T,c>0\}\)

[eff ]: \(\{ c\darr,g\uarr\}\)

1. move-to-x-half-loaded:如果剩下的球数量小于空夹子数量，则夹起剩下的所有球，并移动到目标房间

[pre]:\(\{ !T,b=0,c>0,g>0\}\)

[eff ]: \(\{ T\}\)

1. move-to-x-fully-loaded:如果剩下的球数量大于空夹子数量，则用所有夹子夹起对应数量的球，并移动到目标房间

[pre]:\(\{ !T,c>0,g=0\}\)

[eff ]: \(\{ T\}\)

1. pick-ball-not-in-x:把不位于目标房间的球捡起来

[pre]:\(\{!T,b>0,g>0\}\)

[eff ]: \(\{ b \darr c\darr,g\uarr \}\)

1. leave-x:离开目标房间

[pre]:\(\{ T,c=0,g>0\}\)

[eff ]: \(\{ !T\}\)