The Pattern Recognition Basis of Artificial Intelligence

Chapter 8. Problem Solving and Heuristic Search

Whereas it is easy to observe heuristic search in people solving problems notice that people have some kind of general architecture that lets them do all sorts of problems whereas AI researchers have not yet found such a general approach, every new problem must be programmed. One tool called SOAR makes this easy yet every new problem requires a special effort. Notice too that in these heuristic programs the approach is normally to list all the possible moves you can make, rate each one and then take the best of these moves. I've never studied how people do such things but it seems to me that the way a person works is to use a Boltzman machine like strategy to come up with a solution and try it out immediately without trying to come up with more solutions. If this good solution does not work then the person tries to come up with another one.

The other thing I want to mention is this "flash of insight" behavior since it may be that quantum mechanics can explain it. In Penrose's book, The Emperor's New Mind, he talks about one case where he was busy trying to solve a certain problem in mathematical physics. Then one day while he was doing something unrelated, walking down a road discussing a different subject with a colleague he had a flash of insight into how to solve his mathematical physics problem. Later on he used this insight to solve his problem. There are other similar examples of this that other famous scientists have reported.

I'd like you to notice that this flash of insight works a lot like something that happens to ordinary people. Suppose you're simply trying to remember something. For instance, who played that part in a certain movie or TV show? Its one of those things that you know you know but you can't get to the answer, only a faint impression of it. Then perhaps hours later when you're not even trying, the answer pops into your mind. Some quantum mechanics enthusiasts suggest that the flash of insight behavior is really the same thing except in this case you're remembering the future. For instance in Penrose's case out there in the future he had the solution in his mind. Now in the present all he has to do is "remember" it. If information can be passed along at faster than the speed of light this is quite possible. If that is what is going on then it gives people a heuristic that no ordinary computer can duplicate.

If QM allows you to remember the future you have to wonder why people don't remember the future all the time, especially useful things like the winning lottery numbers? My answer to this is that if anyone could remember the future with any degree of accuracy we would not have lotteries because everyone would win and having a lottery would be pointless. If you're going to have a lottery the "universe" has to find a compromise between everyone remembering the winning numbers and no one winning the lottery. It has to be rare for memories from the future to appear in the present. Mathematicians and other scientists are lucky in that when they have a flash of insight they have the means to prove it correct here in the present.

NOTE THAT NO QM OR FLASH OF INSIGHT BEHAVIOR IS COVERED IN THIS CHAPTER, I simply put the above comments in this introduction so that readers can appreciate that there may be more to what people do than plain heuristic search.

8.1 The 8-Puzzle

The 8-puzzle is perhaps the best example of how you can use heuristic search to solve a problem.

8.2 A Geometry Theorem Prover

This covers Gelernter's sort of geometry theorem proving. Its a blend of having to use symbol processing with heuristics involving pictures, even though the "pictures" are represented internally by symbolic facts and numerical quantities. Notice just how unthinkable it would be to try and do this problem with simple neural networking techniques like backprop. You would need an architecture resembling the human architecture to do this and we are nowhere near that point. The PROLOG code is in the PROLOG Programs Package.

8.3 Symbolic Integration and Heuristic Search

This is largely the famous SAINT program, a little bit about LEX, a program that finds heuristic rules to speed up the search and how a little backprop network can be used to generate heuristics as well. Notice here too that full-blown symbolic integration would be a real nightmare to do using only neural networks.

The integration problem is probably a nice candidate for solving using image based/picture based and case based/memory based processing. Imagine a system that would look at a problem on a piece of paper. This should bring to mind a similar case from the past, an image that has been remembered. Then the program should go and apply the same transformation to the new problem as was used in the old problem. It would write out the new version on another piece of paper, use this as input to decide on a new transformation to apply and so on until the problem is solved. Could it all be done with just images, without any symbols at all? I suspect it can and that is how people really operate. Anybody want to try to program this?

Notice another thing about the integration problem. Whereas people view a piece of paper and write down symbols on it these symbol based programs like SAINT have internalized this symbol manipulation by using LISP to do this part of the work. Symbol processing can then be seen as a substitute for having hands, using pencils and writing on paper. Is this an improvement over the human method?

8.4 Other Heuristic Programs

This section just briefly lists some heuristic search programs. Again let me note that the SOAR home page is at Carnegie-Mellon. For a little more on SOAR used to do air combat simulations see the SOAR-group page at the University of Michigan.

Note that there are many, many other heuristic search techniques that have been researched to solve particular problems and they have not been included in this chapter. For any particular application any one of these may be much better than a human being yet I have to doubt that studying them will help much in trying to create a human-like heuristic search program. People are using some wonderful method that can be used for all sorts of problems. Trying to track down that algorithm would be a useful thing for artificial INTELLIGENCE researchers to do. Although maybe the algorithm is just a Boltzman machine-like process that works with memories. Whatever the case those many, many other heuristic search techniques don't quite belong in artificial INTELLIGENCE, they belong in a course on "advanced programming techniques" or "analysis of algorithms".

If you have any questions or comments, write me.

To Don's Home Page