conference paper
Stochastic shortest path with energy constraints in POMDPs
published
yes
Tomáš
Brázdil
author
Krishnendu
Chatterjee
author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X
Martin
Chmelik
author 3624234E-F248-11E8-B48F-1D18A9856A87
Anchit
Gupta
author
Petr
Novotny
author 3CC3B868-F248-11E8-B48F-1D18A9856A87
KrCh
department
AAMAS: Autonomous Agents & Multiagent Systems
Modern Graph Algorithmic Techniques in Formal Verification
project
Rigorous Systems Engineering
project
International IST Postdoc Fellowship Programme
project
Quantitative Graph Games: Theory and Applications
project
We consider partially observable Markov decision processes (POMDPs) with a set of target states and positive integer costs associated with every transition. The traditional optimization objective (stochastic shortest path) asks to minimize the expected total cost until the target set is reached. We extend the traditional framework of POMDPs to model energy consumption, which represents a hard constraint. The energy levels may increase and decrease with transitions, and the hard constraint requires that the energy level must remain positive in all steps till the target is reached. First, we present a novel algorithm for solving POMDPs with energy levels, developing on existing POMDP solvers and using RTDP as its main method. Our second contribution is related to policy representation. For larger POMDP instances the policies computed by existing solvers are too large to be understandable. We present an automated procedure based on machine learning techniques that automatically extracts important decisions of the policy allowing us to compute succinct human readable policies. Finally, we show experimentally that our algorithm performs well and computes succinct policies on a number of POMDP instances from the literature that were naturally enhanced with energy levels.
ACM2016Singapore
eng
Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems
1465 - 1466
Brázdil T, Chatterjee K, Chmelik M, Gupta A, Novotný P. 2016. Stochastic shortest path with energy constraints in POMDPs. Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems. AAMAS: Autonomous Agents & Multiagent Systems, 1465–1466.
T. Brázdil, K. Chatterjee, M. Chmelik, A. Gupta, and P. Novotný, “Stochastic shortest path with energy constraints in POMDPs,” in <i>Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems</i>, Singapore, 2016, pp. 1465–1466.
Brázdil, T., Chatterjee, K., Chmelik, M., Gupta, A., & Novotný, P. (2016). Stochastic shortest path with energy constraints in POMDPs. In <i>Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems</i> (pp. 1465–1466). Singapore: ACM.
Brázdil, Tomáš, Krishnendu Chatterjee, Martin Chmelik, Anchit Gupta, and Petr Novotný. “Stochastic Shortest Path with Energy Constraints in POMDPs.” In <i>Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems</i>, 1465–66. ACM, 2016.
Brázdil T, Chatterjee K, Chmelik M, Gupta A, Novotný P. Stochastic shortest path with energy constraints in POMDPs. In: <i>Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems</i>. ACM; 2016:1465-1466.
T. Brázdil, K. Chatterjee, M. Chmelik, A. Gupta, P. Novotný, in:, Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems, ACM, 2016, pp. 1465–1466.
Brázdil, Tomáš, et al. “Stochastic Shortest Path with Energy Constraints in POMDPs.” <i>Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems</i>, ACM, 2016, pp. 1465–66.
13272018-12-11T11:51:23Z2021-01-12T06:49:54Z