# Probabilistic Planning with Partially Ordered Preferences over Temporal Goals

arXiv: https://arxiv.org/abs/2209.12267 · HTML: https://mlsanity.com/paper/2209.12267/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 18 references that are in the map.
- First posted on arXiv 25 Sep 2022.

## Builds on (most cited first, 6 of 6)

- [A Survey of Multi-Objective Sequential Decision-Making](https://mlsanity.com/paper/1402.0590/) (2014)
- [Specifying User Preferences using Weighted Signal Temporal Logic](https://mlsanity.com/paper/2010.00752/) (2020)
- [Optimal Probabilistic Motion Planning with Potential Infeasible LTL Constraints](https://mlsanity.com/paper/2007.14325/) (2020)
- [What to Do When You Can't Do It All: Temporal Logic Planning with Soft Temporal Logic Constraints](https://mlsanity.com/paper/2008.01926/) (2020)
- [Minimum-Violation Planning for Autonomous Systems: Theoretical and Practical Considerations](https://mlsanity.com/paper/2009.11954/) (2020)
- [Probabilistic Planning with Preferences over Temporal Goals](https://mlsanity.com/paper/2103.14489/) (2021)

## Built on by (most cited first, 3 of 3)

- [Opportunistic Qualitative Planning in Stochastic Systems with Incomplete Preferences over Reachability Objectives](https://mlsanity.com/paper/2210.01878/) (2022)
- [Preference-Based Planning in Stochastic Environments: From Partially-Ordered Temporal Goals to Most Preferred Policies](https://mlsanity.com/paper/2403.18212/) (2024)
- [Automata Learning of Preferences over Temporal Logic Formulas from Pairwise Comparisons](https://mlsanity.com/paper/2505.18030/) (2025)

## Abstract (arXiv)

In this paper, we study planning in stochastic systems, modeled as Markov decision processes (MDPs), with preferences over temporally extended goals. Prior work on temporal planning with preferences assumes that the user preferences form a total order, meaning that every pair of outcomes are comparable with each other. In this work, we consider the case where the preferences over possible outcomes are a partial order rather than a total order. We first introduce a variant of deterministic finite automaton, referred to as a preference DFA, for specifying the user's preferences over temporally extended goals. Based on the order theory, we translate the preference DFA to a preference relation over policies for probabilistic planning in a labeled MDP. In this treatment, a most preferred policy induces a weak-stochastic nondominated probability distribution over the finite paths in the MDP. The proposed planning algorithm hinges on the construction of a multi-objective MDP. We prove that a weak-stochastic nondominated policy given the preference specification is Pareto-optimal in the constructed multi-objective MDP, and vice versa. Throughout the paper, we employ a running example to demonstrate the proposed preference specification and solution approaches. We show the efficacy of our algorithm using the example with detailed analysis, and then discuss possible future directions.