S.C.Lynch,  2016

abstract

Switching from imperative and object oriented programming languages to functional symbolic languages can be challenging. This becomes more demanding if, at the same time, the focus of programming work changes to a new, more ambitious domain. None the less, many computer scientists face this situation, compounded for some by the need to "come up to speed" in a short time-frame.

 

The following paper is developed from a workshop used to introduce the principles of symbolic computation in Clojure and investigate how Clojure can be used to build some key inference engines used in Artificial Intelligence.

 

notes

1.    many of the examples rely on the Clojure matcher, this is available at:
http://s573859921.websitehome.co.uk/pub/clj/tools_index.htm

2.    some examples are taken from the user guide for the matcher, see the following URL for this user guide and related documents:
http://s573859921.websitehome.co.uk/pub/clj/tools_index.htm

 

 


 

 

contents

setup

 

move generators for breadth 1st search

- maths puzzle

- route planning

 

simple rules (no matching)

- rule application

- forward chaining

- backward chaining

 

tuples

- example: searching through tuples

 

matching rules

- application

- forward chaining

 

operators

- application

 

operator search

 

summary notes

 

 


 

 

setup

The examples make use of the Clojure files/packages below, these can be obtained from...

www.agent-domain.org

...follow the menus to "Clojure tools".

 

files...

         cgsx.tools.matcher        this used throughout, have this loaded at all times

 

these other files are only used for specific examples...

         breadth-search

         operator search

 

NB: we also use clojure.tools.trace

 

The following imports are needed throughout...

(require '[clojure.set :refer :all])

(require '[cgsx.tools.matcher :refer :all])

(require '[clojure.tools.trace :refer :all])

 

move generators for breadth 1st search

A common theme in Artificial Intelligence is to find a path from some starting position (a start state) to some desired outcome (the goal state). This could be, for example, to reorganise a random configuration of objects into organised piles or to efficiently distribute materials around a warehouse.

 

The nature of state and the way they are represented depends on the specifics of the problem. For example: the state can sometimes be represented simply by place names if the problem is to find a route between places can be necessarily more complex for other planning problems.

 

One of the simpler methods for finding a path from a start state to a goal state is to use breadth first search. A breadth first search is available in Clojure from www.agent-domain.org (follow links to Clojure tools). This search takes 3 arguments: a start state, a goal state and a transformation function which is often called a Legal Move Generator (LMG).

 

LMGs are simple functions which take a state as their only argument and return a sequence of successor states (states which can be reached by a single move from the current state).

 

maths puzzle

With this puzzle you have to work out how to get from one number to another by using a small number of simple (mathematical rules). For example... how can you get from 5 to 159 with the following three rules...

1.   you can add 3

2.   multiply by 2

3.   subtract 7

 

The breadth first search does most of the work but it needs an LMG (a function which takes one state and produces a list of successor states), eg:

 

(defn lmg1 [n]

  [ (+ n 3) (* n 2) (- n 7) ])

 

user=> (breadth-search 5 35 lmg1)

(5 8 16 32 35)

 

user=> (time (breadth-search 5 1357 lmg1))

"Elapsed time: 847.73328 msecs"

(5 8 11 22 44 88 176 169 338 341 682 1364 1357)

 

Notice a couple of things...

    breadth-search takes 3 arguments: a start state, a goal state & a LMG

    functions get passed as arguments just like any other data

 

route planning

Since LMGs are essentially abstractions which, given some state-type S (a state abstraction) produce a sequence of new states, Clojure maps can also be used as LMGs as long as they are a map of the form {S => S', S'', S'''...}. The following example uses this approach.

 

We want to find a route of interconnecting flights from one airport to another given some representation of which airports have direct connecting flights to which other airports. We can conveniently specify direct connections using a data structure which is a map. We can then use this to build a LMG...

 

(def flights

  '{ teesside  (amsterdam dublin heathrow)

     amsterdam (dublin teesside joburg delhi dubai)

     delhi     (calcutta mumbai chennai)

     calcutta  (mumbai kathmandu)

     mumbai    (chennai delhi dubai)

     chennai   (colombo)

     dubai     (delhi colombo joburg)

    })

 

user=> (flights 'delhi)

(calcutta mumbai chennai)

user=> (flights 'amsterdam)

(dublin teesside joburg delhi dubai)

 

Notice, as discussed above, the call (flights airport-name) works like an LMG it takes one state and generates successor states. This means we can use it as an LMG...

 

user=> (breadth-search 'teesside 'colombo flights)

(teesside amsterdam dubai colombo)

 

tuples

Another common approach taken with symbolic Artificial Intelligence is to represent facts as tuples (short structured sequences of symbols). So the fact "tom is a cat" could be represented as...

[:isa tom cat]

 

Notice...

(i)   here we use the structure [relation object value] this is normal practice

(ii)  we use a Clojure vector as the tuple type (idiomatic but probably a good idea)

(iii) we use a keyword for the relation (personal choice I use sometimes)

 

Fact-based inference engines then inspect and act on collections of facts either to infer new facts or to explicitly identify relationships between existing facts.

 

example: searching through tuples

The matcher supports two forms to provide iteration and collection capability, these are called mfor and mfor*. They iterate over sets of data using one pattern (mfor) or multiple patterns (mfor*). The following examples use food data:

 

(def food

 '([isa cherry  fruit]   [isa cabbage veg]

   [isa chilli  veg]     [isa apple   fruit]

   [isa radish veg]      [isa leek    veg]

   [color leek  green]   [color chilli  red]

   [color apple green]   [color cherry  red]

   [color cabbage green] [color radish red]

  ))

 

(mfor ['[isa ?f veg] food] (? f))

→ (cabbage chilli radish leek)

 

(mfor* ['([isa ?f veg] [color ?f red])

        food]

    (? f))

→ (chilli radish)

 

Our first example of working with facts considers writing a query mechanism which examines a collection of tuples to identify objects which have some specified properties. Eg: we may want to find "all the red cubes which are on the table" given the following set of facts:

 

(def blocks

  '( [isa b1 cube]  [isa b2 cube]  [isa  b3 cube] [isa  b4  wedge]

     [isa b5 wedge] [isa b6 wedge] [color b1 red] [color  b2  red]

     [color  b3  red] [color  b4  blue] [color  b5  blue]

     [color b6 blue] [on b1 table] [on b2 table] [on b5 table]))

 

The searching and selection forms provided in the matcher pass patterns across collections of data, returning the first match which is found. These matcher forms are called mfind (which matches one pattern across a collection of data) and mfind* (which consistently matches a group of patterns across a collection of data). The next two examples use the food data (the blocks data above is used for practical exercises in the workshop).

 

Note that in these example we use vectors in our data, this is perhaps idiomatic but we sometimes prefer wrapping tuples as vectors (rather than as lists) and the matcher deals with either vectors or lists (or maps).

 

mfind takes one pattern:

 

(mfind ['[isa ?f veg] food] (? f))

→ cabbage

 

mfind* takes multiple patterns:

 

(mfind* ['([isa ?f veg] [color ?f red])

         food]

    (? f))

→ chilli

 

 

The matcher allows patterns to be created dynamically (ie: while functions are evaluating). We can take advantage of this to build a flexible lookup function for tuples...

 

 

(defn lookup [reln  val tuples]

  (set (mfor [[reln '?x val] tuples]

         (? x))))

 

 

user=> (lookup 'isa 'fruit food)

  #{cherry apple}

user=> (lookup 'color 'red food)

  #{radish cherry chilli}

 

; set operations can combine these values

user=> (intersection (lookup 'isa 'fruit food) (lookup 'color 'red food))

  #{cherry}

user=> (union (lookup 'isa 'fruit food) (lookup 'color 'red food))

  #{radish cherry chilli apple}

 

; reduce + set-operation can also be used

user=> (reduce intersection [(lookup 'isa 'fruit food) (lookup 'color 'red food)])

  #{cherry}

user=> (reduce union [(lookup 'isa 'fruit food) (lookup 'color 'red food)])

  #{radish cherry chilli apple}

 

 

(defn query [data set-op pairs]

  (reduce set-op

    (map (fn [[reln val]] (lookup reln  val data)) pairs)))

 

 

user=> (query food union '([isa fruit][color red]))

  #{radish cherry chilli apple}

user=> (query food intersection '([isa fruit][color red]))

  #{cherry}

 

simple rules (no matching)

Other fact-based inference mechanisms infer new facts from existing facts, we use rules to do this. If, for example, we know "Sally is Ellen's daughter and Sam is Sally's son" then we can infer that "Ellen is one of Sam's grandparents". A general purpose rule could be used to capture this relationship...

 

[grandparent-rule-2

  [parent ?a ?b]  [parent ?b ?c]  :=>  [grandparent ?a ?c]]

 

This rule has 3 parts...

1.    a name: grandparent-rule-2

2.    antecedents facts that must be true for the rule to apply:
[parent ?a ?b]  [parent ?b ?c]

3.    consequents facts that are inferred if the rule applies:
[grandparent ?a ?c]

 

This style makes use of the matcher to abstract out the names of people and is thereby general purpose. Later examples will develop rule-apply mechanisms for these types of rule but before then we consider a simple rule structure.

 

rule application

Simplified rules are of the form...

 

[pop corn => popcorn]

 

... facts are simple symbols (like "pop" and "corn") and the rules do not use match expressions (but the matcher is still used in the rule compiler).

 

For the next examples we use the following rules...

 

(def rules

  (compile-rules

    '( [tom and jerry   => cartoon two-d  ]

       [shrek           => cartoon three-d]

       [cartoon popcorn => movie]

       [pop corn => popcorn]

       [mouse    => jerry micky]

       [cat      => tom felix]

       [ogre     => shrek]

       )))

 

The rule compiler is a simple function which strips apart textual forms of rules,

converts antecedent & consequents lists to sets and rebuilds the result into a map

 

(defn compile-rules [rules]

  (mfor ['[??pre => ??post] rules]

    {:ante (set (? pre)), :consq (set (? post))}

    ))

 

; after rule compilation...

user=> rules

( {:ante #{and jerry tom}, :consq #{two-d cartoon}}

  {:ante #{shrek}, :consq #{three-d cartoon}}

  {:ante #{popcorn cartoon}, :consq #{movie}} ...etc...)

 

With facts specified as a set of symbols...

 

(def facts '#{mouse meets cat with pop and corn})

 

...rule application becomes a simple subset test...

 

(defn apply-rule [facts rule]

  (when (subset? (:ante rule) facts)

    (:consq rule)))

 

;user=> (apply-rule '#{jerry meets tom with pop and corn} (first rules))

;  #{two-d cartoon}

 

forward chaining

Forward chaining is a simple inference mechanism which exhaustively applies rules, continuing for as long as it can generate new facts.

 

The forward chainer below repeatedly applies its rules keeping account of the number of facts it has and stopping when no new facts are generated.

 

 (reduce union ...) is used to combine new facts with existing facts.

 

(defn fwd-chain [facts rules]

  (println (list 'facts= facts))     ; to help see what is happening

  (let [fact-count (count facts)

        new-facts  (reduce union facts (map #(apply-rule facts %) rules))

        ]

    (if (= fact-count (count new-facts))

      facts

      (recur new-facts rules)

      )))

 

 

user=> (def facts '#{mouse meets cat with pop and corn})

#'user/facts

user=> (fwd-chain facts rules)

** facts= #{mouse corn with meets cat and pop}

** facts= #{micky felix mouse corn with popcorn meets cat

             and pop jerry tom}

** facts= #{two-d micky felix mouse corn with popcorn meets

             cat and cartoon pop jerry tom}

** facts= #{two-d micky felix mouse corn with popcorn meets

             movie cat and cartoon pop jerry tom}

#{two-d micky felix mouse corn with popcorn meets movie cat

   and cartoon pop jerry tom}

 

backward chaining

Forward chaining can often be useful but it can also be inefficient. If you know a specific fact you wish to generate then backward chaining, a goal directed inference mechanism is more optimal.

 

The simplest way to specify a backward chainer is use a global (but still immutable) set of rules and a global and mutable fact base. To allow the fact base to be mutable we use the atom reference type (see Clojure core documentation for details).

 

(def facts (atom '#{mouse meets cat with pop and corn}))

 

(defn add-facts [newfs]

  "fact-base updater"

  (swap! facts (fn [fs] (union fs newfs))))

 

user=> facts

#<Atom@1d5faf4b: #{mouse corn with meets cat and pop}>

user=> (add-facts '(mango melon banana))

#{mouse corn mango with meets melon banana cat and pop}

 

The backward chainer is given a goal-fact to assert/prove or refute. It operates a kind of depth first search using rules to generate successor states.

 

It works as follows: if the goal is present in the set of facts then it is proven & the facts are returned otherwise it finds any rules which can prove the goal (those which include the goal in their consequents) then sequentially steps through these rules (using some) trying to prove their antecedents. When a rule has its antecedents satisfied, its consequents are added to the fact-base. The backward chainer fails if cannot find any chain of rule applications which assert the goal.

 

(defn bwd [goal]

  (if (contains? @facts goal) @facts

 

    ;; else run through suitable rules

    ;; rules2 are rules with (contains? :consq goal)

    (let [rules2 (filter #(contains? (:consq %) goal) rules)]

      (some (fn [r] (when (every? bwd (:ante r))

                      (add-facts (:consq r))))

        rules2))

    ))

 

 

user=> (def facts (atom '#{mouse meets cat with pop and corn}))

#'user/facts

user=> (bwd 'movie)

  #{two-d micky felix mouse corn with popcorn meets movie cat

     and cartoon pop jerry tom}

 

; notice that bwd-chain dosn't do more work than necessary

user=> (def facts (atom '#{mouse meets cat with pop and corn}))

#'user/facts

user=> (bwd 'two-d)

  #{two-d micky felix mouse corn with meets cat and cartoon pop jerry tom}

 

; to examine bwd-chain in detail use trace

user=> (def facts (atom '#{mouse meets cat with pop and corn}))

#'user/facts

user=> (trace-vars bwd)

#'user/bwd

user=> (bwd 'movie)

TRACE t534: (user/bwd movie)

TRACE t535: | (user/bwd popcorn)

TRACE t536: | | (user/bwd corn)

TRACE t536: | | => #{mouse corn with meets cat and pop}

TRACE t537: | | (user/bwd pop)

TRACE t537: | | => #{mouse corn with meets cat and pop}

TRACE t535: | => #{mouse corn with popcorn meets cat and pop}

TRACE t538: | (user/bwd cartoon)

TRACE t539: | | (user/bwd and)

TRACE t539: | | => #{mouse corn with popcorn meets cat and pop}

TRACE t540: | | (user/bwd jerry)

TRACE t541: | | | (user/bwd mouse)

TRACE t541: | | | => #{mouse corn with popcorn meets cat and pop}

TRACE t540: | | => #{micky mouse corn with popcorn meets cat and pop jerry}

TRACE t542: | | (user/bwd tom)

TRACE t543: | | | (user/bwd cat)

TRACE t543: | | | => #{micky mouse corn with popcorn meets cat and pop

                        jerry}

TRACE t542: | | => #{micky felix mouse corn with popcorn meets cat and

                      pop jerry tom}

TRACE t538: | => #{two-d micky felix mouse corn with popcorn meets cat

                    and cartoon pop jerry tom}

TRACE t534: => #{two-d micky felix mouse corn with popcorn meets movie

                  cat and cartoon pop jerry tom}

  #{two-d micky felix mouse corn with popcorn meets movie cat and

    cartoon pop jerry tom}

 

matching rules

Before investigating the forward & backward chainers above we noted that general purpose rules contained matching expressions to match against facts. Having established the general principles using non-matching rules (last section), we now consider a rule application mechanism which uses matching.

application of matching rules

Consider the following rule...

 

[rule 15 [parent ?a ?b] [parent ?b ?c]

  => [grandparent ?a ?c]]

 

...which would work on data like...

 

(def family

  '#{[parent Sarah Tom]

     [parent Steve Joe]

     [parent Sally Sam]

     [parent Ellen Sarah]

     [parent Emma  Bill]

     [parent Rob   Sally]})

 

As an initial step these rules are compiled into a map and sets. This time we use a rule compiler for individual rules...

 

(defmatch compile-rule []

  ([rule ?id ??antecedents => ??consequents]

    :=> {:id (? id), :ante (? antecedents) :consq (? consequents)}

    ))

 

A suitable rule application mechanism needs to split the rule into its constituent parts; search for all consistent sets of antecedents; ripple any antecedent variable bindings through to consequents and collect evaluated consequents for each rule every time it fires. In practice these requirements can be by using a match function to pull a rule apart, mfor* to satisfy all possible antecedent combinations and mout to bind variables into consequents. This can be specified as follows...

 

(defn apply-rule [facts rule]

  (set (mfor* [(:ante rule) facts]

         (mout (:consq rule)))))

 

(apply-rule family

  (compile-rule '[rule 15 [parent ?a ?b] [parent ?b ?c]

                  => [grandparent ?a ?c]]

     ))

 

 →  #{[grandparent Ellen Tom] [grandparent Rob Sam]}

 

forward chaining with matching rules

To investigate this rule deduction example further we use a richer set of facts and rules (where the consequences of some rules trigger the antecedents of others)...

 

(def facts1

  '#{ [big elephant]  [small mouse]

      [small sparrow] [big whale]

      [on elephant mouse]

      [on elephant sparrow]

     })

 

(def rules1

  (map compile-rule

    '( [rule 0 [heavy ?x] [small ?y] [on ?x ?y]

        => [squashed ?y] [sad ?x]]

       [rule 1 [big ?x]   => [heavy ?x]]

       [rule 2 [light ?x] => [portable ?x]]

       [rule 3 [small ?x] => [light ?x]]

       )))

 

Given these definitions it is possible to develop a function to apply all rules once...

 

(defn apply-all [facts rules]

  (reduce union

    (map #(apply-rule facts %) rules)

    ))

 

(apply-all facts1 rules1)

 →  #{[light mouse] [heavy elephant] [light sparrow] [heavy whale]}

 

NB: the fwd-chain function is the same as we used before...

 

(defn fwd-chain [facts rules]

  (println '** 'facts= facts)     ; to help see what is happening

  (let [fact-count (count facts)

        new-facts  (reduce union facts (map #(apply-rule facts %) rules))

        ]

    (if (= fact-count (count new-facts))

      facts

      (recur new-facts rules)

      )))

 

(fwd-chain facts1 rules1)

 →  #{(light mouse) (heavy elephant)

     (on elephant sparrow)

     (squashed sparrow)

     (small sparrow) (on elephant mouse)

     (squashed mouse) (small mouse)

     (portable sparrow) (big whale)

     (portable mouse) (big elephant)

     (sad elephant) (light sparrow)

     (heavy whale)}

 

operators

When we first considered using breadth first search (the first part of this workshop) we assumed simple (atomic) state representations (number or symbols). Most problems are a little more involved and state representations then become necessarily more complex. One common approach is to represent states as a set of facts (actually we often use 2 sets: one which may change between different problem states, the other which cannot change). There are many good reasons to take this approach but a discussion of these is beyond the scope of this document.

 

In this example we consider how to apply the kind of state changing operators that are used in some planning systems. Broadly we adapt a representation borrowed from PDDL for use with a STRIPS style solver. The operators are specified in terms of their preconditions and their effects. We use tuples to capture state information. The following tuples, for example, describe a simple state in which some (animated) agent (R) is at a table is holding nothing and a book is on the table.

 

#{(at R table)

  (on book table)

  (holds R nil)

  (path table bench)

  (manipulable book)

  (agent R)

  }

 

In order to generalise an operator (so it can be used with different agents, objects and in various locations) it is necessary to specify it using variables, in this case matcher variables. An operator which describes a "pickup" activity for an agent and which can be used to produces a new state (new tuples) could be described as follows...

 

  {:pre ((agent ?agent)

         (manipulable ?obj)

         (at ?agent ?place)

         (on ?obj   ?place)

         (holds ?agent nil)

         )

   :add ((holds ?agent ?obj))

   :del ((on ?obj   ?place)

         (holds ?agent nil))

   }

 

The operator is map with three components (i) a set of preconditions which must be satisfied in order for the operator to be used (ii) a set of tuples to add to an existing state when producing a new state and (iii) a set of tuples to delete from an existing state.

 

application

To apply this kind of operator specification we extract patterns from the operator then use mfind*

 

(defn apply-op

  [state {:keys [pre add del]}]

  (mfind* [pre state]

    (union (mout add)

      (difference state (mout del))

      )))

 

 (apply-op state1 ('pickup ops))

 →  #{(agent R) (holds R book)

      (manipulable book)

      (path table bench) (at R table)}

 

The patterns used by mfind* are provided dynamically when apply-op is called and furthermore the patterns themselves define the semantics of the operators.

 

Collections of operators are conveniently held in a map, and ordered sequences of operator applications can be formed by chaining apply-op calls, eg:

 

(def ops

  '{pickup {:pre ((agent ?agent)

                  (manipulable ?obj)

                  (at ?agent ?place)

                  (on ?obj   ?place)

                  (holds ?agent nil)

                  )

            :add ((holds ?agent ?obj))

            :del ((on ?obj   ?place)

                  (holds ?agent nil))

            }

    drop    {:pre ((at ?agent ?place)

                   (holds ?agent ?obj)

                   )

             :add ((holds ?agent nil)

                   (on ?obj   ?place))

             :del ((holds ?agent ?obj))

             }

    move    {:pre ((agent ?agent)

                   (at ?agent ?p1)

                   (path ?p1 ?p2)

                   )

             :add ((at ?agent ?p2))

             :del ((at ?agent ?p1))

             }

    })

 

(-> state1

  (apply-op ('pickup ops))

  (apply-op ('move   ops))

  (apply-op ('drop   ops)))

 

→ #{(agent R) (manipulable book)

    (on book bench) (holds R nil)

    (at R bench) (path table bench)}

 

 

operator search

This section is taken from the matcher documentation.

 

ops-search provides a simple, partially optimised implementation of a breadth-first search mechanism for applying simple STRIPS-style operators (NB: in many real-world situations a breadth first search can be inefficient, for a more efficient engine check out the planner follow the link to Clojure tools at www.agent-domain.org).

 

ops-search takes the following arguments...

           start       - a start state

           goal        - a minimally specified goal state (see below)

           operators:         - a collection of operators

           :world     - a definition of unchanging world states

 

ops-search returns a map showing...

           the goal state it reached

           the path it took

           any comands to send to another subsystem

           a textual description of the path

 

Note: it is possible to use ops-search without the pattern matcher but its use is then highly restricted. For this guide we assume the pattern matcher will be used.

 

Goals are minimally specified so any state which is a superset of the goal is deemed a goal state.

 

In addition to :pre, :add & :del entries, operators may (optionally) also specify...

:txt     - a textual description of the operator application to aid readibility

:cmd   - an encoded command for the operator, typically for the benefit of some other subsystem.

 

A more complete (but still slightly toy) set of operators could be...

 

(def ops

  '{pickup {:pre ( (agent ?agent)

                   (manipulable ?obj)

                   (at ?agent ?place)

                   (on ?obj   ?place)

                   (holds ?agent nil)

                   )

            :add ((holds ?agent ?obj))

            :del ((on ?obj   ?place)

                   (holds ?agent nil))

            :txt (pickup ?obj from ?place)

            :cmd [grasp ?obj]

            }

    drop    {:pre ( (at ?agent ?place)

                    (holds ?agent ?obj)

                    (:guard (? obj))    ;this prevents ?obj matching nil

                    )                   ;for details check matcher/guard

             :add ( (holds ?agent nil)

                    (on ?obj   ?place))

             :del ((holds ?agent ?obj))

             :txt (drop ?obj at ?place)

             :cmd [drop ?obj]

             }

    move    {:pre ( (agent ?agent)

                    (at ?agent ?p1)

                    (connects ?p1 ?p2)

                    )

             :add ((at ?agent ?p2))

             :del ((at ?agent ?p1))

             :txt (move ?p1 to ?p2)

             :cmd [move ?p2]

             }

    })

 

The next example uses the pickup, drop & move operators as defined above and the following state...

 

(def state1

  '#{(at R table)

     (on book table)

     (on spud table)

     (holds R nil)

     (connects table bench)

     (manipulable book)

     (manipulable spud)

     (agent R)

     })

 

Note (as stated above) goals are minimally specified so any state which is a superset of the goal is deemed a goal state.

 

user=> (ops-search state1 '((on book bench)) ops)

{:state #{(agent R) (manipulable book) (on spud table)

          (on book bench) (holds R nil) (at R bench)

          (manipulable spud) (connects table bench)},

:path (#{(agent R) (manipulable book) (on spud table)

         (holds R nil) (manipulable spud) (connects table bench)

         (on book table) (at R table)}

        #{(agent R) (holds R book) (manipulable book)

          (on spud table) (manipulable spud)

          (connects table bench) (at R table)}

        #{(agent R) (holds R book) (manipulable book)

          (on spud table) (at R bench)

          (manipulable spud) (connects table bench)}),

:cmds ([grasp book] [move bench] [drop book]),

:txt ((pickup book from table) (move table to bench) (drop book at bench))}

 

using :world knowledge

:world definitions contain unchanging state relations. Separating static/world relations from those that may change improves the efficiency of the search.

 

(def world

  '#{(connects table bench)

     (manipulable book)

     (manipulable spud)

     (agent R)

     })

 

(def state2

  '#{(at R table)

     (on book table)

     (on spud table)

     (holds R nil)

     })

 

 

user=> (ops-search state2 '((on book bench)) ops :world world)

{:state #{(on spud table) (on book bench) (holds R nil) (at R bench)},

:path (#{(on spud table) (holds R nil) (on book table) (at R table)}

        #{(holds R book) (on spud table) (at R table)}

        #{(holds R book) (on spud table) (at R bench)}),

:cmds ([grasp book] [move bench] [drop book]),

:txt ((pickup book from table) (move table to bench) (drop book at bench))}

 

using compound goals

 

(def world2

  '#{(connects table bench)

     (connects bench table)

     (connects bench sink)

     (connects sink bench)

     (manipulable book)

     (manipulable spud)

     (agent R)

     })

 

(def state3

  '#{(at R table)

     (on book table)

     (on spud table)

     (holds R nil)

     })

 

user=> (ops-search state3 '((on book bench)(on spud sink)) ops :world world2)

{:state #{(at R sink) (on book bench) (holds R nil) (on spud sink)},

 :path (#{(on spud table) (holds R nil) (on book table) (at R table)}

        #{(holds R book) (on spud table) (at R table)}

        #{(holds R book) (on spud table) (at R bench)}

        #{(on spud table) (on book bench) (holds R nil) (at R bench)}

        #{(on spud table) (on book bench) (holds R nil) (at R table)}

        #{(on book bench) (holds R spud) (at R table)}

        #{(on book bench) (at R bench) (holds R spud)}

        #{(at R sink) (on book bench) (holds R spud)}),

 :cmds ([grasp book] [move bench] [drop book]

        [move table] [grasp spud] [move bench] [move sink] [drop spud]),

 :txt ((pickup book from table) (move table to bench) (drop book at bench)

       (move bench to table) (pickup spud from table) (move table to bench)

       (move bench to sink) (drop spud at sink))}

 

Note that goals can be specified as matcher patterns so the following is also a valid call...

 

(ops-search state3 '((on ?x bench)(on ?y sink)) ops :world world2)

 

summary notes

This paper forms the basis of a workshop used to introduce the principles of symbolic computation in Clojure for participants who have only rudimentary prior knowledge of Clojure. It assumes no knowledge exposure to either Symbolic Computation or Artificial Intelligence. A primary aim of the workshop is to introduce some additional Clojure tools and work through the development of some key inference engines used in Artificial Intelligence.

 

In its current form, the paper does not examine the practical exercises used as part of the workshop, for more information about these please contact the author. See the Clojure tools pages of www.agent-domain.org for additional details about the matcher, optimised search routines and a goal-directed planner which provides a more efficient means to apply state-changing operators.