Abstract
Autonomous agents operating in partially observable environments must often manage finite resources, such as battery life, while pursuing specific goals. Standard planning algorithms frequently prioritize expected cost over absolute safety, leading to potential resource exhaustion. We introduce FiPOMDP, a framework that combines formal safety guarantees with heuristic planning. By pre-computing a "shield"—a safety filter that prunes risky actions—FiPOMDP ensures 100% survival in Resource-constrained Goal Optimization (RSGO) problems. Experimental results across various benchmarks, including a large-scale Manhattan routing task, demonstrate that FiPOMDP maintains perfect safety where unshielded baselines fail, with manageable computational overhead.
Introduction
Consider an autonomous underwater vehicle (UUV) navigating a grid with stochastic currents and noisy sensors. To reach its destination, it must manage a limited battery, recharging only at specific stations. In AI, this is modeled as a Partially Observable Markov Decision Process (POMDP). While modern solvers like POMCP are effective at optimizing paths, they often ignore "hard" safety constraints. An agent might choose a shortcut that is efficient on average but carries a non-zero risk of stranding the vehicle.
The Resource-constrained Goal Optimization (RSGO) problem seeks to reach a goal at minimum expected cost while guaranteeing that the agent never runs out of resources. Previous approaches often required perfect information or lacked cost-optimization capabilities.
Methodology: The FiPOMDP Framework
The authors propose a two-stage approach to solve RSGO problems:
1. The Safety Shield
The core innovation is a "shield" ($\sigma$) that acts as a protective layer. Before an action is executed, the shield verifies if it could lead to resource exhaustion or a "trap"—a state from which the goal is unreachable given the remaining fuel.
To compute this shield efficiently, the authors use Threshold Levels. Instead of tracking every possible resource level, they determine the minimum resource required at any given "belief support" (the set of possible states the agent might be in) to guarantee safety. This is achieved by transforming the POMDP into a "Token Consumption MDP," allowing the use of formal verification tools to find these safety thresholds.
2. Integration with POMCP
The pre-computed shield is integrated into POMCP, a popular online planning algorithm based on Monte Carlo Tree Search. During the search process, the shield prunes unsafe branches of the tree, ensuring the agent only considers trajectories that are guaranteed to be safe.
Experimental Evaluation
FiPOMDP was evaluated on three benchmarks:
- Resource-constrained Tiger: A classic problem modified to include energy consumption for listening actions.
- UUV Grid-world: Navigation tasks in grids up to 20x20 with stochastic drift and noisy sensors.
- Manhattan AEV: A large-scale routing problem using real-world Uber Movement traffic data and Department of Energy charging station locations, involving over 22,000 states.
Key Results and Discussion
The empirical evaluation highlights the fragility of unshielded agents in resource-critical scenarios. As shown in the table below, FiPOMDP achieved a 100% survival rate across all tests.
In contrast, the unshielded POMCP baseline failed significantly as environment complexity increased. For instance, in the 16x16 UUV grid, the unshielded agent ran out of fuel 96% of the time (achieving only a 4% survival rate). While the shielded agent may take longer paths to ensure safety—reflected in higher average costs in some "fuzzy" scenarios—it is the only method that reliably completes the task.
Furthermore, the shield computation proved efficient. Even for the massive Manhattan AEV model, the shield was generated in just 65 seconds, demonstrating the scalability of the threshold-based approach.
Conclusion
FiPOMDP successfully decouples safety logic from planning logic, providing a modular solution for resource-constrained navigation. By treating safety as a non-negotiable qualitative constraint, the framework ensures 100% survival without sacrificing the ability to optimize for cost. Future work will explore combining this shielding technique with other modern POMDP solvers to further improve goal-reaching efficiency in highly uncertain environments.
Summary updated