Probabilistic Preference Planning Problem for Markov Decision Processes

Meilun Li, Andrea Turrini, Ernst Moritz Hahn, Zhikun She, Lijun Zhang*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

3 Citations (Scopus)
131 Downloads (Pure)

Abstract

The classical planning problem aims to find a sequence of permitted actions leading a system to a designed state, i.e., to achieve the system's task. However, in many realistic cases we also have requirements on how to complete the task, indicating that some behaviors and situations are more preferred than others. In this paper, we present the probabilistic preference-based planning problem (P4) for Markov decision processes, where the preferences are defined based on an enriched probabilistic LTL-style logic. We first recall Solver P4 Solver, an SMT-based planner computing the preferred plan by reducing the problem to a quadratic programming one previously developed to solve P4. To improve computational efficiency and scalability, we then introduce a new encoding of the probabilistic preference-based planning problem as a multi-objective model checking one, and propose the corresponding planner SolverMOP4 Solver MO. We illustrate the efficacy of both planners on some selected case studies to show that the model checking-based algorithm is considerably more efficient than the quadratic-programming-based one.

Original languageEnglish
Pages (from-to)1545-1559
Number of pages15
JournalIEEE transactions on software engineering
Volume48
Issue number5
Early online date15 Sept 2020
DOIs
Publication statusPublished - 1 May 2022

Keywords

  • Planning
  • Markov decision processes
  • Preferences
  • Quadratic programming
  • Multi-objective model checking
  • 22/2 OA procedure

Fingerprint

Dive into the research topics of 'Probabilistic Preference Planning Problem for Markov Decision Processes'. Together they form a unique fingerprint.

Cite this