Fast Incremental Policy Compilation from Plans in Hybrid Probabilistic Domains

We present the domain-independent HRFF algorithm, which solves goal-oriented HMDPs by incrementally aggregating plans generated by the METRIC-FF planner into a policy defined over discrete and continuous state variables. HRFF takes into account non-monotonic state variables, and complex combinations of many discrete and continuous probability distributions. We introduce new data structures and algorithmic paradigms to deal with continuous state spaces: hybrid hierarchical hash tables, domain determinization based on dynamic domain sampling or on static computation of probability distributions' modes, optimization settings under METRIC-FF based on plan probability and length. We deeply analyze the behavior of HRFF on a probabilistically-interesting structured navigation problem with continuous dead-ends and non-monotonic continuous state variables. We compare with HAO* on the Rover domain and show that HRFF outperforms HAO* by many order of magnitudes in terms of computation time and memory usage. We also experiment challenging and combinatorial HMDP versions of benchmarks from numeric classical planning.

• Publication year

  2012

• Venue

  International Conference on Automated Planning and Scheduling

• Publication date

  2012-05-14

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1609/icaps.v22i1.13519
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Heuristic Search Approach to Planning with Continuous Resources in Stochastic Domains

  2014influential reference
• 数値計算のためのGNU Scientific Libraryの紹介(教育講座)

  2012cited by this paper
• Automatic Construction of Efficient Multiple Battery Usage Policies

  2011cited by this paper
• Incremental plan aggregation for generating policies in MDPs

  2010cited by this paper
• Classical Planning in MDP Heuristics: with a Little Help from Generalization

  2010cited by this paper
• A Hierarchical Hashing Scheme for Nearest Neighbor Search and Broad-Phase Collision Detection

  2009cited by this paper
• Probabilistic Planning via Determinization in Hindsight

  2008influential reference
• A Fast Analytical Algorithm for Solving Markov Decision Processes with Real-Valued Resources

  2007cited by this paper
• Solving Factored MDPs with Hybrid State and Action Variables

  2006influential reference
• Lazy Approximation for Solving Continuous Finite-Horizon MDPs

  2005cited by this paper
• PPDDL 1 . 0 : An Extension to PDDL for Expressing Planning Domains with Probabilistic Effects

  2004influential reference
• Adaptive state space partitioning for reinforcement learning

  2004cited by this paper
• The Metric-FF Planning System: Translating ''Ignoring Delete Lists'' to Numeric State Variables

  2003cited by this paper
• PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains

  2003cited by this paper
• Planning Under Continuous Time and Resource Uncertainty: A Challenge for AI

  2002influential reference

• Automated Planning and Acting

  2016cites this paper
• Solving Goal Hybrid Markov Decision Processes Using Numeric Classical Planners

  2012cites this paper
• Planning with Markov Decision Processes: An AI Perspective

  2012cites this paper