Abstract
Solving large-scale Partially Observable Markov Decision Processes (POMDPs) remains a significant challenge due to the exponential growth of state and observation spaces. This paper introduces Anytime Error Minimization Search (AEMS), an online algorithm that leverages approximate offline value functions to guide real-time search. By prioritizing the expansion of nodes that contribute most to the uncertainty of the current decision—measured as the expected error gap between upper and lower value bounds—AEMS efficiently refines policies within strict time constraints. Experimental results on the RockSample and FieldVisionRockSample benchmarks demonstrate that AEMS significantly outperforms existing online search methods, particularly in environments with large observation spaces.
Introduction
The "curse of dimensionality" often renders offline POMDP solvers impractical for complex real-world tasks. While online methods offer a localized alternative by planning from the current belief state, they frequently struggle to achieve sufficient search depth under real-time constraints. AEMS bridges this gap by using an "anytime" search strategy that starts with a rough offline policy and iteratively improves it. The core philosophy of AEMS is to focus search effort where it matters most: on future scenarios that are likely to occur and where the current policy is most uncertain.
The AEMS Algorithm
AEMS operates by building an AND-OR search tree from the current belief state. The algorithm's efficiency stems from its Expected Error Evaluation heuristic, which selects nodes for expansion based on their potential to reduce the error in the root's value estimate.
The heuristic considers three primary factors: the error gap ($\hat{\epsilon}$) between optimistic and pessimistic value estimates, the probability ($P$) of reaching a specific belief state, and the discount factor ($\gamma$). The paper explores two variants: AEMS1, which uses a uniform distribution for action optimality, and AEMS2, a more focused version that prioritizes actions with the highest upper bounds. AEMS is inherently "anytime," allowing it to provide the best-found action whenever a decision is required.
Experimental Evaluation
The authors evaluated AEMS against state-of-the-art algorithms using the RockSample (RS) benchmark and a new, more complex variant called FieldVisionRockSample (FVRS). FVRS significantly increases the observation space by allowing the agent to perceive all rocks simultaneously, testing the algorithm's robustness to high-dimensional sensor data.
Results and Discussion
In all benchmarks, AEMS demonstrated superior performance compared to algorithms like Satia-Lave, BI-POMDP, and RTBSS. Notably, AEMS2 often outperformed AEMS1, suggesting that focusing search on the most promising actions is more effective than exploring all potentially optimal actions.
As shown in the RockSample results, AEMS2 consistently achieved higher rewards and greater error reduction within a 1-second planning window. For instance, in the large-scale RS(7,8) task, AEMS2 improved the average reward from a baseline of 7.7 (PBVI) to 21.3. The algorithm's ability to reuse search trees across time steps further enhances its real-time viability.
Conclusion
AEMS represents a significant step forward in online POMDP planning. By intelligently guiding search through error minimization, it enables high-quality decision-making in domains previously considered too large for online search. Future research will focus on handling cyclic belief graphs and refining the heuristic models for action optimality.
Summary updated