Goal-based problems

[vakker]

Hi,

I was wondering if SHOP3 allows goal-based planning, i.e. similarly to how classical planning problems are phrased (like PDDL).
E.g. there's the toy example with the kiwi and banjo:

(defdomain basic-example (
  (:operator (!pickup ?a) () () ((have ?a)))
  (:operator (!drop ?a) ((have ?a)) ((have ?a)) ())

  (:method (swap ?x ?y)
    ((have ?x))
    ((!drop ?x) (!pickup ?y))
    ((have ?y))
    ((!drop ?y) (!pickup ?x)))))

(defproblem problem1 basic-example
  ((have banjo)) ((swap banjo kiwi)))

This explicitly tells the planner that we want to do (swap banjo kiwi), but with PDDL the goal would be specified, which is (have kiwi) and the planner would find the combination of the operators to achieve the goal state from the init state.

Other examples (e.g. blockworld) has a list of goals that needs to be achieved, but the high-level goal captures the skeleton of the solution:

        ;; The method for the top-layer task
        (:method (achieve-goals ?goals)
           ()
           ((assert-goals ?goals nil)
            (find-nomove)
            (add-new-goals)
            (find-movable)
            (move-block)
            (verify-solution)
            ))

Can that be done, or is that out of scope of SHOP3?
I assume that's more like a hierarchical goal network problem (instead of task).

[Maumagnaguagno]

You can solve this problem with a goal operator that has the original goal as preconditions and no effects, and include it as the last task.
(:operator (!!goal) ((have kiwi)) () ())

(defproblem problem1 basic-example
  ((have banjo))
  ((swap banjo kiwi) (!!goal)))

[Maumagnaguagno]

I see, sorry about that.
You would need to add a method that tries every action/operator available, and at this point a classical planner would be a better choice. You could try more complex methods to beat a classical planner.
EDIT: If you want to convert a classical planning instance to HTN, it is complex to do it automatically for every case.
See these papers: Method Composition through Operator Pattern Identification and Constructing Hierarchical Task Models Using Invariance Analysis.

[vakker]

Thanks!
I was looking at Hierarchical Planning: Relating Task and Goal Decomposition with Task Sharing paper, that relates the goal and task based approaches, FAPE or GTPyhop are interesting alternatives.

[rpgoldman]

I don't know about FAPE, but I believe you would find GTPyhop a lot less efficient than SHOP (for the same set of methods). Again, I don't know much about GTPyhop, but Pyhop did not have a unifier or theorem-prover, which is a major decrease in expressive power (if you are working in a framework more expressive than STRIPS).

@ukuter has worked on Godel, which combines both HTN and HGN planning; we plan to bring that algorithm to SHOP, but have no immediate plans.

For a short term expedient, a common method is to add tasks to (ACHIEVE X) for various goals X. Of course, as the set of possible goal schemas expands, this does not scale, because you need to provide more methods to achieve these goals.

In practice, however, for most domains, the set of possible goal schemas does not expand. E.g., if you look at the IPC domains, logistics has package delivery, openstacks has goal shipping, the airports domain has aircraft that must either be taken from the runways to the gate, or taken from the gate to the runways, etc.

[vakker]

@rpgoldman thanks, that's very helpful!

[rpgoldman]

@vakker Mind marking this as "Answered"? I don't seem to be able to do this.