Heuristic Search for SSPs with Lexicographic Preferences over Multiple Costs

SOCS-22 Volume 15

Volume

Vol. 15 No. 1 (2022): Fifteenth International Symposium on Combinatorial Search

Long Papers

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.

10.1609/socs.v15i1.21760