General Problem Solver
The General
Problem Solver (GPS) was an AI program
proposed by Herbert Simon,
J.C.Shaw, and Allen Newell. It was the first
useful computer program that came into existence in the AI world. The goal was to make it work
as a universal problem-solving machine. Of course there were many software
programs that existed before, but these programs performed specific tasks only.
GPS was the first program that was intended to solve any general problem. GPS
was supposed to solve all the problems using the same base algorithm for every
problem.
To program the GPS,
the authors created a new language called Information Processing Language (IPL). The basic premise
is to express any problem with a set of well-formed formulas. These formulas
would be a part of a directed graph with multiple sources and sinks. In a
graph, the source refers to the starting node and the sink refers to the ending
node. In the case of GPS, the source refers to axioms and the sink refers to
the conclusions.
Even though GPS was intended to be a
general purpose, it could only solve well-defined problems, such as proving mathematical
theorems in geometry and logic. It could also solve word puzzles and play chess. The reason
was that these problems could be formalized to a reasonable extent. But in the real world,
this quickly becomes intractable because of the number of possible paths you can take. If
it tries to brute force a problem by counting the number of walks in a graph, it becomes
computationally infeasible.
Solving a problem with GPS
Let's see how to
structure a given problem to solve it using GPS:
1. The first step is
to define the goals. Let's say our goal is to get some milk from the grocery
store.
2. The next step is to
define the preconditions. These preconditions are in reference to
the goals. To get milk from the grocery store, we need to have a mode of transportation
and the grocery store should have milk available.
3. After this, we need
to define the operators. If my mode of transportation is a car and
if the car is low on fuel, then we need to ensure that we can pay the fueling station.
We need to ensure that you can pay for the milk at the store.
An operator takes care of the conditions
and everything that affects them. It consists of actions, preconditions, and
the changes resulting from taking actions. In this case, the action is giving
money to the grocery store. Of course, this is contingent upon you having the money
in the first place, which is the precondition. By giving them the money, you
are changing your money condition, which will result in you getting the milk.
GPS will work as long as you can frame the
problem like we did just now. The constraint is that it uses the search process to perform
its job, which is way too computationally complex and time consuming for any meaningful
real-world application.
