This page is provided to give more information about the technical aspect of AI (Artificial Intelligence.) There's also many examples of actual usage of AI in everyday life. This includes everything I hear about AI, and eventually from you: all your suggestions and references are welcome in my electronic mail box. (However, if you want me to include information on this page, I will need proof of what you tell me.)
This page has been created to talk about Artificial Intelligence (AI). Its main purpose is to be used has a documentary source for those who want to program with AI. The page presents explanations and algorithms. There is no information such has code source or programs which use AI in this page, but the page may refer to such documents.
For non technical persons, the only page you should read is the one referencing examples about what's available in AI on the market.
Artificial Intelligence (AI) is two things:
You need to be intelligent to program a computer to react properly in some predetermined situations. One chess game, on computer, won games against the world chess master. That's a proof of intelligence.
The basic idea is to have a mechanical system do what we ask it to do. The fact that it is mechanical reflects the artificial aspect of the AI.
All intelligent creatures have one thing in common: they can recognize and act upon that recognition. Each category of animal can recognize different kinds of things. Computers can be taught to recognize all these different kinds of things. Some examples (skip examples):
Bats detect objects with a radar, they emit a sound which
bounces off of solid or liquid objects and listen to the result with
their ears. This way they know how far away the objects are.
Computers present on planes detect the ground and other planes with radars, thus avoiding crashes. The crashes occuring today are mostly because of defective electronics; and some are from criminals. |
The photo of the bat comes from the American Association of Zoo Keepers.
This beautiful eagles can be seen at the wonderful Santa Ana Zoo!
The photo comes from the Entomology department of the Colorado State University.
Snakes detect approching creatures by feeling ground vibrations. THose vibrations are enough for them to know how far and how big the creature is.
The snake on the photo is a cottonmouth. The picture has been taken by Ken Felsman. More photos can be found in Herp Pictures, Galleries.
This photo of myrmica rubra comes from the best myrmecology page on the web!
Cats see in the night. They can detect shapes because
of the size of their pupil. It seems they even have the ability
to see colors in the night, which humans can't do.
Computers can use an infra-red camera. Infra-red can't be seen by humans, but computers can work on the data for people to be able to see shapes and show what the camera detects. |
Beavers uses tools to prepare their food. Their tools are simple rocks, and they break the shells of the nuts they've collected. Then they select what's good to eat in the broken pieces.
This beaver photo comes from NetPets.
Now we know that most birds which migrate know where
north is. In their brain, they have a magnetic field, which
always indicates the north, like a compass.
Computers may use many means to know where the north is. They can use astral readings, or use an electronic compass. This is useful for planes, boats and telescopes. |
The picture of the wood stork is from the Endangered Species Program (U.S. Fish and Wildlife Service)
Dogs are well known as trackers. They can easily
track animals using their sense of smell.
Computers are not very well known as smell detectors, but most smoke detector alarms are. We also use smoke detectors to check car emissions. Other odor or gas detectors are used in very specific industries which use dangerous materials. |
The wolf's picture is a copyright (1989-1994) of Philip Greenspun (Old address: Philip Greenspun)
ZooNet
is THE place to go when you want to know about Zoos!
This chimpanze photo is a ©1995 ZooNet. Monkeys can be taught many tricks. For instance it can be taught how to insert items with specific shapes, in a board with holes having the corresponding shapes. A monkey will especially enjoy it if he can earn a banana.
|
Examples shows the three different parts of AI:
We all know the five human senses: sight, touch, smell,
taste, hearing. Computers can have all of these and more. A
camera can replace the sight, captors can replace the touch,
electronic meters can replace the smell and taste, and a
microphone can replace hearing. Today, technology allows
us to check a lot more things like X-ray, radio waves,
vibrations, ultra-sound, radioactivity... This enables
a computer to percept sufficiently to replace human senses.
Analysis is the hardest part. We don't yet know
how a human brain can make the difference between a
thousand images of people in such a small amount of time.
Computers can recognize hand writing, papers, money bills,
code bars, and some more advanced systems can recognize
streets and accidents in a street. But the processing
time is still too slow to match a human mind.
Analysis is mostly what AI research is about
today, and that what this page will describe.
However, people are still working on the other
parts, the perception devices can perform better
so analysis becomes simpler and faster. With microphones,
it is possible to use a series of transistors to
hash the sound before transmitting the information to
the software part of the robot. Thus, analysis can
avoid many calculations. Similar hardware processing
can be applied to any perceptive device.
Once the analysis part is done, the automaton can take the
last step and act. The action can be anything, move a piece
on a chess board, turn on a light, start a motor, write an
answer on the screen...
The very last action is usually what is called the goal.
The three different parts of AI (Perceptions, Analysis and Action)
may be used as many times as
necessary to accomplish the goal. Once the goal is accomplished
or if no solution is found (no more steps can be taken,)
the automaton stops.
To speak about AI, we need a minimum knowledge about
its environment. A program uses a problem from which is
defined a starting database, some rules, and at least one state.
A problem calls for a solution, so the program
has a goal. It defines the starting state (called root)
and is used to create the starting database and a set
of rules.
Some problems may require more than one starting
state. This is perfectly possible and viable, however it
makes things harder to understand.
And there is also always a way to create one single state
before all the "root states" you define.
For instance, when defining a language with a tool (like yacc,)
you may define several "start" rules. In C you can start with
a function, a variable or an external definition. To simplify
the problem, the tool shall generate a preceding starting
point (called start' with yacc,) which links to all the
user defined "start" rules.
Note: yacc stands for "Yet Another Compiler Compiler."
The database is composed of the information necessary
for the program to understand its environment (or world.)
The database may grow as the program goes (a chess program
can save the games so it remembers good and bad moves.)
Rules (or functions) are related to the database and
the states. The program can check a state against all the rules,
and defines a set of new states. Depending upon programs, the
result may or may not be saved for further reference.
A rule is for instance how you can move a piece on a chess
board. Bishops can go only in diagonals, castles in straight
lines, kings move only one square at a time... And also a king
can't go to a square which is attacked by one or more of the
enemy pieces. If the rules are stated separatly, the computer
can eventually generates more complex rules so it would test
less rules to know if a move is legal or not.
A state determines the current environment. In
some cases, a computer will calculate future possible
states (like in chess.) When a state is memorized,
we often speak about a node. For instance, in chess,
the current state is where the pieces are on the board
at this time, and a new set of states can be all
possible moves from the current state.
Usually, a problem defines one single state at
start, called the root state (or node.)
Breadth-first is a simple search. From the root
state, it creates all possible states one level lower.
Then from all these new states, it creates all
possible states two levels lower. And so on until a
solution is found or no more state can be created.
Breadth-first search is good in the sense that
if there is a solution to be found, the
best solution is found first. However,
it eats up a lot of memory really fast, and many
systems will not work properly with this kind of
search. At the same time, it will take a lot of time
to process.
If it is not necessary to keep track of
the trajectory taken, it is possible to save much
memory by keeping only the lowest node level.
This search is a form of the breadth-first
search, using a cost parameter. Each node receives
a cost information defined as necessary, and then
the search continues with the lowest cost node.
This will often be enough to regain most of the memory
and the time processing of the breadth-first
search.
This search look in one single direction at a time.
If the taken direction is not a solution, then a second
one will be checked, and so forth until a solution is found.
The memory necessary for a depth-first search is
the number of nodes necessary to reach the deepest level.
This reduces considerably the amount of memory used in
a breadth-first search. However, only the nodes for
the solution are kept.
The time processing can be very long as the last
direction maybe the solution. The best solution will also
not be found except if all directions are taken one after
another.
This search is similar to the depth-first, so it
looks for a solution in one direction first, then checks
the next direction and so forth. The difference is that
only a certain amount of nodes will be defined, before
checking the following direction, thus avoiding an
incredibly long search.
This kind of search is particuliarly interesting
when we guess that the solution should not be at more than
a certain level. Then we may avoid calculating unnecessary
nodes in many directions. The necessary maximum memory
is known.
This search is a depth-limited search with a growing
limit. A first limit can be used to check all directions.
If no solution is found, but some nodes could have been
extended at least once more, then the limit is enlarged
and the search is repeated.
It is often that the depth-limited search will not
work if the limit is too small. Using this algorithm
gives the system the power to find a solution. However,
many nodes will be recomputed many times if the depth limit
is very slowly increased.
A bidirectional search may use any of the previous
search algorithms, but it is bidirectional in the sense that
the search starts from the beginning and from the end of the tree.
Nodes are created in both directions and when two nodes are
identical in both trees, we found a solution.
There are many problems which can't be reverted,
so the bidirectional search is not well known yet.
Technical terms and definitions
Search algorithms in use today
References