Paper Info
Title
Towards faster planning with continuous resources in stochastic domains
Abstract
Agents often have to construct plans that obey resource limits for continuous resources whose consumption can only be characterized by probability distributions. While Markov Decision Processes (MDPs) with a state space of continuous and discrete variables are popular for modeling these domains, current algorithms for such MDPs can exhibit poor performance with a scale-up in their state space. To remedy that we propose an algorithm called DPFP. DPFP's key contribution is its exploitation of the dual space cumulative distribution functions. This dual formulation is key to DPFP's novel combination of three features. First, it enables DPFP's membership in a class of algorithms that perform forward search in a large (possibly infinite) policy space. Second, it provides a new and efficient approach for varying the policy generation effort based on the likelihood of reaching different regions of the MDP state space. Third, it yields a bound on the error produced by such approximations. These three features conspire to allow DPFP's superior performance and systematic trade-off of optimality for speed. Our experimental evaluation shows that, when run stand-alone, DPFP outperforms other algorithms in terms of its any-time performance, whereas when run as a hybrid, it allows for a significant speedup of a leading continuous resource MDP solver.
Year
Venue
Keywords
2008
AAAI
poor performance,stochastic domain,policy space,dual formulation,dual space,continuous resource,any-time performance,state space,mdp state space,towards faster planning,leading continuous resource mdp,superior performance,homeland security,cumulant,probability distribution
Field
DocType
Citations 
Mathematical optimization,Computer science,Dual space,Markov decision process,Probability distribution,Cumulative distribution function,Artificial intelligence,Solver,State space,Machine learning,Speedup
Conference
8
PageRank 
References 
Authors
0.46
11
2
Name
Order
Citations
PageRank
Janusz Marecki168549.06
Milind Tambe26008522.25