---
_id: '10847'
abstract:
- lang: eng
  text: 'We study the two-player zero-sum extension of the partially observable stochastic
    shortest-path problem where one agent has only partial information about the environment.
    We formulate this problem as a partially observable stochastic game (POSG): given
    a set of target states and negative rewards for each transition, the player with
    imperfect information maximizes the expected undiscounted total reward until a
    target state is reached. The second player with the perfect information aims for
    the opposite. We base our formalism on POSGs with one-sided observability (OS-POSGs)
    and give the following contributions: (1) we introduce a novel heuristic search
    value iteration algorithm that iteratively solves depth-limited variants of the
    game, (2) we derive the bound on the depth guaranteeing an arbitrary precision,
    (3) we propose a novel upper-bound estimation that allows early terminations,
    and (4) we experimentally evaluate the algorithm on a pursuit-evasion game.'
acknowledgement: "This research was supported by the Czech Science Foundation (no.
  19-24384Y), by the OP VVV MEYS funded project CZ.02.1.01/0.0/0.0/16 019/0000765
  “Research Center for Informatics”, by the ERC CoG 863818 (ForM-SMArt), and by the
  Combat Capabilities Development Command Army Research Laboratory and was accomplished
  under Cooperative\r\nAgreement Number W911NF-13-2-0045 (ARL Cyber Security CRA).
  The views and conclusions contained in this document are those of the authors and
  should not be interpreted as\r\nrepresenting the official policies, either expressed
  or implied, of the Combat Capabilities Development Command Army Research Laboratory
  or the U.S. Government. The U.S. Government is authorized to reproduce and distribute
  reprints for Government purposes not withstanding any copyright notation here on. "
article_processing_charge: No
author:
- first_name: Petr
  full_name: Tomášek, Petr
  last_name: Tomášek
- first_name: Karel
  full_name: Horák, Karel
  last_name: Horák
- first_name: Aditya
  full_name: Aradhye, Aditya
  last_name: Aradhye
- 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: 'Tomášek P, Horák K, Aradhye A, Bošanský B, Chatterjee K. Solving partially
    observable stochastic shortest-path games. In: <i>30th International Joint Conference
    on Artificial Intelligence</i>. International Joint Conferences on Artificial
    Intelligence; 2021:4182-4189. doi:<a href="https://doi.org/10.24963/ijcai.2021/575">10.24963/ijcai.2021/575</a>'
  apa: 'Tomášek, P., Horák, K., Aradhye, A., Bošanský, B., &#38; Chatterjee, K. (2021).
    Solving partially observable stochastic shortest-path games. In <i>30th International
    Joint Conference on Artificial Intelligence</i> (pp. 4182–4189). Virtual, Online:
    International Joint Conferences on Artificial Intelligence. <a href="https://doi.org/10.24963/ijcai.2021/575">https://doi.org/10.24963/ijcai.2021/575</a>'
  chicago: Tomášek, Petr, Karel Horák, Aditya Aradhye, Branislav Bošanský, and Krishnendu
    Chatterjee. “Solving Partially Observable Stochastic Shortest-Path Games.” In
    <i>30th International Joint Conference on Artificial Intelligence</i>, 4182–89.
    International Joint Conferences on Artificial Intelligence, 2021. <a href="https://doi.org/10.24963/ijcai.2021/575">https://doi.org/10.24963/ijcai.2021/575</a>.
  ieee: P. Tomášek, K. Horák, A. Aradhye, B. Bošanský, and K. Chatterjee, “Solving
    partially observable stochastic shortest-path games,” in <i>30th International
    Joint Conference on Artificial Intelligence</i>, Virtual, Online, 2021, pp. 4182–4189.
  ista: 'Tomášek P, Horák K, Aradhye A, Bošanský B, Chatterjee K. 2021. Solving partially
    observable stochastic shortest-path games. 30th International Joint Conference
    on Artificial Intelligence. IJCAI: International Joint Conferences on Artificial
    Intelligence Organization, 4182–4189.'
  mla: Tomášek, Petr, et al. “Solving Partially Observable Stochastic Shortest-Path
    Games.” <i>30th International Joint Conference on Artificial Intelligence</i>,
    International Joint Conferences on Artificial Intelligence, 2021, pp. 4182–89,
    doi:<a href="https://doi.org/10.24963/ijcai.2021/575">10.24963/ijcai.2021/575</a>.
  short: P. Tomášek, K. Horák, A. Aradhye, B. Bošanský, K. Chatterjee, in:, 30th International
    Joint Conference on Artificial Intelligence, International Joint Conferences on
    Artificial Intelligence, 2021, pp. 4182–4189.
conference:
  end_date: 2021-08-27
  location: Virtual, Online
  name: 'IJCAI: International Joint Conferences on Artificial Intelligence Organization'
  start_date: 2021-08-19
date_created: 2022-03-13T23:01:47Z
date_published: 2021-09-01T00:00:00Z
date_updated: 2025-07-14T09:10:13Z
day: '01'
department:
- _id: KrCh
doi: 10.24963/ijcai.2021/575
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.24963/ijcai.2021/575
month: '09'
oa: 1
oa_version: Published Version
page: 4182-4189
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 30th International Joint Conference on Artificial Intelligence
publication_identifier:
  isbn:
  - '9780999241196'
  issn:
  - 1045-0823
publication_status: published
publisher: International Joint Conferences on Artificial Intelligence
quality_controlled: '1'
scopus_import: '1'
status: public
title: Solving partially observable stochastic shortest-path games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '11909'
abstract:
- lang: eng
  text: This article presents a high-level discussion of some problems that are unique
    to web search engines. The goal is to raise awareness and stimulate research in
    these areas.
article_processing_charge: No
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Rajeev
  full_name: Motwani, Rajeev
  last_name: Motwani
- first_name: Craig
  full_name: Silverstein, Craig
  last_name: Silverstein
citation:
  ama: 'Henzinger MH, Motwani R, Silverstein C. Challenges in web search engines.
    In: <i>18th International Joint Conference on Artificial Intelligence</i>. Association
    for Computing Machinery; 2003:1573-1579.'
  apa: 'Henzinger, M. H., Motwani, R., &#38; Silverstein, C. (2003). Challenges in
    web search engines. In <i>18th International Joint Conference on Artificial Intelligence</i>
    (pp. 1573–1579). Acapulco, Mexico: Association for Computing Machinery.'
  chicago: Henzinger, Monika H, Rajeev Motwani, and Craig Silverstein. “Challenges
    in Web Search Engines.” In <i>18th International Joint Conference on Artificial
    Intelligence</i>, 1573–79. Association for Computing Machinery, 2003.
  ieee: M. H. Henzinger, R. Motwani, and C. Silverstein, “Challenges in web search
    engines,” in <i>18th International Joint Conference on Artificial Intelligence</i>,
    Acapulco, Mexico, 2003, pp. 1573–1579.
  ista: 'Henzinger MH, Motwani R, Silverstein C. 2003. Challenges in web search engines.
    18th International Joint Conference on Artificial Intelligence. IJCAI: International
    Joint Conference on Artificial Intelligence, 1573–1579.'
  mla: Henzinger, Monika H., et al. “Challenges in Web Search Engines.” <i>18th International
    Joint Conference on Artificial Intelligence</i>, Association for Computing Machinery,
    2003, pp. 1573–79.
  short: M.H. Henzinger, R. Motwani, C. Silverstein, in:, 18th International Joint
    Conference on Artificial Intelligence, Association for Computing Machinery, 2003,
    pp. 1573–1579.
conference:
  end_date: 2003-08-15
  location: Acapulco, Mexico
  name: 'IJCAI: International Joint Conference on Artificial Intelligence'
  start_date: 2003-08-09
date_created: 2022-08-18T06:40:02Z
date_published: 2003-08-01T00:00:00Z
date_updated: 2023-02-09T12:05:25Z
day: '01'
extern: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.ijcai.org/Proceedings/03/Papers/278.pdf
month: '08'
oa: 1
oa_version: Published Version
page: 1573-1579
publication: 18th International Joint Conference on Artificial Intelligence
publication_identifier:
  issn:
  - 1045-0823
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Challenges in web search engines
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2003'
...