Robotics Reference
In-Depth Information
realm of automatic problem solving. But, without infinite resources of
computer time or memory, it became essential to find ways of managing
the expansion and search of the goal/subgoal tree so that a solution could
be found economically. This ultimately proved impossible to achieve,
causing the generality of the aim of GPS to be its undoing. Given any
specific problem, such as solving a Rubik Cube, heuristics could be de-
veloped that would enable a program to focus on the most promising
pathsthroughthetreeandthemostimportantgoals,therebykeeping
the size of the tree in trim. But it proved to be simply impossible to
find such solutions for every tree. Going from the specific to the general
was too difficult for GPS, which always needed to be primed with large
amounts of knowledge about the specific domain in which it was being
asked to solve a problem. There was no general strategy available that
would automatically lead to the solution of every problem.
Planning
With a decline in the belief that GPS or some other system might lead to
the creation of programs with general problem solving capabilities, the
attention of many within the AI community shifted from this utopian
dream to the subject of planning. Creating a plan involves determining
all the small tasks that must be carried out in order to accomplish a goal,
and the achievement of a suitable plan is therefore synonymous with solv-
ing a problem. If your goal is to buy a pint of milk, superficially a trivial
task, there might be several small tasks involved in achieving that goal.
These might include finding your car keys, finding your wallet, starting
your car, driving to the grocery store, finding milk on the shelves at the
store, picking up the milk, taking it to the checkout, paying for it and
finally driving home. The process of planning takes into account various
constraints (or rules), that affect when certain tasks in your list can or
cannot happen. In this simple example, the constraints include finding
your car keys and wallet before you drive to the store and, once you are
there, finding milk on the shelves before you take it to the checkout.
The main benefits of planning include reducing the amount of search
required to solve a problem, resolving possible conflicts between differ-
ent goals, and providing a basis for enabling a program to recover from
errors. One of the earliest planning systems to gain recognition within
the AI community was STRIPS, developed in the early 1970s by Richard
