Composite heuristic for the 8-puzzle

Question

While reading Artificial Intelligence a Modern Approach I came across the concept of deriving a heuristic from the solution cost of a sub-problem of a given problem.

For example, the following puzzles shows a sub problem of the 8-puzzle instance where the goal is to place tiles 1, 2, 3, 4 into their correct positions.

Start State = [ * 2 4 ]    Goal State = [   1 2 ]                      
              [ *   * ]                 [ 3 4 * ]
              [ * 3 1 ]                 [ * * * ]  

Then, the author expand this concept by saying that these heuristics derived from the sub-problems can be combined by taking the maximum value.

h(n)= max{ h1(n), . . , hm(n) }

Moreover, by using this approach the performance is improved greatly when compared to a simple heuristic like Manhattan distance.

I have been trying to wrap my head around the composite heuristics and the reasoning behing them. Let's say we have two heuristics derived from the solution cost of the following sub-problems:

h1234(n) = [   1 2 ]     h5678(n) = [   * * ]                    
           [ 3 4 * ]                [ * * 5 ]
           [ * * * ]                [ 6 7 8 ]

Will a composite heuristic like:

h1...8(n)= max{ h1234(n), h5678(n) }

1. Really work in finding a solution for the complete 8-puzzle problem?

It seems to me that using a heuristic like h1...8(n) we will end up alternating between heuristics h1234(n) and h5678(n) which in turn might lead to one heuristic messing up the work of the other and never reaching a solution.

2. Or will the heuristics help each other towards the complete solution?

Honestly, I do no see how this could work...

Answer 1

First I will give you a brief overview of the idea behind the heuristic and why solving a subproblem, also called relaxed problem, helps to find the solution. Then, I will cast the following general considerations to the 8-puzzle problem and thus answer to your specific question. For more detailed information, you can start, as you already did, reading carefully Chapter 3 of Artificial Intelligence: a Modern Approach, by Stuart and Russell; if you want to deepen the topic about best-first search strategies and heuristics, you can start from one of the seminal papers by Dechter and Pearl, 1984, ACM, and look at the cited papers and those who cite it.

Overview of heuristics and informed search

The idea behind using a heuristic is to guide the search through the search space (usually exponential size) and carefully selecting nodes to be expanded (this type of search algorithms are also called informed search algorithms). If the heuristic is good (namely, close to the actual cost to the goal, starting from an initial state), then the number of nodes expanded during the search is greatly reduced, and actually that number is optimal -- namely no other search algorithm can expand less nodes guaranteeing optimality of the solution. Remember that the heuristic should be admissible -- its value of a given node should not exceed the actual cost to the goal. This is the only property required if an open list is used, namely not eliminating duplicate states. If duplicate states are eliminated, the heuristic should be also consistent -- i.e., the heuristic of a given node should be less or equal than the sum of the cost to get to a successor node and the heuristic in that successor node.

Usually, finding a solution for a relaxed problem can be done in less computation time. A heuristic can be extracted from that solution and is typically more informative than a heuristic coming from just an estimate on the whole problem, as the solution provides actual actions that should be performed. Notice that when defining a subproblem, it is fundamental to check whether the heuristic that can be derived from the solution of the subproblem is still admissible for the general problem, in order to have an optimal solution.

8-puzzle problem

In the specific case of 8-puzzle, the heuristic coming from the subproblem is still intuitively admissible for the original problem. Specifically, the optimal solution in the original problem is also a solution to the relaxed problem and satisfies in addition all the relaxed constraints. So, the solution cost matches at most the original optimal solution. Second, the relaxed problem has fewer constraints. Therefore, the search algorithm can find less expensive solutions and provide a lower cost, thus admissible, relaxed solution.

Given this analysis and answering to your question, using the heuristic that you mention works in finding a solution for the complete 8-puzzle problem. Taking the max allows to have an estimate closer (and admissible) to the actual cost to the solution and thus helping expanding less number of nodes.