Heuristic Search for SSPs with Lexicographic Preferences over Multiple Costs

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.

• Publication year

  2022

• Venue

  Symposium on Combinatorial Search

• Publication date

  2022-07-17

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1609/socs.v15i1.21760
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Engine Activation Planning for Series Hybrid Electric Vehicles

  2021influential reference
• A Multi-Objective Approach to Mitigate Negative Side Effects

  2020cited by this paper
• A multicriteria Master Planning DSS for a sustainable humanitarian supply chain

  2018cited by this paper
• Lexicographic multi-objective linear programming using grossone methodology: Theory and algorithm

  2018cited by this paper
• Multiobjective Optimal Control With Safety as a Priority

  2018cited by this paper
• I-dual: Solving Constrained SSPs via Heuristic Search in the Dual Space

  2017cited by this paper
• Occupation Measure Heuristics for Probabilistic Planning

  2017cited by this paper
• Multi-Objective Decision Making

  2017cited by this paper
• Heuristic Search in Dual Space for Constrained Stochastic Shortest Path Problems

  2016influential reference
• Multi-Objective MDPs with Conditional Lexicographic Reward Preferences

  2015influential reference
• Revisiting Multi-Objective MDPs with Relaxed Lexicographic Preferences

  2015influential reference
• SAVES: a sustainable multiagent application to conserve building energy considering occupants

  2012cited by this paper
• A dual-based algorithm for solving lexicographic multiple objective programs

  2007cited by this paper
• The First Probabilistic Track of the International Planning Competition

  2005cited by this paper
• Multi-objective decision-theoretic path planning

  2004influential reference
• PPDDL 1 . 0 : An Extension to PDDL for Expressing Planning Domains with Probabilistic Effects

  2004cited by this paper
• Labeled RTDP: Improving the Convergence of Real-Time Dynamic Programming

  2003influential reference
• LAO*: A heuristic search algorithm that finds solutions with loops

  2001influential reference
• Constrained Markov Decision Processes

  1999influential reference
• Constrained discounted Markov decision processes and Hamiltonian cycles

  1997influential reference
• An Analysis of Stochastic Shortest Path Problems

  1991cited by this paper
• Linear lexicographic optimization

  1982influential reference
• A Probabilistic Production and Inventory Problem

  1963cited by this paper

• Generalizing Multi-Objective Search via Objective-Aggregation Functions

  2025cites this paper
• Markov Decision Processes with Sure Parity and Multiple Reachability Objectives

  2024cites this paper
• Beyond Markov Decision Process with Scalar Markovian Rewards

  2022influential citation