Goal-HSVI: Heuristic search value iteration for goal-POMDPs Conference Paper


Author(s): Horák, Karel; Bošanský, Branislav; Chatterjee, Krishnendu
Title: Goal-HSVI: Heuristic search value iteration for goal-POMDPs
Affiliation IST Austria
Abstract: 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.
Conference Title: IJCAI: International Joint Conference on Artificial Intelligence
Volume: 2018
Conference Dates: July 13-19, 2018
Conference Location: Stockholm, Sweden
ISBN: 978-099924112-7
Publisher: IJCAI  
Start Page: 4764
End Page: 4770
Copyright Statement: © 2018 International Joint Conferences on Artificial Intelligence.All right reserved.
DOI: 10.24963/ijcai.2018/662
Notes: ERC Starting grant (279307: Graph Games).
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work