Artificial Intelligence Search Techniques in Java Version 0.6

This document is licensed under the Open Document License Agreement, and is Copyright by Mark Watson, 1998. Please visit www.markwatson.com for the newest version of this Open Document.

Table of contents 1. A brief history of AI 2. Why search algorithms are not AI 3. How we use search algorithms in AI projects 4. A Java Framework for Search Engines 5. Implementing Depth First Search 6. Implementing Breadth First Search Java source code links: SearchApplet.java DepthFirstSearch.java BreadthFirstSearch.java

Depth first search Breadth first search

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.

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".

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.

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);                

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

• 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.

Chapter 6 - Implementing Breadth First Search

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:

• 2
• 5
• 6

• 6
• 5
• 2

Methods defined in class BreadthFirstSearch

• 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.

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.