Introduction to TAL

TAL is a non-monotonic temporal logic for reasoning about action and change. It is used for reasoning about how the state of a formally defined world changes over time.

This page will explain:

Features and fluents -- properties of a world
The inertia assumption -- nothing changes except as the result of an action
Action scenario descriptions -- descriptions of a world (and their syntax)
Interpretations -- possible assignments of values to fluents
Models -- interpretations where all formulas are true

Other pages explain:

The structure of TAL logic formulas
How to use VTAL

Features and fluents

A world is defined in terms of features and fluents.

A feature is a property of the world. For example, "the color of my car" can be a feature; so can "the door being closed" and "the place where I am now".

Each feature has a value domain -- a set of values that the feature can have. For example, the feature "the color of my car" may take a value from the domain {red, blue, black}, if we want to model a world where all cars must be of those colors -- or we may use a domain with thousands of different colors, if we want to model the "real world" more accurately. The feature "the door being closed" would take a value from the domain {true, false}, since the door is either closed or not closed.

A feature is a static property -- a state variable. However, the state of the world changes over time. A fluent is a function from time to the value domain of the corresponding feature. For example, there can be a fluent that given a timepoint returns the color of my car at that given timepoint. My car may be red at time 0 so that ColorOfMyCar(0) = red; I may choose to repaint it at time 20 so that ColorOfMyCar(20) = black.

The inertia assumption

The entire point of reasoning about the values of fluents at different timepoints is that we don't want to explicitly state the values at all timepoints -- we want to tell the logic about the values at certain timepoints, and then let the logic calculate the values at all other timepoints. For example, I don't want to have to tell the logic that "At time 0, my car is red. At time 1, my car is red. At time 2, my car is red.".

The inertia assumption is the assumption that nothing changes unless we perform an action that changes it.

For example, suppose we know that the car is red at timepoint 0. If we repaint the car blue at time 20 but we never perform any other action that changes the color of the car, we can conclude that the car must have been red at timepoints 0 to 19, and that at timepoint 20 and all timepoints after time 20, the car will be blue.

As another example, if the door is open at timepoint 0, and noone ever closes it, we assume that it stays open and does not suddenly become closed.

Action scenario descriptions

An action scenario description defines a world describes what happens in a certain scenario -- what actions we perform and what observations we make. It contains the following parts (see also below for larger examples):

Definitions of value domains
Definitions of features
Observation statements
Definitions of action symbols
Action law schemas

We will now describe the parts of an action scenario description in more detail; at the same time, we will describe the syntax used for this part of a scenario description in an action scenario description file. There is also a complete grammar for scenario descriptions.

Definitions of value domains

Value domains

As described above, a value domain is a set of values, and it is given a name. A value domain is defined using the syntax

    domain <name1> = { <value1>, <value2>, ..., <valuen> },
           <name2> = { <value1>, <value2>, ..., <valuen> },
           ...,
           <namen> = { <value1>, <value2>, ..., <valuen> },

For example, you could define a domain containing fruit, one containing cars and one containing colors:

domain fruit  = { apple, orange, banana }
domain cars   = { my_car, your_car, this_car, that_car },
       colors = { red, green, blue, cyan, magenta, yellow, black, white }

There is one predefined value domain, boolean, which contains the two values true and false.

Value domains must be defined before they can be used in feature definitions and action symbol definitions.

Features

Each feature is given a name and a value domain; it can also (but does not have to) take values from value domains as parameters. This works like functions in programming languages: A function can (but does not have to) take values of specific types (value domains) as parameters, and always returns a value of a specific type (value domain). Features are defined using the syntax

feature <name> <value domain>

feature <name>(<argument domain 1>, ..., <argument domain n>)
    <value domain>

For example, assume that you have defined a domain car containing cars and a domain colors containing the colors a car can have, and want a feature that is true iff a given car is broken and another feature corresponding to the color of the car:

feature broken(car) boolean
feature color_of_car(car) colors

On the other hand, if you are only reasoning about one car, you may never mention it explicitly. Instead, you could have a feature without arguments:

feature car_is_broken boolean

Assume that you have defined a domain locations containing different places, and that you have defined a domain people containing people. You want to know where the people are. You could do this in one of two ways:

feature place_of(people) location

feature is_at(people, location) boolean

The second way would allow someone to be at several locations, or at no location at all. If this is not what you intended, you may need to use domain constraints to enforce the condition that everyone is always at exactly one place.

Action symbols

An action symbol definition is like a procedure name declaration: It gives us the name of an action that we can perform, but it does not define what the action really does. Like a procedure, an action can take arguments but can not return a value. You must declare an action symbol for each action that you want to define; the action symbol is not implicitly declared when you define it. The syntax for this, with or without arguments, is:

action <symbol>

action <symbol>(<argument domain 1>, ..., <argument domain n>)

depending on whether the action takes arguments or not.

For example, in the broken car example above, you may want an action that breaks a car:

action break(car)

You may want an action that moves someone to a location:

action move(people, location)

Observation statements

An observation statement consists of a logic formula that must be true in all models of the scenario description. For example, you can specify part of the state of the world at time zero:

obs [0] place_of(me) ==  here & place_of(you) ==  there

obs [0] forall v[car] [ !broken(v[car]) ]

You can observe fluents at any timepoint:

obs [20] color_of_car(my_car) == red | color_of_car(your_car) ==  white

At timepoint 20, my car is red or your car is white. At least one of those must be true; it may be the case that your car is black and mine is red, or that mine is black and yours is white, or that mine is red and yours is white, but both cars can't be black.

Action law schemas

An action law schema is like a procedure definition: We define what happens if we call the procedure, but we don't actually call it now. Action law schemas can contain preconditions that must be satisfied for the action to take place; the actual action changes the values of fluents. An action law schema defines the actual meaning of an action symbol:

acs [t1,t2] move(people1, location1) ~>
            [t1] !(place_of(people1) == location1) ->
                     [t1,t2] place_of(people1) := location1

An action is executed during a time interval. The schema above defines what happens when an action is executed during the time interval [t1,t2], where t1 and t2 are temporal variables.

The action that is defined is the move action. It takes two arguments. In the action symbol definition, we used the names of the value domains, people and location. Now, we must use value variables instead; when we actually execute the action, these value variables will be replaced by the actual arguments of the action occurrence statement (to be defined below). Value variables are named domainname, domainname1, domainname2, and so on.

The "~>" symbol consists of a tilde followed by a "larger than" sign, and separates the action symbol with arguments from the actual reassignment formula.

The reassignment formula can be conditional, which it is in this case: We have a precondition (a fixed fluent formula) saying that we don't execute the action if the given person is already in the given location. We only execute the action if at time t1, it is not the case that the place of the person belongs to the set consisting of the location1 argument -- in other words, if the person already where he is supposed to be, we don't move him.

If the condition is true -- the person isn't already at the place we want to move him to -- then during the interval [t1,t2], the feature place_of(people1)gets the new value location1. This is done using the reassignment operator ":=" (colon-equals).

An action law schema can change several fluents using the "&" operator, and can contain alternatives using the "|" operator:

    acs [t1,t2] whatever ~> [t1,t2] something1 :=  true & something2 :=  false |
                                    something1 :=  false & something2 :=  true

Here, both something1 and something2 will get new values. When the action has been executed, either something1 == true & something2 == false or something1 == false & something2 == true.

Action occurrence statements

Action occurrence statements define which actions are executed at which timepoints, and correspond roughly to procedure calls. The syntax is:

    occ [<time1>,<time2>] <action symbol>

    occ [<time1>,<time2>] <action symbol>(<arguments>)

For example, if we want to move me "there" during the time interval [5,7]:

    occ [5,7] move(me, there)

Observation statements

An observation statement contains a logic formula -- which can contain conjunctions, disjunctions, implications and so on -- which must be true. For example: An observation statement consists of a logic formula that must be true in any model of the scenario description. For example, you can specify the state at time zero:

    obs [0] place_of(me) ==  here & place_of(you) ==  there

    obs [0] forall v[car] [ !broken(v[car]) ]

You can use all of the boolean operators defined in the table above:

[20] color_of_car(my_car) == red | color_of_car(your_car) ==  white

Interpretations

An interpretation is an assignment of values to fluents. Each interpretation corresponds to one possible assignment of values to all fluents in the scenario during the entire timeline.

Suppose, for example, that we had this simple scenario:

feature door_is_open boolean
action close_door

obs [0] door_is_open

acs [t1,t2] close_door ~> [t1,t2] door_is_open :=  false

occ [4,5] close_door

In reality, there are always infinitely many interpretations for a scenario, since we consider all timepoints from zero to infinity. However, assuming that we are only interested in timepoints from 0 to 9 -- ten timepoints -- there are 2¹⁰= 1024 possible interpretations for this scenario, since the door_is_open fluent can take on any of two values during ten timepoints. If we had had another fluent with three values, we would have had 6¹⁰= 60466176 possible interpretations of the scenario.

The set of interpretations is independent of the actual logic formulas in the scenario description; it only depends on which features we have.

Models

A model is an interpretation in which all scenario formulas are true.

In the simple example above, we know that the door must be open at timepoint zero (according to the observation) and that it must be closed at timepoint 5 (according to the action law schema and action occurrence statement). The scenario doesn't say anything explicitly about whether the door is closed or not at other timepoints, however; at timepoints 1, 2, 3, 4, 6, 7, 8 and 9, we don't know the value of the fluent. This means that there are 2⁸ = 256 possible models for this scenario.

However, according to the inertia assumption, we don't want fluents to change value unless an action changes the value. This means that since the door was open at time 0, it can't magically close itself later; it must remain open until timepoint 5, when we close it. Then, it must remain closed since we never open it. The models that remain if we take this assumption into account are called the preferred models of the scenario; in this case, there is only one preferred model.

In most of the text, we will use model and preferred model interchangeably.

Examples

This section contains some very small standard examples from the literature. The examples may seem trivial, but many early logics did not produce the intended conclusions from them.

The Yale Shooting Scenario

feature alive boolean

feature loaded boolean

action Load

action Fire

obs [0] alive & !loaded

occ [2,4] Load

occ [5,6] Fire

acs [t1,t2] Load ~> [t1,t2] loaded := T

acs [t1,t2] Fire ~> ([t1] loaded -> [t1,t2] (alive := F & loaded := F))

This scenario consists of a turkey, which is alive at the beginning of the scenario, and a gun, which is not loaded. We load the gun and fire it. The action laws state that loading the gun makes it loaded, and that firing a loaded gun makes the gun unloaded and kills the turkey (but firing an unloaded gun has no effect at all). The intended conclusion is that the turkey is dead at the end of the scenario.

The Stanford Murder Mystery

feature alive boolean
feature loaded boolean
action Fire
obs [0] alive
occ [5,6] Fire
obs [8] !alive
acs [t1,t2] Fire ~> [t1] loaded -> [t1,t2] alive :=  F & loaded := F

This scenario is similar to the previous one. The difference is that we don't say anything about whether the gun is loaded or not at the beginning, we don't load it, and we explicitly observe that the turkey is dead after we have fired the gun. The intended conclusion is that nothing but firing the gun could have killed the turkey; therefore the gun must have been loaded at the beginning of the scenario.