The first tutorial aims to model a simple planning problem in the language PDDL. You may check your solution using the Fast Downward planner. If you download the Apptainer (previously Singularity) image, you can find a plan for your PDDL files as follows:

./fast-downward.sif domain.pddl problem.pddl --search "astar(ipdb())"

where domain.pddl is the file defining your domain and problem.pddl defines a particular problem instance.

Your main task is to model a shunting game in PDDL. For an example, see this page. Don't play the game too long so that you still have some time to finish your task .

The above image shows several shunting rails $R1, R2, R3$ with wagons $1-8$ and a locomotive on an outgoing rail $OR$. Our task is to build a train having five wagons sorted from $1$ to $5$. The locomotive can pull several wagons from a shunting rail to the outgoing rail. Conversely, it can push wagons from the outgoing rail to a shunting rail. The switchers determine which shunting rail we operate on. Note also that each rail has a limited capacity.

We want to model such tasks in PDDL. To simplify it, we will not model each particular switch. Instead, we will simply create an action schema that allows us to pull the first wagon from a shunting rail to the end of the outgoing rail. Dually, we will create an action schema for pushing the last wagon from the outgoing rail to a shunting rail. Further, we will model each rail as a stack with a bounded capacity. For the example above, we will have four stacks $R1,R2,R3,OR$ with respective capacities $5,3,3,3$. Note that the outgoing rail can accommodate only three wagons. Thus, to build the outgoing train, we must prepare the first three wagons on the outgoing rail, and the remaining two must be located in the proper order at the beginning of a shunting rail.

We will model a stack as a linked list so that we know the wagon on the top of the stack and the wagon order is captured by a binary relation. Moreover, we introduce an empty wagon $\emptyset$ as a marker to recognize the last wagon in the stack. The above example in the simplified form is shown below:

If we pull a wagon from the top shunting rail, we get the wagon 8 to the end of the outgoing rail.

Note that the stack representing the outgoing rail is ordered in the opposite order, i.e., from the end to the beginning.

We create a domain file defining our predicate language for modeling states and action schemata specifying how to transform states. The domain file has the following structure:

(define (domain shunting)  ; name of the domain
 
    (:requirements
        :typing            ; we will use types of objects
        :action-costs      ; actions have associated costs
    )
 
; predicate language here
 
; action schemata here
)

The requirements section tells us that we are going to use object types. They correspond to unary predicates defining different kinds of objects. For instance, wagons, rails, etc. Next, we require the action costs. Even though we could make all the actions have the same unit cost in the above example, we will make it more flexible so that you see how to model action costs as well.

First, we must define a suitable predicate language modeling the rails, their capacities, and the ordering of wagons on them. Thus, we introduce three types: wagon, track, and cap-num, which represent wagons, rails, and the remaining free capacity on the rail, respectively. Further, we must distinguish between the outgoing rail and the shunting rails. So we introduce two subtypes of the type track, namely mtrack representing the outgoing rail, and strack representing the shunting rails. Altogether, we add the following section into our domain file:

    (:types
       wagon track cap-num - object
       mtrack strack - track
    )

As there is always only a single outgoing rail, we model it as a constant main-track of our predicate language. Recall that we model the rails as stacks of wagons. You can imagine the stack as a linked list of wagons with a pointer to the first wagon. To make it work properly, we need to recognize the end of the linked list. Thus, we introduce a special constant empty of type wagon that will serve as a marker for the end of the stack.

    (:constants
        main-track - mtrack
        empty - wagon
    )

Next, we introduce predicates to express the relations between objects. To model a stack, we need a binary predicate (head ?w - wagon ?t - track) expressing that a wagon ?w is on the top of the stack ?t. The predicate head meaning differs depending on the rail type. If ?t is a shunting rail, it means that ?w is the first wagon on the rail. If ?t is the outgoing rail, then ?w is the last wagon. Further, we add a predicate (next ?w1 ?w2 - wagon) expressing that a wagon ?w2 is next after a wagon ?w1 on the same rail.

To model the capacity of a rail, we add a binary predicate (capacity ?t - track ?n - cap-num) saying that a rail ?t has ?n many free slots for wagons. When we pull (resp. push) a wagon from a shunting rail, its capacity increases (resp. decreases) by one. To capture this simple arithmetic operation, we introduce a binary predicate (pred ?n1 ?n2 - cap-num) expressing that ?n1 is the predecessor of ?n2, i.e., $n_1=n_2-1$. The following code introduces all the mentioned predicates (we will discuss the extra predicate tail later on):

    (:predicates
        (head ?w - wagon ?t - track)
        (next ?w1 ?w2 - wagon)
        (capacity ?t - track ?n - cap-num)
        (pred ?n1 ?n2 - cap-num)
        (tail ?w - wagon)
    ) 

Finally, we introduce two functions to capture the action costs. Suppose that the shunting rails might have different accessibility (e.g., the number of nested switches needed to access the rail) so that the pulling/pushing on them takes different times. The function (track-cost ?t - strack) assigns for each shunting rail its accessibility cost. The function total-cost serves as a counter for the plan's total cost.

    (:functions
      (track-cost ?t - strack) - number
      (total-cost) - number
    )

We have only two action schemata: one for pulling and one for pushing. They are dual to each other. Let us start with the action schema pull. Its parameters are

(?w1 ?w2 ?w3 - wagon ?t - strack ?n1 ?n2 ?n3 ?n4 - cap-num)

It pulls the first wagon ?w1 from a shunting rail ?t. To define the action-schema effect, we need a context: the wagon ?w2 next after ?w1 and the last wagon ?w3 on the outgoing rail. The precondition and effect can be depicted as follows:

In terms of preconditions, the following must hold:

(head ?w1 ?t)
(next ?w1 ?w2)
(head ?w3 main-track)

The effect after pulling is the following (see the picture above):

(not (head ?w1 ?t))
(not (head ?w3 main-track))
(not (next ?w1 ?w2))
(head ?w1 main-track)
(next ?w1 ?w3)
(head ?w2 ?t)

Next, we must handle the rail ?t capacity ?n1 and outgoing rail capacity ?n4. The capacity of ?t will increase to ?n2 by pulling the wagon, whereas the capacity of the outgoing rail will decrease to ?n3. Thus, we have further preconditions:

(capacity ?t ?n1)
(pred ?n1 ?n2)
(capacity main-track ?n4)
(pred ?n3 ?n4)

The effect on the capacity is the following:

(capacity ?t ?n2)
(not (capacity ?t ?n1))
(capacity main-track ?n3)
(not (capacity main-track ?n4))

The complete code for the action schema pull (the effect's explanation can be found in the comments):

code

    (:action pull
        :parameters (?w1 ?w2 ?w3 - wagon ?t - strack ?n1 ?n2 ?n3 ?n4 - cap-num)
        :precondition (and 
            (head ?w1 ?t)
            (next ?w1 ?w2)
            (head ?w3 main-track)
            (capacity ?t ?n1)
            (pred ?n1 ?n2)
            (capacity main-track ?n4)
            (pred ?n3 ?n4)
            (tail ?w1)                             ; ignore for the moment
        )
        :effect  (and 
            (not (head ?w1 ?t))                    ; ?w1 is not the first wagon on ?t
            (not (head ?w3 main-track))            ; ?w3 is not the last wagon on the outgoing rail
            (not (next ?w1 ?w2))                   ; ?w2 is not next after ?w1
            (head ?w1 main-track)                  ; ?w1 is the last wagon on the outgoing rail
            (next ?w1 ?w3)                         ; the next wagon after ?w1 on the outgoing rail is ?w3   
            (head ?w2 ?t)                          ; ?w2 becomes the new head of ?t
            (capacity ?t ?n2)                      ; the capacity of ?t increases
            (not (capacity ?t ?n1))                
            (capacity main-track ?n3)              ; the capacity of the outgoing rail decreases
            (not (capacity main-track ?n4))
            (tail ?w2)                             ; ignore for the moment
            (not (tail ?w1))                       ; ignore for the moment
            (increase (total-cost) (track-cost ?t)); by applying the action, the plan cost increases by the accessibility cost of ?t
        )
    )

For the moment, ignore the predicate tail in the above definition. We will discuss this later on.

The code for the action schema push is completely dual.

code

    (:action push
        :parameters (?w1 ?w2 ?w3 - wagon ?t - strack ?n1 ?n2 ?n3 ?n4 - cap-num)
        :precondition (and 
            (head ?w1 main-track)
            (next ?w1 ?w2)
            (head ?w3 ?t)
            (capacity ?t ?n2)
            (pred ?n1 ?n2)
            (capacity main-track ?n3)
            (pred ?n3 ?n4)
            (tail ?w3)
        )
        :effect  (and 
            (not (head ?w1 main-track))
            (not (head ?w3 ?t))
            (not (next ?w1 ?w2))
            (head ?w1 ?t)
            (next ?w1 ?w3)
            (head ?w2 main-track)
            (capacity ?t ?n1)
            (not (capacity ?t ?n2))
            (capacity main-track ?n4)
            (not (capacity main-track ?n3))
            (tail ?w1)
            (not (tail ?w3))
            (increase (total-cost) (track-cost ?t))
        )
    )

It remains to encode particular domain instances. We will do it for the example shown above. The problem file defines an initial state. It will correspond to the picture above. Further, it defines a goal that we want to achieve. The skeleton of the problem file looks as follows:

(define (problem p01) (:domain shunting)
 
; initial state goes here
 
; goal definition goes here
 
(:metric minimize (total-cost))
)

The metric section defines an optimal plan, i.e., we want to minimize the plan cost captured by the function total-cost.

To define the initial state, we need to specify our objects. We have eight wagons, three shunting rails, and six capacity numbers (as the largest capacity is five). We don't have to mention the constant objects main-track and empty defined in the domain file.

(:objects
    w1 w2 w3 w4 w5 w6 w7 w8 - wagon
    t1 t2 t3 - strack
    n0 n1 n2 n3 n4 n5 - cap-num
)

Next, we define what ground atoms hold in the initial state. For the capacity numbers, we define the predecessor relation:

    (pred n0 n1)
    (pred n1 n2)
    (pred n2 n3)
    (pred n3 n4)
    (pred n4 n5)

The free wagon slots of the shunting and outgoing rails t1, t2, t3, and main-track are $0,0,3,3$ respectively.

    (capacity t1 n0)
    (capacity t2 n0)
    (capacity t3 n3)
    (capacity main-track n3)

The outgoing rail main-track and the shunting rail t3 are empty.

    (head empty main-track)
    (head empty t3)

The shunting rail t1 holds wagons: $8,5,7,4,2$. Thus we have

    (head w8 t1)
    (next w8 w5)
    (next w5 w7)
    (next w7 w4)
    (next w4 w2) 
    (next w2 empty)

Similarly, the shunting rail t2 holds wagons: $6,3,1$.

    (head w6 t2)
    (tail w6)
    (next w6 w3)
    (next w3 w1)
    (next w1 empty)

To specify the accessibility cost for each shunting rail, we add the following definitions into the init section:

    (= (track-cost t1) 1)
    (= (track-cost t2) 2)
    (= (track-cost t3) 2)

Finally, we define a goal. There is a small issue with its definition. We are in a goal state if the outgoing rail holds the first wagons w1, w2, and w3. As we order them reversely in our representation, we want to achieve the following:

(:goal
    (and 
        (head w3 main-track)
        (next w3 w2)
        (next w2 w1)
 
        ; rest of the train w4 and w5 
    )
)

The rest of the train w4 and w5 must be on a shunting rail. We could define it as follows:

        (or (head w4 t1) (head w4 t2) (head w4 t3))
        (next w4 w5)

Alternatively, we can even use the existential quantifier instead of the disjunction.

        (exists (?t - strack)
           (head w4 ?t))
        (next w4 w5)

However, the above variants need not work. It depends on whether your planner supports disjunctive goals or not. Fast Downward support of disjunctive goals is limited only to satisficing planning. If we want to find an optimal plan, it will complain. So we must get rid of it somehow. We do it via the mysterious unary predicate (tail ?w - wagon). It expresses that a wagon ?w occurs at the beginning of a shunting rail. We add the following ground atoms to the init state, capturing the first wagons for each shunting rail:

    (tail w8)
    (tail w6)
    (tail empty)

Next, we incorporate this predicate into action schemata to update it correctly after each application of pull and push (see the action schemata above). The complete code for the problem file can be found below:

code

(define (problem p01) (:domain shunting)
 
(:objects
    w1 w2 w3 w4 w5 w6 w7 w8 - wagon
    t1 t2 t3 - strack
    n0 n1 n2 n3 n4 n5 - cap-num
)
 
(:init
    (pred n0 n1)
    (pred n1 n2)
    (pred n2 n3)
    (pred n3 n4)
    (pred n4 n5)
 
    (capacity t1 n0)
    (capacity t2 n0)
    (capacity t3 n3)
    (capacity main-track n3)
 
    (= (track-cost t1) 1)
    (= (track-cost t2) 2)
    (= (track-cost t3) 2)
 
    (head empty main-track)
    (head empty t3)
    (tail empty)
    (head w8 t1)
    (tail w8)
    (next w8 w5)
    (next w5 w7)
    (next w7 w4)
    (next w4 w2) 
    (next w2 empty)
 
    (head w6 t2)
    (tail w6)
    (next w6 w3)
    (next w3 w1)
    (next w1 empty)
)   
 
(:goal
    (and 
        (head w3 main-track)
        (next w3 w2)
        (next w2 w1)
        (next w4 w5)
        (tail w4)
    )
)
 
(:metric minimize (total-cost))
)

Now you can try to find an optimal plan using Fast Downward. Executing the following command:

./fast-downward.sif shunting.pddl p01.pddl --search "astar(ipdb())"

returns after 333 seconds the following plan:

pull w8 w5 empty t1 n0 n1 n2 n3 (1)
pull w5 w7 w8 t1 n1 n2 n1 n2 (1)
push w5 w8 empty t3 n2 n3 n1 n2 (2)
pull w7 w4 w8 t1 n2 n3 n1 n2 (1)
pull w4 w2 w7 t1 n3 n4 n0 n1 (1)
push w4 w7 w5 t3 n1 n2 n0 n1 (2)
pull w2 empty w7 t1 n4 n5 n0 n1 (1)
push w2 w7 w4 t3 n0 n1 n0 n1 (2)
pull w6 w3 w7 t2 n0 n1 n0 n1 (2)
push w6 w7 empty t1 n4 n5 n0 n1 (1)
push w7 w8 w6 t1 n3 n4 n1 n2 (1)
push w8 empty w7 t1 n2 n3 n2 n3 (1)
pull w3 w1 empty t2 n1 n2 n2 n3 (2)
push w3 empty w8 t1 n1 n2 n2 n3 (1)
pull w1 empty empty t2 n2 n3 n2 n3 (2)
pull w2 w4 w1 t3 n0 n1 n1 n2 (2)
pull w3 w8 w2 t1 n1 n2 n0 n1 (1)
[t=333.866s, 267540 KB] Plan length: 17 step(s).
[t=333.866s, 267540 KB] Plan cost: 24