

![0_image_0.png](0_image_0.png)

optimization problem, e.g., a problem in which the objective is to find a plan having the least possible cost. With the sort-by construct, we can write a heuristic function to estimate the anticipated cost of each set of variable bindings, and sort the sets of variable bindings according to their heuristic-function values so that SHOP2 **will try most promising one first.**
For example, if we have the precondition

## (And (At ?Here) (Distance ?Here ?There ?D))

then there may be several different combinations of ?here, ?there, and ?d **that satisfy this**
precondition. The expression
(:sort-by ?d \#'> (and (at ?here) (distance ?here ?there ?d)))
will cause SHOP2 to consider the variable bindings in decreasing order of the value of ?d.

As a more complicated example, recall the precondition of the method in Figure 3.

There may be several sets of variable bindings that satisfy this precondition in the current state. The reformulation of the precondition in Figure 6 tells SHOP2 to sort the sets of variable bindings in increasing order of the ?cost **variable. This way, SHOP2 will look first** at the alternative that has the lowest ?cost **value.**

## 3.3.2 Branch-And-Bound Optimization

SHOP2 allows the option of using branch-and-bound optimization to search for a leastcost plan. This option generally results in spending additional planning time in order to search for plans of superior quality. When using the branch-and-bound option, one can also specify a time limit for the search. If the search takes longer than the time limit, SHOP2 terminates the search and returns the best plan it has found so far; this functionality was partly inspired by anytime algorithms (Boddy & Dean, 1989).