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