conference paper published yes Karel Horák author Branislav Bošanský author Krishnendu Chatterjee author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X KrCh department IJCAI: International Joint Conference on Artificial Intelligence Efficient Algorithms for Computer Aided Verification project Rigorous Systems Engineering project Quantitative Graph Games: Theory and Applications project Partially observable Markov decision processes (POMDPs) are the standard models for planning under uncertainty with both finite and infinite horizon. Besides the well-known discounted-sum objective, indefinite-horizon objective (aka Goal-POMDPs) is another classical objective for POMDPs. In this case, given a set of target states and a positive cost for each transition, the optimization objective is to minimize the expected total cost until a target state is reached. In the literature, RTDP-Bel or heuristic search value iteration (HSVI) have been used for solving Goal-POMDPs. Neither of these algorithms has theoretical convergence guarantees, and HSVI may even fail to terminate its trials. We give the following contributions: (1) We discuss the challenges introduced in Goal-POMDPs and illustrate how they prevent the original HSVI from converging. (2) We present a novel algorithm inspired by HSVI, termed Goal-HSVI, and show that our algorithm has convergence guarantees. (3) We show that Goal-HSVI outperforms RTDP-Bel on a set of well-known examples. IJCAI2018Stockholm, Sweden eng 00076417540412710.24963/ijcai.2018/662 2018-July4764 - 4770 Horák, K., Bošanský, B., &#38; Chatterjee, K. (2018). Goal-HSVI: Heuristic search value iteration for goal-POMDPs. In <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i> (Vol. 2018–July, pp. 4764–4770). Stockholm, Sweden: IJCAI. <a href="https://doi.org/10.24963/ijcai.2018/662">https://doi.org/10.24963/ijcai.2018/662</a> K. Horák, B. Bošanský, K. Chatterjee, in:, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI, 2018, pp. 4764–4770. Horák K, Bošanský B, Chatterjee K. 2018. Goal-HSVI: Heuristic search value iteration for goal-POMDPs. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. IJCAI: International Joint Conference on Artificial Intelligence vol. 2018–July, 4764–4770. K. Horák, B. Bošanský, and K. Chatterjee, “Goal-HSVI: Heuristic search value iteration for goal-POMDPs,” in <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>, Stockholm, Sweden, 2018, vol. 2018–July, pp. 4764–4770. Horák, Karel, Branislav Bošanský, and Krishnendu Chatterjee. “Goal-HSVI: Heuristic Search Value Iteration for Goal-POMDPs.” In <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>, 2018–July:4764–70. IJCAI, 2018. <a href="https://doi.org/10.24963/ijcai.2018/662">https://doi.org/10.24963/ijcai.2018/662</a>. Horák K, Bošanský B, Chatterjee K. Goal-HSVI: Heuristic search value iteration for goal-POMDPs. In: <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>. Vol 2018-July. IJCAI; 2018:4764-4770. doi:<a href="https://doi.org/10.24963/ijcai.2018/662">10.24963/ijcai.2018/662</a> Horák, Karel, et al. “Goal-HSVI: Heuristic Search Value Iteration for Goal-POMDPs.” <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>, vol. 2018–July, IJCAI, 2018, pp. 4764–70, doi:<a href="https://doi.org/10.24963/ijcai.2018/662">10.24963/ijcai.2018/662</a>. 252018-12-11T11:44:13Z2026-06-18T18:34:17Z