Tutorial 3.3: Translate a PDSketch Planning Problem into STRIPS

PDSketch offers a translator from PDSketch representations into STRIPS representations. The key difference is that in STRIPS, everything (action parameters, predicate types) are all discrete (actually the internal representation is completely Boolean). Therefore, each state can be represented as a Python set of propositions (a.k.a. grounded predicates). This will make the evaluation of expressions and thus search very efficient. Moreover, using a discrete representation will allow us to easily track visited states and compute heuristics. The translators below will only work for “grounded” case. That is, they requires an input state (including all objects in the world and their associated state variables).

However, (because of the no-free lunch theorem!), translating a PDSketch domain that allows continuous representations for action parameters and predicates) into a domain that is completely discrete is not straightforward. In the original paper, two translation strategies have been described.

First: optimistic translation. In optimistic translation, all continuous parameters will be translated into two Boolean propositions: (<p>-optimistic) and (<p>-initial), indicating whether the value of <p> has been changed from its original state. Any assignment expression to these state variables will set (<p>-optimistic) to be true. The computation rule for these propositions is simple: any function that takes an optimsitic state variable as input will return (optimistically) true of false. That is, for example, if (pose-optimistic blockA) is true (the pose of block A has been changed to “optimistic”), any Boolean expression involving it will return true. For example: on(blockA, blockB), onTable(blockA), not(onTable(blockA)), etc. This is a very aggressive (but efficient) discretization.

Note that this function will handle compositions of these Boolean predicates correctly. That is, for example, consider the state: (pose-optimistic blockA), (pose-initial blockB) (and both blocks are not on table originally), the following expression will return False: (and (onTable blockA) (onTable blockB)).

Another note (which is probably obvious) is that for domains with only Boolean predicates and action parameters, this translator will faithfully translate into a STRIPS representation. No approximation will be made.

Second: AO-Discretization. TBD.

import concepts.dm.pdsketch as pds

# From tutorial/3-pdsketch/3-translate-into-strips.ipynb
domain_string = r"""(define (domain blocks-wold)
    (:types block)
    (:predicates
        (clear ?x - block)          ;; no block is on x
        (on ?x - block ?y - block)  ;; x is on y
        (robot-holding ?x - block)  ;; the robot is holding x
        (robot-handfree)            ;; the robot is not holding anything
    )
    (:action pick
     :parameters (?x - block)
     :precondition (and (robot-handfree) (clear ?x))
     :effect (and (not (robot-handfree)) (robot-holding ?x) (not (clear ?x)))
    )
    (:action place
     :parameters (?x - block ?y - block)
     :precondition (and (robot-holding ?x) (clear ?y))
     :effect (and (robot-handfree) (not (robot-holding ?x)) (not (clear ?y)) (clear ?x) (on ?x ?y))
    )
)"""

domain = pds.load_domain_string(domain_string)
domain

Domain(blocks-wold)

executor = pds.PDSketchExecutor(domain)

# From tutorial/3-pdsketch/3-translate-into-strips.ipynb
state, ctx = executor.new_state({'a': domain.types['block'], 'b': domain.types['block'], 'c': domain.types['block']}, create_context=True)
ctx.define_predicates([
    ctx.robot_handfree(),
    ctx.clear('a'),
    ctx.clear('b'),
    ctx.clear('c')
])
state

State{
  states:
    - clear: Value[bool, axes=[?x], tdtype=torch.int64, tdshape=(3,), quantized]{tensor([1, 1, 1])}
    - robot-holding: Value[bool, axes=[?x], tdtype=torch.int64, tdshape=(3,), quantized]{tensor([0, 0, 0])}
    - robot-handfree: Value[bool, axes=[], tdtype=torch.int64, tdshape=(), quantized]{tensor(1)}
    - on: Value[bool, axes=[?x, ?y], tdtype=torch.int64, tdshape=(3, 3), quantized]{
      tensor([[0, 0, 0],
              [0, 0, 0],
              [0, 0, 0]])
    }
  objects: a - block, b - block, c - block
}

goal_expr = domain.parse('(and (on a b) (on b c))')
goal_expr

AndExpression<and(on(OBJ::a, OBJ::b), on(OBJ::b, OBJ::c))>

GStripsTranslator is an alias for grounded STRIPS translator. In PDSketch, the convention is that all classes and functions that works with STRIPS (a.k.a. discrete) representations starts with S or s_, while all classes and functions for grounded STRIPS representations starts with GS or gs_.

translator = pds.strips.GStripsTranslatorOptimistic(executor)
translator

<concepts.dm.pdsketch.strips.strips_grounding.GStripsTranslatorOptimistic at 0x127fe0340>

gstrips_task = translator.compile_task(state, goal_expr)
gstrips_task

GStripsProblem{
  state: SState({'clear 2', 'robot-handfree', 'clear 1', 'clear 0'})
  goal: CONJ(on 1 2, on 0 1)
  operators:
    GStripsOperator{action::pick(?x=a)}{
      CONJ(clear 0, robot-handfree)
      EFF[add=frozenset({'robot-holding 0'}), del=frozenset({'clear 0', 'robot-handfree'})]
    GStripsOperator{action::pick(?x=b)}{
      CONJ(robot-handfree, clear 1)
      EFF[add=frozenset({'robot-holding 1'}), del=frozenset({'robot-handfree', 'clear 1'})]
    GStripsOperator{action::pick(?x=c)}{
      CONJ(clear 2, robot-handfree)
      EFF[add=frozenset({'robot-holding 2'}), del=frozenset({'clear 2', 'robot-handfree'})]
    GStripsOperator{action::place(?x=a, ?y=a)}{
      CONJ(clear 0, robot-holding 0)
      EFF[add=frozenset({'clear 0', 'robot-handfree'}), del=frozenset({'clear 0', 'robot-holding 0'})]
    GStripsOperator{action::place(?x=a, ?y=b)}{
      CONJ(robot-holding 0, clear 1)
      EFF[add=frozenset({'clear 0', 'robot-handfree', 'on 0 1'}), del=frozenset({'robot-holding 0', 'clear 1'})]
    GStripsOperator{action::place(?x=a, ?y=c)}{
      CONJ(clear 2, robot-holding 0)
      EFF[add=frozenset({'clear 0', 'robot-handfree'}), del=frozenset({'clear 2', 'robot-holding 0'})]
    GStripsOperator{action::place(?x=b, ?y=a)}{
      CONJ(clear 0, robot-holding 1)
      EFF[add=frozenset({'robot-handfree', 'clear 1'}), del=frozenset({'clear 0', 'robot-holding 1'})]
    GStripsOperator{action::place(?x=b, ?y=b)}{
      CONJ(robot-holding 1, clear 1)
      EFF[add=frozenset({'robot-handfree', 'clear 1'}), del=frozenset({'robot-holding 1', 'clear 1'})]
    GStripsOperator{action::place(?x=b, ?y=c)}{
      CONJ(clear 2, robot-holding 1)
      EFF[add=frozenset({'on 1 2', 'robot-handfree', 'clear 1'}), del=frozenset({'clear 2', 'robot-holding 1'})]
    GStripsOperator{action::place(?x=c, ?y=a)}{
      CONJ(clear 0, robot-holding 2)
      EFF[add=frozenset({'clear 2', 'robot-handfree'}), del=frozenset({'clear 0', 'robot-holding 2'})]
    GStripsOperator{action::place(?x=c, ?y=b)}{
      CONJ(clear 1, robot-holding 2)
      EFF[add=frozenset({'clear 2', 'robot-handfree'}), del=frozenset({'clear 1', 'robot-holding 2'})]
    GStripsOperator{action::place(?x=c, ?y=c)}{
      CONJ(clear 2, robot-holding 2)
      EFF[add=frozenset({'clear 2', 'robot-handfree'}), del=frozenset({'clear 2', 'robot-holding 2'})]
  derived_predicates:

  facts: {'robot-holding 0', 'clear 1', 'on 0 1', 'robot-holding 2', 'robot-handfree', 'clear 2', 'on 1 2', 'clear 0', 'robot-holding 1'}
}

pds.strips.strips_brute_force_search(gstrips_task)

strips_brute_force_search::task.goal=CONJ(on 1 2, on 0 1)
strips_brute_force_search::task.facts=9
strips_brute_force_search::task.operators=12

strips_brute_force_search::depth=2, states=12: : 197it [00:00, 108720.77it/s]

(GStripsOperator{action::pick(?x=b)}{
   CONJ(robot-handfree, clear 1)
   EFF[add=frozenset({'robot-holding 1'}), del=frozenset({'robot-handfree', 'clear 1'})],
 GStripsOperator{action::place(?x=b, ?y=c)}{
   CONJ(clear 2, robot-holding 1)
   EFF[add=frozenset({'on 1 2', 'robot-handfree', 'clear 1'}), del=frozenset({'clear 2', 'robot-holding 1'})],
 GStripsOperator{action::pick(?x=a)}{
   CONJ(clear 0, robot-handfree)
   EFF[add=frozenset({'robot-holding 0'}), del=frozenset({'clear 0', 'robot-handfree'})],
 GStripsOperator{action::place(?x=a, ?y=b)}{
   CONJ(robot-holding 0, clear 1)
   EFF[add=frozenset({'clear 0', 'robot-handfree', 'on 0 1'}), del=frozenset({'robot-holding 0', 'clear 1'})])

pds.strips.strips_heuristic_search(gstrips_task, pds.strips.StripsHFFHeuristic(gstrips_task, translator), verbose=True)

strips_heuristic_search::task.goal=CONJ(on 1 2, on 0 1)
strips_heuristic_search::task.facts=9
strips_heuristic_search::task.operators=12
strips_heuristic_search::init_heuristic=4

strips_heuristic_search::expanding: 60it [00:00, 84591.01it/s]

[GStripsOperator{action::pick(?x=b)}{
   CONJ(robot-handfree, clear 1)
   EFF[add=frozenset({'robot-holding 1'}), del=frozenset({'robot-handfree', 'clear 1'})],
 GStripsOperator{action::place(?x=b, ?y=c)}{
   CONJ(clear 2, robot-holding 1)
   EFF[add=frozenset({'on 1 2', 'robot-handfree', 'clear 1'}), del=frozenset({'clear 2', 'robot-holding 1'})],
 GStripsOperator{action::pick(?x=a)}{
   CONJ(clear 0, robot-handfree)
   EFF[add=frozenset({'robot-holding 0'}), del=frozenset({'clear 0', 'robot-handfree'})],
 GStripsOperator{action::place(?x=a, ?y=b)}{
   CONJ(robot-holding 0, clear 1)
   EFF[add=frozenset({'clear 0', 'robot-handfree', 'on 0 1'}), del=frozenset({'robot-holding 0', 'clear 1'})]]

Now let’s try a domain that is larger and more complicated. This example shows how you can basically use this library as a standard PDDL planner.

domain = pds.load_domain_file('mini-behavior.pddl')
domain

Domain(mini-behavior)

object_types, object_names = (
    ['human', 'robot', 'location', 'location', 'location'] + ['phyobj'] * (6 + 3 + 5),
    ['h', 'r', 'c', 't', 's'] + ('plr1 plr2 pmb3 pmg4 psr5 psg6 blg1 bmb2 bsr3 clb1 clg2 cmr3 cmr4 csg5').split()
)
object_names_dict = {
    n: domain.types[t] for n, t in zip(object_names, object_types)
}

executor = pds.PDSketchExecutor(domain)
state, ctx = executor.new_state(object_names_dict, create_context=True)

predicates = list()
predicates.extend([ctx.type_cupboard('c'), ctx.type_table('t'), ctx.type_sink('s')])
for name in object_names[-(6 + 3 + 5):]:
    assert len(name) == 4
    t = {'p': 'plate', 'b': 'bowl', 'c': 'cup'}[name[0]]
    z = {'l': 'large', 'm': 'medium', 's': 'small'}[name[1]]
    c = {'r': 'red', 'g': 'green', 'b': 'blue'}[name[2]]
    predicates.append(ctx.get_predicate('type-' + t)(name))
    predicates.append(ctx.get_predicate('size-' + z)(name))
    predicates.append(ctx.get_predicate('color-' + c)(name))

predicates.append(ctx.at('plr1', 's'))
predicates.append(ctx.state_used('plr1'))
predicates.append(ctx.at('plr2', 'c'))
predicates.append(ctx.state_clean('plr2'))
predicates.append(ctx.at('pmb3', 't'))
predicates.append(ctx.state_clean('pmb3'))
predicates.append(ctx.at('pmg4', 's'))
predicates.append(ctx.state_used('pmg4'))
predicates.append(ctx.at('psr5', 't'))
predicates.append(ctx.state_full('psr5'))
predicates.append(ctx.at('psg6', 't'))
predicates.append(ctx.state_used('psg6'))

predicates.append(ctx.at('blg1', 'c'))
predicates.append(ctx.state_clean('blg1'))
predicates.append(ctx.at('bmb2', 'c'))
predicates.append(ctx.state_clean('bmb2'))
predicates.append(ctx.at('bsr3', 'c'))
predicates.append(ctx.state_clean('bsr3'))

predicates.append(ctx.at('clb1', 't'))
predicates.append(ctx.state_full('clb1'))
predicates.append(ctx.at('clg2', 't'))
predicates.append(ctx.state_used('clg2'))
predicates.append(ctx.at('cmr3', 't'))
predicates.append(ctx.state_used('cmr3'))
predicates.append(ctx.at('cmr4', 'c'))
predicates.append(ctx.state_clean('cmr4'))
predicates.append(ctx.at('csg5', 't'))
predicates.append(ctx.state_full('csg5'))

predicates.append(ctx.on('bmb2', 'pmb3'))
predicates.append(ctx.clear('plr1'))
predicates.append(ctx.clear('plr2'))
predicates.append(ctx.clear('pmg4'))
predicates.append(ctx.clear('psr5'))
predicates.append(ctx.clear('psg6'))
predicates.append(ctx.clear('blg1'))
predicates.append(ctx.clear('bmb2'))
predicates.append(ctx.clear('bsr3'))
predicates.append(ctx.clear('clb1'))
predicates.append(ctx.clear('clg2'))
predicates.append(ctx.clear('cmr3'))
predicates.append(ctx.clear('cmr4'))
predicates.append(ctx.clear('csg5'))

predicates.append(ctx.is_working('h'))

ctx.define_predicates(predicates)

translator = pds.strips.GStripsTranslatorOptimistic(executor, use_string_name=True)
task = translator.compile_task(
    state, '(is-goal1 h)', verbose=True,
    forward_relevance_analysis=True, backward_relevance_analysis=True
)

[Timer::compile_task::actions] Start...
[Timer::compile_task::actions] End. Time elapsed = 1.09096097946167
[Timer::compile_task::state] Start...
[Timer::compile_task::state] End. Time elapsed = 0.0006299018859863281
[Timer::compile_task::operators] Start...
[Timer::compile_task::operators] End. Time elapsed = 0.1288151741027832
[Timer::compile_task::goal] Start...
[Timer::compile_task::goal] End. Time elapsed = 0.0009219646453857422
[Timer::compile_task::relevance_analysis] Start...
[Timer::compile_task::relevance_analysis] End. Time elapsed = 0.017339229583740234

heuristic = pds.strips.StripsHFFHeuristic(task, translator, forward_relevance_analysis=True, backward_relevance_analysis=True)
plan = pds.strips.strips_heuristic_search(task, heuristic, verbose=True)
plan

strips_heuristic_search::task.goal=CONJ(is-goal1 0)
strips_heuristic_search::task.facts=142
strips_heuristic_search::task.operators=601
strips_heuristic_search::init_heuristic=5

strips_heuristic_search::expanding: 3005it [00:00, 11459.01it/s]

[GStripsOperator{action::human-make-full(?h=h, ?p=bmb2, ?c=c)}{
   CONJ(at 7 0, state-clean 7)
   EFF[add=frozenset({'state-full 7'}), del=frozenset({'state-clean 7'})],
 GStripsOperator{action::human-move(?h=h, ?p=bmb2, ?from=c, ?to=t)}{
   CONJ(at 7 0)
   EFF[add=frozenset({'at 7 1'}), del=frozenset({'at 7 0'})],
 GStripsOperator{action::human-make-full(?h=h, ?p=cmr4, ?c=c)}{
   CONJ(at 12 0, state-clean 12)
   EFF[add=frozenset({'state-full 12'}), del=frozenset({'state-clean 12'})],
 GStripsOperator{action::human-move(?h=h, ?p=cmr4, ?from=c, ?to=t)}{
   CONJ(at 12 0)
   EFF[add=frozenset({'at 12 1'}), del=frozenset({'at 12 0'})],
 GStripsOperator{action::reach-goal1(?h=h, ?p1=pmb3, ?b1=bmb2, ?c1=cmr4, ?t=t)}{
   CONJ(at 7 1, state-full 12, at 12 1, state-full 7, at 2 1)
   EFF[add=frozenset({'is-goal1 0'}), del=frozenset()]]

Final Note: Doing STRIPS planning for purely discrete domains is much faster than solving them using the original PDSketch representations, due to various implementation details. Therefore, if you want to apply PDSketch just as a PDDL planner (maybe for its simplicity? Otherwise I will suggest faster C/C++ implementations such as FF or FD), you should probably always use this STRIPS planner. Later on in the tutorials we will see how this is used as a subroutine when we are doing Task and Motion Planning (TAMP).