[Top]
 

NuPDDL: nondeterminism and more in PDDL


Main features


PDDL compatibility

NuPDDL retains most of PDDL2.1, including the handling of functions, conditional effects, and quantifiers. In NuPDDL, arbitrary nesting of conditional effects and/or quantifiers is legal.

In the current NuPDDL version, the following restrictions apply:
- every object/function must be typed
- no nested functions is allowed
- axioms are not handled

Here is an example of a deterministic domain showing most of the features above.


Uncertainty in the initial state

NuPDDL introduces the oneof keyword to represent uncertainty in the initial state.
Oneof takes as argument a list of propositions: (oneof f1 f2 .. fn) . Intuitively, one of the formulas must hold for the oneof clause to hold.

Consider the example initial situation below, which also highlights the way oneof interacts with the closed-world assumption (CWA):

(define (domain d) ... (:predicates (P1) (P2) (P3) (P4) (P5) (P6)) ...)

(define (problem p)
   ....
   (:init (and (P1) (oneof (and (P2) (P3)) (P4)) (unknown (P5))))
   ....)

These are the admitted models in the initial situation (T stands for True, F for False):


(P1)
(P2)
(P3)
(P4)
(P5)
(P6)
T
T
T
F
T
F
T
F
F
T
T
F
T
T
T
F
F
F
T
F
F
T
F
F

Notice that (P6) is always False due to the CWA, and that, when (P4) is True, (P2) and (P3) are False for the same reason.

NuPDDL also introduces the unknown keyword, expressing oneof upon any possible value of a given function (or predicate).

Here is some example of uncertain initial situations.


Nondeterministic action effects

The keywords oneof and unknown are also used, in NuPDDL, to represent nondeterministic action effects. In this context, (oneof f1 f2 ... fn) represents the fact that after executing the action, one of the formulas is required to hold (and nothing is required abouth the other formulas).
Consider the nondeterministic effect below, which also shows the way unknown interacts with inertia.

(define (domain d) ... (:predicates (P1) (P2) (P3) (P4) (P5) (P6)) ...)

(define (problem p)
   ....
   (:effect (and (P1) (oneof (and (P2) (P3)) (P4)) (unknown (P5))))
   ....)

These are the admitted models of the next values of the predicates:


(P1)'
(P2)'
(P3)'
(P4)'
(P5)'
(P6)'
T
T
T
(P4)
T
(P6)
T
(P2)
(P3)
T
T
(P6)
T
T
T
(P4)
F
(P6)
T
(P2)
(P3)
T
F
(P6)

Similarly, (unknown f) represents the fact that after executing the action, f may have any value.

Here is some example of nondeterministic action effects.


Partial observability

NuPDDL allows specifying partially observable domains by stating what can be observed, and how this is related to the domain state. This is obtained by describing boolean observations, in the form of formulas that may represent perfect or non-perfect sensing. Observations are parametric.

Consider the example below. It describes a perfect robot sensor wall_north and a non-perfect robot sensor wall_east (if the sensor is on, the wall can be there or not)

(define (domain simple_robot)
  (:types x_coord y_coord)
  (:constants east west - x_coord
              north south - y_coord)
  (:functions
      (robot_x) - x_coord
      (robot_y) - y_coord)

  ;....
  ;....
  (:observation wall_north - boolean
     :parameters ()
     (iff (= wall_north 1)
            (or (= (robot_y) north) (= (robot_x) west))))
 
 

  ;....
  (:observation wall_east - boolean
     :parameters ()
     (imply (= wall_east 0)
            (= (robot_x) west))
     (imply (= wall_east 1)
            (true))
  ;....
  ;....
)

Here is another example of a partially observable domain.


Problem classes

NuPDDL allows specifying several problem classes, which differ by the required "strength" of the plan, by the assumed degree of observability upon the domain status, and by the fact that goals may involve sequences of states rather than focus on the final states only.

These are the keywords introduced in NuPDDL:


Here you can see an example of a CTL goal. In the examples you can download here, several of these goals are represented.


Plan language

NuPDDL embeds a powerful plan language that reflects the idea that a plan is a finite state machine. NuPDDL's plan language easily represents standard sequential plans, as well as more complex bplans with branching and/or looping, and provides the user with a set of imperative-style primitives.

The plan language has the following main features:
- plans may feature an internal state
- a plan execution step results in evolving the plan's state, and producing an action that is provided to the domain
- the evolution of the finite state machine is described based on conditions upon the plan's state and the observable part of the domain's state.

This nonsensical example shows most of the features of the plan language:

(define (plan silly_plan)
        (:domain robot_navigation)
        (:problem navigation_problem)
        (:planvars visited_lab - boolean
                   visited_SW_room_no - (range 0 10))
        (:init
            (= (visited_SW_room_no) 0)
            (= (visited_lab) 0)
        )
        (:body
            (sequence
                (while (< (visited_lab) 10)
                    (sequence
                       (evolve (assign
                                  (next (visited_SW_room_no))
                                  (+ (visited_SW_room_no) 1))
                               (action (move_robot_down)))
                       (action (move_robot_up))))
                (action (move_robot_right))
                (label i_am_in_lab (if (= (robot_position) lab)
                    (sequence
                      (evolve
                              (assign (next(visited_lab)) 1)
                              (action (move_robot_down)))
                      (action (move_robot_down)))
                    (action (move_robot_down))))
                (switch
                   (case (= (robot_position) dep) (done))
                   (case (= (robot_position) lab) (goto i_am_in_lab))
                   (case (= (robot_position) store) (fail))
                   (else (fail))))))

In the examples you can download here, some more sensible plans are represented.


Acknowledgements

NuPDDL started on a note on extending PDDL with nondeterminism, by Blai Bonet, Alessandro Cimatti, Enrico Giunchiglia, Keith Golden, Jussi Rintanen, David E. Smith.
Also, it profited of valuable discussions with the participants to the AIPS'02 Planning as Model Checking Tutorial. Suggestions are very welcome: write to mbp@fbk.eu.