Probabilistic Temporal Planning with Uncertain Durations

AAAI Conferences

Few temporal planners handle both concurrency and uncertain durations, but these features commonly cooccur in realworld domains. In this paper, we discuss the challenges caused by concurrent, durative actions whose durations are uncertain.


Planning with Durative Actions in Stochastic Domains

Journal of Artificial Intelligence Research

Probabilistic planning problems are typically modeled as a Markov Decision Process (MDP). MDPs, while an otherwise expressive model, allow only for sequential, non-durative actions. This poses severe restrictions in modeling and solving a real world planning problem. We extend the MDP model to incorporate -- 1) simultaneous action execution, 2) durative actions, and 3) stochastic durations.We develop several algorithms to combat the computational explosion introduced by these features. The key theoretical ideas used in building these algorithms are -- modeling a complex problemas an MDP in extended state/action space, pruning of irrelevant actions, sampling of relevant actions, using informed heuristics to guide the search, hybridizing different planners to achieve benefits of both, approximating the problem and replanning. Our empirical evaluation illuminates the different merits in using various algorithms, viz., optimality, empirical closeness to optimality, theoretical error bounds, and speed.


Planning with Durative Actions in Stochastic Domains

AAAI Conferences

Probabilistic planning problems are typically modeled as a Markov Decision Process (MDP). MDPs, while an otherwise expressive model, allow only for sequential, non-durative actions. This poses severe restrictions in modeling and solving a real world planning problem. We extend the MDP model to incorporate -- 1) simultaneous action execution, 2) durative actions, and 3) stochastic durations. We develop several algorithms to combat the computational explosion introduced by these features. The key theoretical ideas used in building these algorithms are -- modeling a complex problem as an MDP in extended state/action space, pruning of irrelevant actions, sampling of relevant actions, using informed heuristics to guide the search, hybridizing different planners to achieve benefits of both, approximating the problem and replanning. Our empirical evaluation illuminates the different merits in using various algorithms, viz., optimality, empirical closeness to optimality, theoretical error bounds, and speed.


Concurrent Probabilistic Temporal Planning

AAAI Conferences

Probabilistic planning problems are often modeled as Markov decision processes (MDPs), which assume that a single action is executed per decision epoch and that actions take unit time. However, in the real world it is common to execute several actions in parallel, and the durations of these actions may differ. This paper presents efficient methods for solving probabilistic planning problems with concurrent, durative actions. We adapt the formulation of Concurrent MDPs, MDPs which allow multiple instantaneous actions to be executed simultaneously. We add explicit action durations into the concurrent MDP model by encoding the problem as a concurrent MDP in an augmented state space. We present two novel admissible heuristics and one inadmissible heuristic to speed up the basic concurrent MDP algorithm. We also develop a novel notion of hybridizing an optimal and an approximate algorithm to yield a hybrid algorithm, which quickly generates highquality policies. Experiments show that all our heuristics speedup the policy construction significantly. Furthermore, our approximate hybrid algorithm runs up to two orders of magnitude faster than other methods, while producing policies whose make-spans are typically within 5% of optimal.


Concurrent Probabilistic Temporal Planning: Initial Results

AAAI Conferences

Probabilistic planning problems are often modeled as Markov decision problems (MDPs), which assume that a single action is executed per decision epoch and that actions take unit time. However, in the real world it is common to execute several actions in parallel, and the durations of these actions may differ. This paper presents our ongoing work on incorporating concurrent, durative actions in probabilistic planning. In particular we describe Concurrent MDPs, MDPs which allow multiple instantaneous actions to be executed simultaneously, and present two algorithms which perform orders of magnitude faster than naive approaches. We then add explicit action durations into our model and encode them as concurrent MDPs in an augmented state space. We present a novel heuristic and prove it admissible. Initial experimental results demonstrate the promise of our approach, showing speedup due to both the heuristic and our sampled RTDP algorithm.