---
_id: '25'
abstract:
- lang: eng
  text: '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.'
acknowledgement: '∗This work has been supported by Vienna Science and Technology Fund
  (WWTF) Project ICT15-003, Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE),
  and ERC Starting grant (279307: Graph Games). This research was sponsored by the
  Army Research Laboratory and was accomplished under Cooperative Agreement Number
  W911NF-13-2-0045 (ARL Cyber Security CRA). '
article_processing_charge: No
author:
- first_name: Karel
  full_name: Horák, Karel
  last_name: Horák
- first_name: Branislav
  full_name: Bošanský, Branislav
  last_name: Bošanský
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
citation:
  ama: '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>'
  apa: '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>'
  chicago: '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>.'
  ieee: '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.'
  ista: '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.'
  mla: '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>.'
  short: 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.
conference:
  end_date: 2018-07-19
  location: Stockholm, Sweden
  name: 'IJCAI: International Joint Conference on Artificial Intelligence'
  start_date: 2018-07-13
date_created: 2018-12-11T11:44:13Z
date_published: 2018-07-01T00:00:00Z
date_updated: 2025-04-14T13:51:04Z
day: '01'
department:
- _id: KrCh
doi: 10.24963/ijcai.2018/662
ec_funded: 1
external_id:
  isi:
  - '000764175404127'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.24963/ijcai.2018/662
month: '07'
oa: 1
oa_version: Published Version
page: 4764 - 4770
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
publication: Proceedings of the Twenty-Seventh International Joint Conference on Artificial
  Intelligence
publication_status: published
publisher: IJCAI
publist_id: '8030'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Goal-HSVI: Heuristic search value iteration for goal-POMDPs'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2018-July
year: '2018'
...