AI search

search.clj

(ns adgoji.planning.search
  (:require [clojure.data.priority-map :as priority-map]))

(defprotocol IStack
  (next-node [_])
  (rest-nodes [_])
  (add-nodes [_ nodes]))

(defrecord Queue [queue]
  IStack
  (next-node [_]
    (peek queue))

  (rest-nodes [this]
    (assoc this :queue (pop queue)))

  (add-nodes [this nodes]
    (assoc this :queue (into queue nodes))))

(defn queue []
  (->Queue (clojure.lang.PersistentQueue/EMPTY)))

(defrecord Stack [stack]
  IStack
  (next-node [_]
    (peek stack))

  (rest-nodes [this]
    (assoc this :stack (pop stack)))

  (add-nodes [this nodes]
    (assoc this :stack (into stack nodes))))

(defn stack []
  (->Stack '()))

(defrecord PriorityQueue [queue]
  IStack
  (next-node [_]
    (ffirst queue))

  (rest-nodes [this]
    (assoc this :queue (pop (not-empty queue))))

  (add-nodes [this nodes]
    (assoc this :queue (into queue
                             (map (fn [node]
                                    [node (get node :utility 0)]))
                             nodes))))

(defn priority-queue []
  (->PriorityQueue (priority-map/priority-map-by (fn [a b]
                                                   (compare b a)))))

(defn add-successors [successors-fn {:keys [node path] :as current-state}]
  (map (fn [{:keys [node] :as next-state}]
         (assoc next-state :path (conj path node)))
       (successors-fn current-state)))

(defn search [{:keys [initial-state
                      goal-fn
                      n-goals
                      stack
                      successors-fn
                      max-nodes]}]
  (loop [node-count max-nodes
         solutions []
         {:keys [node] :as current-state} {:node initial-state :path [initial-state]}
         stack stack]
    (if (<= node-count 0)
      {:error :max-count-reached :solutions solutions :steps (- max-nodes node-count)}
      (if node
        (let [stack0 (add-nodes stack (add-successors successors-fn current-state))]
          (if (goal-fn node)
            (let [solutions0 (conj solutions current-state)]
              (if (< (count solutions) n-goals)
                (recur (dec node-count) solutions0 (next-node stack0) (rest-nodes stack0))
                {:solutions solutions0 :steps (- max-nodes node-count)}))
            (recur (dec node-count) solutions (next-node stack0) (rest-nodes stack0))))
        {:solutions solutions :steps (- max-nodes node-count)}))))

search_test.clj

(ns adgoji.planning.search-test
  (:require [adgoji.planning.search :refer :all]
            [midje.sweet :refer :all]))

(fact "Breadth first search"
       (let [deps {:a #{:b}
              :b #{:a :c}
              :c #{:d :g}
              :g #{:f}
              :d #{:e}
              :e #{:f}}
        goal-fn (fn [state]
                  (= state :f))

        expand-state (fn [state]
                       (get deps state))]
    (-> (search {:initial-state :a
                 :goal-fn goal-fn
                 :n-goals 1
                 :max-nodes 1000
                 :successors-fn (fn [{:keys [node] :as state}]
                                  (expand-state node))
                 :stack (queue)

                 }))
    =>  {:solutions [{:node :f, :path [:a :b :c :g]}
                     {:node :f, :path [:a :b :c :d :e]}], :steps 11}))

(fact "Depth first search"
       (let [deps {:a #{:b}

              :b [:c #_:a]
              :c #{:d :g}
              :g #{:f}
              :d #{:e}
              :e #{:f}}
        goal-fn (fn [state]
                  (= state :f))

        expand-state (fn [state]
                       (vec (get deps state)))]
    (search {:initial-state :a
             :goal-fn goal-fn
             :max-nodes 100
             :n-goals 1
             :successors-fn (fn [ {:keys [node]}]
                              (expand-state node))
             :stack (stack)}))
       =>  {:solutions [{:node :f, :path [:a :b :c :d :e]} {:node :f, :path [:a :b :c :g]}], :steps 7}
       )