Domain-independent Heuristics

Helping search algorithms to solve domain-independent problems.

Heuristic: Recap

We discussed in previous post about heuristic which is an estimate of the minimum cost from a state to goal state, to aid search algorithm in reducing the number of nodes it has to explore to find a solution plan, in the hope that it will reduce the runtime of the search algorithm and find optimal plan.

In other words, without heuristic, the search algorithms explore blindly to find a solution. With heuristic, the search algorithms are informed.

In the previous post, we looked into domain-specific examples to show how heuristic helps with visualization of explored and selected nodes. You can read the post here:

In this post, we look into domain-independent heuristic which can be used for domain-independent planning problems which we are interested in.

Relaxation

We discussed a little bit about relaxation in the previous post which is the best known way to write heuristic function, by weakening some of the constraints that we use in our Planning Domain. We will see concrete examples of the relaxation in the sections below.

We look into two related algorithms in this post:

• Max-cost
• Additive

Max-cost Heuristic

To understand this heuristic and Additive-cost heuristic, we start with borrowing a term from predicate logic, literal.

A literal is either an atomic formula or its negation

and atomic formula, or atom is

An atomic formula is a logical expression

Definitions taken from here.

Basically we break down our goal state into literals. Using our example Pacman, as shown in the picture below, the goal is to eat all three foods.

We can break our goal state down into 3 literals:

• food(a, b) = False
• food(c, d) = False
• food(e, f) = False

From there, we can work our way backward from goal state to the state that we are interested in. This is better visualized using And/Or tree.

And/Or Tree

The definition of And/Or Tree is:

A tree whose nodes are labelled with either AND or OR.

It is good to visualize problem reduction into sub-goals like what we are doing with our Pacman goal state.

Visualization

The goal is broken down into three literals, and all of them must be True, for the Goal node to be True (Goal node is an AND node, shown by an arc connecting all its three edges).

food(a,b) = F node is an OR node, it has 3 children (let’s assume for this example), it only needs one of its children to be True. This node is an Action node.

To expand the node, we use the preconditions of the action:

• no wall in between, that is the move is possible
• Pacman is at the location

This process continues until we reach the state that we are evaluating.

The action has associated cost, after we have completed building the tree, we can calculate the cost.

Nodes in red show the state we are evaluating, the total cost of this branch is 2. Let’s assume that the next branch’s total cost is 1 and the last one is 10.

The Max-cost heuristic function returns 10 because it is the maximum cost out of three branches.

The relaxation in this approach is that it uses only the max-cost of all the literals. Planning problem is relaxed in the way that it assumes that the goal can be reached by just using one literal in the goal.

To see the difference, we use GBFS algorithm without heuristic function and with max-cost heuristic function to solve our problem.

Without heuristic, Pacman explores all possible areas as shown below.

With max-cost heuristic, Pacman is able to reduce the explored areas as shown in red dots below.

It is clear that Max-cost heuristic helps in reducing the number of nodes explored by Pacman.

In the next section we look at slightly different approach, Additive-cost Heuristic.

Additive-cost Heuristic

Additive-cost Heuristic is closely related to Max-cost heuristic. It is not admissible because the cost is often larger than the optimal cost.

Recall that 0 ≤ h(s) ≤ h*(s).

Additive-cost heuristic uses the same approach as Max-cost heuristic, but instead of choosing the largest cost among all literals, it adds all of them up. This approach is generally better in practice because it considers all literals, not only one of them.

Using And/Or Tree with cost in the picture above, the heuristic is the total of 2+1+10 = 13.

Let’s look at how it performs on our problem:

We can see that this works better than Max-cost heuristic and without heuristic and the solutions are different. See videos below to see the execution of the plans.

Consideration

Although the number of explored nodes reduce when using these two heuristics, we need to always consider the trade-off between the computation time of heuristic function and number of reduced nodes.

A heuristic is only helpful if it reduces the total time required by search algorithm, otherwise even if it helps in reducing the number of explored nodes it is not worthwhile if the total time is more than without heuristic.

In our example, the available actions for Pacman are quite low-level in that it only moves the Pacman one step, they are not directly related to other literals in states such as foods, capsules, etc. Therefore, using these two heuristics, the total time is longer than without heuristic. Because the heuristic is essentially a backward search from goal to the state that we want to examine.

Delete-relaxation Heuristic

In the next post we will discuss about another approach, delete-relaxation heuristic.