The General Problem Solver

Paradigms of Artificial Intelligence Programming has been sitting on my desk for a few months since I worked through the Eliza chapter, so time for me to brush it off and (finally) work my way through it.

The General Problem Solver is early example of computer AI. Herbert Simon made a speech at the 12th National Meeting of the Operations Research Society where he stated:

It is not my aim to surprise or shock you- if indeed that were possible in an age of nuclear fission and prospective-interplanetary travel. But the simplest way I can summarize the situation is to say that there are now in the world machines that think, that learn, and that create. Moreover, their ability to do these things is going to increase rapidly until - in a visible future -the range of problems they can handle will be coextensive with the range to which the human mind has been applied. (Heuristic Problem Solving: The Next Advance in Operations Research [PDF])

That's a pretty big claim that proves (unsurprisingly) to be slightly wide of the mark!

The GPS solution solves problems by gathering the following information:

• The current state of the world


• The available operations that transfer from one-state to the next


• A goal that we desire to reach

States and goals are represented using symbols. We represent the initial state of the world as a set of symbols, for example, #{'Bored 'At Home'}, indicates that the current state is bored and at home and the goal condition might be #{'Happy 'Inebriated}. Given a series of operators, GPS will attempt to find the way there.

An operator alters the current states. An operator consists of an action (a friendly name for what is taking place), a set of preconditions and an add/remove list which affect the current state of the world. For example, the operation drink might be defined as {:action drink :preconditions #{'have-money} :add-list 'drunk :remove-list 'money}.

The complete code is shown below. Note that it has mutable state and that references are used to hold this. This is enforced by Clojure and is one of the key differences between Lisp and Clojure.

One thing that caught me out was contains? which checks the presence of an INDEX not a value. Hence, the contains-value? definition.

;;; Implementation of a simplified General Problem Solver
;;; http://en.wikipedia.org/wiki/General_Problem_Solver
;;; Based on code in "Paradigms of Artificial Intelligence Programming"
(ns uk.co.fatvat.gps
  (:use [clojure.set]))

(defstruct operation :action :preconditions :add-list :delete-list)

(defn make-op
  [action preconditions add-list delete-list]
  (struct operation action preconditions add-list delete-list))

(def *state* (ref nil))

(def *ops* (ref nil))

(defn contains-value?
  [coll val]
  (not (nil? (some (partial = val) coll))))

(defn appropriate?
  [goal operation]
  "An op is appropriate to a goal if it is in its add list"
  (contains-value? (:add-list operation) goal))

(defn apply-op
 [op]
 "Print a message and update state if op is applicable"
 (when (every? achieve (:preconditions op))
   (println "Executing: " (:action op))
   (dosync
    (alter *state* 
           (fn [s]
             (union 
              (difference s (:delete-list op))
              (:add-list op)))))))

(defn achieve
  [goal]
  "A goal is achieved if it already holds.  Or if there is an appropriate
   operation for it that is applicable"
  (or (contains-value? @*state* goal)
      (some apply-op (filter (fn [x] (appropriate? goal x))  @*ops*))))

(defn gps
  [state goals ops]
  "General Problem Solver: Achieve all goals using the operations available."
  (when (every? achieve goals) 'solved))

So having written all this code, how'd we use it? All we have to do is define the problem in terms that GPS can understand. The example below shows a common problem. I'm at home, with money and Facebook, however I'd much rather be at a bar and dancing the night away. However, I need to get to the bar and before I can dance I really need a drink.

(def example-operations
     [(make-op 'message-friends
               #{'have-facebook}
               #{'friends-emailed}
               #{'at-home})

      (make-op 'arrange-party
               #{'friends-emailed}
               #{'party-arranged}
               #{})

      (make-op 'get-on-bus
               #{'party-arranged}
               #{'at-club}
               #{})
      
      (make-op 'drink
               #{'have-drink}
               #{'had-drink}
               #{'have-drink})

      (make-op 'dance
               #{'had-drink}
               #{'dancing}
               #{})

      (make-op 'give-bar-money
               #{'have-money 'at-club}
               #{'bar-has-money 'have-drink}
               #{'have-money})])

(defn example []
  (dosync
   (ref-set *state* #{'at-home 'have-money 'have-facebook}) 
   (ref-set *ops* example-operations))
  (gps @*state*
       #{'dancing 'at-club}
       example-operations))

Running this at the REPL shows me the way to go:

  uk.co.fatvat.gps> (example)
  Executing:  message-friends
  Executing:  arrange-party
  Executing:  get-on-bus
  Executing:  give-bar-money
  Executing:  drink
  Executing:  dance
  solved

This isn't very general, but we'll save that till next time!