conference paper published yes Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X Martin Chmelik author 3624234E-F248-11E8-B48F-1D18A9856A87 Raghav Gupta author Ayush Kanodia author KrCh department IAAI: Innovative Applications of Artificial Intelligence Modern Graph Algorithmic Techniques in Formal Verification project Rigorous Systems Engineering project Quantitative Graph Games: Theory and Applications project We consider partially observable Markov decision processes (POMDPs) with a set of target states and every transition is associated with an integer cost. The optimization objec- tive we study asks to minimize the expected total cost till the target set is reached, while ensuring that the target set is reached almost-surely (with probability 1). We show that for integer costs approximating the optimal cost is undecidable. For positive costs, our results are as follows: (i) we establish matching lower and upper bounds for the optimal cost and the bound is double exponential; (ii) we show that the problem of approximating the optimal cost is decidable and present ap- proximation algorithms developing on the existing algorithms for POMDPs with finite-horizon objectives. While the worst- case running time of our algorithm is double exponential, we present efficient stopping criteria for the algorithm and show experimentally that it performs well in many examples. AAAI Press2015Austin, TX, USA eng 1411.3880 000372683700002 53496-3502 https://research-explorer.ista.ac.at/record/1529 Chatterjee K, Chmelik M, Gupta R, Kanodia A. 2015. Optimal cost almost-sure reachability in POMDPs. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence . IAAI: Innovative Applications of Artificial Intelligence, Artifical Intelligence, vol. 5, 3496–3502. Chatterjee, Krishnendu, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. “Optimal Cost Almost-Sure Reachability in POMDPs.” In <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i>, 5:3496–3502. AAAI Press, 2015. K. Chatterjee, M. Chmelik, R. Gupta, A. Kanodia, in:, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence , AAAI Press, 2015, pp. 3496–3502. K. Chatterjee, M. Chmelik, R. Gupta, and A. Kanodia, “Optimal cost almost-sure reachability in POMDPs,” in <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i>, Austin, TX, USA, 2015, vol. 5, pp. 3496–3502. Chatterjee, K., Chmelik, M., Gupta, R., &#38; Kanodia, A. (2015). Optimal cost almost-sure reachability in POMDPs. In <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i> (Vol. 5, pp. 3496–3502). Austin, TX, USA: AAAI Press. Chatterjee K, Chmelik M, Gupta R, Kanodia A. Optimal cost almost-sure reachability in POMDPs. In: <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i>. Vol 5. AAAI Press; 2015:3496-3502. Chatterjee, Krishnendu, et al. “Optimal Cost Almost-Sure Reachability in POMDPs.” <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence </i>, vol. 5, AAAI Press, 2015, pp. 3496–502. 18202018-12-11T11:54:11Z2025-09-18T11:05:08Z