---
_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: Proceedings of the Twenty-Seventh International Joint
Conference on Artificial Intelligence. Vol 2018-July. IJCAI; 2018:4764-4770.
doi:10.24963/ijcai.2018/662'
apa: 'Horák, K., Bošanský, B., & Chatterjee, K. (2018). Goal-HSVI: Heuristic
search value iteration for goal-POMDPs. In Proceedings of the Twenty-Seventh
International Joint Conference on Artificial Intelligence (Vol. 2018–July,
pp. 4764–4770). Stockholm, Sweden: IJCAI. https://doi.org/10.24963/ijcai.2018/662'
chicago: 'Horák, Karel, Branislav Bošanský, and Krishnendu Chatterjee. “Goal-HSVI:
Heuristic Search Value Iteration for Goal-POMDPs.” In Proceedings of the Twenty-Seventh
International Joint Conference on Artificial Intelligence, 2018–July:4764–70.
IJCAI, 2018. https://doi.org/10.24963/ijcai.2018/662.'
ieee: 'K. Horák, B. Bošanský, and K. Chatterjee, “Goal-HSVI: Heuristic search value
iteration for goal-POMDPs,” in Proceedings of the Twenty-Seventh International
Joint Conference on Artificial Intelligence, 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.”
Proceedings of the Twenty-Seventh International Joint Conference on Artificial
Intelligence, vol. 2018–July, IJCAI, 2018, pp. 4764–70, doi:10.24963/ijcai.2018/662.'
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: 2023-09-19T14:44:59Z
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'
...