1. General Problem Solver

The General Problem Solver (GPS) is a universal problem solving approach.

GPS is the first approach that makes the distinction between knowledge of problems domains and how to solve problems

GPS is domain and task independent approach.

GPS does not put any restrictions both on the domain knowledge and on the task.

Examples of GPS are: automated theorem proving and generic search methods
Automated theorem proving

Automatic theorem provers are GPS for which every problem can be expressed as logical inference

Automated theorem proving is about proving of mathematical theorems by a computer program
Generic Search Methods

Generic Search Methods are GPS for which every problem can be expressed as search

One particular example of a Generic Search Method is the A* algorithm.

A* works for problems that can be represented as a state space i.e. a graph of states. Initial conditions of the problem are represented as start state , goal conditions are represented as end state

A* is an informed search or heuristic search approach that uses the estimation function:

f(n)=g(n)+h(n)

g(n) the cost to get from the star state to current state n

h(n) estimated cost to get from current state n to end state

f(n) estimated total cost from start state through current state n to the end state
More in Lecture 5
1. General Problem Solver (1)

However, GPS has a set of limitations :

It works in theory but in practice works only on toy problems (e.g. Tower of Hanoi)

Could not solve realworld problems because search was easily lost in the combinatorial explosion of intermediate states