Heuristic Search for SSPs with Lexicographic Preferences over Multiple Costs
Citations Over Time
Abstract
Real-world decision problems often involve multiple competing objectives. The Stochastic Shortest Path (SSP) with lexicographic preferences over multiple costs offers an expressive formulation for many practical problems. However, the existing solution methods either lack optimality guarantees or require costly computations over the entire state space. We propose the first heuristic algorithm for this problem, based on the heuristic algorithm for Constrained SSPs. Our experiments show that our heuristic search algorithm can compute optimal policies while avoiding a large portion of the state space. We further analyze the theoretical properties of the problem, showing the conditions under which SSPs with lexicographic preferences have a proper optimal policy.
Related Papers
- → A Survey of Heuristic Search Method of Multimodal Optimum Point(1974)6 cited
- Experimental Study of Heuristic Search Method for Two-Dimensional Multimodal Optimum Point.(1971)
- → Bidirectional Heuristic Search Reconsidered(1997)1 cited
- → Nested Search versus Limited Discrepancy Search(2022)1 cited