Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members  

XIDDL User's Guide

Modeling in XIDDL

An Overview of XIDDL

XIDDL is an acronym for XML Idea Domain Definition Language, which is an XML encoding of the Idea Domain Definition Language, a "generic" modeling language for simultaneous constraint based planning and execution.

This User's Guide is intended to provide you with an overview of Modeling in XIDDL and the XIDDL Support Tools.

This guide does not cover the following important topics:

Modeling in XIDDL depends on the modeler having some familiarity with the following subjects:

Of these, the first is by far the most important. If you don't know your domain, you end up encoding constraints that, not being part of a well understood system, probably don't make much sense. However, once the domain is will in mind, the modeling and XIDDL support tools start to make sense and are not difficult to use.

A complete model for an Idea Agent will require more than just an XIDDL model. In addition, a Europa based Agent requires an initial state (still true as of 03/02/05) and heuristics for each of the (Europa based) planners. The XIDDL model includes all of the other necessary information, including both the model itself, and the agent topology declaration.

The XIDDL Language

XIDDL is an XML encoding of the Idea Domain Description Language (IDDL). IDDL was in turn based on DDL, the HSTS and Europa Domain Description Language. For an overview of modeling in DDL (which will be very helpful here), see the Europa 1 User's Guide.

The most complete and accurate definition of XIDDL can currently be found in the XIDDL schema.

XIDDL Internal Model Documentation

In order to support internal model documentation about many of the model components, XIDDL supports a <doc/> tag in many places throughout the XIDDL schema.

The <doc/> is always the first (optional) tag in the tag which it documents: 

<define_label_set>
  <doc>
    In this model, all closed loop external entities return either
    "OK" or "Failed".  "OK" indicates success, "Failed" indicates
    failure.
  </doc>
  <name>ReturnStatus</name>
  <value>OK</value>
  <value>Failed</value>
</define_label_set>

The tags which support the <doc/> tag are the following:

XIDDL Constants

XIDDL supports the following constants.

Constants are intended to stand in for "magic numbers" sprinkled throughout the model. Use constants. Don't not use constants. There is some checking for magic numbers, and where they are found, they will be reported as errors when you run the semantic tests. It is possible to bypass the tests, but doing so will cause lots of problems in the long run.

Numeric Constants

Numeric constants need units perhaps... Numeric constants are intended to be used in place of "magic numbers" in the code which represent quantities other than durations.

Example: 

  <define_numeric_constraint>
    <name>*max_thrust*</name>
    <value>40</value>
  </define_numeric_constraint>

Duration Constants

Duration constants are rounded up to the nearest latency boundary during translation to Europa/DDL. In addition, they also support an optional <unit/> tag. The currently supported time units are documented in the Agent Latency and Time Units section. The default value is seconds. 

  <define_duration_constant>
    <name>*thrust_time*</name>
    <unit>milli_seconds</unit>
    <value>400</value>
  </define_duration_constant>

All duration constants are "rounded" up to the next multiple of latency (with respect to the time unit of latency). For example, using the default seconds time unit and a latency of 3, a duration constant of 400 seconds would be rounded up to 402.

As an example of the use of both explicit and default time units, consider the following (illustrative rather than useful) definitions: 

    <define_agent>
      [...]
      <agent_latency>30</agent_latency>
      <time_unit>deci_seconds</time_unit>
    </define_agent>

    <define_duration_constant>
      <name>*epsilon*</name>
      <value>1</value>
    </define_duration_constant>

    <define_duration_constant>
      <name>*max_planning_duration*</name>
      <value>3600</value>
    </define_duration_constant>

    <define_duration_constant>
      <name>*min_get_path_duration*</name>
      <value>1</value>
    </define_duration_constant>

    <define_duration_constant>
      <name>*max_get_path_duration*</name>
      <value>10</value>
    </define_duration_constant>

    <define_duration_constant>
      <name>*four_seconds*</name>
      <unit>centi_seconds</unit>
      <value>400</value>
    </define_duration_constant>

Latency is set here to 30 deci_seconds, i.e., 3 seconds, *epsilon* to 1 second (using the default time unit of seconds), *max_planning_duration* to 3600 seconds, *min_get_path_duration* to 1 second, *max_get_path_duration*, to 10 seconds, and *four_seconds* is defined as 400 centi_seconds (4 seconds). Given these inputs, the following DDL output is produced: 

  ;;; Duration Constants (latency of 30 in deci_seconds)

  ;; duration of 1 (in seconds) scaled to latency of 30 (in deci_seconds)
  (Define_Constant *epsilon* 30)
  ;; duration of 3600 (in seconds) scaled to latency of 30 (in deci_seconds)
  (Define_Constant *max_planning_duration* 36000)
  ;; duration of 1 (in seconds) scaled to latency of 30 (in deci_seconds)
  (Define_Constant *min_get_path_duration* 30)
  ;; duration of 10 (in seconds) scaled to latency of 30 (in deci_seconds)
  (Define_Constant *max_get_path_duration* 120)
  ;; duration of 400 (in centi_seconds) scaled to latency of 30 (in deci_seconds)
  (Define_Constant *four_seconds* 60)

Take a moment to read and understand these, and to convince yourself that they are indeed correct. They are a bit anti-intuitive, particularly since this example is meant to be illustrative.

An alternative translation scheme might be instead to have the agent latency automatically set to the smallest time unit used in the model, and all other time scaled to that unit. Given that the IDEA-DEV infrastructure always prints times uniformly (regardless of the unit used to define them), the output would still be readable and would make sense with respect to the model.

Do I need to point out that using these facilities requires care and thought in relation not only to the agent latency and various definitions duration constants, but in particular, to the values used in the Europa1 style initial state files. Be absolutely sure to put those in terms of the agent latency time units!

It is also dangerous to use a definition of *epsilon* which is not identical to latency (in terms both of magnitude and units) if there are any transitive relationships which might produce unexpected results as the result of propagation. For example, suppose you set latency to "2" deci_seconds, but leave *epsilon* as "1" and allow it to use the default unit of seconds. Now, if there is some process, such as deliberative planning, which lasts a minimum of *epsilon*, you have created a situation in which it is possible for deliberative planning to take less time than your model says it will. Believe me, this is not what you want to be doing. Think very carefully about what your model says.

XIDDL Types and Objects

XIDDL Objects

Objects are declared with <define_object_class/>. An consists of name (i.e., class name), an optional "dynamic" flag (on the "type" attribute), and zero or more attributes (<attr> elements).

I'm leaving this whole "object" mechanism somewhat undefined since I don't really know where we're heading with respect to PLASMA, in particular static object data, dynamic objects, and so on. 

  <define_object_class>
    <name>Class_Name</name>
    <attr>Timeline_Name</attr>
  </define_object_class>

XIDDL Types

XIDDL supports the following types:

Boolean, Real, Integer and String are built in, and need not be declared, but user define Objects and Label Sets must be. Note that in Europa1 (and probably Europa2) the "built-in" String type is automatically translated into a dynamic label sets with a single value, "none". This single "none" is included to make the Europa parsers happy.

Label sets can be used for both "enumerations" and "strings", however, the "string" usage is now deprecated (05/11/05). The build-in String type is the better way to use strings. However, both are declared using the <define_label_set/> tag. A label set consists of a "type name" in the <name/> tag and one or more "values" in <value/> tags. Non-string labels are, like enumerations, limited in the characters that can be included and may well be further limited by back-end in which they will be used (e.g., something like "[a-zA-Z0-9_]+"). 

  <define_label_set>
    <name>Label_Name</name>
    <value>Value1</value>
    <value>Value2</value>
  </define_label_set>

More complex labels can be represented as double quoted "stings" in label sets. Note the required use of "double quotes" in the following example. 

  <define_label_set>
    <name>CameraNames</name>
    <value>"rsr1.xml"</value>
  </define_label_set>

XIDDL Procedures

Procedures are also often called "predicates" or "tokens",

Unfortunately, with the current Europa back-ends, all token names must be unique (i.e., they can not be shared on similar timelines).

Procedures have zero or more parameters. Each parameters consists of one of four types:

The semantics of all but <internal_modes/> are inverted depending on whether they are used on an "executable" timeline or a "goal" timeline. An executable timeline is one which an agent uses to represent a subsystem that it can control by sending commands out to it, and from which it may receive some number of return values and a status. A goal timeline is a timeline which an agent uses to represent a "super-system" which exerts control over the agent itself. That is, the agent with the goal timeline is a "subsystem" being controlled by some other external entity.

In the following discussion, the point of view taken is the former (the semantics of executable timelines), but keep in mind that the semantics are inverted if the these parameter types are used on goal timelines.

Call Args

Call args are parameters which must be sent out to controlled subsystems. When the procedure starts, these arguments will be passed to the Agent Relay, which will pass them to the Comm Relay, which will in turn send the out of the agent to the system specified in the Agent Declared (see XIDDL Agents).

<call_args/> consist of one or more <arg/> elements, each of which have one <type/> element which specifies the type of the arg, zero or one <range/> elements which, in the case of Integer and Real types, constrains the domain over which the numbers can range, and one <name/> elements which names the parameter.

More than one group of call args may be declared in a procedure, though the most elegant style would group them all together.

Example:

A set_mode procedure which sends one of four modes and a flag which allows (or forbids) retries: 

  <define_procedure>
    <name>set_mode</name>
    <call_args>
      <arg>
        <type>Integer</type>
        <range> <lb>0</lb> <ub>3</ub> </range>
        <name>mode</name>
      </arg>
      <arg>
        <type>Boolean</type>
        <name>allow_retries</name>
      </arg>
    </call_args>
  </define_procedure>

Internal Modes

Internal modes are parameters which are sent neither to other systems nor received from other systems. <internal_modes/> consist of one or more <mode/> elements, each of which consists of a <type/>, an optional <range/>, and <name/>.

Example:

A current_mode procedure which uses a label set for internal reasoning: 

  <define_label_set>
    <name>Agent_Mode</name>
    <value>Standby</value>
    <value>Nominal</value>
  </define_label_set>

  <define_procedure>
    <name>current_mode</name>
    <internal_modes>
      <mode>
        <type>Agent_Mode</type>
        <name>mode</name>
      </mode>
    </internal_modes>
  </define_procedure>

Return Args

Return args are intermediate (i.e., not the final return status) values returned from external subsystems via the Agent Relay.

<return_args/> consist of one or more <arg/> elements, each of which has a <type/>, and optional <range/> constraint, a required <name/>, and a required <flag/>. The <flag/> arg may (or may not) be predicted (set) by planners, but it will be set by PSL if and when the return value is actually received.

Example:

In this example, the FSC_IPS_MISSION_PRESSURIZE token can receive an intermediate Interim_Pressure_Value while it is executing. Note that in this particular case, this would be an open loop token, since there is no explicit <return_status/> arg. The only reason for this is that <return_status/> will be in the following section. 

  <define_label_set>
    <name>Interim_Pressure_Value</name>
    <value>XFS_INIT_STATE</value>
    <value>PRES1_FAILED</value>
  </define_label_set>

  <define_procedure>
    <name>FSC_IPS_MISSION_PRESSURIZE</name>
    <return_args>
      <arg>
        <type>Interim_Pressure_Value</type>
        <name>pres1Value</name>
        <flag>pres1ValueFlag</flag>
      </arg>
    </return_args>
  </define_procedure>

Return Status

There is, by definition, only one <return_status/> for a procedure. The return status is the mechanism Idea uses for doing closed loop execution.

A <return_status/> consists of a required <type/>, and optional <range/>, a required <name/> and a required <flag/>. The planner (or planners) in an agent are free to predict if (<flag/>), what (<type/>) and when (via token duration) the return status will be received, however, the final disposition of these will ultimately be determined by whether, what and when they actually are received (which is enforced by PSL). 

  <define_label_set>
    <name>ReturnStatus</name>
    <value>OK</value>
    <value>Failed</value>
  </define_label_set>

  <define_procedure>
    <name>MICAS_Turning_Off<name>
    <return_status>
      <type>ReturnStatus</type>
      <name>status</name>
      <flag>statusFlag</flag>
    </return_status>
  </define_procedure>

XIDDL Compatibilities

Compatibilities are the heart of the XIDDL modeling language. Most, though not all constraints, are specified in the compatibility declarations. Constraints can be specified:

Compatibility Masters

A compatibility master is a pattern which can be matched by a token instantiated in the plan database. If the master is matched, the all of the constraints and subgoals specified in the compatibility in question must be satisfied. If any of the constraints or subgoals can not be satisfied, the master must be retracted from the plan database.

In its simplest form, a master looks like this: 

  <define_compatibility>
    <master>
      <class>Agent_Class</class>
      <attr>Agent_Mode</attr>
      <pred>Standby_Mode</name>
    </master>
    [one or more constraints or subgoals]
  </define_compatibility>

A compatibility may not be empty. Every compatibility must specify at least one of the above types of constraint or subgoal.

Compatibility Guards

A compatibility guard allows the modeler greater control over the "signature" of the master to be matched in the plan database. The signature of a <master/> can only match tokens if the plan database if all of the guards are satisfied.

In the above <master/> example, since there are no guards, all Standby_Mode tokens are matched, regardless of the bindings of any of the parameters of that token. However, if more than one disjunctive decomposition is needed for such a token, one way to control which constraints and subgoals (decomposition) are tried by the planner is to refine the pattern matching with guards. For example, consider: 

  <define_compatibility>
    <master>
      <class>Agent_Class</class>
      <attr>Agent_Mode</attr>
      <pred>Standby_Mode</name>
      <guard name="eq">
        <arg>successor</arg>
        <value>Nominal_Mode</value>
      </guard>
    </master>
    [one or more constraints or subgoals]
  </define_compatibility>

Here, the intent is that the "one or more constraints or subgoals" will only be tried if the value of the "successor" parameter is specified as "Nominal_Mode".

Duration Bounds

Every compatibility may have a duration bounds. A duration bounds limits how long the a token matching the master of the compatibility may last. The upper and lower bounds of a duration bound may only be specified with built-in or declared constants (due to the limitations of the currently supported back-ends). The built-in constants are _plus_infinity_ and _minus_infinity_. 

  <define_duration_constant>
    <name>*epsilon*</name>
    <value>1</value>
  </define_duration_constant>

  <define_compatibility>
    <master>
      <class>Agent_Class</class>
      <attr>Agent_Mode</attr>
      <pred>Standby_Mode</name>
    </master>
    <duration_bounds>
      <range> <lb>*epsilon*</lb> <ub>_plus_infinity_</ub> </range>
    </duration_bounds>
  </define_compatibility>

Note that, since this has explicit constraints on the duration of the token, this is a complete compatibility (i.e., it does have one or more constraints or subgoals).

Duration bounds, like all constraints and subgoals, can be guarded by Compatibility Guards.

Parameter Functions

Parameter functions allow the modeler to use arbitrary relations among the parameters of a token, including the following built-it parameters:

There are many built in parameter functions, e.g., "eq", "addeq", "neq", and so on. For Europa1, see NewPlan/ConstraintNetwork for forty or so examples.

This section only covers how to use such constraints, not how to write them.

To use such a constraint, the constraint must already be compiled and registered in the agent executable. Once this is done, it is only a matter of encoding the "signature" of the constraint in XIDDL.

Here, for example, is how to constraint an explicit parameter of a token to be the same as the built-in duration parameter (?_duration_) of that token: 

  <define_procedure>
    <name>Standby_Mode</name>
    <internal_mode>
      <type>Integer</type>
      <name>duration</name>
    </internal_mode>
  </define_procedure>

  <define_compatibility>
    <master>
      <class>Agent_Class</class>
      <attr>Agent_Mode</attr>
      <pred>Standby_Mode</name>
    </master>
    <parameter_functions>
      <function>
        <name>eq</name>        <!-- a built in parameter function -->
        <arg>duration</arg>    <!-- an explicit arg of Standby_Mode -->
        <var>?_duration_</var> <!-- the built-in duration variable -->
      </function>
    </parameter_functions>
  </define_compatibility>

Now, the duration parameter of the Standby_Mode token will always track the value of the built-in ?_duration_ variable.

Compatibility Subgoals

Conditional Subgoals

Temporal Constraints

A Temporal constraint is a relation between two tokens which has zero, one or two duration bounds which specify temporal distance between the two tokens in the relation.

The best overview of the temporal relations is the following:

There are three types of temporal relations, those with no distance bounds, those with zero or one distance bound, and those with zero or two distance bounds.

Those with no bounds are:

These three relations are a short hand for some of the other relations below where the temporal distances are "[0 0]".

The temporal relations with zero or one bounds are the following:

When a temporal distance "[d D]" is specified with any of these, these are interpreted as "the minimum temporal distance d, and the maximum temporal distance D".

Where a temporal distance is not given, it defaults to [0 _plus_infinity_], which is the maximum flexibility possible.

The remainder of the inverse relations are left as an exercise for the reader.

The following are the temporal relations with zero or two bounds:

For these relations, the model must specify either zero or two relations. Though the case of specifying one isn't particularly ambiguous, it is poor style and is likely to confuse later readers and maintainers of the model.

These relation have similar inverses, for example

Parameter Codesignation

XIDDL Agents

Agent Latency and Time Units

An agent declaration is required to have a <agent_latency/> tag, and may optionally have <time_unit/> tag.

Latency is always expressed as an integer, so in order to support sub-second response times, the optional <time_unit/> tag can be used to define exactly what is meant by the integer latency.

The value of the <time_unit/> tag defaults to seconds, which it the typical unit used by agents. However, there are (currently) five supported time units:

For example: 

  <agents>
    <define_agent>
      <name>Example_Agent</name>
      <agent_latency>1</agent_latency>
      <time_unit>centi_seconds</time_unit>
      [...]
    </define_agent>
  </agents>

Goal Timelines

All timelines are of one of three types:

A timeline is declared as a goal timeline by including a <channel/> with a <type>goal</type> in the master agent declaration and an executable timeline with <type>executable</type>. For example: 

  <channel>
    <object>RSR_Channel_1</object>
    <attr>Requests</attr>
    <type>goal</type>
    <relay>BOGUS_BOOMERANG_RELAY</relay>
    <target>Sim</target>
  </channel>

All other timelines are (implicitly) internal.

XIDDL Initial State

The initial state specification in XIDDL is similar in content to the previous Europa (and PLASMA) initial state languages.

The following small but complete initial state which follows is given in both the old Europa/PLASMA language and in XIDDL. 

[0 200]

Object_Timelines MyClass objectName
(
 Timeline1 ([0 0] token1 (True)
            [4 6] token2 () ...)
 Timeline2 ([0 0] token3 () ...
            [8 10] token4 [10 20] () ...)
)

This example give most of the required idioms needed for initial states.

The first timeline, Timeline1, has two tokens, token1 and token2 which are joined by a meets relation. The first token is required to start at time 0, while the second is allowed to start anywhere from time 4 to 6. Further, the first token has its first (positional) arg bound to "True". There is no information give about then the second can end. The ellipsis ("...") after token2 indicates that this timeline is "open" after that token.

The second timeline, Timeline2, also has two tokens, token3 and token4, but these tokens are separated by a "gap" on the timeline, indicated by the intervening ellipsis. The first token (token3), starts at time 0, and ends anywhere from 2 to 4. The second token starts anywhere from 8 to 10, and is required to last at least 10 and at most 20 time units. Note that there was no way to specify time units, though they were generally assumed to be "seconds".

Here follows the same initial state, now given in XIDDL as the <subsystem/> element of the <define_agent/> tag. 

<subsystem>
  <class>MyClass</class>
  <name>objectName</name>
  <attr>
    <name>Timeline1</name>
    <pred>
      <name>token1</name>
      <start> <lb>0</lb> <ub>0</ub> </start>
      <constraint> <arg>arg1</arg> <value>True</value> </constraint>
    </pred>
    <pred>
      <name>token2</name>
      <start> <lb>4</lb> <ub>6</ub> </start>
    </pred>
  </attr>
  <attr>
    <name>Timeline2</name>
    <pred>
      <name>token2</name>
      <start> <lb>0</lb> <ub>0</ub> </start>
    </pred>
    <gap/>
    <pred>
      <name>token3</name>
      <start> <lb>8</lb> <ub>10</ub> </start>
    </pred>
  </attr>
</subsystem>

Note that the <gap/> is still explicitly represented.

Although this particular initial state doesn't do so, the time units, which by default are seconds, can be conveniently expressed here in <start/> (or <end/> or <duration/>) tag thus: 

  <start> <unit>deci_seconds</unit> <lb>5</lb> <ub>10</ub> </start>

See Duration Constants for details on how these durations are handled with respect to Agent Latency and Time Units.

XIDDL Initial State Tags

XIDDL Heuristics

XIDDL and PLASMA

XIDDL to PLASMA Caveats

Things Remaining To Be Done

Common XIDDL Idioms

I haven't used Europa2 (PLASMA) yet, so I don't really know what idioms there may be there to document at this point.

Goal Timeline Idioms

The semantics of all parameter types (<call_args/>, <internal_modes/>, <return_args/> and <return_status/>) are inverted on goal timelines.

I don't have an example of how to do the heuristics (and other bits and pieces) for this just now, but keep it in mind.

Goal Timeline Tokens

For reasons which at this particular moment escape me, it can be tricky to get tokens on goal timelines to connect. For the present, these are as much notes to myself as anything, so please forgive their brevity.

Goal <met_by/> GoalIdle on a goal timeline (Goal Timelines) needs the following heuristics: 

  [Goal() After GoalIdle()] (full)

You might also have to use a value ordering to minimize search.

Open Loop Idioms

Closed Loop Idioms

Telemetry Idioms

Guarded Parameter Functions

Use multiple masters, putting the guarded parameter function in a master with the appropriate (implicit) guard(s). 

  <define_procedure>
    <name>Whatever</name>
    <internal_modes>
      <mode>
        <type>Boolean</type>
        <name>FireGuardedFunction</name>
      </mode>
    </internal_modes>
  </define_procedure>

  <define_compatibility>
    <class></class>
    <attr></attr>
    <pred>Whatever</name>
    <guard type="eq">
      <arg>FireGuardedFunction</arg>
      <value>True</value>
    </guard>
    <parameter_functions>
      <function>
        <name>GuardedFunction</name>
        <arg>FireGuardedFunction</arg>
      </function>
    </parameter_functions>
  </define_compatibility>

Successor Selectors

Europa1 Optimizations

Make Fewer Decisions

The Europa1 planner can only make decisions at a certain rate, which depends primarily on the size of the token network. My experience is that it can make about 30 decisions a second with some reliability. Starting with an empty database, I've seen as much as an average of 55 decisions per second for up to around 10 seconds. If you have a problem which the planner is having trouble solving in the given time, the only way to "optimize" it (that I know of) is to reduce the number of decisions the planner is making. Some ways to do this are listed below.

Note that these "optimizations" are all hacks, kludges, or work arounds. Use them when you must, but not as a steady diet.

XIDDL Support Tools

To get from a model in XIDDL to an agent, there is a set of support tools that live in the IDEA-DEV/XIDDL directory.

Currently, this directory contains a README file, the XIDDL schema, the XIDDL semantic tests, shell scripts to build the pre-processed xiddl model file and to run the semantic tests and target translations, Europa specific tests, and several files related to translating to xnddl.

The steps to get from an XIDDL model are:

The XIDDL Scripts

Shell Scripts

Currently, these script are, by convention, copied in to XIDDL/bin for use by applications, since this directory will be needed in any case for various other binaries. 


  build-xiddl <agent-xiddl> <output-xiddl> <error-report> [debug]

  run-xiddl2ddl <output-xiddl> [debug]

Scripts

The XIDDL Schema

The XIDDL schema lives in IDEA-DEV/XIDDL/xiddl.xsd. It includes a fair amount of useful documentation, so do feel free to consult it.

XIDDL "Semantic" Tests

The current XIDDL generic semantic tests live in IDEA-DEV/XIDDL/xiddl-tests.xsl. There are brief descriptions of all of the implemented test therein (and a few old tests that haven't been removed yet).

Backend Specific Tests

XIDDL Translation

Contact information
© IDEA
Generated on Fri Feb 3 17:09:44 2006 for IDEA.