[{"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. ","year":"2021","citation":{"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.","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>","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.","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.","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>."},"date_updated":"2025-07-14T09:10:13Z","day":"01","doi":"10.24963/ijcai.2021/575","abstract":[{"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.","lang":"eng"}],"ec_funded":1,"quality_controlled":"1","page":"4182-4189","publisher":"International Joint Conferences on Artificial Intelligence","scopus_import":"1","_id":"10847","author":[{"full_name":"Tomášek, Petr","first_name":"Petr","last_name":"Tomášek"},{"full_name":"Horák, Karel","first_name":"Karel","last_name":"Horák"},{"full_name":"Aradhye, Aditya","last_name":"Aradhye","first_name":"Aditya"},{"last_name":"Bošanský","first_name":"Branislav","full_name":"Bošanský, Branislav"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X"}],"article_processing_charge":"No","date_created":"2022-03-13T23:01:47Z","department":[{"_id":"KrCh"}],"publication_status":"published","title":"Solving partially observable stochastic shortest-path games","main_file_link":[{"open_access":"1","url":"https://doi.org/10.24963/ijcai.2021/575"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"conference","date_published":"2021-09-01T00:00:00Z","publication_identifier":{"issn":["1045-0823"],"isbn":["9780999241196"]},"oa":1,"language":[{"iso":"eng"}],"conference":{"name":"IJCAI: International Joint Conferences on Artificial Intelligence Organization","start_date":"2021-08-19","end_date":"2021-08-27","location":"Virtual, Online"},"publication":"30th International Joint Conference on Artificial Intelligence","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"}],"oa_version":"Published Version","month":"09"},{"extern":"1","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://www.ijcai.org/Proceedings/03/Papers/278.pdf"}],"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."}],"oa":1,"day":"01","publication_identifier":{"issn":["1045-0823"]},"date_published":"2003-08-01T00:00:00Z","type":"conference","date_updated":"2023-02-09T12:05:25Z","citation":{"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.","short":"M.H. Henzinger, R. Motwani, C. Silverstein, in:, 18th International Joint Conference on Artificial Intelligence, Association for Computing Machinery, 2003, pp. 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.","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.","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.","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."},"year":"2003","conference":{"start_date":"2003-08-09","name":"IJCAI: International Joint Conference on Artificial Intelligence","end_date":"2003-08-15","location":"Acapulco, Mexico"},"publisher":"Association for Computing Machinery","language":[{"iso":"eng"}],"page":"1573-1579","quality_controlled":"1","title":"Challenges in web search engines","month":"08","publication_status":"published","oa_version":"Published Version","date_created":"2022-08-18T06:40:02Z","article_processing_charge":"No","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Motwani, Rajeev","last_name":"Motwani","first_name":"Rajeev"},{"full_name":"Silverstein, Craig","last_name":"Silverstein","first_name":"Craig"}],"publication":"18th International Joint Conference on Artificial Intelligence","_id":"11909","scopus_import":"1"}]