Artificial Intelligence 
Search Techniques in Java by Mark Watson

Chapter 1 - A brief history of AI

When computers were first built, their speed of numerical computations convinced most people that the following fallacy was true:

• Computers have more computational power than the human brain

Now, computers are millions of times faster than they were fifty years ago. Still, I would argue that for many tasks, this statement is still a fallacy.

Human brains seem to be far "faster" than computers for a wide variety of tasks; for example:

• Recognizing human faces in photographs
• Driving a car using computer vision
• Some types of associative memory recall

Still, greater computational speed does make some so-called AI systems seem smarter. Very good examples of this are computer games that use search techniques. I have been interested in writing computer chess and Go programs for a long time (I wrote the BASIC chess program on the demo cassette tape for the Apple II computer, and I wrote and marketed a commercial Go program, Honninbo Warrior, also for the Apple II).

This short "book" covers the very rudiments of AI search techniques: we initially cover depth first and then breadth first search of networks. We will discuss how to add heuristics to the breadth first search.

A network is defined as a set of nodes and a set of bi-directional links connecting these nodes.

Unless you are not at all curious, you have already tried running the two example Java applets that appeared to the right of the table of contents of this book. Each applet has a network of nine nodes, with several links (e.g., connecting node 0 to node 1, 2 to 3, 2 to 4, etc.). Each Java applet tries to find a path from the starting node to the goal node. In the two sample applets, you can change the starting node and the goal node by using the Java AWT (abstract window toolkit) choice controls.

The development of search techniques was considered to be one of the early successes of AI research.

There are many techniques of AI programming that are not covered here (e.g., expert systems, neural networks, planning, etc.). Also, the material on search in this "book" is very rudimentary, and is written for home hobbiest-programmers.

Chapter 2 - Why search algorithms are not AI

Search algorithms are a technique, but, in my opinion, do not represent AI at all. However, search algorithms are useful for building some types of AI systems. For example, search is an important part in computer programs for game playing (like chess and Go) and planning systems.

Planning systems usually involve the automatic generation and evaluation of plans to accomplish specific goals. It a very simple form, one might (or might not) call our two sample Java applets simple planning systems (to answer questions like "what route will take me from node 0 to node 9?"). However, real AI planning systems involve more complex tasks such as planning routes for robots to take through real (physical) environment, etc.

So, we will consider search to be a tool, or technique, that can be used in AI planning systems, computer games, et.

One idea that came out of early AI research was the notion of separating domain independent code from domain dependent data. Probably the best example of this technique is so-called "expert systems". There are many good domain independent "engines" like OPS5, CLIPS, and Jess that are completely independent of any knowledge for solving specific problems. Instead, these "engines" use data in the for of "if/then" rules to solve problems. As an example (from my Java AI book) we might want to write an expert system to diagnose medical problems associated with skin diving and scuba diving. Here we would develop a large set of domain specific (i.e., specific to solving the problem of diving medical problems) rules. An example rule might be (translated to "English"):

If there are two puncture marks and the surronding area is red, then there
is a strong probablity of an octopus bite.
If there are two puncture marks and the surronding area is not red, then there
is a weak probablity of an octopus bite.

Most people consider so-called "expert systems" to be AI. Another example of AI is natural language processing. There are many aspects to automatically processing (with computer software) natural language text. Most systems start by calculating parts of speech for input text. For example (from my free Open Source NLPServer will calculate parts of speech for any input sentence (or at least try to!). The NLPserver outputs results in either plain text, HTML, or XML. For example:

Output type: TEXT  Part of speech query: the dog ran down the street

  art, the;
  noun, dog;
  verb, ran;
  adj, down;
  art, the;
  noun, street;

Other types of AI research involve the use of artificial neural networks, genetic algorithms, and genetic programming.

Chapter 3 - How we can use search algorithms in AI systems

In Chapter 2, we indicated that search techniques are a powerful tool for building some types of AI systems. Here are two example applications of search techniques:

• Scheduling deliveries - You own a local flower shop, with two delivery drivers. You receive about 50 orders a day, and you want to minimize the cost (in time and fuel) for making these deliveries. You decide to write a program that accepts as input a list of street addresses, and prints out a suggested route. Your program contains a network (like the two example applets on the table of contents page) representing the major streets in your small town. The "links" in the network represent streets, and the "nodes" represent intersections. "Links" might also include average travel speed.
• Computer game - you are writing a computer game that involves a "dungeon" made up of caves (the "nodes" in a network) and tunnels (the "links" in a network). You want "AI" characters to be able to move in reasonable paths, so you use a simple search (like the breadth first example applet) to calculate paths for the "AI" characters to move along. You have a general game engine that moves the "AI" characters a specified distance along a path each "game turn".

There are many other possible uses for the search, but I think that one of these examples would be a good way for you to apply what you learn in this "book".

Chapter 4. A Java Framework for Search Engines

Purpose

We want a Java class framework for implementing different search algorithms. Our goals (or requirements) are to design and implement:

• An abstract Java class Search that encapsulates the data required for storing nodes in a network, and the connections between nodes. This class will also supply common behavior for specific search algorithm classes that we derive from this abstract class.
• Two sample classes derived from Search:
  • DepthFirstSearch - search nodes depth first
  • BreadthFirstSearch - search nodes breadth first

We also want a nice way to display networks and to visualize how the search algorithms work for a given network, and for a given starting and ending path point. We will design and implement a Graphics User Interface (GUI) class SearchPanel that can be created with any instance of a sub-class of Search.

As a final task, we will write two Java applets (that is shown on the first page) that demonstrates both depth first and breadth first search.

These three Java classes are Open Source software; please feel free to remove the search specific code from the two test applets, and use it in your own applications! (Also, please feel free to re-distribute this document!)

Chapter 5 - Implementing Depth First Search

There are two active Java applets shown to the right of the table of contents of this book showing a demonstration of depth first and breadth first search . These two Java applets show a simple network:

Before we design and implement any search programs, we will "walk through" a search of this simple network, trying to find a path from node "0" to node "9". Specifically, we will manually perform a depth first search.