LTF for Domains

Author: Jeff Dalton

Introduction

LTF is a language that can be used to define domains that can be used with I-Plan, the I-X planner. "LTF" is just a convenient name for the language. It stands for "List TF", where "TF" is Task Formalism, the name of the language that was used to define domains for I-Plan's predecessor, O-Plan. The "List" part is because it has a Lisp-like syntax.

The file syntax for LTF domains uses the (equivalent) file-types "ltf" and "lsp".

LTF can also be used to represent plans as domains. That's discussed separately.

This document is primarily about the syntax, and it does not go into detail about all elements of the language. Instead, the information is given in other documents that use LTF for examples:

We'll start with a "quick reference" for the syntax of the whole langauge (which can be skimmed on first reading), then go into some things further, with examples.

Syntax: Quick Reference

In the syntax definitions below, all bold-face names are literals and other names are syntactic variables. Other bold-face text should also appear literally. All round parens are bold and hence literal. None are optional, nor can extra ones be added without affecting the meaning. Elements of the syntax are grouped using curly brackets instead. "|" separates alternatives. Square brackets also serve to group, but what's within them is optional. A "*" means zero or more repetitions of the element or bracketed group before the *. The repeated items must either begin and end with parens or be separated by white-space (rather than run together). For example,
  {integer | (letter)}*
would match any of the following:
  1
  1 2 3
  (z)12 13 -14876 (q) 77
  1 (a) 2 (b) (c)
  1(a)2(b)(c)

Number, symbol, string, and duration appear as terminal symbols in the grammer and are explained later.

LTF syntax
Domains
domain ::= {header | refinement | object-class | annotations | include}*

header ::= (domain domain-property*)

domain-property ::= (name string)

include ::= (include file-name-or-URL-as-string)
Refinements
refinement ::= (refinement name pattern clause*)

name ::= symbol | string

pattern ::= (item*)

item ::= number | symbol | string | pattern | variable

variable ::= ?symbol

clause ::= (variables variable-declaration*)
        |  (issues issue*)
        |  (nodes node*)
        |  (orderings ordering*)
        |  (constraints constraint*)
        |  annotations

Refinement clauses should appear at most once in a refinement.

variable-declaration = variable

issue ::= (issue pattern)

node ::= (node-id pattern)
node-id ::= number | symbol | string

ordering ::= ({node-end-ref | (node-end-ref*)}*)

node-end-ref ::= node-ref | b/node-ref | e/node-ref
node-ref ::= node-id | self

References to self are not currently supported, except in duration constraints.

constraint ::= (world-state condition pattern = value)
            |  (world-state effect pattern = value)
            |  (compute [multiple-answer] pattern = value)
            |  (advice expansion-refinement verb (symbol*))
            |  (temporal duration self = min-duration .. max-duration)
            |  (resource operation pattern = value)
            |  other-constraint

other-constraint ::= (type subtype pattern = value)

value ::= item
verb, operation, type, subtype ::= symbol
min-duration, max-duration ::= duration
Object classes
object-class ::= (object-class class-name supers object-property*)

supers = (class-name*)

object-property ::= (property-name [class-name] [:syntax value-syntax])

class-name ::= symbol | string
property-name ::= symbol
value-syntax ::= number | symbol | string | list | object | default
Annotations
annotations :: = (annotations annotation*)
annotation ::= (aKey = aValue)

aKey, aValue ::= item | map

map ::= (Map map-entry*)
map-entry ::= (aKey = aValue)

The word map must be written "Map".

Background

<I-N-C-A>

The underlying ontology in I-X is called <I-N-C-A>; it stands for Issues - Nodes - Constraints - Annotations.

<I-N-C-A> represents something that is being modelled or produced as a set of constraints. Although we will often use "constraint" only for the "C" part, all <I-N-C-A> elements can be considered constraints. Issues are sometimes called "implied constraints" or "flaws" that need to be addressed. Nodes can be seen as include-node constraints, where the nodes represent the principal entities or components to model or include. Even annotations can imply constraints.

The "C" constraints can usefully be divided into "critical constraints" and everything else: "auxiliary constraints". Critical constraints are also sometimes called "cross constraints"; they're a bit like a common language that can be used to express many of the requirements imposed by different types of constraints.

The nodes and constraint types can be different in different application areas (as can which constraints are considered critical). For example, if <I-N-C-A> is used to describe buildings, the nodes might be structural elements such as walls, floors, doors and windows, and there could be constraints that express spatial relationships.

In the <I-N-C-A> view of plans, a plan is a set of constraints on possible behaviour in the doman being modelled. In a plan, the nodes represent actions or activities, and the critical constraints are temporal ordering constraints and variable constraints. The variable constraints are essentially about which objects to use, with "object" taken very abstractly. For example, if a block is going to be painted some colour, by an activity paint ?block ?colour, where ?block and ?colour are variables, the available blocks and the colours would be objects.

The critical constraints are used to resolve conflicts between activities, due to other constraints. For example, resource-use constraints might mean that two activities would conflict if they tried to use the same resource at the same time; and the conflict might be avoided either by saying one activity must finish before the other can start, or by saying the activities must use different resources (different objects).

An example

At this point, it's useful to have an example. The example is unrealistic in many ways as a model of the problem domain, but it illustrates the most-used features of LTF. Here is the first refinement:

(refinement get-up-and-go (get-to-work)
  (variables ?paper)
  (nodes
    (1 (wake-up))
    (2 (shower))
    (3 (get-dressed))
    (4 (eat-breakfast))
    (5 (read-paper ?paper))
    (6 (travel home work)))
  (orderings
    (1 (2 3 4 5) 6)
    (2 3))
  (constraints
    (world-state condition (have-paper ?paper) = true)))

Here are two more refinements. They could be used to refine the (travel home work) acticity introduced by get-up-and-go, because they have patterns that would match it.

(refinement walk (travel ?from ?to)
  (variables ?from ?to)
  (constraints
    (world-state condition (weather) = sunny)
    (world-state condition (location me) = ?from)
    (world-state effect (location me) = ?to)
    (temporal duration self = PT20M .. PT30M)))

(refinement take-bus (travel ?from ?to)
  (variables ?from ?to)
  (constraints
    (world-state condition (location me) = ?from)
    (world-state effect (location me) = ?to)
    (temporal duration self = PT15M .. PT25M)))

Each refinement represents a way for "me" to travel and, although they treat where I'm traveling from and to as variables, for illustrative purposes, they don't make sense for arbitrary journeys; instead they're meant for the journey from home to work. Walking requires sunny weather and takes between 20 and 30 minutes; the bus can be used in any weather and takes between 15 and 25 minutes.

Some details

Comments

A comment begins with a semicolon and continues to the end of the line. Comments are discarded when the domain description is parsed. An annotation can be used to attach something more permanently.

Symbols and strings

Symbols are the usual way to represent words, names, and operators. A symbol is written as a sequence of characters, often just letters, or letters and digits, that (a) is not a number, (b) does not contain whitespace, and (c) does not contain any significant punctuation characters such as double quotes or round parentheses. To include such characters in a symbol, the entire symbol is written between vertical bars. Inside the "|...|" notation, a vertical bar can be included by putting a backslash in front of it. Such symbols should usually be avoided but are sometimes convenient. Case is retained in all symbols. Examples:

   refinement
   world-state
   +
   <=
   /=
   /doc/notes
   UNESCO-Visitors
   |an unusual symbol that even includes a \| within it|

Note that some sequences of characters that you might not normally think of as a single item are treated as one symbol. For example, a+b>=c is a single symbol. That's a consequence of (a) allowing characters such as '+', '>' and '=' to be combined in symbols so that operators such as >= can be single symbols, and (b) allowing them to be mixed with other characters rather than having special rules.

It is sometimes more convenient to use strings. A string is written as a sequence of characters between double-quote marks. A \ at the end of a line includes the newline sequence in the string and allows the string to continue on the next line. Within a string, the escape sequences such as \t, \n, \r are converted to single characters. Backslash and double-quote can also be escaped in that way. Examples:

   "This is a sring."
   "This is a string that \"quotes\" a string."

Variables

Variables are symbols that begin with "?". They should not contain any special characters, and the "|...|" notation should not be used.

All variables used in a refinement should be delcared in the refinement's variables clause.

Examples:

   ?x
   ?location
   ?vehicle

Numbers

Numbers are signed and can be integers (longs) or double-precision floating point. In floating point numbers, the exponent character is 'e' or 'E'; and 'd', 'D', 'f', or 'F' may be placed on the end. Examples:

   12
   -1024
   1d
   1.14e20

Orderings

Here's a version of the syntax that's better at suggesting the semantics:

Orderings in a refinement
  clause ::= (orderings ordering*)

  ordering ::= sequential-ordering

  sequential-ordering ::= (node-end-group*)

  node-end-group ::= node-end-ref | (node-end-ref*)

  node-end-ref ::= node-ref | end-ref

  end-ref ::= b/node-ref | e/node-ref

  node-ref ::= node-id | self

Durations

Durations are written in a subset of the ISO 8601 notation used for the XML Schema duration datatype.

The full duration datatype is difficult to work with, because the number of days in a month varies. Hence durations aren't even totally ordered. However, in the 1.1 version of the Schema definition, there are two derived types that are each totally ordered: yearMonthDuration and dayTimeDuration.

Our durations are dayTimeDurations. The full duration syntax is PnYnMnDTnHnMnS, optionally preceded by a minus sign, where each n is a possibly different unsigned number, 'Y', 'M', 'D', 'H', 'M, and 'S' stand for years, months, days, hours, minutes, and seconds respectively, 'P' stands for "period", and 'T' separates the year-month-day date portion from the time portion. 'P' must always be present, and 'T' must be present if any hours, minutes, or seconds are specified. The number-letter combinations are all optional, so long as at least one is specified. All of the numbers must have no decimal point except for the number of seconds. None of the numbers is restricted in range.

Since LTF supports only dayTimeDurations, year and month values must not be given.

Examples: PT0.001S = 1 millisecond and P10DT23H59.012S = 10 days, 23 hours, 59 seconds, and 12 milliseconds.


Jeff Dalton <J.Dalton@ed.ac.uk>