RAPID: A Reachable Anytime Planner for Imprecisely-sensed Domains

Emma Brunskill, Stuart Russell

Abstract

RAPID is a novel planning algorithm designed to scale Partially Observable Markov Decision Processes (POMDPs) to massive state spaces, reaching up to $10^{30}$ states. By exploiting the topological structure of learning hierarchies—specifically "Unique Preconditions"—RAPID focuses its computational effort on a reachable "envelope" of states. This approach enables sophisticated automated tutoring in domains that are computationally intractable for generic solvers.

Introduction

Decision-making under uncertainty is a cornerstone of artificial intelligence, often modeled via Partially Observable Markov Decision Processes (POMDPs). These models account for both environmental randomness and imperfect observations, such as a student's latent understanding of a concept. However, generic POMDP planning is notoriously difficult (PSPACE-complete). As the number of variables grows, the state space explodes exponentially—a phenomenon known as the "curse of dimensionality."

Standard solvers often fail on problems with more than a few dozen variables. Yet, many real-world applications, like automated tutoring, involve hundreds of skills. RAPID addresses this gap by identifying and leveraging specific structural properties common in these domains, allowing it to scale to problems of unprecedented size.

The RAPID Algorithm

RAPID targets a specific class of problems defined as POFUP processes: Factored states, Positive-Only effects (skills are not forgotten), and Unique Preconditions (each skill has exactly one set of prerequisites).

The relationship between a precondition graph and its corresponding state space.

The core innovation of RAPID lies in its four-step workflow:

  1. Deterministic Relaxation: The algorithm initially ignores uncertainty to treat the problem as a simple reachability task. It uses the precondition graph to find a valid path from the start to the goal in linear time ($O(L)$ where $L$ is the number of variables).
  2. Initial Envelope: This path forms an "envelope"—a tiny subset of the massive state space where the agent is most likely to operate.
  3. POMDP Planning: RAPID solves a POMDP only over this envelope. States outside the envelope are lumped into a single "out" state with a high penalty to discourage the agent from wandering into unknown territory.
  4. Anytime Expansion: As more computation time becomes available, RAPID identifies new reachable states to grow the envelope, gradually refining the policy.

Experimental Evaluation

The paper evaluates the algorithm on two tutoring-inspired simulations based on established educational learning hierarchies.

A learning hierarchy for elementary mathematics used to evaluate RAPID.
  • SmallMath: 19 elementary math skills, resulting in ~500,000 possible states.
  • BigMath: A massive curriculum of 122 skills (addition, subtraction, multiplication, and fractions). This creates a state space of $2^{122} \approx 10^{30}$ states—roughly the number of bacterial cells on Earth.

Key Results and Insights

  • Breaking the Scale Barrier: RAPID successfully generated policies for the BigMath domain ($10^{30}$ states). In contrast, state-of-the-art generic solvers like SARSOP and Symbolic Perseus failed to even initialize on the much smaller SmallMath domain.
  • Outperforming Heuristics: RAPID was compared against the common Fixed Threshold, No-Forgetting (FTNF) heuristic used in Intelligent Tutoring Systems. RAPID consistently achieved higher rewards because it could "look ahead" and infer mastery of earlier skills based on performance in complex tasks.
  • Topological Advantage: The "Unique Preconditions" assumption allows the algorithm to compute an optimal MDP policy (an upper bound) in linear time, providing a high-quality "skeleton" for the POMDP planner.

Conclusion and Future Work

RAPID demonstrates that domain-specific topology can break the scale barrier of POMDPs. While the current model assumes known transition and observation probabilities, future work aims to learn these from student data. Additionally, the authors suggest that reusing "alpha-vectors" from previous iterations during envelope expansion could lead to significant computational speedups.

Summary updated

Abstract

Despite the intractability of generic optimal partially observable Markov decision process planning, there exist important problems that have highly structured models. Previous researchers have used this insight to construct more efficient algorithms for factored domains, and for domains with topological structure in the flat state dynamics model. In our work, motivated by findings from the education community relevant to automated tutoring, we consider problems that exhibit a form of topological structure in the factored dynamics model. Our Reachable Anytime Planner for Imprecisely-sensed Domains (RAPID) leverages this structure to efficiently compute a good initial envelope of reachable states under the optimal MDP policy in time linear in the number of state variables. RAPID performs partially-observable planning over the limited envelope of states, and slowly expands the state space considered as time allows. RAPID performs well on a large tutoring-inspired problem simulation with 122 state variables, corresponding to a flat state space of over 10^30 states.
BibTeX
@misc{brunskill2010rapid,
  author = {Emma Brunskill and Stuart Russell},
  title = {{RAPID: A Reachable Anytime Planner for Imprecisely-sensed Domains}},
  year = {2010},
  eprint = {1203.3538},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1203.3538},
}
Figure