NEW FUNCTIONALITIES FOR 2008 updated Apr 20/08 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ N.B.: FOR THE REVISED/EXTENDED GRIDWORLD CODE DISCUSSED HERE, see "new-gridworld-code-2008" in this directory. This is an evolving document describing the new functionalities being progressively added to the gridworld infrastructure (both for supporting the CSC 290A/08 course project, and the research beyond that). The four main functionalities under development are 1. Allowing COMPUTABLE FUNCTIONS AND PREDICATES in the specification of preconditions and effects of action operators; e.g., we could include the assertions (tired_to_degree ?t), (<= ?t 0.5) as preconditions of a (walk ?x ?y ?r ?t) action (meaning "walk from ?x to ?y on road ?r, starting with a degree of fatigue ?t), and include (tired_to_degree (+ ?t .5)), (not (tired_to_degree ?t)) as effects, where "<=" is recognized as a computable predicate and "+" is recognized as a computable function. A fancier version of the effects of walking on level of fatigue might be (tired_to_degree (+ ?t (* 0.1 (distance_in_miles? ?x ?y ?r)))), (not (tired_to_degree ?t)), i.e., the level of fatigue grows by 0.1 for every mile walked. Here "+", "*", and "distance_in_miles?" would be recognized as computable functions. In general, predicate and function names ending in "?" are recognized as computable, and also arithmetic predicates < <=, =, >=, > and aithmetic functions +, -, *, / are recognized as computable. Naturally, for predicate/function names ending in "?", it is up to the user to supply their Lisp definitions; e.g., the body of (defun distance_in_miles? (x y z) ), where x, y are names of points in the Gridworld and z is the name of a road connecting them, might look at roadmap-knowledge to find out what that distance is (which presupposes that this numerical information has been made part of the roadmap knowledge). The TIME REQUIRED for an action instance and its inherent VALUE also allow for computable functions. (This is all implemented.) 2. Separating conceptual operators (the agent's understanding of action in the world) from actual ones, and clearly separating the agent's beliefs from the facts of the world. The code now allows for operators to be defined in pairs, a conceptual operator (as understood by the agent, and used for chaining forward) and an actual operator (for correctly updating the world). We use names like 'walk' and 'walk.actual', i.e., the actual version has extension '.actual'. A constraint is that we assume the agent's model to be correct as far as preconditions are concerned, i.e., the parameters are the same for both, and if the agent believes the preconditions of an operator hold for particular values of the parameters in the current state, then indeed they do. But the effects could in principle be different. The separation of beliefs from world facts is discussed in (3) below, since it also bears on the issue of exogenous change. It's not obligatory to define '.actual' versions, because if none are provided, the program simply assumed that the actual versions are the same as the conceptual ones. 3. Allowing EXOGENOUS CHANGE -- i.e., changes in Gridworld that occur independently of the agent's actions. This requires a clear distinction between what is true in the world and what the agent knows (or believes). In partial preparation for this, some "repairs" have been implemented to the way facts about the world, and the agent's knowledge, are handled. Originally, information about entities at a given point in the Gridworld was stored as a 'facts' property of that point, but this information was not updated when the agent carried out an action. For example, if there was food at a certain location, this fact was be listed in the facts for that location. If the agent came to this location and ate up the food, the *current state* knowledge of the agent (stored in the 'wffs' field of the current state) were correspondingly updated -- but the facts for the location continued to say that there is food present. So if the agent came back to that location later on, then -- because it assimilated any facts stored at a location that were not present in the wffs in its current state -- it picked up the (old) fact that there was food at the location, and hence ended up with a mistaken belief. So one repair that has been made is to make a clear distinction between the actual facts of the world, and the agent's beliefs. The facts of the world (other than *general-knowledge*) are now stored in *world-facts*, rather than at particular locations. The 'wffs' field of the current-state node represent the agent's beliefs. When the agent has executed an action, it updates its belief state by "noticing" what has changed at its current locale. In particular, it notices when any of the ground predications that it believes and that in principle should be locally obsrvable in fact are *not* locally observable, and deletes these from its beliefs; and it notices when there are locally observable facts that are not in its belief set, and adds these to its beliefs. The notion of "local observability" is a bit tricky: the locally observable facts are typically ones about entities x apprearing in subject position (first argument position) of a predication in *world-facts*, where there is also an (is_at x *here*) predication in *world-facts* (*here* being the location of the agent). However, note that some objects might implicitly "co-move" with others. For example, if the agent picks up an apple and then walks to another place, the apple will also be at that other place. If such implicit motion is part of the model, then the user needs to specify two lists, namely *left-comoving-preds* and *right-comoving-preds*. An example of the former might be "is_in" (i.e., if x is_in y, then the "left" object x moves wherever the "right" object y moves); an example of the latter might be "has" (i.e., if x has y, then the "right" object y moves wherever the "left" object x moves. Objects that co-move with ones already known to be at the current location are computed iteratively, and the properties of these objects -- if not occluded -- are regarded as noticable to the agent. Another problem that arises is that of maintaining inferred facts, i.e., variable facts ("fluent facts") that aren't directly modified by action effects, but rather are inferred from them, using general knowledge. For example, we might possibly make inferences that if the agent is at a place, then it is "near" each of the other objects at that place. How do we handle the fact that these inferred properties can become false when another action is carried out (e.g., the agent moves away from that place again)? The way it is done here is that a subset of *world-facts* is maintained, called *protected-facts*. This does not include any inferred facts, only permanent facts and variable ones that were explicitly asserted as action effects. In the current version, for simplicity, it contains no inferred facts, not even static (unchangable) ones. When an action is carried out in the world, the deletions and additions are at first made only to the *protected-facts*. Then the inference procedure is run so as the re-establish inferred facts, and the *protected-facts* together with the inferred ones become the new *world-facts*. Note that when the agent "observes" the local world facts, it may thus also notice inferred facts, and add them to its beliefs, without having to perform inference. However, when it develops a new plan by lookahead, it should ideally elaborate the future states it hypothesizes by inference, and currently it does not do that. So its "view of the future" may be quite incomplete. 4. Allowing for IGNORANCE AND UNCERTAINTY ABOUT THE EFFECTS OF ACTIONS. We want to make a clear distinction, ultimately, between the actual effects of actions and what the agent knows or believes about those effects. For example, Suppose the agent has a 'drink' action that he can take when he is thirsty and a potable beverage is at hand. It may be that if the beverage is hard liquor, he will be very tired upon drinking it -- even though that's not a consequence of drinking that is known to him (as specified by the drinking effects). On the other hand, it may also be that the effects of that action in the agent's model of it *do* specify an increase in fatigue -- but only probabilistically, because the agent (let's assume) can't tell whether a beverage is intoxicating or innocuous. But of course the agent's model in general may be distinct from how an action in fact works -- e.g., the real drinking action may have perfectly predictable effects, if we assume that it has an extra precondition concerning the alcoholic content of the beverage, and a deterministic effect dependent on this precondition. (That's not to say that an action can't have uncertain outcomes even in reality. For example, rolling a die in a gambling situation has an uncertain outcome, and the best we can hope from, in a model of the action, is that the likelihood that the model assigns to various outcomes -- if it's capable of doing that sort of thing -- will match the actual outcome frequencies.) This is a difficult and ambitious extension, because it involves uncertain inference -- something not fully understood.