Clojure

ops-search [ start goal operators {:keys [world debug]} ]

ops-search provides a simple, partially optimised implementation of a breadth-first search mechanism for applying simple STRIPS-style operators (NB: for a more efficient engine check out the planner).

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.

operators

Operators for this search are specified in a map which should associate the operator name with its definition. Operator definitions describe preconditions and effects; effects are specified in terms of deletions and additions. The operators used in the examples below are based on a tuple representation.

For example, a move-agent operator could be written as...

move {:pre ((agent ?agent)

(at ?agent ?p1)

(connects ?p1 ?p2)

)

:add ((at ?agent ?p2))

:del ((at ?agent ?p1))

Given a state description like...

'#{(at Ralf table)

(connects table bench)

(agent Ralf)

})

The move operator could produce a successor state...

'#{(at Ralf bench)

(connects table bench)

(agent Ralf)

})

...by deleting (at Ralf table) and adding (at Ralf bench).

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))

)

: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]

}

})

example 1 – without using :world

All following examples use the pickup, drop & move operators defined above.

(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))}

example 2 – using :world

: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))}

example 3 – 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)