# 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.

Remember that we are interested in *estimates*. These
estimates should balance computation time against estimate quality
(not to mention that you have plenty of other things to do in the
course). Thus there is no need to perfectly calculate the remaining
number of actions, but at the same time the estimate should not be
too trivial. Simply try to make sure that you demonstrate your
understanding of the concepts and how one can estimate the action
distance to an "abstract" goal such as the correct placement of
blocks.