Robotics Reference
In-Depth Information
is represented in PROLOG contributes to the ease with which the lan-
guage can manipulate information in order to arrive at the solution to a
problem.
The General Problem Solver
Another early attempt at automatic problem solving was a program called
GPS developed by Allen Newell and Herbert Simon at Carnegie Institute
of Technology during the late 1960s. GPS employed an approach called
means-end analysis, which is based on the idea of breaking down the
goals of a problem into sub-goals and then attempting to solve each sub-
goal. If a difference is detected between the current state of a problem and
a goal, then a sub-goal is created by minimizing or otherwise reducing
the most important difference between the goal and the current state.
For example, let us assume that the problem I want to solve is that I
am hungry and I want to be full. What is the difference between my
current state (being hungry) and the state I want to reach (being full)?
The answer is an empty stomach. What changes the emptiness of my
stomach? Eating food. So eating food becomes a sub-goal. The process
then determines whether I can eat food, in order to satisfy the new sub-
goal. If I do not have any food, what is the difference between what
I have (no food) and what I want to have (food)? The answer is the
presence of food. So achieving the presence of food becomes another
sub-goal on the path to solving the original problem. And so on.
Solving problems in this way becomes an exercise in growing trees of
the various goals and sub-goals, hopefully leading eventually to a solution
path from the original problem state to the original goal. If the original
problem is solvable, then eventually the goal state will be generated. The
solution to the original problem then consists of carrying out the various
actions that convert the original problem state to the goal state.
A serious difficulty in using this approach for complex problems is
that, as the number of sub-goals in the search tree increases, so the num-
ber of possibilities for creating new sub-goals also increases, and unless a
program has the benefit of extremely powerful heuristics for encouraging
it to search for a solution in sensible ways, the growth of the search tree
can get out of hand, consuming vast amounts of computer time and, in
some cases, computer memory.
During the heyday of GPS in the late 1960s, the project was being
viewed optimistically within the AI community as a breakthrough in the
