Issues in theoretical and practical complexity for heuristic search algorithms

Abstract

The 8-puzzle and the 15-puzzle have been used for many years as a domain for testing heuristic search techniques. From experience it is known that these puzzles are and therefore useful for testing search techniques. In this dissertation we give evidence that these puzzles are indeed good test problems. We extend the 8-puzzle and the 15-puzzle in a natural way by allowing arbitrary board size, and show that finding a shortest solution for the extended puzzle is computationally infeasible. This is done by proving that the following decision problem is NP-complete: Input. two n x n boards and a bound k. Question. is there a solution for transforming the first board into the second board requiring less than k moves? We give an approximation algorithm for transforming boards that is guaranteed to use no more than c (.) L(SP) moves, where L(SP) is the length of the shortest solution and c is a constant which is independent of the given boards and their size n. We prove that relocating elements that reside in nodes of planar graph via an Eulerian path is NP-complete. This problem and the above problem can be viewed as a simple robotics problem: A robot needs to efficiently relocate objects in the plane. We introduce two new algorithms, Joint and LPA*, which can be used to solve difficult combinatorial problems heuristically. These algorithms result from a combination of approximation and search algorithms. The algorithms find reasonably short solution paths and are very fast. Both algorithms work in polynomial time in length of the description of the problem. Once we have proved that finding a shortest path in the generalized 15-puzzle is NP-hard, we can use, without any hesitation, the 15-puzzle as an experimental domain. The algorithms have been benchmarked on a standard set of 50 problems, and outperform other known methods within time limitations.