PAIP in Clojure Chapter 4
The fourth chapter of Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp on the General Problem Solver.
Summary
The chapter starts with a quote by Herbert Simon, a Nobel Prize winner and one of the inventors of the General Problem Solver (GPS):
There are now in the world machines that think.
This GPS machine that thought was the first useful Artificial Intelligence program. It was written to solve every problem using the same algorithm (reasoning). GPS was written in (1959) in a computer language created by the authors called Information Processing Language (IPL): an assembly language for manipulating lists. As can be imagined by looking at IPL's Wikipedia page the code was complex. Nowadays using a language at a higher level of abstraction a GPS can be written in a few lines of code and we can have a clearer grasp of the concepts at work. It turns out the program is not so general as it name suggests. According to Norvig the exaggerated claims probably had to do with the complex code: if the code is complex the program must be doing something interesting.
GPS is a searching algorithm that given various means with their pre- and postconditions finds means to a specific end. Simon and his colleagues realized humans often use means-end analysis to solve a problem. Here's an example:
I want to take my son to nursery school. What’s the difference between what I have and what I want? One of distance. What changes distance? My automobile. My automobile won’t work. What is needed to make it work? A new battery. What has new batteries? An auto repair shop. I want the repair shop to put in a new battery; but the shop doesn’t know I need one. What is the difficulty? One of communication. What allows communication? A telephone… and so on. — Newell and Simon’s example from their 1972 book Human Problem Solving
We can pose this problem when we structure it of consisting of various goals with starting conditions and operators.
In Clojure we can introduce a record called Op:
(defrecord Op [action preconds add-list del-list])
Op consist of an action (goal), and sets of preconditions, additions once the action is executed and a list of things that are no longer the case (del-list).
Now we can structure the taking our son to school problem posed above as consisting of the following operators:
(def school-ops
#{(Op. :drive-son-to-school
#{:son-at-home :car-works}
#{:son-at-school}
#{:son-at-home})
(Op. :shop-installs-battery
#{:car-needs-battery :shop-knows-problem :shop-has-money}
#{:car-works}
nil)
(Op. :tell-shop-problem
#{:in-communication-with-shop}
#{:shop-knows-problem}
nil)
(Op. :telephone-shop
#{:know-phone-number}
#{:in-communication-with-shop}
nil)
(Op. :look-up-number
#{:have-phone-book}
#{:know-phone-number}
nil)
(Op. :give-shop-money
#{:have-money}
#{:shop-has-money}
#{:have-money})})
GPS can solve any problem that is posed this way when it is given an initial state, a goal and available operations:
(GPS #{:son-at-home :car-needs-battery :have-money :have-phone-book} ; initial state
#{:son-at-school} ; goal
school-ops) ; available operations
Some problems, however, take too much time to solve in such a way. Computing the solution to these problems takes exponentially more time as the size of the problem grows. It is generally assumed [citation needed] these problems cannot be solved by an algorithm: there is simply not enough time to find a solution. Problems like that are called NP-hard. So GPS is not general since it fails to solve these problems in a reasonable amount of time.
Intermezzo The physicist Arkardy Bolotin states in Computational Solution to Quantum Foundational Problems that NP-hard problems can manifest itself in our physical reality (read in this blog post). Quantum physics breaks down at a macroscopic level (i.e., we do not see people in superposition or tunneling through walls, but electrons do), but there is no reason why it should break down. Bolotin argues that finding a solution to the quantum equations takes too much time (is NP-hard) and that therefore macroscopic objects in our world do not show quantum behaviour.
/edit: a computer scientist I respect called Scott Aaronson states the above is complete garbage and ignores basic physics and computer science:
End intermezzoIt gives me no pleasure to respond to this sort of thing—it would be far better to let papers this gobsmackingly uninformed about the relevant issues fade away in quiet obscurity—but since that no longer seems to be possible in the age of social media Response: https://www.scottaaronson.com/blog/?p=1767#comment-103591
Here's, anyhow, the first implementation of the GPS algorithm in the book translated to Clojure:
(def state
"The current state: a list of conditions."
(atom #{}))
(def ops
"A list of available operators."
(atom #{}))
(defrecord Op [action preconds add-list del-list])
(defn appropriate?
"An op is appropriate to a goal if it is in its add list."
[goal op]
(some #(= % goal) (:add-list op)))
(declare apply-op)
(defn achieve
"A goal is achieved if it already holds,
or if there is an appropriate op for it that is applicable."
[goal]
(or (some #(= % goal) @state)
(some apply-op
(filter #(appropriate? goal %) @ops))))
(defn apply-op
"Print a message and update *state* if op is applicable."
[op]
(when (every? achieve (:preconds op))
(println "Executing" (:action op))
(reset! state (clojure.set/difference @state (:del-list op)))
(reset! state (clojure.set/union @state (:add-list op)))))
(defn GPS
"General Problem Solver: achieve all goals using *ops*."
[state' goals ops']
(reset! state state')
(reset! ops ops')
(if (every? achieve goals) :solved))
When we execute GPS for the son to school problem
(GPS #{:son-at-home :car-needs-battery :have-money :have-phone-book}
#{:son-at-school}
school-ops)
this is the result:
Executing :look-up-number
Executing :telephone-shop
Executing :tell-shop-problem
Executing :give-shop-money
Executing :shop-installs-battery
Executing :drive-son-to-school
GPS finds the means to an end.
NP-hardness is not the only problem of the current GPS algorithm. Norvig explains numerous other problems with it in PAIP. In the exercises he wants us to solve some of them. I'll do my best, but I am not sure I have enough time.
Exercises
Exercise 4.2 [m]
Write a function that generates all permutations of its input.
(This is probably useful for improving GPS later.)
Seems like a good idea to use a recursive strategy. The permutations of zero elements is only the element itself. Permutations of a list are the permutations of the rest plus the first element added at every position in its permutations.
(defn add-all-positions
"Creates collection where element elem is added at every position of coll."
[elem coll]
(let [size (count coll)]
(loop [n 0 acc []]
(if (> n size) acc
(let [[before after] (split-at n coll)
permutation (concat before [elem] after)]
(recur (inc n) (conj acc permutation)))))))
(defn permutations
"Generates permutations of input bag."
[bag]
(if (empty? bag) [[]]
(conj (mapcat (partial add-all-positions (first bag))
(permutations (rest bag))))))
Testing:
(count (permutations [1 2 3 4]))
;; => 24
This algorithm is O(N2) since it loops over all previous permutations. According to Norvig finding permutations can be improved to O(N), but I do not see how.
Exercise 4.3 [h]
GPS does not recognize the situation where a goal is accidentally solved as part of achieving another goal. Consider the goal of eating dessert. Assume that there are two operators available: eating ice cream (which requires having the ice cream) and eating cake (which requires having the cake). Assume that we can buy a cake, and that the bakery has a deal where it gives out free ice cream to each customer who purchases and eats a cake.
(1) Design a list of operators to represent this situation.
(def dessert-ops
#{(Op. :eating-ice-cream
#{:having-ice-cream}
#{:eating-dessert}
#{:having-ice-cream})
(Op. :eating-cake
#{:having-cake}
#{:eating-dessert :having-ice-cream}
#{:having-cake})
(Op. :buying-cake
#{:able-to-buy-cake}
#{:having-cake}
nil)})
(2) give GPS the goal of eating dessert. Show that with the right list of operators, GPS will device to eat ice cream, then decide to buy and eat the cake in order to get the free ice cream, and then go ahead and eat the ice cream, even though the goal of eating dessert has already been achieved by eating the cake.
(GPS #{:able-to-buy-cake}
#{:eating-dessert}
dessert-ops)
;; => Executing :buying-cake
;; Executing :eating-cake
;; Executing :eating-ice-cream
(3) Fix GPS so that it does not manifest this problem.
This can be solved by adding a check to see if operations are already achieved:
(defn already-achieved?
"Checks if new operations are not already achieved"
[ops]
(clojure.set/subset? ops @state))
And adding this check to apply-op (and ensure to return true since the truthy return value is used in GPS):
(defn apply-op
"Print a message and update *state* if op is applicable."
[op]
(when (every? achieve (:preconds op))
(when-not (already-achieved? (:add-list op))
(reset! state (clojure.set/difference (set @state) (:del-list op)))
(reset! state (clojure.set/union (set @state) (:add-list op)))
(println "Executing" (:action op)))
true))
This leads to:
;; => Executing :buying-cake
;; Executing :eating-cake
Now, there are various other problems that can be solved. Norvig wants me to introduce a GPS that does: pattern matching; solves the problem of "leaping before you look" (e.g., when a subgoal is :jump-of-cliff GPS has already jumped and cannot go back if it turns out to be a bad idea); can reorder goals; identifies problems that cannot be solved with reordering goals ("Sussman anomaly"), and solves mazes. I decided to only look at some solutions, and not implement them myself.
If you want to know more you can view Norvig's source code for GPS that solves some of these problems at Norvig's website. More about the history and problems of the GPS can be found at General Problem Solver (GPS)