prev content

The Object Centered Language Manual
OCLh - Version1.2

Planform Home

5. Development of an Hierarchical Domain Model

5.1. Sort Hierarchy

As a larger example, we will use a transport logistics model based on Translog [4]. This is a nice example of a domain needing hierarchy and hierarchical operators. A sort hierarchy for Translog is shown in Example 1, containing 4 dynamic primitive sorts truck, package, train, traincar and hence 15 dynamic objects. In here we give a full specification of our version ofTranslog.
   sorts(physical-obj, [vehicle, package])
   sorts(vehicle, [railv,roadv])
   sorts(roadv, [truck])
   sorts(railv, [train, traincar])
   sorts(location, [city-location,city])
   sorts(city-location, [tcentre,not-tcentre])
   sorts(tcentre, [train-station])
   sorts(not-tcentre, [clocation,post-office])
   sorts(route, [road-route, rail-route])
   objects(train-station, [city1-ts1,city2-ts1,city3-ts1])
   objects(clocation, [city1-cl1,city1-cl2,city2-cl1,city3-cl1])
   objects(post-office, [post_1])
   objects(city, [city_1, city_2, city_3])
   objects(train,[train_1,train_2])
   objects(traincar,[traincar_1])
   objects(road-route, [road-route_1,road-route_2,road-route_3]) 
   objects(rail-route,[rail-route_2,rail-route_3,rail-route_4 ]) 
   objects(truck, [truck_1, truck_2, truck_3, truck_11, truck_22, truck_33]) 
   objects(package,[pk_1, pk_2, pk_3, pk_4, pk_5, pk_6])
Example 1
Let the predicates that describe a train be at(train,location), attached(train,traincar), unattached(train), in-service(train), available(train). An example of an object description is:
   (train,train_1,[at(train_1,city1-ts1), in-service(train_1), attached(train_1,traincar_1)])
Example 2
Here the local closed world assumption tells us that, for example, the train is not available, and it is not attached to other traincars apart from traincar_1. Example 3 is an object expression as it is satisfied by an least one object description - that of Example 2. In this case train is a subsort of railv, t = [train_1/T, city1-ts1/Y] and in-city(city1-ts1,city1) is consistent with the domain model.
   (railv,T,[at(T,Y),in-service(T),in-city(Y,city1)])
Example 3
The substate in Example 2 has three hierarchical components - at, relating to physical objects, attached relating to rail vehicles, and in-service, relating specifically to trains. Objects of sort train are described by predicates through their primitive sort but they also inherit the dynamic predicates from supersorts railv and physical_obj.
   substate_classes(physical_obj, P, [ [at(P,L), is-of-sort(L,train-station) ])
   substate_classes(railv, V,  [ [unattached(V)] ,
            [attached(V,V1),is-of-sort(V1,traincar)] ])
   substate_classes(train, T, [ [out-of-service(T)], [in-service(T)], 
            [in-service(T),available(T)] ])
Example 4: hierarchical substate specification for trains
Example 4 implicitly specifies the substates of the train. If there are n stations, m traincars, and t trains then this implicitly defines all t*(n*(m+1)*3) substates. Static predicates are used to capture the exact set required.

5.2. Special Rules Relating to Hierarchical Transitions

When object transitions appear in hierarchical domain operators and methods, the idea of specifying a (many - to - one) change from substates to substates is more complex. It is possible that only one or some of the hierarchical levels of a sort may change on transition. To reflect this we use the following rule:

if NO predicates from level N in the hierarchy appear in the right hand side of a transition, then the state at that level persists. If predicates from level N in the hierarchy appear in the right hand side of a transition, then they must specify a unique substate class at that level}.

For example, the transition of package P

   [waiting(P),certified(P)][loaded(P,V),certified(P)]
changes the class expression:
    (package,pk_1,[at(pk_1,L),waiting(pk_1),certified(pk_1)]
to:
    (package,pk_1,[at(pk_1,L),loaded(pk_1,V),certified(pk_1)]
when this transition is applied. Here t = [pk_1/P], and the predicate at(pk_1,L) persists as it is specified at a higher level in package's hierarchy than the other predicates.

5.3. Compound and Method Operators

A compound operator C has components:
   (Nm,Pre,Index, 
     [(Cons1,Temps1,Body1),
      ..., 
     (Consn,Tempsn,Bodyn)])
Nm is the operator's name followed by its parameters, and Pre is a set of object expressions that must be true before C (unlike the prevail in a primitive operator objects in Pre may be affected by the operators in the expansion of C). Index is a set of necessary state transitions (possibly null) similar to Index in the primitive operator case. The (Consi,Tempsi,Bodyi) are conditional expansions, where Consi and Tempsi are static conditions on the parameters in the operator, and temporal constraints on the nodes in the Bodyi, respectively. If a Consi can be satisfied, the compound operator can be expanded into the network as specified in Bodyi (the Consi need not be mutually exclusive). Bodyi contains nodes in the usual HTN fashion: a node is either the name of a primitive operator, the name of a compound operator, or an expression of the form `achieve-goal(G)', where G is a class expression.

Compound operators can be split into n methods of the form

   (Nn,Pre,Index,Consi,Tempsi,Bodyi)
The example shows a method for carrying a package from one location to another within the same city.
   method( carry-direct(P,O,D), [], 
           [ sc(package, P, [at(P,O),waiting(P),certified(P)] 
                      [at(P,D),waiting(P),certified(P)])] 
           [is-of-sort(P,package), is-of-sort(V,truck), 
                       in-city(O,CY), in-city(D,CY) ],
           [before(1,2), before(2,3), before(3,4),before(4,5) ], 
           [comission(V,P), move(V,OL,O,R), 
                       load-package(P,V,O), move(V,O,D,R1),
                       unload-package(P,V,D) ]). 
Example 5: a `carry-direct' method
An OCLh compound operator has no achievable conditions on intermediate nodes in its body. This is because constraints on the persistence of facts (e.g. using a `between' constraint) throughout a sequence of nodes in compound operator bodies can be represented within the substate specification of each sort, making the constraints implicit as discussed in reference
[2].

Whenever a method has been fully expanded to primitive operators, the resulting plan must effect the transitions given in the Index. C may, however, change other objects in ways conditional on its expansion into more detailed task networks (such as the vehicle V in the example above). The property that methods decompose into networks that guarantee the transitions specified in a method's index we have calledtransparency.

5.4. The Transparency Property

Hierarchical domain models in OCLh are regulated by the semantic property of transparency - this ensures the methods are structured in a coherent manner This property should be true for every method in a model. The technical details of this are given elsewhere [2]. Key to the property is the idea that the method's decomposition into a task network will necessarily achieve the method's post-conditions (the RHSs of the necessary transitions indexing the method) -- if this is the case, the method is called sound. The transparency property is then as follows: A method m is transparent if it and every expansion of m, consistent with its static constraints, is sound.

To check that a method is transparent, we first check that its decomposition necessarily achieves the post-condition and the pre-conditions of operators/methods in the method's body (task network). This is done by examining each of the nodes in the task network and proving that the conditions are necessarily achieved, using the post-conditions of the nodes as achievers. An `achieve-goal(G)' is treated as a transition with an unspecified LHS, where the post-condition (RHS) is G. After this is proved, we must study the consistent decompositions of the task network and re-check this property for each such decomposition.

A method or operator's statement of transitions can be turned into pre- and post conditions - conditions that must be true initially and those that are true after execution. Note that, of course, the statement of transitions contains more information than this (eg conditions that persist through the duration an action).

The transparency property is checked for each method. Essentially, a partially ordered task network is created where the start is the preconditions of the method, the end is the post-condition of the method. Transparency means that the post-condition of the method and the pre-condition of all the operators are necessarily achieved for all sorts in the pre- and post-conditions. Any conditions relating to objects not in the pre- and post-conditions are ignored.

Example

Consider the DRUM world in the resource page. An example method is as follows:

     method(navigate_method_dock(Rob,REF1,REF),
     % dynamic constraints 
     [ ],
     % necessary substate changes
     [sc(robot,Rob,[position(Rob,REF1)] [position(Rob,REF),at(Rob,REF)])],
     % static constraints 
     [in_range(REF2,REF), is_of_primitive_sort(REF,RFT),
                is_of_primitive_sort(Rob,RT),allowed_position(RT,RFT)],
     % temporal constraints 
     [before(1,2), before(2,3)],
     % decomp 
     [navigate_method(Rob, REF1 ,REF2),
      navigate(Rob,REF2,REF),
      dock(Rob,REF)]).

The proof of transparency can be shown by inspecting the following presentation:


PRE: position(Rob,REF1)

PRE: position(Rob,REF1)
navigate_method(Rob, REF1 ,REF2)
POST: position(Rob,REF2),at(Rob,REF)

PRE: position(Rob,REF2)
navigate(Rob,REF2,REF),
POST: position(Rob,REF),near(Rob,REF)

PRE: position(Rob,REF),near(Rob,REF)
dock(Rob,REF)
POST: position(Rob,REF),at(Rob,REF)


POST: position(Rob,REF),at(Rob,REF)

5.5. Task Specification

A task specification in OCLh has three components:

(i) a task network, where a task is the name of a method or a condition on an object to be achieved
(ii) an initial world state
(iii) a set of constraints on the task network.

The first component is thus similar to that used in Estlin et al's integrated planner framework [5]. Their `activity-goals' are the same as method tasks, and their `state-goals' are like our `achieve goals'. An example task comprising a task network containing two achieve goals and a method, is as follows:

( [ achieve(ss(traincar,traincar1,
              [at(traincar1,city1-ts1)])),
   transport(pk-5-z,city3-cl1-z,city2-cl1),
   achieve(ss(package,pk-5,
              [at(pk-5,X),delivered(pk-5)] )) ],
 [before(1,3)],
 [serves(X,city3-x)])
Use of parameter X means the third node in the network can be paraphrased as `deliver pk-5 to any destination X where X is a town centre location serving city3-x'.
prev content Feedback:t.l.mccluskey@hud.ac.uk