### 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 real-world problems because search was easily lost in the combinatorial explosion of intermediate states