Heuristic Search for SSPs with Lexicographic Preferences over Multiple Costs

Authors

  • Shuwa Miura Manning College of Information and Computer Sciences , University of Massachusetts Amherst
  • Kyle Hollins Wray Alliance Innovation Lab Silicon Valley
  • Shlomo Zilberstein Manning College of Information and Computer Sciences , University of Massachusetts Amherst

Keywords:

Problem Solving Using Search

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.

Downloads

Published

2022-07-17