World
It's important that machine is aware of past states as well as possible futures of the microworld. In Situation Calculus the microworld is thought of as a state machine. Every time an action is performed by an object that brings any change to the state of the microworld, the time variable is moved forward by one unit.
The initial state of the microworld is considered to be at time t = 0.
After the first action, the microworld will move to time t = 1. Then the machine is aware of the state of the microworld in both times t = 0 and t = 1. Queries can specify a particular time. If the query refers to a time that has not been reached yet, it is implied that we are querying for all possible values at such time in the future.
In our example we are currently at time t = 1. Now if we query for the value of a particular property of a particular object at time t = 3, we are querying for all possible values after any two valid actions have been performed. The result of such query is a set of possible values.
The state of a microworld at any given point (time) is called a world. A world is a snapshot of all the objects in the microworld at some specific point in time.
----------------- | | | | G | 4 ----------------- | R | | | X | 3 ----------------- | . | | | X | 2 ----------------- | . | | X | X | 1 ----------------- A B C D
Assuming the current time of the Maze microworld is 2, we can query the position of the robot at some point of time in the past. Here the position property of Robot object called MyRobot? is obtained at a world with time stamp of 1:
> time. 2 > Robby position. A3 > at time 1 Robby position. A2
Still assuming we're currently at time 3, we can query a property of an object in some time in the future?. In that case, the interpreter looks at all possible actions doable by that object to produce a set of all possible world values that this property may have at the given future time:
> at time 3 Robby position.
Possible World values (1 time unit from now):
{ B3, A4 }
A world is a particular state of the micro-world, holding the property values for objects at some instance in time. Possible Worlds provides an elegant, incredibly simplifying, life changing methodology for:
- There is absolutely no need for backtracking, undoing. Possible worlds are sprouted by the parent world and they all coexist. Once a desired world is found, the micro-world is "magically" moved to that world by a simple currentWorld pointer update from the old world to that desired world. Going back to any past states is equally as easy as changing this pointer to some past world.
- Worlds are time stamped and with every change, the micro-world moves to a new world. Thus at any point of time, the state of an object at any past time can be queried. Only changes relative to the current world would go into the child world (world at time
t+1), thus all lookups are dynamically scoped. Each world has a pointer to parent, as well as any number of children. - At any point of time, the possible states of some object at some future time can be deduced. This is done by getting a list of all possible changes that can occur to the objects (actions or methods that each object is capable of) with every combination of arguments for those actions, thus generating a set of possible worlds via running those actions each in a new child world.
-----------------
| | | | G | 4 R: Robot position
-----------------
| R | | | X | 3 G: Goal Square
-----------------
| . | | | X | 2 X: Blocked Square
-----------------
| . | | X | X | 1 .: Visited (also Blocked)
-----------------
A B C D
Assuming R is a Robot that is capable of moving one square Up, Down, Left, or Right, provided the target square is not blocked (X marked), nor a previously visited square:
Assuming the current time of the Maze micro-world is 2, we can query the position of the robot at some point of time in the past. Here the position property of a Robots object called Robot is obtained at a world with time stamp of 1:
> time. 2 > Robot position. A3 > at time 1 Robot position. A2
world w0 world w1 world w2
time 0 time 1 time 2
----------- ----------- -----------
| w0: t=0 | | w1: t=1 | | w2: t=2 |
| R @ A1 | | R @ A2 | | R @ A3 |
----------- ----------- -----------
Still assuming we're currently at time 3, we can query a property of an object in some time in the future. In that case, the interpreter looks at all possible actions doable by that object to produce a set of all possible world values that this property may have at the given future time:
> at time 3 Robot position.
Possible World values (1 time unit from now):
{ B3, A4 }
time 3
----------
time 2 / Robot move Up? ---------> | w3a: t=3 |
----------- / ___ Robot move Down? No. | R @ A4 |
| w2: t=2 | /__/ ----------
| R @ A3 | //
----------- -------- Robot move Left? No.
\ ------------
\ Robot move Right? --------> | w3b: t=3 |
| R @ B3 |
------------
Similarly, building the possible worlds tree for even farther time ahead:
> at time 5 Robot position
Possible World values (3 time unit from now):
{ B3, A4 , C4, C2, B1 }
Another advantage of worlds is that since any object properties are static in a given world, all properties and relation lookups can be cached. Also the children of a world (possible worlds of time t + t0) are never calculated twice, since the worlds cache their parent and children worlds.
Moving from parent world to a child, the child world stores the action taken in the causingAction field. This field along with the parent field makes it possible to get the series of actions (solution) in the path from the initial world to the current world.