TY - GEN
T1 - Finding Optimal Deterministic Policies for Constrained Stochastic Shortest Path Problems
AU - Schmalz, Johannes
AU - Trevizan, Felipe
N1 - Publisher Copyright:
© 2024 The Authors.
PY - 2024/10/16
Y1 - 2024/10/16
N2 - Constrained Stochastic Shortest Path problems (CSSPs) are a modelling framework for probabilistic problems with a primary cost and constraints over secondary costs such as fuel consumption or monetary budget.While the optimal solution for a CSSP is usually a stochastic policy, practical considerations often demand deterministic solutions, for instance, in aviation and multi-agent systems.Previous works have addressed this issue for special cases of CSSPs; in this work, we show the technical issues in generalising these results and show how they can be addressed.Then, using these methods, we extend the state-of-the-art heuristic search method for finding optimal stochastic policies to efficiently find deterministic policies for CSSPs.We show experimentally that our algorithm competes with the state-of-the-art, and is able to solve the class of problems with difficult-to-satisfy constraints on which the state-of-the-art fails.
AB - Constrained Stochastic Shortest Path problems (CSSPs) are a modelling framework for probabilistic problems with a primary cost and constraints over secondary costs such as fuel consumption or monetary budget.While the optimal solution for a CSSP is usually a stochastic policy, practical considerations often demand deterministic solutions, for instance, in aviation and multi-agent systems.Previous works have addressed this issue for special cases of CSSPs; in this work, we show the technical issues in generalising these results and show how they can be addressed.Then, using these methods, we extend the state-of-the-art heuristic search method for finding optimal stochastic policies to efficiently find deterministic policies for CSSPs.We show experimentally that our algorithm competes with the state-of-the-art, and is able to solve the class of problems with difficult-to-satisfy constraints on which the state-of-the-art fails.
UR - http://www.scopus.com/inward/record.url?scp=85216696107&partnerID=8YFLogxK
U2 - 10.3233/FAIA240986
DO - 10.3233/FAIA240986
M3 - Conference contribution
AN - SCOPUS:85216696107
T3 - Frontiers in Artificial Intelligence and Applications
SP - 4148
EP - 4156
BT - ECAI 2024 - 27th European Conference on Artificial Intelligence, Including 13th Conference on Prestigious Applications of Intelligent Systems, PAIS 2024, Proceedings
A2 - Endriss, Ulle
A2 - Melo, Francisco S.
A2 - Bach, Kerstin
A2 - Bugarin-Diz, Alberto
A2 - Alonso-Moral, Jose M.
A2 - Barro, Senen
A2 - Heintz, Fredrik
PB - IOS Press BV
T2 - 27th European Conference on Artificial Intelligence, ECAI 2024
Y2 - 19 October 2024 through 24 October 2024
ER -