PROGRAM INTERFACE FOR THE "MOTIVATED EXPLORER'S (ME'S) GRIDWORLD ================================================================ Preliminary Comments about Self-Awareness ========================================= Self-awareness -- knowing what one knows, wants, etc. (and also knowing what others know and want) -- is particularly important in dialogues. It is not clear yet how far "conversational" interactions (between agents at various locations and ME) can be taken using the current infra- structure, but a simple example is given in eg-dialog-world.lisp. However, you will also be able to implement simple demonstr- ations of self-awareness through interaction of the agent with you, as user; i.e., you can implement ways of querying the self-knowledge of the system, with questions such as (Q (know-whether ME (hungry ME))), (assuming that `Q' is used as the query function) , or (Q (know-that ME ((know-whether ME (is_hungry Grunt)) (from a user perspective, this asks, "Are you aware that you know whether Grunt is hungry?"). Perhaps a little more challengingly, you can ask about what was done so far by ME. A *history* list is maintained when you step ME through a sequence of actions, with a time (0, 1, 2, ...) for each action, and so you should be able to allow for questions like "Did you ever eat a banana?" -- say, (Q (and (eat ME ?x) (is_a_banana ?x))). NOTE THAT THE GIVEN INFRASTRUCTURE INCLUDES METHODS OF MATCHING A LIST OF "GOAL" FORMULAS (POTENTIALLY CONTAINING VARIABLES) TO A SET OF "FACTS" (positive ground literals such as (is_a_banana Banana3)).). A little more ambitiously, you could also implement question-answering about intentions. After each step taken by ME (by executing the function (go!)), ME will have a plan tree whose leftmost branches correspond to its "most promising" plan. The global constant *plan* gives those leftmost branches. Using this to talk about intentions would be straightforward, but you could also "dig deeper" into the plan tree structure, to obtain information about WHY ME intends to do this. (This is not trivial. There are values associated with states and actions, but the simple ways in which the examples given below for value-computation are calculated would make it awkward to decide exactly WHAT is is about a given step or resulting state that makes it "attractive".) This kind of QA implementation would depend on only a portion of the infrastructure, and so could be pursued by you almost independently of the latter. In particular, the function `all-bindings-of-goals-to-facts' described below should suffice for much of the QA. Also, for QA based on *history*, you could easily hand-construct example values of *history* and develop your code based on these. Even for dealing with intentions, you could hand-construct simple values for *plan* (a list of actions, with values of parameters) and *states* (a sequence of lists of wffs, each list of wffs describing a state travesed by the intended plan in *plan*). General knowledge other than what is added via 'def-object' can also be added by hand to *general-knowledge*. For example, if you wanted your agent to hate snakes, you could push the "emotional" knowledge item ((snake ?x) => (hate ME ?x)) onto the *general-knowledge* list. For use in question- answering, the challenge is then to build routines that can dig up such a formula from *general-knowledge* and answer a question with it. (Note: it might not be optimal to use an alternative representation like (hate ME snake), because then `snake' is being treated as a (constant) TERM, i.e., given how first-order logic interprets arguments of predicates, it must denote some particular object. So then in order to say that "Slithy is a snake" you couldn't use (snake Slithy), which treats `snake' as a predicate. But a possible option is to use (isa Slithy snake), where `isa' is a predicate that relates an ordinary thing to a concept.) Another possibility is the idea of having the agent "comment" spontaneously on what it is doing and thinking. This could be incorporated, in part, by "attaching" functions for producing comments to particular planned (or just- accomplished) actions (as traceable from *curr-state*). For instance, if the immediately planned action is (eat ME banana3), then the details of the action structure and resultant state-node for that action will show that the action itself has a positive value (say 2), and further, the resulting state is more positive one than the current state in its `local-value', because of the change from (hungry ME) to (not (hungry ME)) (i.e., deletion of (hungry ME)). This is a little bit tricky, but quite possible to extract, and could lead to an output "I will eat banana3 because eating is a pleasure and I am hungry". Genuine long-term planning would apparently require rather extensive work to implement. However, the current approach, based on forward search through applicable actions at each state reached or predicted, already allows for goal-oriented behavior in a limited, implicit way. For example, if the forward search goes to depth 3, then the agent will quite possibly give up an immediate reward for a bigger one 2 or 3 time-steps hence, simply because the net worth of the plan with later gratification seems higher than the one with immediate gratification. Some known shortcomings ======================= @ The forward chaining used in the planning does not at present recognize that a state that has been reached is identical to one that has already been reached on another branch of the search tree. Collapsing identical states would be a major improvement; for instance, in the 3-disk Towers- of-Hanoi puzzle, there are only 27 distinct states; but a "blind" forward search running for 7 steps (the minimum needed) would generate over 2000 states in solving the puzzle (and in all likelihood, wouldn't find the solution). @ Actions shouldn't really be assumed to have fully predictable effects -- sometimes we just "try and see what happens". Accordingly a major revision is planned, for updating the world somewhat independently of how ME *thinks* it will change. [Implemented preliminarily in 2008] Current Global Parameters/Variables: ==================================== *roadmap-knowledge* : see below; *general-knowledge* : see below; *occluded-predicates* : a list of predicates such as `is_hungry', `is_hidden_in', `knows-whether', etc., whose truth for particular subjects OTHER THAN ME is not immediately apparent to ME, even if the subjects are at the same location as ME. This is in contrast with predicates `is_at', `sasquatch' or `has' (let's assume); *operators* : the list of names of user-defined operators; the user is responsible for providing a value to *operators*; *here* : current location of ME; *now* : current time (in number of steps taken) *curr-state* : the state-node for the current state; *history* : facts about what actions were done by ME when (in anti-chronological order); *plan* : the best plan as most recently produced by `chain-forward'; *states* : the series of states, starting in the state that was given to `chain-forward', generated by *plan* def-roadmap points roads ======================== Create a graph-like "roadmap", consisting of points (nodes) and connections (edges) beween pairs of points. The connections are labeled, where we think of these labels as road names; at most 2 edges impinging on a node may have any particular name. (Having 2 edges with the same name at a node means that we can follow a road through an "intersection" -- or, if these are the only 2 edges -- past a "point of interest", usually one where some object is located.) The corresponding facts about points, and about points being on particular roads, is stored as knowledge in the global parameter *roadmap-knowledge*, using the 1-place predicate `point' and the 2-place predicate `is_on' (see example below). points: a list of distinct node names, such as Point1, Point2, Cross-roads1, Dead-end3, etc.; roads: a list of lists, each beginning with a road name, followed by a sequence of points that this road reaches; a road must not reach any point twice, because we want "taking road x from point y to point z" to correspond to a unique path; theoretically, 'points' may include points not reached by any road, though it's unclear if any interesting use can be made of this; A graph structure is created in which `next' properties are attached to points, where the value of the property is a list of (road-name adjacent-point) pairs. Example of creating roadmap (outputs are indented): ~~~~~~~~~~~~~~~~~~~~~~~~~~~ (def-roadmap '(a b c d e) '((r1 a b c d) (r2 b d))) ### ISOLATED POINTS: (E) NIL (get 'b 'next) ((r1 a) (r1 c) (r2 d)) *roadmap-knowledge* ((POINT E) (IS_ON A R1) (POINT A) (IS_ON B R1) (IS_ON B R1) (IS_ON B R2) (POINT B) (IS_ON C R1) (IS_ON C R1) (POINT C) (IS_ON D R1) (IS_ON D R2) (POINT D) (ROAD R2) (ROAD R1)) def-object obj-type properties ============================== obj-type: an atomic identifier for a type, e.g., 'sasquatch'; properties: a list of abbreviated general properties such as '(is_animate is_furry (has_IQ 50)); This is expanded so as to produce a conditional whose antecedent applies the type predicate to a variable and whose consequent applies the given predicate in each property first to the variable and then to any additional arguments that are given; thus we will get ((sasquatch ?x) => (is_animate ?x)) ((sasquatch ?x) => (is_furry ?x)) ((sasquatch ?x) => (has_IQ ?x 50)) (Note: the originally planned temporal arguments have been omitted. These might still be added, but at this point it seems more convenient to omit them.) The knowledge in this expanded form is added to the value of the global parameter *general-knowledge* (assumed to be available to the Motivated Explorer). Example of defining an object type: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (def-object 'sasquatch '(is_animate is_furry (has_IQ 50))) *general-knowledge* (((SASQUATCH ?X) => (HAS_IQ ?X 50)) ((SASQUATCH ?X) => (IS_FURRY ?X)) ((SASQUATCH ?X) => (IS_ANIMATE ?X))) place-object name obj-type point time associated-things ======================================================= curr-facts propos-attitudes) ============================ In naming an entity (of a specified type) and placing it at some point in the Gridworld (as a `facts' property of the point and of the object), at a specified `time' (an atom), we are supplying three kinds of additional information for it (where these become available to ME as knowledge "packets" if ME is at that point): - things that it currently "has" (e.g., a key or sword or banana); these may be regarded as *possessions* in the case of animate beings, or as contained or attached objects, in the case of inanimate objects such as trees or boxes; for example, a type predication like (key Key3) supplied under this heading means that the named entity has Key3, and that thing is a key; (see below for the representation of these facts); the type facts are placed on the `facts' property of the possessed thing of that type, while the possession fact is associated with the `facts' property of the possessor; - current-state facts about it; e.g., (hungry Grunt), or (likes Grunt Tweety); these will have the given time argument added at the end, and are associated with the `facts' property of `name'; - propositional attitudes such as (knows Grunt (has Robbie Banana)); this will no longer have a time inserted into it as an outer time argument. Another example: (wants Grunt (has Grunt Banana1 Soon1)); it is even possible to have nested knowledge facts or goal facts such as (knows Grunt (knows Robbie (want Grunt (has Grunt Banana1)))), i.e., Grunt knows that Robbie knows that Grunt wants to have the banana; but such complex facts would more likely be produced by inference than by manual input. Again these facts are associated with the `facts' property of `name'. Example of placing an object: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (place-object 'Grunt 'sasquatch 'b 'Now1 '((banana Banana1) (key Key4)) '((hungry Grunt) (likes Grunt Tweety)) '((knows Grunt (has ME Banana2 Now1)))) ; We embed the `get' in a `format' statement because the normal ' Lisp printout routines may not print out a lengthy output ; completely, termination after a few lines with "...". (format t "~%~a" (get 'Grunt 'facts)) ((KNOWS GRUNT (HAS ME BANANA2 NOW1) NOW1) (LIKES GRUNT TWEETY NOW1) (HUNGRY GRUNT NOW1) (HAS GRUNT KEY4 NOW1) (HAS GRUNT BANANA1 NOW1) (IS_AT GRUNT B NOW1) (SASQUATCH GRUNT)) NIL (format t "~%~a" (get 'Key4 'facts)) ((KEY KEY4)) NIL (format t "~%~a" (get 'Banana2 'facts)) NIL NIL (format t "~%~a" (get 'Banana1 'facts)) ((BANANA BANANA1)) NIL all-bindings-of-goals-to-facts goals facts ========================================== Find all unifiers of the variables occurring in goals (a set of +ve & -ve literals, possibly containing variables) obtainable by matching the goals to the facts (a set of +ve ground literals); Unifiers are lists of dotted pairs, where the car of each dotted pair is a variable starting with a question mark (e.g., ?x, ?y, ...) and the cdr is the corresponding binding. Example: ((?x . a) (?y . me) (?z crossroads3)). The function returns a list of such bindings. make-op {:name x} {:pars y} {:preconds z} {:effects u} ======================================================= {:time-required v} {:value w} ============================= This is the `make'-function produced by a `defstruct op' definition. Create an operator. A good way to use this is, for example, (setq eat (make-op :name 'eat :pars '(?x ?y) :preconds ...)); i.e., assign the resulting structure to the same name as you use internally in the `name' field of the structure (just for conceptual simplicity). All the corresponding access functions are available, as usual. E.g., we get the name as (op-name str), the pars as (op-pars str), etc., where `str' is assumed to be the value resulting from the make-op. y is a list of parameters (variables), e.g., '(?x ?y); z is a list of preconditions, e.g., '((loc_at ?x ?y) (hungry ?x) ...); u is a list of effects, e.g., '((not (loc_at ?x ?y)) (satiated ?x)...); v is a numerical time estimate, but this is not currently useable; w is the inherent value (reward) of the action, e.g., 2; (expressions involving user-supplied lisp functions, and containing some of the parameters, are allowed, but no attempt has been made yet to do anything more that simplify and if possible evaluate these. We generally refer to operator instances -- i.e., op-structures in which the variables have been instantiated with ground terms (variable-free terms, usually constants) -- as "actions" (or sometimes, for emphasis "action instances"). Note that the same data type is used for operators and their instances (actions). make-state-node {:name s} {:wffs x} {:children y} {:operators z} =============================================================== {:parent u} {:local-value v} {:forward-value w} =============================================== This is the `make'-function produced by a `defstruct state-node' definition. Create a state node. For example, the initial state in a simple blocks world might be created by (setq init (make-state-node :name 'init :wffs '((on a b) (on b table) (on c table) (clear a) (clear c) (clear table)) :parent nil :local-value 0 :forward-value 2 )) x is a list of positive ground literals such as ((monkey Cheech) (is_on Cheech Tree5) (is_at ME Crossroads7) ...); y is a list of (action-name . state-node-name) dotted pairs, such as ((put91 . state-node34) (put86 . state-node463) ...), where each of these pairs names an action that can be taken in the state at hand, and the resulting state (given as the name of another state node). If we `eval' one of the action- names, we get the corresponding op-structure, and if we `eval' one of the state node names, we get the corresponding state-node structure. z is a list of the names of the operators that were used so far in generating children of this state-node; more might yet be added, generating further children; u is an (action-name . state-node-name) dotted pair, supplying the action that generated the present state, by application of the action in the given in the prior state named by the state-node-name. For the initial state this is nil. v is the inherent value of this state, e.g., 2 w is the value of the seemingly best continuation from this state (where a continuation is a sequence of actions and the corresponding states). chain-forward state-node-name search-beams ========================================== Chain forward from the given state (set of ground atoms), conducting a beam search using the operators and beam widths specified in `search-beams', and return the forest of plans, attached to `state-node' with the best plan first (i.e., following leftmost branches in the leftmost tree). The idea is to call this program, and then actually execute the first step of the best plan, and then iterate. If we stick to the same beam-width after executing the first step, and the beam- widths for successive steps are decreasing, then after each step the forward search just adds some more branches to the plan-tree, rather than starting from scratch. state-node-name: the name of a state node, from which we are to chain forward (in general, adding to children that are already present); search-beams: a list ((n_1 . ops_1) ... (n_k . ops_k)), where the n_i are numerical upper bounds on the number of distinct successor actions to be searched further from, when adding the ith step of any plan obtained in the forward-chaining, and each ops_i is a list of names of operators to be considered (in addition to ones that may have been considered in a previous iteration) when adding possible ith steps to any plan. initialize-state -- a top-level function with no arguments ========================================================== This sets *curr-state* to a state-node, using `make-state-node'. Most importantly, it sets the `wffs' field of that state-node so as to cover the *roadmap-knowledge* (or, on second thought, perhaps just facts about nearby roads/points?), plus the "non-occluded" facts (that should be evident to the ME agent) about entities located at *here* (the point at which the ME agent has been placed by the user), plus expansions of those facts obtained by the implicative formulas in *general-knowledge*. The `local-value' of the initial state is set to 0 -- this is just an arbitrary reference value, and the `forward-value' is set by default to, say, 2 (larger values would mean greater "optimism about what the future may bring"). go! -- a top-level function with no arguments ============================================ This function chains forward from the *curr-state*, using some fixed (or user-tweaked) search beam; it reports the seemingly best plan (*plan*) and corresponding state sequence (*states*); then it executes the first step of that best plan, adds the action type paired with the value of *now* to *history* (e.g., it might add ((eat ME Banana3) . 7) to the *history* list), updates *now*, *curr-state*, *plan* and *states*, and reports the contents (as a set of wffs) of the new current state. (This current state will already have been partially anticipated in *states*; but the assumption is that some facts associated with objects at a particular point won't become known to the agent till it gets to that point, and so the new state will in general be richer in facts that the anticipated state.) USER-SUPPLIED FUNCTIONS ======================= The infrastructure contains simple versions of the following functions (for a particular, simple Gridworld domain), so you should load your versions AFTER the main infrastructure programs have been loaded. (Then the existing definitions will be overridden by yours.) state-value wffs additions deletions prior-local-value ====================================================== For a given set of wffs describing a state, and the given additions to and deletions from that state (again, given as sets of wffs), compute the resulting state value, given that the value corresponding to `wffs' is `prior-local-value'. expected-rewards wffs ===================== This is currently a stub, giving output 2. It is intended to be a function that estimates the "net future rewards" that can be obtained, starting from the state described by the wffs. EXAMPLES ======== See the eg-...lisp files for example worlds. For instance, in `eg-eating-world2.lisp'a roadmap with a single point is defined, ME and other objects are placed at that point, operators (and *operators*) are defined, and then (initialize-state) and (go!) are used to get the ball rolling. -=-=-=-=-=-=-=-=-=-=- In the following two examples, if you first load the infrastructure code, and then the remaining definitions and setq's, executing the subsequently indicated chain-forward command will produce a tree of actions and states, and you can see the "best" sequence of actions, and corresponding state sequence, by writing *plan* and *states*. ;;;;;;;;;;;;;;;;;;;;;;;;; ;; SIMPLE BLOCKS WORLD ;; ;;;;;;;;;;;;;;;;;;;;;;;;; (load "infrastructure.lisp") (setq put (make-op :name 'put :pars '(?x ?y ?z) :preconds '((on ?x ?y) (clear ?x) (clear ?z)) :effects '((on ?x ?z) (not (on ?x ?y)) (clear table) (clear ?y) (not (clear ?z)) ) :value 2 )) (setq init (make-state-node :name 'init :wffs '((on a b) (on b table) (on c table) (clear a) (clear c) (clear table)) :parent nil :local-value 0 :forward-value 2 )) (defun state-value (wffs additions deletions prior-local-value) ;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ; Allocate +ve points for addition of desirable properties, and ; subtract away that number of points for deletions of those ; properties; analogously for addition of undesirable properties; ; the additions and subtractions are made using 'prior-local-value' ; as starting value; ; ; As a way of implying that the "preferred" situation is one where ; block a is on b, b is on c, and c is on the table, we assign ; unit values to any one of these when they become true, and -1 ; when they become false. Also, we express a preference for ; objects bein clear, rather than having somethin on them. ; this will cause a general tendency to unstack initial stacks, ; and this often makes it easier to build the structures we really ; want. (However, this is definitely not adequate for solving ; complicated blocks world problems.) (let ((local-value prior-local-value) incr) (dolist (wff additions) (if (equal wff '(on a b)) (incf local-value 1)) (if (equal wff '(on b c)) (incf local-value 1)) (if (equal wff '(on c table)) (incf local-value 1)) (if (eq (car wff) 'clear) (incf local-value 1)) ) (dolist (wff deletions) (if (equal wff '(on a b)) (incf local-value -1)) (if (equal wff '(on b c)) (incf local-value -1)) (if (equal wff '(on c table)) (incf local-value -1)) (if (eq (car wff) 'clear) (incf local-value -1)) ) local-value )); end of state-value ; NOW WE CAN TRY THE FOLLOWING (or use '(go!) for chaining forward): (chain-forward 'init '((3 put) (3 put) (3 put))) ; Thus we're allowing the best 3 successor actions to be generated ; at each level of the forward search. ; Result: (((PUT A B TABLE) . 8) ((PUT A B C) . 7) ((PUT C TABLE A) . 6)) ; After running this, writing *plan* and *states* will give the ; seemingly best plan generated by the forward search, and the ; corresponding sequence of states (provided as lists of wffs): *plan* ((PUT A B TABLE) (PUT B TABLE C) (PUT A TABLE B)) *states* (((ON A B) (ON B TABLE) (ON C TABLE) (CLEAR A) (CLEAR C) (CLEAR TABLE)) ((CLEAR B) (ON A TABLE) (CLEAR TABLE) (CLEAR C) (CLEAR A) (ON C TABLE) (ON B TABLE)) ((ON B C) (ON C TABLE) (CLEAR A) (CLEAR TABLE) (ON A TABLE) (CLEAR B)) ((ON A B) (CLEAR TABLE) (CLEAR A) (ON C TABLE) (ON B C))) ;;;;;;;;;;;;;;;;;;;;;;;;; ;; SIMPLE EATING WORLD ;; ;;;;;;;;;;;;;;;;;;;;;;;;; (setq eat (make-op :name 'eat :pars '(?x ?y) :preconds '((loc_at ?x ?y) (edible ?y) (hungry ?x)) :effects '((not (loc_at ?x ?y)) (not (edible ?y)) (not (hungry ?x)) ) :value 2 )) (setq sleep (make-op :name 'sleep :pars '() :preconds '((not (hungry me))) :effects '((hungry me)) :value 2 )) (setq init (make-state-node :name 'init :wffs '((loc_at me a) (loc_at me b) (loc_at me c) (edible a) (edible b) (hungry me) ) :parent nil :local-value 0 :forward-value 2 )) (defun state-value (wffs additions deletions prior-local-value) ;~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ; Just as an example, let's suppose the agent ME likes knowing ; things, likes being liked, and likes having things, and ; dislikes being hungry. So we reward addition of wffs of form ; (know-whether ME ...), (know-that ME ...), (likes ... ME), ; (has ME ...); and we reward removal of (hungry ME). Also ; we punish (correspondingly) removal of (likes ... ME) and ; (has ME ...), and addition of (hungry ME). ; (let ((local-value prior-local-value) pred incr) (dolist (wff additions) (when (listp wff) (setq pred (car wff)) (setq incr (case pred ((know-whether know-that has) (if (eq (second wff) 'ME) 1 0) ) (likes (if (eq (third wff) 'ME) 1 0) ) (hungry (if (eq (second wff) 'ME) -1 0) ) (t 0) )) (incf local-value incr) )) (dolist (wff deletions) (when (listp wff) (setq pred (car wff)) (setq incr (case pred (likes (if (eq (third wff) 'ME) -1 0) ) (hungry (if (eq (second wff) 'ME) 1 0) ) (t 0) )) (incf local-value incr) )) local-value )); end of state-value ; NOW WE CAN TRY: (chain-forward 'init '((2 eat sleep) (2 eat sleep) (2 eat sleep) (2 eat sleep))) ((EAT ME A) . 12) ((EAT ME B) . 12)) ; Again, *plan* and *states* will show the essential results. *plan* (EAT ME A) (SLEEP) (EAT ME B) (SLEEP)) *states* (((LOC_AT ME A) (LOC_AT ME B) (LOC_AT ME C) (EDIBLE A) (EDIBLE B) (HUNGRY ME)) ((EDIBLE B) (LOC_AT ME C) (LOC_AT ME B)) ((HUNGRY ME) (LOC_AT ME B) (LOC_AT ME C) (EDIBLE B)) ((LOC_AT ME C)) ((HUNGRY ME) (LOC_AT ME C)))