Abstract
Recently, "determinization in hindsight" has enjoyed surprising success in on-line probabilistic planning. This technique evaluates the actions available in the current state by using non-probabilistic planning in deterministic approximations of the original domain. Although the approach has proven itself effective in many challenging domains, it is computationally very expensive. In this paper, we present three significant improvements to help mitigate this expense. First, we use a method for detecting potentially useful actions, allowing us to avoid estimating the values of unnecessary ones. Second, we exploit determinism in the domain by reusing relevant plans rather than computing new ones. Third, we improve action evaluation by increasing the chance that at least one deterministic plan reaches a goal. Taken together, these improvements allow determinization in hindsight to scale significantly better on large or mostly-deterministic problems.
Introduction
Probabilistic planning addresses the inherent uncertainty of real-world environments, such as a robot navigating a warehouse where actions like "pick up box" may fail. Calculating a complete policy for every possible state is often computationally intractable. A common shortcut is determinization: treating the world as certain and replanning when expectations fail. While fast, this "naive" approach often fails in "probabilistically interesting" domains where risk assessment is critical.
Determinization in Hindsight (DH) offers a more sophisticated alternative by sampling multiple potential "futures" and selecting actions based on their average performance across these samples. However, DH is computationally intensive, scaling linearly with both the number of samples and the number of available actions. This paper introduces FF-Hindsight+, which optimizes this process through three key enhancements.
Methods: The FF-Hindsight+ System
- Probabilistically Helpful Actions (PHA): Instead of evaluating every possible action at a given state, the planner identifies a subset of "helpful" actions that actually contribute to successful plans in sampled futures. By focusing deep evaluation only on these actions, the search space is drastically reduced.
- Deterministic Action Sequence Detection: The algorithm identifies sequences of actions that remain identical across all sampled plans. These are executed as "macros," bypassing expensive replanning for deterministic segments of the problem.
- All-Outcome Determinization Mixing: To prevent the planner from missing rare but essential outcomes (e.g., a low-probability "zoom" action), the system mixes in a determinization where every possible outcome is treated as an available action. This provides a necessary "safety net" for finding paths that rely on unlikely events.
Key Insights
- The Power of Pruning: In domains like Random or Boxworld, up to 90% of available actions are irrelevant to the goal. PHA effectively filters this noise, leading to massive speedups.
- Exploiting Local Certainty: Even in uncertain environments, plans often contain "pockets" of determinism. Recognizing these allows the planner to "coast" through easy sections and save its computational budget for hard decisions.
- Tempering Optimism: Determinization is inherently optimistic. By re-weighting solutions and incorporating all-outcome determinizations, FF-Hindsight+ becomes more robust in domains where success hinges on rare events.
Key Results
The system was evaluated using benchmarks from the International Probabilistic Planning Competitions (IPPC). FF-Hindsight+ demonstrated superior scalability and performance across a wide range of domains.
As shown in the results table, FF-Hindsight+ solved a total of 468 rounds, significantly outperforming the original FF-Hindsight (365 rounds) and the competition-winning FF-Replan (414 rounds). Notably, in the challenging "Tireworld" domain, FF-Hindsight+ was the only planner capable of solving the "17-tire" instance. Furthermore, in Zenotravel, the system utilized deterministic sequences for nearly 70% of its actions, showcasing the efficiency gains from plan reuse.
Limitations and Future Work
While highly effective, PHA can occasionally be "misled" by risky, short-term actions that appear better in deterministic samples than safer, multi-step alternatives. Future work may involve "adaptive sampling" using techniques like Hoeffding races to dynamically determine the necessary number of samples, further optimizing performance. Additionally, the system's reliance on off-the-shelf deterministic solvers like FF means it can be limited by the robustness and syntax compatibility of those underlying tools.
Summary updated