Easy to Learn Java: Programming Articles, Examples and Tips

Start with Java in a few days with Java Lessons or Lectures

Home

Code Examples

Java Tools

More Java Tools!

Java Forum

All Java Tips

Books

Submit News
Search the site here...
Search...
 

Contents (First page with contents)

Custom Search
Contents (First page with contents)

[ Return to Artificial Intelligence ]

Page: 1/3 



Next Page (2/3) Next Page
Artificial Intelligence  Search Techniques in Java by Mark Watson

Artificial Intelligence 
Search Techniques in Java by Mark Watson

 

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.

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.



[ Return to Artificial Intelligence ]


Top 10 read Java Articles
 Get free "1000 Java Tips eBook"

 Java Calendar and Date: good to know facts and code examples

 Array vs ArrayList vs LinkedList vs Vector: an excellent overview and examples

 How can I convert any Java Object into byte array? And byte array to file object

 The Java Lesson 1: What is Java?

 How do I compare two dates and times, date between dates, time between times and

 Maven vs Ant or Ant vs Maven?

 How to open, read, write, close file(s) in Java? Examples on move, rename and de

 Java Array

 Java: JLabel font and color


[ More in News Section ]
Java Lessons

The Java Lesson 1:
What is Java?
The Java Lesson 2:
Anatomy of a simple Java program
The Java Lesson 3:
Identifiers and primitive data types
The Java Lesson 4:
Variables, constants, and literals
The Java Lesson 5:
Arithmetic operations, conversions, and casts
The Java Lesson 6:
Boolean expressions and operations
The Java Lesson 7:
Bitwise operations
The Java Lesson 8:
Flow control with if and else
The Java Lesson 9:
switch statements
The Java Lesson 10:
for, while, and do-while statements
The Java Lesson 11:
Using break and continue
The Java Lesson 12:
Class methods and how they are called
The Java Lesson 13:
Using the Math class
The Java Lesson 14:
Creating and calling custom class methods
The Java Lesson 15:
Overloading class methods
The Java Lesson 16:
An introduction to objects and object references
The Java Lesson 17:
The String class
The Java Lesson 18:
The StringBuffer class
The Java Lesson 19:
Initializing and processing arrays of primitives
The Java Lesson 20:
Initializing and processing arrays of objects
The Java Lesson 23:
Inheritance and overriding inherited methods
The Java Lesson 24:
abstract classes and polymorphism
The Java Lesson 25:
Interfaces, instanceof, and object conversion and casting
The Java Lesson 26:
Introduction to graphical programming and the java.awt packa
The Java Lesson 27:
The Component class
The Java Lesson 28:
Containers and simple layout managers
The Java Lesson 29:
The Color and Font classes
The Java Lesson 30:
Drawing geometric shapes
The Java Lesson 31:
Choice, List, and Checkbox controls
The Java Lesson 32:
Using the Scrollbar graphical control
The Java Lesson 33:
Menus and submenus
The Java Lesson 34:
An introduction to applets and the Applet class
The Java Lesson 35:
Essential HTML to launch an applet and pass it parameters
The Java Lesson 36:
Mouse event processing
Java Lesson 37:
Menus and submenus
Java Lesson 38:
The WindowListener interface and the WindowAdapter class
Java Lesson 39:
An introduction to GridBagLayout
Java Lesson 40:
An introduction to the Java Collections API
Java Lesson 41:
Exception handling with try, catch, and finally blocks
Java Lesson 42:
Claiming and throwing exceptions
Java Lesson 43:
Multithreading, the Thread class, and the Runnable interface
Java Lesson 44:
An introduction to I/O and the File and FileDialog classes
Java Lesson 45:
Low-level and high-level stream classes
Java Lesson 46:
Using the RandomAccessFile class
Java Lessons by
Joh Huhtala: Update

Latest articles
 Java Profiler JProbe to Resolve Performance Problems Faster

 SSL with GlassFish v2, page 5

 SSL with GlassFish v2, page 4

 SSL with GlassFish v2, page 3

 SSL with GlassFish v2, page 2

 The Java Lesson 2: Anatomy of a simple Java program, page 2

 New site about Java for robots and robotics: both software and hardware.

 Exceptions -III: What's an exception and why do I care?

 Exceptions -II: What's an exception and why do I care?

 Exceptions: What's an exception and why do I care?

 Double your Java code quality in 10 minutes, here is receipt

 Murach's Java Servlets and JSP

 How to get ascii code from a char in Java?

 Can we just try without catch? Yes!

 Make Tomcat page load faster

 Make your Tomcat More secure - limit network address for certain IP addresses

 New Java book online starts now here...

 Implementing RESTful Web Services in Java

 Firefox trimming from 1 GB to 40 Mb with many tabs opened

 SSL with GlassFish v2

 My request to replublish Tech Tips

 Search JavaFAQ.nu site here

 New Advanced Installer for Java 6.0 brings XML updates and imports 3rd party MSI

 EJB programming restrictions

 Maven vs Ant or Ant vs Maven?

 Why Java does not use default value which it should?

 How to unsign signed bytes in Java - your guide is here

 The Java Lesson 3: Identifiers and primitive data types. Page 2

 The Java Lesson 7: Bitwise operations with good examples, click here! Page 4

 The Java Lesson 7: Bitwise operations with good examples, click here! Page 3


[ More in News Section ]


Home Code Examples Java Forum All Java Tips Books Submit News, Code... Search... Offshore Software Tech Doodling

RSS feed Java FAQ RSS feed Java FAQ News     

    RSS feed Java Forums RSS feed Java Forums

All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest 1999-2006 by Java FAQs Daily Tips.

Interactive software released under GNU GPL, Code Credits, Privacy Policy