Abstract
This paper addresses the challenge of synthesizing optimal strategies for systems characterized by uncertain transition probabilities, modeled as Interval Markov Decision Processes (IMDPs). We investigate the multi-objective robust strategy synthesis problem, where a controller seeks to satisfy multiple conflicting objectives (e.g., safety vs. performance) against an adversarial environment. We prove that this problem is PSPACE-hard and propose a novel value-iteration algorithm to approximate the Pareto curve of optimal trade-offs. Our methodology is evaluated on complex case studies, including robot motion planning and autonomous tour guides, demonstrating practical efficiency and the ability to generate diverse control strategies.
Introduction
In traditional Markov Decision Processes (MDPs), transition probabilities between states are assumed to be precisely known. However, in real-world applications like robotics or logistics, environmental noise and sensor inaccuracies lead to inherent uncertainty. Interval MDPs (IMDPs) provide a more realistic framework by defining transition probabilities within specified ranges or intervals.
The complexity increases when multiple, often conflicting, objectives must be satisfied simultaneously. For instance, an autonomous robot must balance reaching a destination quickly (efficiency) with avoiding obstacles (safety). This paper focuses on "robust" synthesis, ensuring that the chosen strategy remains effective even when an "adversarial nature" selects the most unfavorable transition probabilities within the allowed intervals.
Problem Formulation and Complexity
An IMDP extends the standard MDP by replacing fixed transition probabilities with intervals $[L, U]$. The core challenge lies in the dual-optimization nature of the problem: the controller aims to maximize the probability of success or minimize costs, while the environment (nature) acts as an adversary to minimize the controller's performance.
We formally establish that the multi-objective robust strategy synthesis problem for IMDPs is PSPACE-hard. This indicates that while the problem is computationally demanding, it remains solvable within polynomial memory constraints.
Methodology
To address the multi-objective nature of the problem, we employ a weight-based normalization approach, converting multiple objectives into a single weighted sum. By iteratively varying these weights, we can explore the trade-off space.
Robust Value Iteration
We introduce a robust value-iteration algorithm specifically designed for IMDPs. At each step, the algorithm solves a minimax problem. To handle the non-linear nature of the uncertainty, we utilize the dual of a Linear Program (LP). This conversion allows us to solve the inner optimization (nature's choice) efficiently using standard linear optimization techniques.
Pareto Curve Approximation
Our approach approximates the Pareto set—the collection of optimal strategies where no objective can be improved without degrading another. The algorithm uses geometric approximation, identifying "separating hyperplanes" to find gaps in the current Pareto front and optimizing new weight vectors to fill those gaps, effectively growing the known set of optimal trade-offs.
Experimental Evaluation
The proposed algorithms were implemented and tested on two primary case studies:
- Robot Motion Planning: A grid-based environment with 204 states where a robot navigates noisy dynamics to reach a target. The objectives were maximizing safety (reachability) versus minimizing energy consumption.
- Autonomous Tour Guides (ANTG): A scalable museum model where a visitor seeks to reach an exit while minimizing penalties from visiting closed exhibitions.
Despite the theoretical PSPACE-hardness, our tool solved these scenarios in a matter of seconds on standard hardware. The results provided clear visualizations of the Pareto curves, allowing for the synthesis of specific strategies ranging from "reckless" (fast but high risk) to "conservative" (slow but zero penalty).
Conclusion and Future Work
This work provides a robust framework for multi-objective decision-making under transition uncertainty. While the current approach is efficient for hundreds of states, future work will address the "curse of dimensionality" for larger systems and extend the synthesis to more complex specifications, such as those defined by Linear Temporal Logic (LTL).
Summary updated