WASP Automated Planning: Exercise

For the automated planning part, we will focus mainly on lab exercises, where you will learn how to model planning problems in a common modeling language and how to apply state of the art planners to these problems. Therefore there is only a single hand-in exercise.

As discussed during the lecture, many current state-of-the-art planners are based on forward search in the state space, starting in the initial state as specified in the problem specification. Searching this space requires a suitable search algorithm that determines which search node to visit next.

Blind search algorithms "move" through the planner's abstract search space, defined by the state set S and the state transition function γ(s,a), using a strategy that only takes into account the part of the search space thas has been seen up to this point. The goal of the planning problem is only used passively, to detect whether the search algorithm happens to have reached a goal state or not. Examples of such algorithms include depth first search, breadth first search, and Dijkstra's algorithm. Using such algorithms is infeasible for all but the very smallest planning problems.

Instead we need informed search, where the search algorithm makes use of the goal when determining which search node to visit. Often (but far from always) the goal-related information is specified in terms of a heuristic function that estimates the distance from the current search node to the nearest goal node. For forward state space search, each search node is simply a state. The heuristic is therefore a function h(s) taking a state and returning a numeric estimate.

During the lecture we briefly discussed two classes of heuristic functions: Heuristics based on landmarks and pattern databases. These are domain-independent: They can be applied to any classical planning problem and extract all the information they require from the operator specifications and other specifications contained therein.

Creating good domain-independent heuristics requires considerable research and is outside the scope of the course. However, in order to gain a deeper understanding of the information that may be available for a planner to use, you should now create a heuristic function specifically for the blocks world as described in the lecture. A PDDL specification of this domain follows; PDDL is described at the beginning of the lab exercises, but you should also be able to follow the general syntax given that you understand the concepts we discussed during the lecture.

  (define (domain blocksworld)
(:requirements :strips :equality)
(:predicates (clear ?x)
             (on-table ?x)
             (arm-empty)
             (holding ?x)
             (on ?x ?y))

(:action pickup
  :parameters (?ob)
  :precondition (and (clear ?ob) (on-table ?ob) (arm-empty))
  :effect (and (holding ?ob) (not (clear ?ob)) (not (on-table ?ob)) 
               (not (arm-empty))))

(:action putdown
  :parameters  (?ob)
  :precondition (and (holding ?ob))
  :effect (and (clear ?ob) (arm-empty) (on-table ?ob) 
               (not (holding ?ob))))

(:action stack
  :parameters  (?ob ?underob)
  :precondition (and  (clear ?underob) (holding ?ob))
  :effect (and (arm-empty) (clear ?ob) (on ?ob ?underob)
               (not (clear ?underob)) (not (holding ?ob))))

(:action unstack
  :parameters  (?ob ?underob)
  :precondition (and (on ?ob ?underob) (clear ?ob) (arm-empty))
  :effect (and (holding ?ob) (clear ?underob)
  (not (on ?ob ?underob)) (not (clear ?ob)) (not (arm-empty)))))

The heuristic function should take a current state s, completely specifying which facts are true in the current state, and a goal specification g, a list or conjunction of facts that must be true in every goal state. These facts are instances of the five blocks world predicates. The function should compute an estimate of the number of actions required to reach the nearest goal state. The description can be formal or informal, but should in either case be clear and comprehensible.