Artificial Intelligence Search Techniques in Java

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.

In the file DepthFirstSearch.java, we define the positions of nine test nodes:

        addNode("0", 0.0f, 0.0f);
        addNode("1", 1.0f, 1.0f);
        addNode("2", 5.0f, 2.0f);
        addNode("3", 2.0f, 5.0f);
        addNode("4", 7.0f, 5.0f);
        addNode("5", 8.0f, 8.0f);
        addNode("6", 10.0f, 5.0f);
        addNode("7", 8.0f, 2.0f);
        addNode("8", 12.0f, 8.0f);
        addNode("9", 13.0f, 5.0f);

In the above figure showing our sample network, we define the "links" in the following order:

        addLink(0,1);
        addLink(1,2);
        addLink(2,3);
        addLink(2,4);
        addLink(4,5);
        addLink(4,6);
        addLink(6,8);
        addLink(8,9);
        addLink(2,7);
        addLink(7,9);

The order that the links are defined is important in a depth first search. if we start at node "0" and search to node "9", then we find the first link leaving node "0" (in this case link "0" to "1"). Then we take the first link leaving node "1" (in this case link "1' to "2"), etc. When we "run out of" links to explore from a given node, then we "back up" to the preceeding node, and explore all other links that leave that node.

I am sure that you have already tried running the depth first search applet, right? Then you will have noticed that it found a rather long path from node "0" to "node "9". The depth first search applet stops when it has found a path. The breadth first search applet in Chapter 6 finds better paths, in general. I assume that you know how to program in Java, so I will just briefly explain what each method in classes SearchApplet and DepthFirstSearch. We will discuss the implementation of BreadthFirstSearch in Chapter 6.

Methods in SearchApplet

• init - this method is called by the applet container (e.g., a Java enabled web browser, or the "appletviewer" utility) when an applet is started. Here, we just get the applet width and height, and set up two Java AWT "Choice" controls so that the user of the applet can change the start and goal nodes. We use internal anonymous classes to handle events for the "Choice" controls, so this applet requires Java version 1.1 or higher.
• repaintPath(int [] path, int num_in_path) - this is a graphics utility method for drawing a specified path on the applet's canvas.
• repaintPath(int [] path) - this is a graphics utility method for drawing a specified path on the applet's canvas.
• paintNode(Graphics g, String name, int x, int y) - this is a simple utility method for drawing a node at a specified location.
• paint(Graphics g) - this method is called by the applet's container whenever the applet needs to update its display.
• addNode(String name, float x, float y) - for adding a new node to the network.
• String getNodeName(int index) - returns a specified node's name.
• float getNodeX(ind index) - returns a speficified node's X coordinate.
• float getNodeY(ind index) - returns a speficified node's Y coordinate.
• float getPathLength(int index) - returns a specified link's length. This is not currently used, but would be required for adding heuristics to the search.
• addLink(int index1, int index2) - for adding a link given two node indices.
• addLink(String name1, String name2) - for adding a link given two node names.
• abstract int [] findPath(int node_1, int node_2) - this is an abstract method for finding a path between two specified nodes. This method will be overriden in the classes DepthFirstSearch and BreadthFirstSearch
• int getNodeIndex(String node_name) - returns the node index, given its name.

Methods defined in class DepthFirstSearch

The class DepthFirstSearch is derived from the class SearchApplet and defines the following methods:

• init - this method defines a test network, then calls the super class SearchApplet method init.
•  
• int [] findPath(int node_1, int node_2) - this is a method for finding a path between two specified nodes using a depth first search as described in the text. The return value for this method is an array of node indices.
• int [] findPathHelper(int [] path, int num_path, int goal_node) - this is the actual search method that calls itself recursively.
• repaintPath(int [] path, int num_path) - converts an ordered list of node indices to a doubled up list, then calls the super class method repaintPath.
• int [] connected_nodes(int [] path, int num_path) - this is a helper method called by findPathHelper that finds all nodes connected to the last node on the current path that are not already on the current path.
• int [] copy_path(int [] path, int num_to_copy) - this is a helper method called by findPathHelper that copies a path array.

If you have not already done so, return to the table of contents page, and experiment with the depth first search applet.

Chapter 6 - Implementing Breadth First Search

We saw in Chapter 5 how networks are initialized in the base class SearchApplet and the implementation of the derived class DepthFirstSearch. In this chapter, we will derive another class BreadthFirstSearch from class SearchApplet that calculates, in general, better paths that the depth first version. You can use this new class in your own applications, optionally adding search heuristics for the particular type of problem that you are solving.

The breadth first search uses a Queue data structure (a queue is a sequence that is "first in, first out"; that is, you remove items from a queue in the same order that they were added). If we want to perform a breadth first search from node "0" to node "9", we start by putting all of the nodes connected to node "0" on the queue. Then we add the nodes connected to the items currently in the queue, and continue this process until we arrive at the goal node.

For many applications, you would want to add heuristics to a breadth first search by controlling the "order in which nodes are added to the queue. For example, let us look again at our sample network:

If we are starting at node "4" and searching for node "9", then we would first add the following nodes to the queue:

• 2
• 5
• 6

The BreadthFirstSearch class adds these nodes in an arbitrary order. However, you might want to add (this is an exercise for the reader) the heuristic that you add nodes that are closer to the goal node first. For most problems, the ordering of nodes added to the queue will have a dramatic effect on performance. If we ordered the nodes connected to node "4" in order of closeness to the goal node "9", then we would add them in this order:

• 6
• 5
• 2

Methods defined in class BreadthFirstSearch

The class BreadthFirstSearch is derived from the class SearchApplet and defines the following methods:

• init - this method defines a test network, then calls the super class SearchApplet method init.
•  
• int [] findPath(int node_1, int node_2) - this is a method for finding a path between two specified nodes using a breadth first search as described in the text. The return value for this method is an array of node indices.
• Inner class Queue - this utility class implements a standard Queue data structure, and is used by method findPath.
• int [] connected_nodes(int node) - this is a helper method called by findPath that finds all nodes connected to a specified node.
• int [] copy_path(int [] path, int num_to_copy) - this is a helper method called by findPathHelper that copies a path array.

This concludes my "book" on simple search techniques in Java. Really, I have just skimmed the surface of this material, but I hope that reading this book has provided you with both some understanding of search techniques, and some Open Source Java source code that you can use for both education and in your own software products.

aa

OpenContent License (OPL)
Version 1.0, July 14. 1998

This document outlines the principles underlying the
OpenContent (OC) movement and may be redistributed
provided it remains unaltered. For legal purposes, this
document is the license under which OpenContent is
made available for use.

The original version of this document may be found at
http://www.opencontent.org/opl.html

LICENSE

Terms and Conditions for Copying, Distributing, and
Modifying Items other than copying, distributing, and
modifying the Content with which this license was
distributed (such as using, etc.) are outside the
scope of this license.

1. You may copy and distribute exact replicas of the
   OpenContent (OC) as you receive it, in any medium,
   provided that you conspicuously and appropriately
   publish on each copy an appropriate copyright notice
   and disclaimer of warranty; keep intact all the notices
   that refer to this License and to the absence of any
   warranty; and give any other recipients of the OC a
   copy of this License along with the OC. You may at
   your option charge a fee for the media and/or handling
   involved in creating a unique copy of the OC for use
   offline, you may at your option offer instructional
   support for the OC in exchange for a fee, or you may at
   your option offer warranty in exchange for a fee. You
   may not charge a fee for the OC itself. You may not
   charge a fee for the sole service of providing access to
   and/or use of the OC via a network (e.g. the Internet),
   whether it be via the world wide web, FTP, or any other
   method.

2. You may modify your copy or copies of the
   OpenContent or any portion of it, thus forming works
   based on the Content, and distribute such modifications
   or work under the terms of Section 1 above, provided
   that you also meet all of these conditions:

     a) You must cause the modified content to carry
        prominent notices stating that you changed it,
        the exact nature and content of the changes,
        and the date of any change.

     b) You must cause any work that you distribute or
        publish, that in whole or in part contains or is
        derived from the OC or any part thereof, to be
        licensed as a whole at no charge to all third
        parties under the terms of this License, unless
        otherwise permitted under applicable Fair Use law.

   These requirements apply to the modified work as a
   whole. If identifiable sections of that work are not
   derived from the OC, and can be reasonably considered
   independent and separate works in themselves, then
   this License, and its terms, do not apply to those
   sections when you distribute them as separate works.
   But when you distribute the same sections as part of a
   whole which is a work based on the OC, the distribution
   of the whole must be on the terms of this License,
   whose permissions for other licensees extend to the
   entire whole, and thus to each and every part
   regardless of who wrote it. Exceptions are made to this
   requirement to release modified works free of charge
   under this license only in compliance with Fair Use law
   where applicable.

3. You are not required to accept this License, since you
   have not signed it. However, nothing else grants you
   permission to copy, distribute or modify the OC. These
   actions are prohibited by law if you do not accept this
   License. Therefore, by distributing or translating the
   OC, or by deriving works herefrom, you indicate your
   acceptance of this License to do so, and all its terms
   and conditions for copying, distributing or translating
   the OC.

NO WARRANTY

4. BECAUSE THE OPENCONTENT (OC) IS
   LICENSED FREE OF CHARGE, THERE IS NO
   WARRANTY FOR THE OC, TO THE EXTENT
   PERMITTED BY APPLICABLE LAW. EXCEPT
   WHEN OTHERWISE STATED IN WRITING THE
   COPYRIGHT HOLDERS AND/OR OTHER
   PARTIES PROVIDE THE OC "AS IS" WITHOUT
   WARRANTY OF ANY KIND, EITHER EXPRESSED
   OR IMPLIED, INCLUDING, BUT NOT LIMITED
   TO, THE IMPLIED WARRANTIES OF
   MERCHANTABILITY AND FITNESS FOR A
   PARTICULAR PURPOSE. THE ENTIRE RISK OF
   USE OF THE OC IS WITH YOU. SHOULD THE OC
   PROVE FAULTY, INACCURATE, OR OTHERWISE
   UNACCEPTABLE YOU ASSUME THE COST OF
   ALL NECESSARY REPAIR OR CORRECTION.

5. IN NO EVENT UNLESS REQUIRED BY
   APPLICABLE LAW OR AGREED TO IN WRITING
   WILL ANY COPYRIGHT HOLDER, OR ANY
   OTHER PARTY WHO MAY MIRROR AND/OR
   REDISTRIBUTE THE OC AS PERMITTED ABOVE,
   BE LIABLE TO YOU FOR DAMAGES,
   INCLUDING ANY GENERAL, SPECIAL,
   INCIDENTAL OR CONSEQUENTIAL DAMAGES
   ARISING OUT OF THE USE OR INABILITY TO
   USE THE OC, EVEN IF SUCH HOLDER OR OTHER
   PARTY HAS BEEN ADVISED OF THE
   POSSIBILITY OF SUCH DAMAGES.