Guided Tour: Planning with InfraEngine

We illustrate the use of the InfraEngine system as a planning engine over inputs represented by RDF documents. Relevant key features of the system are

Related Documents

Contents

1. Prerequisites

1.1 Running Example: The Sussman Anomaly

Our running example is a blocks world planning problem, the so-called Sussman anomaly. Our formalization for InfraEngine is based on the Liner Planning System User Manual – Example: Sussman Anomaly, where the problem is described and formalized for Liner, the system that underlies plan computation in InfraEngine. The example is worked out there in Prolog readable syntax, less cluttered than in RDF. Consulting the Liner documentation might also be helpful to clarify concepts and RDF notation for planning with InfraEngine.

1.2 Documents in the Knowledgebase

It is assumed that the following RDF documents have been loaded into the current knowledgebase:

This can be achieved as described for in Guided Tour: RDF Schema Browsing with InfraEngine. Like vehicles.rdf, these documents are also linked from the Examples page.

The document infraengine_schema.rdf is not strictly necessary for the blocks.rdf example. If it is loaded, additional information about classes in the inf namespace is provided, resulting in more comment lines and fewer void effective domain properties for classes in the bs namespace.

2. Overview on Classes in the Example

We first take a look at the Classes page.

[Screenshot]

Objects with namespace inf are declared in infraengine_schema.rdf. They can be considered as constituting the language in which planning tasks can be expressed with InfraEngine.

Objects with namespace bs are provided by the user in document blocks.rdf, making use of inf objects. The classes bs:WorldObject, bs:Block and bs:Table represent objects of the blocks world. RDF A way to represent

3. Representation of N-Ary Relations by Classes

We represent in RDF a n-ary relation, where n is a natural number >= 0, by a class with arguments identified by properties instead of position numbers. For example, the relation on top of, between blocks, is represented by the class bs:on, the domain of two properties bs:onTop and bs:onBottom. Further relations represented as classes in this way are bs:clear and bs:PutOn.

[Screenshot]

4. Quoting

In planning we reason about the truth values of facts in different states. Thus, in the specifications of start states, goal states and planning rules facts are not asserted, but “mentioned”. We model this with a quoting mechanism included in RDF, the rdf:parseType=Literal construct.

Consider for example the object bs:rulePutOn, an instance of the class inf:Rule. Its Object page, displayed below, can be accessed starting from a Classes page, via the Direct Instances field of the Class page for inf:Rule.

[Screenshot]

The quoting mechanism is used for the values of bs:action, bs:after , bs:before, and bs:remaining. For example, the value of inf:after is a quoted sequence of two facts, an instance of the 2-ary bs:on relation and an instance of the 1-ary bs:clear relation. (The InfraEngine browser currently displays such quoted structures just as pretty printed RDF text.)

5. Rules

We stay with the rule bs:rulePutOn, displayed in the screenshot of the previous section to discuss planning rules in more detail.

5.1 Semantics of Rules – Resource Oriented View of Planning

Rules are semantically understood as “resource oriented” planning rules. See the user manual of the underlying planning system Liner, especially Sections Overview: Resource Oriented View of Planning and Rulebase, for more information and references.

5.2 Properties of Rules

A rule is represented by an instance of the class inf:Rule. This class is the domain of the following properties: Compared to a Liner rule,

5.3 Notation for Facts

A fact is just expressed as a rule with no bs:before, bs:remaining and bs:action component. The rule bs:ruleTableAlwaysClear is an example.

The Liner system, in contrast, provides special syntax for facts.

5.4 Typed Variables in Rules

The values of bs:action, bs:after , bs:before, and bs:remaining can involve logic variables, similar to a Liner rule. The inf:var attribute is used to identify such variables. The scope of such a variable is the rule (this means that if a variable with the same identifier is used in another rule, it is considered as another variable).

A variable has a type, which is a class. For example, in the rule bs:rulePutOn the phrase

    <bs:Block inf:var="Moved" />
denotes the variable Moved with type bs:Block.

In the Liner system, in contrast, variables are not typed.

5.5 Type System

The variable typing is internally used to make plan computation feasible. Planning tasks submitted to Liner are outputs of a compilation step that maps RDF types to a type encoding for logic programs. In contrast to RDFS, this internally used type system does not support multiple inheritance. In such a case, evaluation of a planning query yields an error page that indicates the problem.

Note: An error message Item ... has multiple direct types: [inf_Literal, rdfs_Literal]. can be remedied by loading the document infraengine_schema.rdf, which asserts that inf:Literal is a subclass of rdfs:Literal.

6. Queries in View of the Query Designer

Like rules, queries that expresses planning tasks are represented as RDF objects of a certain class, inf:Query. The quoting mechanism described Section Quoting is also used for queries. Consider for example the object bs:querySussman, an instance of the class inf:Query. Its Object page, displayed below, can be accessed starting from a Classes page analogously as described for bs:rulePutOn in Section Quoted Facts.

[Screenshot]

6.1 Properties of Queries

A query is represented by an instance of the class inf:Query. This class is the domain of the following properties:

6.2 Typed Variables in Queries

The values of bs:goal and bs:start can involve logic variables, as described for rules. The scope of such a variable is the query.

7. Queries in View of the User

The Queries page lists the queries that are present in the current knowledgebase. In our example, this is just bs:querySussman.

[Screenshot]

The link bs:querySussman opens a Query view for the query object:

[Screenshot]

The Evaluate Query button triggers evaluation of the query. Additional fields allow to set evaluation parameters.

8. Solution Plans

Submitting Evaluate Query in Query view leads to a Solutions page that lists the solutions for the query. In our example the list contains just a single solution. In addition attributes of the solutions, such as the plan size (number of actions) are shown in the list.

[Screenshot]

The solutions are, of course, represented by RDF objects. They reside in a knowledgebase that is newly generated for the query evaluation, in our example sys:result1.

The links to the listed solution object opens a Solution view for the object:

[Screenshot]

The partial-order plan represented by the solution object is displayed as graph. The actions are pretty printed in boxes. Property values and classes are indicated by indentation.

Clicking on an action box leads to an Object view of the RDF object that represents the corresponding node in the solution graph (quite low-level).

9. Queries with Parameters

We now leave the blocks world example to show further features of planning with InfraEngine. It is assumed that the following RDF documents have been loaded into the current knowledgebase: The document table.rdf basically is a translation into the RDF representation of the constraints example in the Liner planning system manual. The goal of the planning task is having a table. In the start situation there is a budget of 100 Euros. A solution is buying a table board and four table legs, and assembling these. The RDF version generalizes the example by permitting the user to supply the start budget and the goal object.

[Screenshot]

Suitable alternatives for GoalObject are ...#tableBoard and ...#tableLeg, which all can be achieved by plans with a single buying action. If StartBudget is too small, the planner stops after the timeout without finding a plan.

Parameters in queries are specified with an extension of the variable mechanism that has been described in the context of rules. The following fragment of the table.rdf illustrates what is behind the query just shown.

  <inf:Query rdf:ID="queryTable"
    rdfs:comment="From a given budget to having a world object.">

    <inf:parameter>
      <inf:Parameter
	inf:parameterVar="GoalObject"
	rdfs:comment="The goal is having this world object."
	inf:parameterDefaultValue="http://www.infraengine.com/examples/table#table" />
    </inf:parameter>

    <inf:parameter>
      <inf:Parameter
	inf:parameterVar="StartBudget"
	rdfs:comment="The initially given budget."
	inf:parameterDefaultValue="100" />
    </inf:parameter>

    <inf:goal rdf:parseType="Literal">
      <ex:have>
        <ex:haveObject>
          <ex:WorldObject inf:var="GoalObject" />
        </ex:haveObject>
      </ex:have>
    </inf:goal>

    <inf:start rdf:parseType="Literal">
      <ex:budget>
	<ex:budgetAmount>
           <inf:Literal inf:var="StartBudget" />
        </ex:budgetAmount>
      </ex:budget>
    </inf:start>

  </inf:Query>

10. Arithmetic Constraints in Rules and Queries

The constraint mechanism of the Liner planning system is also available for rules and queries in the RDF representation. Aside of the properties listed in Sections Rules and Queries in View of the Query Designer, a superclass of both inf:Rule and inf:Query is the domain of the inf:constrained property, which specifies constraints between variables. The following fragment of table.rdf illustrates the use of the inf:constrained property.
  <inf:Rule rdf:about="buyingRule"
    rdfs:comment="The agent buys a world object.">

    ...

    <inf:constrained rdf:parseType="Literal">
      <inf:ArithmeticConstraint
	    inf:expression="NewBudget =:= OldBudget - Price" />
      <inf:ArithmeticConstraint
	    inf:expression="NewBudget >= 0" />
    </inf:constrained>
 
  </inf:Rule>

Appendix: The Blocks RDF Document

<?xml version="1.0"?>
<!DOCTYPE rdf:RDF SYSTEM "blocks_generated.dtd" []> 

<rdf:RDF
  xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#"
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
  xmlns:inf="http://www.infraengine.com/planner/"
  xml:base="http://www.infraengine.com/examples/blocks"
  xmlns:bs="http://www.infraengine.com/examples/blocks#" >


  <!-- ================================================================== -->
  <!-- Objects in the Blocks World -->
  <!-- ================================================================== -->

  <rdfs:Class rdf:ID="WorldObject"
    rdfs:comment="An object in the blocks world."/>
  
  <rdfs:Class rdf:ID="Block"
    rdfs:comment="A block that can be moved." >
    <rdfs:subClassOf rdf:resource="#WorldObject" />
  </rdfs:Class>

  <rdfs:Class rdf:ID="Table"
    rdfs:comment="A table with blocks on it." >
    <rdfs:subClassOf rdf:resource="#WorldObject" />
  </rdfs:Class>

  <!-- ================================================================== -->
  <!-- Fluents -->
  <!-- ================================================================== -->
    
  <!-- Fluent "on(top:Block, bottom:WorldObject)" -->

  <rdfs:Class rdf:ID="on" 
    rdfs:comment="Fluent: One block is on top of the other."/>
  
  <rdf:Property rdf:ID="onTop"
    rdfs:comment="Fluent parameter: Top block." >
    <rdfs:domain rdf:resource="#on" />
    <rdfs:range rdf:resource="#Block" />
  </rdf:Property>

  <rdf:Property rdf:ID="onBottom"
    rdfs:comment="Fluent parameter: Bottom block." >
    <rdfs:domain rdf:resource="#on" />
    <rdfs:range rdf:resource="#WorldObject" />
  </rdf:Property>

  <!-- Fluent "clear(object:WorldObject)" -->

  <rdfs:Class rdf:ID="clear"
    rdfs:comment="Fluent: The object is clear."/>
  
  <rdf:Property rdf:ID="clearWorldObject"
    rdfs:comment="Fluent parameter: The clear object." >
    <rdfs:domain rdf:resource="#clear" />
    <rdfs:range rdf:resource="#WorldObject" />
  </rdf:Property>


  <!-- ================================================================== -->
  <!-- The PutOn Action -->
  <!-- ================================================================== -->

  <!-- Action "PutOn(block:Block, from:WorldObject, to:WorldObject)" -->

  <rdfs:Class rdf:ID="PutOn"
    rdfs:comment="Action: Put a block on to another block or the table." />
  
  <rdf:Property rdf:ID="putOnBlock"
    rdfs:comment="Action parameter: The block that is moved.">
    <rdfs:domain rdf:resource="#PutOn" />
    <rdfs:range rdf:resource="#Block" />
  </rdf:Property>

  <rdf:Property rdf:ID="putOnFrom"
    rdfs:comment="Action parameter: The object on which the block
    was lying before." >
    <rdfs:domain rdf:resource="#PutOn" />
    <rdfs:range rdf:resource="#WorldObject" />
  </rdf:Property>

  <rdf:Property rdf:ID="putOnTo"
    rdfs:comment="Action parameter: The object on which the block
    is put." >
    <rdfs:domain rdf:resource="#PutOn" />
    <rdfs:range rdf:resource="#WorldObject" />
  </rdf:Property>


  <!-- ================================================================== -->
  <!-- Rules -->
  <!-- ================================================================== -->

  <!-- Rule 1: We have a table that is always clear. -->

  <inf:Rule rdf:ID="ruleTableAlwaysClear"
    rdfs:comment="We have an instance of Table that is always clear.">
    <inf:after rdf:parseType="Literal">
      <bs:clear>
	<bs:clearWorldObject>
	  <bs:Table rdf:about="#table" />
	</bs:clearWorldObject>
      </bs:clear>
    </inf:after>

  </inf:Rule>

  <!-- Rule 2: The effect of PutOn -->

  <inf:Rule rdf:ID="rulePutOn"
    rdfs:comment="The effect of PutOn.">

    <inf:action rdf:parseType="Literal">
      <bs:PutOn>
	<bs:putOnBlock><bs:Block inf:var="Moved"/></bs:putOnBlock>
	<bs:putOnFrom><bs:WorldObject inf:var="From"/></bs:putOnFrom>
	<bs:putOnTo><bs:WorldObject inf:var="To"/></bs:putOnTo>
      </bs:PutOn>
    </inf:action>

    <inf:after rdf:parseType="Literal">
      <bs:on>
	<bs:onTop><bs:Block inf:var="Moved"/></bs:onTop>
	<bs:onBottom><bs:WorldObject inf:var="To"/></bs:onBottom>
      </bs:on>
      <bs:clear>
	<bs:clearWorldObject><bs:WorldObject inf:var="From"/></bs:clearWorldObject>
      </bs:clear>
    </inf:after>

    <inf:remaining rdf:parseType="Literal">
      <bs:clear>
	<bs:clearWorldObject><bs:Block inf:var="Moved"/></bs:clearWorldObject>
      </bs:clear>
    </inf:remaining>

    <inf:before rdf:parseType="Literal">
      <bs:on>
	<bs:onTop><bs:Block inf:var="Moved"/></bs:onTop>
	<bs:onBottom><bs:WorldObject inf:var="From"/></bs:onBottom>
      </bs:on>
      <bs:clear>
	<bs:clearWorldObject><bs:WorldObject inf:var="To"/></bs:clearWorldObject>
      </bs:clear>
    </inf:before>

  </inf:Rule>


  <!-- ================================================================== -->
  <!-- Queries -->
  <!-- ================================================================== -->

  <inf:Query rdf:ID="querySussman"
    rdfs:comment="The Sussman anomaly.">

    <inf:goal rdf:parseType="Literal">

      <bs:on>
	<bs:onTop rdf:resource="#a" />
	<bs:onBottom rdf:resource="#b" />
      </bs:on>

      <bs:on>
	<bs:onTop rdf:resource="#b" />
	<bs:onBottom rdf:resource="#c" />
      </bs:on>

    </inf:goal>
    

    <inf:start rdf:parseType="Literal">

      <bs:on>
	<bs:onTop rdf:resource="#b" />
	<bs:onBottom rdf:resource="#table" />
      </bs:on>

      <bs:clear>
	<bs:clearWorldObject rdf:resource="#b" />
      </bs:clear>

      <bs:on>
	<bs:onTop rdf:resource="#a" />
	<bs:onBottom rdf:resource="#table" />
      </bs:on>

      <bs:on>
	<bs:onTop rdf:resource="#c" />
	<bs:onBottom rdf:resource="#a" />
      </bs:on>

      <bs:clear>
	<bs:clearWorldObject rdf:resource="#c" />
      </bs:clear>

    </inf:start>

  </inf:Query>
  
</rdf:RDF>

Appendix: The Table RDF Document

<?xml version="1.0"?>
<!DOCTYPE rdf:RDF SYSTEM "table_generated.dtd" [
         <!ENTITY rdf "http://www.w3.org/1999/02/22-rdf-syntax-ns#">
         <!ENTITY rdfs "http://www.w3.org/2000/01/rdf-schema#"> 
]>

<rdf:RDF
  xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#"
  xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
  xmlns:inf="http://www.infraengine.com/planner/"
  xml:base="http://www.infraengine.com/examples/table"
  xmlns:ex="http://www.infraengine.com/examples/table#" >


  <!-- ================================================================== -->
  <!-- Objects in the World -->
  <!-- ================================================================== -->

  <rdfs:Class rdf:ID="WorldObject"
    rdfs:comment="A world object."/>
  

  <!-- ================================================================== -->
  <!-- Fluents -->
  <!-- ================================================================== -->
    
  <!-- Fluent "have(object:WorldObject)" -->

  <rdfs:Class rdf:ID="have" 
    rdfs:comment="Fluent: The agent has a world object at his disposal."/>
  
  <rdf:Property rdf:ID="haveObject"
    rdfs:comment="Fluent parameter: The world object." >
    <rdfs:domain rdf:resource="#have" />
    <rdfs:range rdf:resource="#WorldObject" />
  </rdf:Property>

  <!-- Fluent "budget(amount:Number)" -->

  <rdfs:Class rdf:ID="budget" 
    rdfs:comment="Fluent: The agent has an amount of Euros at his disposal."/>
  
  <rdf:Property rdf:ID="budgetAmount"
    rdfs:comment="Fluent parameter: The amount of Euros." >
    <rdfs:domain rdf:resource="#budget" />
    <rdfs:range rdf:resource="&rdfs;Literal" />
  </rdf:Property>

  <!-- Fluent "offered(object:WorldObject, price:Number)" -->

  <rdfs:Class rdf:ID="offered" 
    rdfs:comment="Fluent: A world object is on offer at a certain price."/>
  
  <rdf:Property rdf:ID="offeredObject"
    rdfs:comment="Fluent parameter: The offered world object." >
    <rdfs:domain rdf:resource="#offered" />
    <rdfs:range rdf:resource="#WorldObject" />
  </rdf:Property>

  <rdf:Property rdf:ID="offeredPrice"
    rdfs:comment="Fluent parameter: The price of the offering." >
    <rdfs:domain rdf:resource="#offered" />
    <rdfs:range rdf:resource="&rdfs;Literal" />
  </rdf:Property>


  <!-- ================================================================== -->
  <!-- Actions -->
  <!-- ================================================================== -->

  <!-- Action "Buy(object:WorldObject, price:Literal)" -->

  <rdfs:Class rdf:ID="Buy"
    rdfs:comment="Action: The agent buys a world object." >
  </rdfs:Class>

  <rdf:Property rdf:ID="buyObject"
    rdfs:comment="Action parameter: The bought world object.">
    <rdfs:domain rdf:resource="#Buy" />
    <rdfs:range rdf:resource="#WorldObject" />
  </rdf:Property>

  <rdf:Property rdf:ID="buyPrice"
    rdfs:comment="Action parameter: The price.">
    <rdfs:domain rdf:resource="#Buy" />
    <rdfs:range rdf:resource="&rdfs;Literal" />
  </rdf:Property>

  <!-- Action "AssembleTable" -->

  <rdfs:Class rdf:ID="AssembleTable"
    rdfs:comment="Action: The agent assembles a table." >
  </rdfs:Class>


  <!-- ================================================================== -->
  <!-- Rules -->
  <!-- ================================================================== -->

  <!-- Rule 1: The agent buys a world object. -->

  <inf:Rule rdf:about="buyingRule"
    rdfs:comment="The agent buys a world object.">

    <inf:action rdf:parseType="Literal">
      <ex:Buy>
	<ex:buyObject><ex:WorldObject inf:var="Object"/></ex:buyObject>
	<ex:buyPrice><inf:Literal inf:var="Price" /></ex:buyPrice>
      </ex:Buy>
    </inf:action>

    <inf:after rdf:parseType="Literal">
      <ex:have>
	<ex:haveObject><ex:WorldObject inf:var="Object" /></ex:haveObject>
      </ex:have>
      <ex:budget>
	<ex:budgetAmount>
           <inf:Literal inf:var="NewBudget" />
        </ex:budgetAmount>
      </ex:budget>
    </inf:after>

    <inf:before rdf:parseType="Literal">
      <ex:offered>
	<ex:offeredObject>
          <ex:WorldObject inf:var="Object" />
       </ex:offeredObject>
	<ex:offeredPrice>
          <inf:Literal inf:var="Price" />
        </ex:offeredPrice>
      </ex:offered>
      <ex:budget>
	<ex:budgetAmount>
          <inf:Literal inf:var="OldBudget" />
        </ex:budgetAmount>
      </ex:budget>
    </inf:before>

    <inf:constrained rdf:parseType="Literal">
      <inf:ArithmeticConstraint
	    inf:expression="NewBudget =:= OldBudget - Price" />
      <inf:ArithmeticConstraint
	    inf:expression="NewBudget >= 0" />
    </inf:constrained>

  </inf:Rule>


  <!-- Rule 2: The agent assembles a table. -->

  <inf:Rule rdf:about="assembleTableRule"
    rdfs:comment="The agent assembles a table from four legs and a board.">

    <inf:action rdf:parseType="Literal">
      <ex:AssembleTable />
    </inf:action>

    <inf:after rdf:parseType="Literal">
      <ex:have><ex:haveObject rdf:resource="#table" /></ex:have>
    </inf:after>

    <inf:before rdf:parseType="Literal">
      <ex:have><ex:haveObject rdf:resource="#tableBoard" /></ex:have>
      <ex:have><ex:haveObject rdf:resource="#tableLeg" /></ex:have>
      <ex:have><ex:haveObject rdf:resource="#tableLeg" /></ex:have>
      <ex:have><ex:haveObject rdf:resource="#tableLeg" /></ex:have>
      <ex:have><ex:haveObject rdf:resource="#tableLeg" /></ex:have>
    </inf:before>

  </inf:Rule>


  <!-- Facts -->

  <inf:Rule rdf:about="offeredTableBoardFact">
    <inf:after rdf:parseType="Literal">
      <ex:offered> 
         <ex:offeredObject rdf:resource="#tableBoard" />
         <ex:offeredPrice>10</ex:offeredPrice>
      </ex:offered>
    </inf:after>
  </inf:Rule>

  <inf:Rule rdf:about="offeredTableLegFact">
    <inf:after rdf:parseType="Literal">
      <ex:offered> 
         <ex:offeredObject rdf:resource="#tableLeg" />
         <ex:offeredPrice>5</ex:offeredPrice>
      </ex:offered>
    </inf:after>
  </inf:Rule>



  <!-- ================================================================== -->
  <!-- Queries -->
  <!-- ================================================================== -->

  <inf:Query rdf:ID="queryTable"
    rdfs:comment="From a given budget to having a world object.">

    <inf:parameter>
      <inf:Parameter
	inf:parameterVar="GoalObject"
	rdfs:comment="The goal is having this world object."
	inf:parameterDefaultValue="http://www.infraengine.com/examples/table#table" />
    </inf:parameter>

    <inf:parameter>
      <inf:Parameter
	inf:parameterVar="StartBudget"
	rdfs:comment="The initially given budget."
	inf:parameterDefaultValue="100" />
    </inf:parameter>

    <inf:goal rdf:parseType="Literal">
      <ex:have>
        <ex:haveObject>
          <ex:WorldObject inf:var="GoalObject" />
        </ex:haveObject>
      </ex:have>
    </inf:goal>

    <inf:start rdf:parseType="Literal">
      <ex:budget>
	<ex:budgetAmount>
           <inf:Literal inf:var="StartBudget" />
        </ex:budgetAmount>
      </ex:budget>
    </inf:start>

  </inf:Query>

</rdf:RDF>

Christoph Wernhard (info@cs.christophwernhard.com)