MBP: a Model Based Planner

[Top]

Weak, Strong, and Strong Cyclic Planning

In nondeterministic domains, a plan is associated with many possible executions. Therefore, a plan can achieve a goal in different ways:

the plan has a chance of success, i.e. some of its executions achieve the goal ("weak planning");
the plan is guaranteed to achieve the goal for all possible executions ("strong planning");
the plan reaches the goal with an iterative trial-and-error strategy ("strong cyclic solutions"), such that all the associated executions always have a possibility of terminating and, when they do, they achieve the goal.

Intuitively, weak plans operate under an "optimistic" assumption about the environment's behaviour, strong plans operate under a "pessimistic" assumption, and strong cyclic plans assume a "reasonably optimistic" assumption (i.e. that the environment cannot be forever "bad" to the executor of the plan).
A detailed description of the strong, weak, and strong cyclic planning algorithms can be found in this paper.

An example

Consider the robot navigation domain depicted below.

Then, if we intend the robot to reach the final position from its starting position:

1 - A weak plan always exists: GoEast, then GoSouth. Its execution may succeed.

2 - If the door D is always open, a strong plan to reach exists: GoSouth, then GoEast.

3 - If the door D is uncontrollable, so it may open or close anytime, then no strong solution exists, but a strong cyclic solution does: GoSouth, then repeat GoEast until B is reached.

These are the NuPDDL formulations of the domain and problems above:

(define (domain robot_navigation)
(:types room)
(:constants store lab NE_room SW_room dep - room)
(:functions (robot_position) - room)

(:action move_robot_up
     :precondition (or (= (robot_position) SW_room )
                       (= (robot_position) dep     )
                       (= (robot_position) NE_room ))
     :effect (and
               (when (= (robot_position) SW_room ) (assign (robot_position) store
))
               (when (= (robot_position) dep     ) (assign (robot_position) NE_room
))
               (when (= (robot_position) NE_room ) (assign (robot_position) lab
))))

(:action move_robot_down
     :precondition (or (= (robot_position) store   )
                       (= (robot_position) lab     )
                       (= (robot_position) NE_room ))
     :effect (and
               (when (= (robot_position) store   ) (assign (robot_position) SW_room
))
               (when (= (robot_position) lab     ) (assign (robot_position) NE_room
))
               (when (= (robot_position) NE_room ) (assign (robot_position) dep
))))

(:action move_robot_right
     :precondition (or (= (robot_position) SW_room )
                       (= (robot_position) store   ))
     :effect (and
               (when (= (robot_position) SW_room ) (assign (robot_position) dep))
               (when (= (robot_position) store     )
                     (oneof
                        (assign (robot_position) NE_room )
                        (assign (robot_position) lab     )))))

(:action move_robot_left
     :precondition (or (= (robot_position) dep     )
                       (= (robot_position) lab     )
                       (= (robot_position) NE_room ))
     :effect (and
               (when (= (robot_position) dep     ) (assign (robot_position) SW_room
))
               (when (= (robot_position) lab     ) (assign (robot_position) store
))
               (when (= (robot_position) NE_room ) (assign (robot_position) store
))))
)

(define (problem navigation_problem)
        (:domain robot_navigation)
(:init       (= (robot_position) store ))
        (:weakgoal (= (robot_position) dep   )))

(define (problem navigation_problem)
        (:domain robot_navigation)
(:init       (= (robot_position) store ))
        (:stronggoal (= (robot_position) dep   )))

(define (problem navigation_problem)
        (:domain robot_navigation)
(:init       (= (robot_position) store ))
        (:strongcyclicgoal (= (robot_position) dep   )))

To solve the problems, run

MBP-solve -plan_output - <domain> <problem>

where <domain> and <problem> are the domain and one of the problems above.