[{"publication":"Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence","month":"07","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","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"oa_version":"Preprint","language":[{"iso":"eng"}],"conference":{"start_date":"2018-07-13","name":"IJCAI: International Joint Conference on Artificial Intelligence","location":"Stockholm, Sweden","end_date":"2018-07-19"},"type":"conference","date_published":"2018-07-17T00:00:00Z","oa":1,"publication_identifier":{"isbn":["978-099924112-7"],"issn":["10450823"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","related_material":{"record":[{"relation":"dissertation_contains","id":"8934","status":"public"}]},"main_file_link":[{"url":"https://arxiv.org/abs/1804.08984","open_access":"1"}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87","full_name":"Fu, Hongfei","first_name":"Hongfei","last_name":"Fu"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-1702-6584","full_name":"Goharshady, Amir","first_name":"Amir","last_name":"Goharshady"},{"full_name":"Okati, Nastaran","first_name":"Nastaran","last_name":"Okati"}],"scopus_import":"1","_id":"5977","intvolume":"      2018","title":"Computational approaches for stochastic shortest path on succinct MDPs","date_created":"2019-02-13T13:26:27Z","department":[{"_id":"KrCh"}],"article_processing_charge":"No","publication_status":"published","quality_controlled":"1","ec_funded":1,"page":"4700-4707","publisher":"IJCAI","external_id":{"isi":["000764175404118"],"arxiv":["1804.08984"]},"isi":1,"year":"2018","citation":{"ista":"Chatterjee K, Fu H, Goharshady AK, Okati N. 2018. Computational approaches for stochastic shortest path on succinct MDPs. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. IJCAI: International Joint Conference on Artificial Intelligence vol. 2018, 4700–4707.","short":"K. Chatterjee, H. Fu, A.K. Goharshady, N. Okati, in:, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI, 2018, pp. 4700–4707.","mla":"Chatterjee, Krishnendu, et al. “Computational Approaches for Stochastic Shortest Path on Succinct MDPs.” <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>, vol. 2018, IJCAI, 2018, pp. 4700–07, doi:<a href=\"https://doi.org/10.24963/ijcai.2018/653\">10.24963/ijcai.2018/653</a>.","ieee":"K. Chatterjee, H. Fu, A. K. Goharshady, and N. Okati, “Computational approaches for stochastic shortest path on succinct MDPs,” in <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>, Stockholm, Sweden, 2018, vol. 2018, pp. 4700–4707.","chicago":"Chatterjee, Krishnendu, Hongfei Fu, Amir Kafshdar Goharshady, and Nastaran Okati. “Computational Approaches for Stochastic Shortest Path on Succinct MDPs.” In <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>, 2018:4700–4707. IJCAI, 2018. <a href=\"https://doi.org/10.24963/ijcai.2018/653\">https://doi.org/10.24963/ijcai.2018/653</a>.","ama":"Chatterjee K, Fu H, Goharshady AK, Okati N. Computational approaches for stochastic shortest path on succinct MDPs. In: <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i>. Vol 2018. IJCAI; 2018:4700-4707. doi:<a href=\"https://doi.org/10.24963/ijcai.2018/653\">10.24963/ijcai.2018/653</a>","apa":"Chatterjee, K., Fu, H., Goharshady, A. K., &#38; Okati, N. (2018). Computational approaches for stochastic shortest path on succinct MDPs. In <i>Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence</i> (Vol. 2018, pp. 4700–4707). Stockholm, Sweden: IJCAI. <a href=\"https://doi.org/10.24963/ijcai.2018/653\">https://doi.org/10.24963/ijcai.2018/653</a>"},"date_updated":"2025-06-02T08:53:44Z","abstract":[{"text":"We consider the stochastic shortest path (SSP)problem for succinct Markov decision processes(MDPs), where the MDP consists of a set of vari-ables, and a set of nondeterministic rules that up-date the variables. First, we show that several ex-amples from the AI literature can be modeled assuccinct MDPs.  Then we present computationalapproaches for upper and lower bounds for theSSP problem: (a) for computing upper bounds, ourmethod is polynomial-time in the implicit descrip-tion of the MDP; (b) for lower bounds, we present apolynomial-time (in the size of the implicit descrip-tion) reduction to quadratic programming. Our ap-proach is applicable even to infinite-state MDPs.Finally, we present experimental results to demon-strate the effectiveness of our approach on severalclassical examples from the AI literature.","lang":"eng"}],"day":"17","doi":"10.24963/ijcai.2018/653","arxiv":1,"volume":2018}]