Page 61 - Introduction to AI Robotics

44
2 The Hierarchical Paradigm
Creating a single representation which can store all of this information can
be very challenging. Part of the reason for the “sub-turtle” velocity was the
lack of computing power during the 1960’s. However, as roboticists in the
1980’s began to study biological intelligence, a consensus arose that even
with increased computing power, the hierarchical, logic-based approach was
unsatisfactory for navigational tasks which require a rapid response time to
an open world.

2.2.1 Strips

Shakey, the first AI mobile robot, needed a generalized algorithm for plan-
ALGORITHM ning how to accomplish goals. (An algorithm is a procedure which is correct
and terminates.) For example, it would be useful to have the same program
allowahumantotype inthatthe robot is inOffice 311and should go to
Office 313 or that the robot is in 313 and should the red box.
GENERAL PROBLEM The method finally selected was a variant of the General Problem Solver
SOLVER (GPS) method, called Strips. Strips uses an approach called means-ends analysis,
STRIPS where if the robot can’t accomplish the task or reach the goal in one “move-
MEANS-ENDS ANALYSIS
ment”, it picks a action which will reduce the difference between what state
it was in now (e.g., where it was) versus the goal state (e.g., where it wanted
to be). This is inspired by cognitive behavior in humans; if you can’t see how
to solve a problem, you try to solve a portion of the problem to see if it gets
you closer to the complete solution.
Consider trying to program a robot to figure out how to get to the Stan-
ford AI Lab (SAIL). Unless the robot is at SAIL (represented in Strips as a
GOAL STATE variable goal state), some sort of transportation will have to arranged.
INITIAL STATE Suppose the robot is in Tampa, Florida (initial state). The robot may
represent the decision process of how to get to a location as function called an
OPERATOR operator which would consider the Euclidean distance (a variable named
DIFFERENCE difference) between the goal state and initial state. The differ-
ence between locations could be computed for comparison purposes, or eval-
DIFFERENCE uation, by the square of the hypotenuse (difference evaluator). For
EVALUATOR example using an arbitrary frame of reference that put Tampa at the center
of the world with made-up distances to Stanford:

initial state: Tampa, Florida (0,0)
goal state: Stanford, California (1000,2828)
difference: 3,000