Herself’s Artificial Intelligence

Blackboard Systems

A blackboard system works like a blackboard in a room full of people. Some people, agents or parts of the program are allowed to add, change, erase or read the information on the blackboard. There is usually an overseer who requests that missing sections get filled in or updated. When each piece does its work the information is complete. There is also a conflict resolution piece to settle disputes. Each agent or program is an expert on an area or type of information. So the blackboard is just a centralized data structure to which various agents or subroutine have access.

State Machines

A state machine keeps a temporal representation of the state of its environment. It tracks the state it begins in, as well as states in which actions or sensory data change the state.

Finite state machines are used as part of the AI engine in games. This type of setup can be computationally efficient for updating game characters.

In a neural net state machine the states are generally stored in some type of a vector. The network has a hidden unit for each feature of the environment it needs. The input consists of an input for each sense, plus the input from the hidden units. There is an out put for each possible action that can be taken.

Another way to store the information is with a map that is updated. This is known as ‘iconic representation’ and is used for agents.

In a robot an ‘artificial potential field’ is used. The field is a grid with attractive and repulsive potentials summed for each box. The attractive spot is where the robot is supposed to be heading. It’s number is some constant times the distance the robot is from the goal. A repulsive field is an obstacle for the robot to avoid. It is scored as the constant divided by the distance. The motion of the robot is along the gradient, or down the hill to its goal.

Turing Machines

Automaton theory is a branch of mathematics that describes the operations of computers, especially that of Turing Machines.

A Turing machine consists of a black box, and an infinite tape. The tape is divided into blocks. Each block has one symbol. The tape head can be on one block at time, it can read or write that block and then move one block forward or one block backward. The black box has a controller, a finite memory and decides what to do based on the information read. Turing Machines can describe any finitely describable function that maps one set of strings onto another set of strings. It is believed that any function that can be computed can be computed by a Turing Machine.

A Finite State Machine is a set consisting of:
a finite set of states
a finite set of input symbols
a finite set of output symbols
the next state function
the next output function

There are two types of computer eyes in use now. One known as ‘spot or jumping’ eyes send out a narrow laser beam and measure the amount of light that comes back. A second type of computer vision uses ‘imaging eyes’ these form pictures like the digital cameras do.

Image filtering from 2-d into 3-d involves filtering many items such as: shading; color; intensity; texture; etc. The information is then used to create a scene.

First the image is decomposed into pixels or small blocks of color and light intensity. Then to erase spikes of light or clean up random noise in the picture, a filter operation, convolution, is slid over the image that averages pixels that are adjacent to each other and replaces the center pixel with the average. Usually a two dimensional Gaussian is used as the weighting function. Another method looks for pixels that vary greatly from the pixels surrounding them. It gives this pixel the average of the surrounding pixels. This method tends not to blur the image as much as the first method.

Next some type of edge detection is performed. One method enhances areas that have large changes in color from pixel to pixel. This is done by a process that, in effect, takes the second derivative of the image. Where the second derivative is zero an edge occurs. This is done by creating a sliding window with a positive and negative section. As it slides over the image it compares the pixel underneath to itself. The sum is zero over areas that don’t change. A method used in maps is ‘contouring’ this measures the difference in intensity of the pixels rather than color. This pulls out and clarifies areas of different depths.

The convolution and edge detection are generally combined into one operation. This results in the Laplacian of the Gaussian function being performed over the image. There are newer, better techniques available now than this one.

Another method to differentiate objects from an image attempts to find areas of gradual change in color, light intensity, etc. An area is a region of homogeneous pixels that differ not more than a small amount, . Adjacent regions are not homogeneous. Split and Merge [Horowitz & Pavlidis] is one such method. The whole image is split into equal parts, these are tested for homogeneity, if the regions are not homogeneous then the splitting continues until all the regions are homogeneous. Regions are then merged with other regions that are homogeneous with themselves. This method and the one above run into many problems with differentiating shadows from edges.

Now scene analysis is done to extrapolate a scene from the information gathered. For this part more information is needed. Other scenes, stereo vision, or positions of the moving camera. In one method a line drawing is extrapolated and the junctions of the lines are matched to table entries to determine if the object extends outward or inward. If the scene contains well known objects the objects may be stored as line drawings in a table to be matched.

Evolutionary programs create individual programs that compete for survival. Those that do well reproduce, usually with another individual that did well. The child gets a random mix of traits from the parents and may do better or worse than the parents. Some of these programs are written for specific problem solving ability, others for general skills. Often a mutation will be thrown in that will effect a very small percentage of the population.

The simplest of these is Conway’s Life. A grid of squares is laid out and life multiplies or dies off depending on the number of occupied neighboring cells. The newer, more complex versions have genetic code that children inherit as subroutines from both parents, a bit of randomness mixed in and they compete in a survival of the fittest environment. The hope is that after many generations we will have intelligence. By modern standards Life is more of a flocking algorithm rather than an evolution of a population.

Artificial societies are also being used to study and predict what real world societies will do. Using a simple version of life you can change the rules and mimic real world situations. This method is also being used by archaeologists to determine what caused the rises and falls of civilizations gone by. In 1971 an economist, Thomas C. Schelling, used such a method to show how neighborhoods segregate and that racism was not the cause of segregation. Usually a few very simple rules are all that are needed to have real life simulations develop.

Game of Life by Conway in Java. A grid of squares randomly is marked with on or off. If a square has less than 2 neighbors it dies of loneliness, if it has 2 neighbors it stays the same, if it has 3 neighbors a birth occurs, if it has more than 3 neighbors it dies of over crowding.

Source Code:
Conway’s Life
Bugs
SantaFe Ant Trail

More information:
3D Traveling Salesman using Genetic Alogrithms
International Society of Artificial Life
Artificial life
Genetic Art
Artificial life and other experiments
Zooland

iPhone apps:

Conway’s Life for iPhones

Papers:
Sexual Swimmers Emergent Morphology and Locomotion Without a Fitness Function
Aspects of Evolutionary Design by Computers
A particle swarm selects for evolution of gliders in non-uniform 2d cellular automata

See also:
Genetic Algorithms
Evolutionary computing finds practical uses
5 new models of flocking behavior discovered
The Hitchhiker’s Guide to Evolutionary Computation