Jake Bishop

Final Project

Artificial Intelligence &

ACCA Argonne - UML

Final Project: case study of an Object Oriented Artificial Intelligence experiment

Object Oriented programming and Artificial Intelligence are not commonly associated with each other in the programming world. Is this because of simple disassociation, or are OO and AI simply not compatible together? This project is a case study to show one possible development plan and implementation of AI using the OO programming paradigm.

Artificial Intelligence by definition is a machine or artifact designed to mimic or possess intelligent behavior. Its conceptual goal is to develop intelligence as good as or better than man, to understand intelligence better, and to perform tasks that require intelligence.

The use of AI in this project is to create intelligent agents who can search a map space, avoiding obstacles and other agents, to find a goal. By using different search algorithms within the agents, it is possible to learn the effectiveness of those algorithms in various scenarios relative to each other.

The Object Oriented programming paradigm allows abstraction of details, representing real-world objects within the code, and reusability and scalability of the program elements after it is completed. The project will be engineered using UML (Universal Markup Language) standards, to represent the OO concepts used in its design.

The first step in designing any good program is a clear, concise statement of the system requirements.

The project should be designed as an object-oriented system utilizing artificial-intelligence algorithms to run a simulation of goal-seeking agents navigating a map. The purpose of this system is to allow the user to test and compare the search strategies of goal-seeking algorithms used in artificial intelligence, using an object oriented programming environment.

From this basic statement, we can develop some concepts about the object models and their relationships. This is derived from the developer’s mental model into pseudo-objects, i.e. without going into implementation details.

The classic AI toy-problem we are using is a goal-seeking agent. A toy-problem is the mental abstract of a real-world problem that retains the key details of the problem while eliminating complex and confusing details. Just as the software is a model of the mental exercise of mobile agents seeking a goal, the mental exercise is a visualization of a real-world problem, such as an Artificial Intelligence robot searching for minerals on a planet surface, or rats searching for food in a maze.

In the mental model, there exist intelligent agents that can travel through a grid space, interact with obstacles, and search for a goal. The grid space is a 2-D map of reference points that the agents, obstacles, and goal co-exist upon. Neither agents nor the goal may reference their position to the same reference point as an obstacle. Agents may move their reference point based on the evaluation of their adjacent surrounding reference points on the map by the designated search algorithm for each agent. Agents may not pass through obstacles, agents must seek the goal, and agents must keep a record of the path they take from their initial reference point to the goal if a solution is reached.

Now the details of the system have been expanded from the requirement statement, they need to be further defined concisely into object-oriented concepts.

The system must meet the needs of the user, as defined above. The tasks that the user needs the system to help perform are called use cases.

Initialize map - define map dimensions (search space)
Initialize goal (define goal and utility)
Initialize obstacles (define problem)
Initialize agents

Choose number of agents

o Choose algorithm for each agent

Choose start pattern for agents (starting point(s) )

Populate map – reference goal, obstacles, and agents
Start simulation

· Cancel simulation

Receive solution data from agents if simulation completes
Repeat same simulation
Begin new simulation
Exit program

Defining objects, and classes of objects, are a key necessity of Object-Oriented design. Objects are the abstract instances of the things that interact in our mental model. An object class is a definition of types of things. By creating a list of object classes for the system model, the use cases can be broken down into relationships between those objects, and the tasks and attributes they must possess. The list of object classes can be constructed as follows:

· Search Algorithms

Agents
The map
The goal
Obstacles
The solution path

And once the objects have been defined, the relations between objects can be defined:

A map references the position of the goal, obstacles, and agents.
Agents traverse the map.
Agents search for the goal.
An agent completes a solution path when it has reached the goal.
Obstacles restrict agents from referencing their position on the map.
Agents require a search algorithm to make decisions.
Agent has found a solution when it references the same ref point as the goal.

These relationships can be modeled in a diagram using a UML class model.

The system requirements have been defined; the objects that may exist within the system have been defined; the object relationships begin to show the rules for their behavior within the system. It is now possible to begin to define the actions of the system in action.

A Sequence diagram shows how messages pass between objects of the system to carry out some task. These tasks can be extrapolated from the use cases, and the rules defined by the object relationships.

Operations:

Agents

load_agent( [algorithm] ) initializes agent for population

optional parameter sets search algorithm

map_init(x,y) during map population, references start point at ref point coordinate {x,y}

look(direction) returns 2 if adjacent ref point in direction is goal

returns 1 if occupied by agent or obstacle

returns 0 if unoccupied

move(direction) sends message to map to 1. reference agent position to adjacent ref point in direction as new ref point for agent, and 2. free current ref point on map (un-occupy)

detect_goal( ) return 1 if occupying goal ref point

return 0 if not occupying goal ref point.

return_path(*address) when agent finds solution path, returns dynamic link to solution path stored in memory

Map

create_map(x,y) generates a map with dimensions x rows and y columns in size.

reference_goal(x,y) marks the reference point at coordinates {x,y} as the goal.

occupy(x,y, obj_name) reference an obstacle or agent as coordinate {x,y} to a ref point if it is currently unoccupied

unoccupy(x,y) de-reference a ref point at coordinate {x,y} (removes obstacle or agent from the ref point)

Obstacle

map_init(x,y) during map population, references start point at ref point coordinate {x,y}

As tasks execute, changes in the system may occur. State diagrams represent the possible changes to objects during execution. Shown is a list of possible states for class objects.

Agents

o Initialized

o Searching

o Goal Found

Map

o Initialized

o Populated

These are the basic design steps necessary to begin the initial implementation and evaluation phases, which is out of the realm of this paper. Implementation is simply a matter of applying good coding techniques from the design. This was intended to be only the analyzation and design steps in the cycle of software development.

Artificial Intelligence programming can benefit from Object Oriented programming, because OO easily represents the real-world models that AI often deals with. The main challenges may be strong logical capabilities, such as good space-time complexity for search algorithms, recursive functions, and supported syntax for complex logical functions and operators.

Works Consulted:

Using UML: Software Engineering with Objects and Components

Rob Pooley & Perdita Stevens, Addison-Wesley Limited 1999

Artificial Intelligence: A new Synthesis

Nils J. Nilsson, Morgan Kaufmann Publishers, Inc. 1998