Searching Graphs

Continuing from the previous post, Finding the Target, it's now time to focus on the basic graph searching algorithms introduced in Chapter 6 of PAIP.

The major difference between searching a graph and searching a tree is that a graph may contain cycles. If you're not careful you'll end up in a infinite loop, constantly searching the same cycle. graph-search handles this by keeping track of old states and defining an equality function that allows you to customize the way two states are considered equal (for example, in a board game, states may be equal if they are rotations of each other). new-states generates successors that haven't been seen before.



This code compares quite well with the ANSI Common Lisp code in PAIP, not needing to use funcall simplifies the code a little, and fn instead of lambda is less verbose. The implementation of A* search below doesn't fair so well!

The A* Search algorithm is a best-first graph search algorithm based on the heuristics you supply. Paths with the least cost so far are explored first. The code below gives an implementation heavily based on the one in PAIP. The code feels butt-ugly and I think this is due to the mutable state that I've ported over from the original. There's almost certainly a nicer functional implementation in there somewhere!



So how can we see what the A* search is doing? I wrote a quick maze algorithm to visualize which is shown in the image. The app uses the A* algorithm to find a route from the top-left to the bottom-right, avoiding the black walls. It's is interactive, left clicking builds a wall, left clicking again destroys it. Right-clicking solves the maze if possible, and shows the shortest solution in pink.



The complete code can be seen in my Git repository. There's a really nice Javascript visualization out there if you don't fancy building the Clojure code.

Finding the Target

I've been steadily working my way through Paradigms of Artificial Intelligence Programming which I am thoroughly enjoying. This time round it's time to look at simple search algorithms. Norvig introduces all the traditional tree search algorithms based off a single function shown below:



From this basic algorithm we can express two simple tree search algorithms, depth first and breadth first.



For depth-first, we simply follow one branch of the tree until it matches the goal or fails to complete. The combiner function puts the next node to be searched at the front of the list of states so that we always follow paths to completion. Depths first search can have problems when the structure to be searched is infinite, as it will blindly follow a path forever. Breadth-first works by exploring all paths at the same level. Breadth-first search doesn't suffer from the same infinite search problem as depth-first search, but it's potentially slower because it is covering each and every node. Both depth and breadth based searches have the same fundamental disadvantage, they don't have any knowledge about the state space and just methodically follow the same pattern regardless of the search.

Best-first search chooses the successor nodes to search first by searching on the results of a cost-function.



This will still visit all the nodes, but the choice of what to search next is based on the cost function. If the cost function is right, then best-first-search can be significantly better than depth or breadth first searching. Beam search is an optimization of best search that forgoes the requirement of searching every node. Instead only a fixed number of alternative states (the beam width) are considered.



The advantage of this is lower memory requirements and that the nodes that the beam width covers can be searched deeper. However, if the beam width is too small, then this search algorithm can fall into the trap of endlessly searching down the wrong path.

To illustrate these search algorithms, we'll use the ridiculous example of the game of darts. Briefly, Darts is played by drinking vast quantities of alcohol and then trying to throw darts at a board. You score points between 1 and 20 (either normal, double or triple), and there's also a outer bull (25) and an inner bull (50). You start from 501, and try to get to zero as quickly as possible, with the caveat that the last dart you throw should be a double or a bulls-eye.

The code below models darts as a series of throws:



Now we can use this with the search algorithms described above.

From the descriptions, you'd expect breadth and depth first search to find the right solution, but be a bit rubbish about doing so. Because they have no idea of the means to get to the goal, they'll just chuck darts about randomly and eventually weave their way to a solution. And indeed they do.



Solving the game of darts using depth-first search from 501 is not ideal! The first branch is happens to explore is the contains 1, so the search repeatedly throws 1's until it's not a legal move. Not good!

  uk.co.fatvat.search> (count (:throws (solve-darts-depth-first 501)))     
  500

Let's see if beam search can do any better:



The cost function models it as however close we are to zero divided by the number of throws of the data. The goal should be to get to the finish as quickly as possible.

  uk.co.fatvat.search> (:throws (solve-darts-beam-search 501))
  [441 381 321 261 201 141 84 30 0]    

We can see that this does achieve the perfect 9 dart finish. (T20,T20,T20,T20,T20,T20,T19,T17,D15). Finishing from 1000001 will apparently take 16667 darts!

The approach described in the book is very clear. The key realization for me was that you don't have to have the entire state space in memory at once for a tree algorithm to succeed; you just need to think in terms of the next step to take.

ICFP Contest - This time it's functional...

Last time, I showed the VM implementation for the ICFP 2009 problem [PDF]. I'd used mutable state and hence it was a bugger to try and understand it. For example, looking back, what's this code do?



After I realized that I was not going to go anywhere with actually solving the problem, I thought it'd be more interesting to make a purely functional implementation of the VM and compare the performance with the mutable solution.

In order to refactor to a functional solution, all mutable state needs to be replaced with items that return a new instance of the code. This means that now we can write the main "loop" as a standard functional construct, reduce, which applies the list of operations to the VM and creates a new instance each time.



Adjusting the code to a functional style was a small transformation. Each instance of swap! was replaced with a creation operation instead. No more dereferences (@) signs cluttering up the code, and something that is much clearer to understand.



So how does this affect performance? Previously, the code did 1000 iterations in 3.85 seconds. Running the functional code gives almost exactly the same results (1000 iterations in about 3.75 seconds). I'm not sure how this compares to other implementations of the same code (I suspect poorly!), so I'll hunt around for some comparisons. Either way, I will definitely prefer no mutation wherever possible...

I thoroughly enjoyed the ICFP contest this year. Learnt some bit-fu, a small amount of orbital mechanics and actually managed to make some progress even though ultimately I didn't even submit a single solution :)

ICFP Contest 2009 (2)

In my last post about the ICFP 2009 Programming Contest I'd wrestled with some bits and finally correctly (well, it matched up with this at least!) interpreted the instructions for the virtual machine that was provided.

The next challenge is to actually run the virtual machine. I went through lots of bad designs, but in this post and the next I thought I'd highlight two of these.

For reasons known only to myself, I decided the first approach would use mutable state. This seemed like a good model of a virtual machine, the memory would be represented by a vector of atoms; each atom would be the value of the memory at that address and I could use swap! to update the value of the atom.

Previously, I'd use simple symbols to represent the machine instructions. Now that we've got to process instructions, it makes more sense to represent each instruction as a function of the virtual machine.

;;; Virtual machine specification
(defstruct virtualmachine :mem :counter :inport :outport :status :firstrun)

(defn get-val
  [vm x]
  @((:mem vm) x))

(defn numeric-op
  "D-type General numeric op"
  [vm [x y] f]
  (let [m (:mem vm)]
    (swap! (m @(:counter vm)) (constantly (f @(m x) @(m y))))))

(defn phi
  "D-type"
  [vm [x y]]
  (let [m (:mem vm)]
    (trace vm 'Phi (format "%s ? %s : %s --> %s" @(:status vm) @(m x) @(m y) (if @(:status vm) @(m x) @(m y))))
    (swap! (m @(:counter vm))
           (constantly
             (if @(:status vm)
               @(m x)
               @(m y))))))

(defn print-args
  [vm op x y]
  (format "%s %s // %s %s %s" x y (get-val vm x) op (get-val vm y)))
    
(defn add
  "D-type Add instruction"
  [vm [x y]]
  (trace vm 'Add (print-args vm '+ x y))
  (numeric-op vm [x y] +))

(defn sub
  "D-type Sub instruction"
  [vm [x y]]
  (trace vm 'Sub (print-args vm '- x y))
  (numeric-op vm [x y] -))

(defn mult
  "D-type Multiply instruction"
  [vm [x y]]
  (trace vm 'Mult (print-args vm '* x y))
  (numeric-op vm [x y] *))

(defn div
  "D-type Divide"
  [vm args]
  (trace vm 'Div)
  (numeric-op vm args (fn [x y] (if (zero? y) 0 (/ x y)))))

(defn noop
  "S-type Noop instruction"
  [vm args]
  (trace vm 'Noop)
  vm)

(defn copy
  "S-Type: Copy instruction"
  [vm [x]]
  (trace vm 'Copy (format "%s // %s" x (get-val vm x)))
  (swap! ((:mem vm) @(:counter vm)) (constantly (get-val vm x))))

(defn sqrt
  "S-Type: Square root instruction: undefined for negative values"
  [vm [x]]
  (trace vm 'Sqrt)
  (assert (not (neg? (get-val vm x))))
  (swap! ((:mem vm) @(:counter vm)) (constantly (Math/sqrt (get-val vm x)))))

(defn input
  "S-Type: Set the memory from the inport"
  [vm [x]]
  (trace vm 'Input)
  (swap! ((:mem vm) @(:counter vm)) (constantly @((:inport vm) x))))

(defn output
  "Output instruction: Set the memory on the outport"
  [vm [x y]]
  (trace vm 'Output (format "%s %s // %s" x y (get-val vm y)))
  (swap! ((:outport vm) x) (constantly (get-val vm y))))

(defn cmpz
  "Comparison function"
  [vm [cmp y]]
  (let [val @((:mem vm) y)
        status (cond ;; TODO replace this with functions so it becomes (apply cmp val)
                 (= cmp 'LTZ) (< val 0)
                 (= cmp 'LEZ) (<= val 0)
                 (= cmp 'EQZ) (zero? val)
                 (= cmp 'GEZ) (> val 0)
                 (= cmp 'GTZ) (>= val 0)
                 :else (assert false))]
    (trace vm 'Cmpz (format "%s %s --> %s" cmp y status))
    (swap! (:status vm) (constantly status))))

(def d-type-instructions {1 add, 2 sub, 3 mult, 4 div, 5 output, 6 phi})
(def s-type-instructions {0 noop, 1 cmpz, 2 sqrt, 3 copy, 4 input})
(def comparison {0 'LTZ, 1 'LEZ, 2 'EQZ, 3 'GEZ, 4 'GTZ})

You'll notice an abundance of trace output! This got added as a found repeated bugs in my code. One thing I learnt this time round at ICFP is that the tracing should be built in from the start (not retrofitted as I did here!).

Originally, I wrote my own trace functions (based on ones mentioned in the GPS Problem Sovler post), but I found that Clojure Contrib has a trace package too.

#clojure helped out once again with how to turn tracing off. (alter-var-root (var clojure.contrib.trace/tracer) (constantly (constantly nil))) alters the bindings of trace/tracer to be a function returning nil. alter-var-root's second argument is a function which takes the previous value of the var and returns the new binding.

The code below shows how the VM was implemented. The virtual machine struct is initialized with 16384 (14 bits of address space) atoms, each representing one memory unit. As we run through the list of operations, we simply apply the operations and increment the program counter.

The virtual machine takes an updater function, the goal of the updater function was to read the outputs and adjust the input functions accordingly. Unfortunately, I realized pretty soon into this, that a team of one is not the way to win this contest so I never got far with implementing the Hohmann transfer implementation.

;;; Virtual machine executing instructions
(defn vector-atoms
  "Create a vector of atoms, initialized to zero"
  [n]
  (into [] (take n (repeatedly #(atom 0)))))

(defn init-vm
  [data]
  (let [memory (vector-atoms (count data))]
    (dosync
     (doall (map (fn [a d] (swap! a (constantly d))) memory data)))
    (struct virtualmachine memory (atom 0) (vector-atoms 16384) (vector-atoms 16384) (atom false) (atom true))))
    
(defn hohmann-updater 
  [vm]
  (when @(:firstrun vm)
    (swap! ((:inport vm) 0x3E80) (constantly 1001))))

(defn create-vm
  [instructions]
  (init-vm (map second instructions)))

(def bin1 (read-data (get-bytes bin1)))

;; TODO This could be purely functional, if I just returned
;; a copy of the entire VM after each operation was applied.
(defn run-machine
  "Run the virtual machine with the decoded instructions.  
   Reset the program counter when complete"
  [vm ops update-input]
  (update-input vm)
  (doseq [[op args] ops]     
    (apply op (list vm args)) ;; dodgy side effect
    (swap! (:counter vm) inc))
  (swap! (:counter vm) (constantly 0))
  (swap! (:firstrun vm) (constantly false))
  vm)

(defn run []
  (let [x (create-vm bin1)
        ops (map first bin1)]
    (count (take 1 (repeatedly #(run-machine x ops hohmann-updater))))))

The speed of the VM is quite important. If it's too slow, you'll spend far too long waiting for satellite transfers, and not enough time working out the right answers. This first version is pretty fast 1000 iterations on my machine takes about 3.5 seconds (about 285 iterations per second). The very first implementation (the very bad one) used refs rather than atoms, and this was about twice as slow. I guess the extra time comes from the STM implementation.

This was the first time I'd made a conscious effort to program with mutable state in Clojure and I really wish I hadn't! The end result is really ugly code that confuses me each time I look at it. In the next post, I'll compare this against the purely functional version.

ICFP Contest 2009

The ICFP Contest 2009 started today, so I thought I'd have an attempt at solving the problem in Clojure.

The contest involves implementing a virtual machine which acts as a control module for a satellite. The fun bit is controlling the satellite (which I haven't got to yet), the really *annoying* bit is decoding the virtual machine instructions.

The code below decodes the first dump and prints out the list of op codes. I've no idea if it prints out the right code though...

(ns uk.co.fatvat.icfp
  (:import [java.lang.reflect Array])
  (:import [java.io FileInputStream File]))

;;; Location of relevant files
(def bin1 "/home/jfoster/clojureprojects/icfp/uk/co/fatvat/bin1.obf")

;;; Boring static definitions
(def d-type-instructions {1 'Add, 2 'Sub, 3 'Mult, 4 'Div, 5 'Output, 6 'Phi})
(def s-type-instructions {0 'Noop, 1 'Cmpz, 2 'Sqrt, 3 'Copy, 4 'Input})
(def comparison {0 'LTZ, 1 'LEZ, 2 'EQZ, 3 'GEZ, 4 'GTZ})

;;; Define what the virtual memory looks like
(defstruct vm :data-memory :instruction-memory :programcounter :status)

(defn get-bytes
  "Read the bytes for the given file, stored as a sequence of bytes"
  [filename]
  (let [file (File. filename)]
    (assert (.exists file))
    (with-open [x (FileInputStream. file)]
      (doall
       (into [] (take-while (partial not= -1) (repeatedly #(.read x))))))))

(defn get-op-code
  [bytes]
  (println "bytes" bytes)
  (bit-shift-right (bit-and (byte (first bytes)) 0xF0) 4))

(defn to-double
  [bytes]
  (Double/longBitsToDouble 
   (long
    (reduce bit-or 
            (map (fn [x shift] (bit-shift-left (bit-and (int x) 0xFF) shift))
                 bytes 
                 (range 0 64 8))))))

(defn to-int
  [bytes]
  (int (reduce bit-or
               (map (fn [x shift] (bit-shift-left (bit-and (int x) 0xFF) shift))
                    bytes
                    (range 0 32 8)))))

(defn get-op
  [ins]
  (let [d-opcode (bit-shift-right (bit-and 0xF0 (last ins)) 4)
        s-opcode (bit-and 0x0F (last ins))]
    (if (zero? d-opcode)
      (let [sins (s-type-instructions s-opcode)]
        [sins (s-args sins ins)])
      [(d-type-instructions d-opcode) (d-args ins)])))

(defn d-args
  [ins]
  (let [x (to-int ins)]
    [(bit-shift-right (bit-and x 0xFFFC000) 14) (bit-and x 0x00003FFF)]))

(defn s-args
  [op ins]
  (if (= 'Cmpz op)
    [(comparison (bit-shift-right (bit-and (to-int ins) 0x700000) 21)) (bit-and (to-int ins) 0x00003FFF)]
    [(bit-and (to-int ins) 0x00003FFF)
     (bit-shift-right (bit-and (last (butlast ins)) 0xF0) 4)]))

(defn get-instruction-data
  [image address]
  (if (even? (/ address 12))
    [(get-op (subvec image (+ address 8) (+ address 8 4)))
     (to-double (subvec image address (+ address 8)))]

    [(get-op (subvec image address (+ address 4)))
     (to-double (subvec image (+ address 4) (+ address 12)))]))
          
(defn read-data
  [image pc]
  (map (fn [x] (get-instruction-data image x)) (range 0 (count image) 12)))
         
        

Currently you can just see the op codes, but not execute them. For example:

uk.co.fatvat.icfp> (take 10 (read-data (get-bytes bin1) 0))
([[Noop [0 0]] 1.0] 
 [[Copy [265 0]] 0.0] 
 [[Noop [0 0]] 30.0]
 [[Noop [0 0]] 0.0] 
 [[Copy [248 0]] 0.0]
 [[Sub [4 3]] 0.0]
 [[Cmpz [EQZ 5]] 0.0]
 [[Phi [2 1]] 0.0] 
 [[Sub [7 0]] 0.0]
 [[Copy [263 0]] 0.0])

Initially the spec was slightly wrong which meant a little banging of my head against a brick rule. Next plan is to get the VM to execute the instructions. I *think* I can do this by replacing my symbols with the real functions, and then just applying them to the arguments. The tricky bit will be modelling the memory model of the VM in Clojure (e.g. not a functional style but with references and so on).

Revisiting Eliza

I previously blogged about Eliza here but decided it was worth revisiting. Looking back I was being daft and trying to use strings to represent sentences the user enters. Lisp's symbol handling is much simpler to deal with.

Eliza is one of the most famous "AI" programs. It was written to give the impression of a Rogerian pyschoanalyst by answering questions with further questions in an effort to make the patient understand the problem.

The original Eliza paper is a good read. The introduction to the paper is awesome and explains the human learning process really well.

It is said that to explain is to explain away. This maxim is nowhere so well fulfilled as in the area of computer programming, especially in what is called heuristic programming and artificial intelligence. For in those realms machines are made to behave in wondrous ways, often sufficient to dazzle even the most experienced observer. But once a particular program is unmasked, once its inner workings are explained in language sufficiently plain to induce understanding, its magic crumbles away; it stands revealed as a mere collection of procedures, each quite comprehensible. The observer says to himself "I could have written that". With that thought he moves the program in question from the shelf marked "intelligent" to that reserved for curios, fit to be discussed only with people less enlightened that he.

This explains my learning process for functional programming in general. First everything seems weird and wonderful, then understandable and then I might even have a chance of solving it myself!

Once the curtain is lifted we see that Eliza is nothing more than a pattern matching system. Lists of symbols are parsed and matched against a series of rules. The pattern matching functions associate variables with parts of the match and then substitutions can be made.

The tests below demonstrate the use of the pattern matching functions based on the examples in PAIP. fail and no-bindings are sentinel values that can be used to distinguish between no match and failure. An alternative would have been to use exceptions to represent failure, but exceptions always feel yucky to me in FP.



In Norvig's example, he uses the Lisp reader to provide a REPL for Eliza. Since Clojure has access to the GUI libraries of Java then it makes sense to use this and get a basic UI together:



The code to create the UI is shown below. The interesting bit is reading the users input as a series of symbols (and the avoidance of laziness!) and the use of interleave to space things out.



Translating this from PAIP was mostly straight-forward, but there were several gotcha's. Nil-punning caught me out a few times, and some Lisp functions didn't have Clojure equivalents with the same name (so digging through the API taught me a few things e.g. sublis and replace). I'm sure there's still much I could do to improve this code. I'm particularly not impressed with position, I must be missing a trick there? Perhaps I should be using vectors more?

The full code can be found on my Clojure Projects Git repository.

Generalizing the General Problem Solver

The last post has a basic implementation of the General Problem Solver from PAIP, but it features a few big problems.

1. "Running around the Block Problem" - In order for an action to occur it must have a consequence. How would you represent running around in circles?
   
2. "Clobbered Sibling Problem" - The function to achieve the goal in the previous version just focuses on whether the each item in the list of goal states is achieved at least once by the end of the solution. By the time the final solution is reached sibling goals may have been undone.
   
3. "Leaping before you look" - If we fail to find a solution we execute all actions on the way (looking before you leak). For example, we might execute jump off cliff before executing wear parachute!
   
4. "Recursive Sub Goal" - To achieve A you need B, which needs A thus resulting in an infinite loop (or recursion in FP terms!).
   

Before we see how to solve these problems, Norvig introduces some nice debug functions, shown below in Clojure form.

The functions allow you to start listening to specific tokens. Lines will only be printing if you are listening to the specific keyword.

This is an example of a function that should probably be rewritten as a macro so that you only pay the cost at compile time. Of course that assumes that you aren't changing the tokens you want to listen to at run time.

(def *dbg-ids* (ref #{:gps}))

(defn dbg 
  [id format-string & args]
  "Print debugging info if (DEBUG id) has been specified"
  (when (contains? id @*dbg-ids*)
    (println (format format-string args))))

(defn debug
  [& ids]
  "Start dbg output on the given ids"
  (dosync
   (alter *dbg-ids* (fn [x] (set (union x ids))))))

(defn undebug
  [& ids]
  "Stop dbg output on the given ids"
  (dosync
   (alter *dbg-ids* (fn [x] (difference x ids)))))

(defn dbg-indent
  [id indent format-string & args]
  "Print indented debugging info if (DEBUG ID) has been specified"
  (when (@*dbg-ids* id)
    (println (format (str (apply str (repeat indent \space)) format-string) args))))

The main difference from the previous code is achieve-all which ensures all goals are achieved throughout the process and the use of the executing convention to
denote actions that are being executed.

As you'd expect the primary difference with Common Lisp is that we've got to use transactions to perform mutability. In achieve-all, I've used an atom to represent the current state. Atoms are used when only one thread needs access to the code and all changes are synchronous. In this case, the atom exists only for one loop hence an atom is the right choice.

Clojure's support of sets meant that representing the goal, add and delete lists as sets made sense. Representing the result as a set is wrong though, because I want to return the list of actions that must be performed in the correct order (see the version history on Git to see the catalogue of mistakes I made before realizing this!).

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

(defn executing?
  [x]
  "Is x of the form: (executing ...)?"
  (and (seq? x) (= 'executing (first x))))

(defn convert-op
  [op]
  "Make op conform the the (EXECUTING op) convention"
  (if-not (some executing? (:add-list op))
    (struct operation 
            (:action op) 
            (:preconditions op) 
            (set (conj (:add-list op) (list 'executing (:action op))))
            (:del-list op))
    op))

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

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

(declare achieve-all)

(defn apply-op
  [state goal op goal-stack]
  "Return a new, transformed state if op is applicable."
  (dbg-indent :gps (count goal-stack) "Consider: %s" (:action op))
  (let [new-state (achieve-all state (:preconditions op) (cons goal goal-stack))]
    (when-not (nil? state)
      (dbg-indent :gps (count goal-stack) "Action: %s" (:action op))
      (concat (remove (fn [x] (= x (:del-list op))) new-state)
              (:add-list op)))))

(defn achieve
  [state goal goal-stack]
  "A goal is achieved if it already holds,
   or if there is an appropriate op for it that is applicable"
  (dbg-indent :gps (count goal-stack) "Goal: %s" goal)

  (cond
    (contains-value? state goal) state
    (contains-value? goal-stack goal) nil
    :else (some (fn [op] (apply-op state goal op goal-stack))
                (filter (fn [x] (appropriate? goal x)) @*ops*))))

(defn sequential-subset?
  [s1 s2]
  (and (<= (count s1) (count s2))
       (every? (fn [x] (contains-value? s2 x)) s1)))

(defn achieve-all 
  [state goals goal-stack]
  "Achieve each goal, and make sure they still hold at the end."
  (let [current-state (atom state)]
    (if (and (every? (fn [g] (swap! current-state 
                                    (fn [s] (achieve s g goal-stack)))) goals)
             (sequential-subset? goals @current-state))
      @current-state)))


(defn GPS
  [state goals ops]
  "General Problem Solver: from state, achieve using ops"
  (dosync
   (ref-set *ops* ops))
  (remove (comp not sequential?) (achieve-all (cons (list 'start) state) goals [])))

GPS is a semi-predicate (a function that returns nil on failure and some useful value otherwise). It returns the list of actions required to reach the goal, or nil.

This GPS can solve a larger class of problems, and Norvig gives the example of the "Monkey and Bananas" problem attributed to Saul Amarel.

The output from the REPL shows this implementation of the "General Problem Solver" working on this problem:

uk.co.fatvat.gps2> (monkey-and-bananas)
Goal: (not-hungry)
Consider: (eat-bananas)
 Goal: (has-bananas)
 Consider: (grasp-bananas)
  Goal: (empty-handed)
  Consider: (drop-ball)
   Goal: (has-ball)
  Action: (drop-ball)
  Goal: (at-bananas)
  Consider: (climb-on-chair)
   Goal: (at-middle-room)
   Consider: (push-chair-from-door-to-middle-room)
    Goal: (at-door)
    Goal: (chair-at-door)
   Action: (push-chair-from-door-to-middle-room)
   Goal: (chair-at-middle-room)
   Goal: (on-floor)
  Action: (climb-on-chair)
 Action: (grasp-bananas)
Action: (eat-bananas)
((start) 
  (executing drop-ball) 
  (executing push-chair-from-door-to-middle-room)
  (executing climb-on-chair)
  (executing grasp-bananas)
  (executing eat-bananas))

So does the GPS live up to the promises? As you may have guessed, not quite! It requires a complete specification of the problem to be useful. Even if you do have a perfect description of the problem, it might take forever to find the answer (see NP-hard problems for many examples).

Full code is available on my Clojure Project git page.