{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,5]],"date-time":"2023-09-05T03:06:24Z","timestamp":1693883184396},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,1,19]],"date-time":"2016-01-19T00:00:00Z","timestamp":1453161600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Front. Comput. Sci."],"published-print":{"date-parts":[[2016,8]]},"DOI":"10.1007\/s11704-015-5038-5","type":"journal-article","created":{"date-parts":[[2016,1,18]],"date-time":"2016-01-18T18:08:30Z","timestamp":1453140510000},"page":"726-740","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Reasoning and predicting POMDP planning complexity via covering numbers"],"prefix":"10.1007","volume":"10","author":[{"given":"Zongzhang","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiming","family":"Fu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaofang","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quan","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,19]]},"reference":[{"issue":"1\u20132","key":"5038_CR1","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0004-3702(98)00023-X","volume":"101","author":"L Kaelbling","year":"1998","unstructured":"Kaelbling L, Littman M, Cassandra A. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 1998, 101(1\u20132): 99\u2013134","journal-title":"Artificial Intelligence"},{"key":"5038_CR2","first-page":"541","volume-title":"In: Proceedings of the 16th National Conference on Artificial Intelligence (AAAI).","author":"O Madani","year":"1999","unstructured":"Madani O, Hanks S, Condon A. On the undecidability of probabilistic planning and infinite-horizon partially observable Markov decision problems. In: Proceedings of the 16th National Conference on Artificial Intelligence (AAAI). 1999, 541\u2013548"},{"key":"5038_CR3","first-page":"542","volume-title":"In: Proceedings of International Conference on Uncertainty in Artificial Intelligence (UAI).","author":"T Smith","year":"2005","unstructured":"Smith T, Simmons R. Point-based POMDP algorithms: improved analysis and implementation. In: Proceedings of International Conference on Uncertainty in Artificial Intelligence (UAI). 2005, 542\u2013547"},{"key":"5038_CR4","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1613\/jair.2078","volume":"27","author":"J Pineau","year":"2006","unstructured":"Pineau J, Gordon G, Thrun S. Anytime point-based approximations for large POMDPs. Journal of Artificial Intelligence Research, 2006, 27: 335\u2013380","journal-title":"Journal of Artificial Intelligence Research"},{"key":"5038_CR5","volume-title":"In: Proceedings of Robotics: Science and Systems (RSS)","author":"H Kurniawati","year":"2008","unstructured":"Kurniawati H, Hsu D, Lee W S. SARSOP: efficient point-based POMDP planning by approximating optimally reachable belief spaces. In: Proceedings of Robotics: Science and Systems (RSS). 2008"},{"key":"5038_CR6","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1007\/978-3-642-17319-6_49","volume-title":"In: Proceedings of the 2nd International Conference on Simulation, Modeling, and Programming for Autonomous Robots (SIMPAR).","author":"Z Zhang","year":"2010","unstructured":"Zhang Z, Chen X. Accelerating point-based POMDP algorithms via greedy strategies. In: Proceedings of the 2nd International Conference on Simulation, Modeling, and Programming for Autonomous Robots (SIMPAR). 2010, 545\u2013556"},{"issue":"1","key":"5038_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10458-012-9200-2","volume":"27","author":"G Shani","year":"2013","unstructured":"Shani G, Pineau J, Kaplow R. A survey of point-based POMDP solvers. Journal of Autonomous Agents andMulti-Agent Systems, 2013, 27(1): 1\u201351","journal-title":"Journal of Autonomous Agents andMulti-Agent Systems"},{"key":"5038_CR8","first-page":"26","volume-title":"In: Proceedings of the 31st International Conference on Machine Learning (ICML).","author":"Z Zhang","year":"2014","unstructured":"Zhang Z, Hsu D, Lee W S. Covering number for efficient heuristicbased POMDP planning. In: Proceedings of the 31st International Conference on Machine Learning (ICML). 2014, 26\u201334"},{"key":"5038_CR9","first-page":"249","volume-title":"In: Proceedings of the 8th Symposium on Combinatorial Search.","author":"Z Zhang","year":"2015","unstructured":"Zhang Z, Hsu D, Lee WS, Lim ZW, Bai A. PLEASE: plam leaf search for POMDPs with large observation spaces. In: Proceedings of the 8th Symposium on Combinatorial Search. 2015, 249\u2013257"},{"key":"5038_CR10","first-page":"689","volume-title":"In: Proceedings of Advances in Neural Information Processing Systems (NIPS).","author":"D Hsu","year":"2007","unstructured":"Hsu D, Lee W S, Rong N. What makes some POMDP problems easy to approximate. In: Proceedings of Advances in Neural Information Processing Systems (NIPS). 2007, 689\u2013696"},{"key":"5038_CR11","first-page":"1853","volume-title":"In: Proceedings of the 26th National Conference on Artificial Intelligence (AAAI).","author":"Z Zhang","year":"2012","unstructured":"Zhang Z, Littman M, Chen X. Covering number as a complexity measure for POMDP planning and learning. In: Proceedings of the 26th National Conference on Artificial Intelligence (AAAI). 2012, 1853\u20131859"},{"key":"5038_CR12","first-page":"362","volume-title":"In: Proceedings of the 12th International Conference on Machine Learning (ICML).","author":"M Littman","year":"1995","unstructured":"Littman M, Cassandra A, Kaelbling L. Learning policies for partially observable environments: scaling up. In: Proceedings of the 12th International Conference on Machine Learning (ICML). 1995, 362\u2013370"},{"key":"5038_CR13","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1613\/jair.678","volume":"13","author":"M Hauskrecht","year":"2000","unstructured":"Hauskrecht M. Value-function approximations for partially observable Markov decision processes. Journal of Artificial Intelligence Research, 2000, 13: 33\u201394","journal-title":"Journal of Artificial Intelligence Research"},{"key":"5038_CR14","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1613\/jair.2567","volume":"32","author":"S Ross","year":"2008","unstructured":"Ross S, Pineau J, Paquet S, Chaib-Draa B. Online planning algorithms for POMDPs. Journal of Artificial Intelligence Research, 2008, 32: 663\u2013704","journal-title":"Journal of Artificial Intelligence Research"},{"key":"5038_CR15","volume-title":"Dynamic Programming","author":"R Bellman","year":"1957","unstructured":"Bellman R. Dynamic Programming. Princeton, NJ, USA: Princeton University Press, 1957"},{"key":"5038_CR16","volume-title":"Probabilistic planning for robotic exploration. Dissertation for the Doctoral Degree","author":"T Smith","year":"2007","unstructured":"Smith T. Probabilistic planning for robotic exploration. Dissertation for the Doctoral Degree. Pittsburgh: Carnegie Mellon University, 2007"},{"key":"5038_CR17","first-page":"306","volume-title":"In: Proceedings of International Conference on Machine Learning (ICML).","author":"S Kakade","year":"2003","unstructured":"Kakade S, Kearns M, Langford J. Exploration in metric state spaces. In: Proceedings of International Conference on Machine Learning (ICML). 2003, 306\u2013312"},{"key":"5038_CR18","first-page":"54","volume-title":"In: Proceedings of the 14th National Conference on Artificial Intelligence (AAAI).","author":"A Cassandra","year":"1997","unstructured":"Cassandra A, Littman M, Zhang N L. Incremental pruning: a simple, fast, exact method for partially observable Markov decision processes. In: Proceedings of the 14th National Conference on Artificial Intelligence (AAAI). 1997, 54\u201361"},{"key":"5038_CR19","first-page":"1641","volume-title":"In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI).","author":"B Bonet","year":"2009","unstructured":"Bonet B, Geffner H. Solving POMDPs: RTDP-Bel vs. point-based algorithms. In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). 2009, 1641\u20131646"},{"key":"5038_CR20","first-page":"406","volume-title":"In: Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence (UAI).","author":"A Ng","year":"2000","unstructured":"Ng A, Jordan M. PEGASUS: a policy search method for large MDPs and POMDPs. In: Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence (UAI). 2000, 406\u2013415"},{"key":"5038_CR21","volume-title":"FHHOP: a factored hybrid heuristic online planning algorithm for large POMDPs","author":"Z Zhang","year":"2012","unstructured":"Zhang Z, Chen X. FHHOP: a factored hybrid heuristic online planning algorithm for large POMDPs. 2012, arXiv preprint arXiv: 1210.4912"},{"key":"5038_CR22","first-page":"1772","volume-title":"In: Proceedings of Advances in Neural Information Processing Systems (NIPS).","author":"A Somani","year":"2013","unstructured":"Somani A, Ye N, Hsu D, Lee WS. DESPOT: online POMDP planning with regularization. In: Proceedings of Advances in Neural Information Processing Systems (NIPS). 2013, 1772\u20131780"},{"key":"5038_CR23","first-page":"1025","volume-title":"In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI).","author":"J Pineau","year":"2003","unstructured":"Pineau J, Gordon G, Thrun S. Point-based value iteration: an anytime algorithm for POMDPs. In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). 2003, 1025\u20131032"},{"key":"5038_CR24","first-page":"194","volume-title":"In: Proceedings of International Conference on Automated Planning and Scheduling (ICAPS).","author":"P Poupart","year":"2011","unstructured":"Poupart P, Kim K E, Kim D. Closing the gap: improved bounds on optimal POMDP solutions. In: Proceedings of International Conference on Automated Planning and Scheduling (ICAPS). 2011, 194\u2013201"},{"key":"5038_CR25","first-page":"2164","volume-title":"In: Proceedings of Advances in Neural Information Processing Systems (NIPS).","author":"D Silver","year":"2010","unstructured":"Silver D, Veness J. Monte-Carlo planning in large POMDPs. In: Proceedings of Advances in Neural Information Processing Systems (NIPS). 2010, 2164\u20132172"},{"key":"5038_CR26","first-page":"28","volume-title":"In: Proceedings of International Conference on Automated Planning and Scheduling (ICAPS).","author":"A Bai","year":"2014","unstructured":"Bai A, Wu F, Zhang Z, Chen X. Thompson sampling based Monte-Carlo planning in POMDPs. In: Proceedings of International Conference on Automated Planning and Scheduling (ICAPS). 2014, 28\u201336"},{"issue":"8","key":"5038_CR27","doi-asserted-by":"crossref","first-page":"1053","DOI":"10.1177\/0278364910369861","volume":"29","author":"S C Ong","year":"2010","unstructured":"Ong S C, Png S W, Hsu D, Lee W S. Planning under uncertainty for robotic tasks with mixed observability. International Journal of Robotics Research, 2010, 29(8): 1053\u20131068","journal-title":"International Journal of Robotics Research"},{"issue":"2","key":"5038_CR28","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1007\/s10458-007-9026-5","volume":"17","author":"S Seuken","year":"2008","unstructured":"Seuken S, Zilberstein S. Formal models and algorithms for decentralized decision making under uncertainty. Journal of Autonomous Agents and Multi-Agent Systems, 2008, 17(2): 190\u2013250","journal-title":"Journal of Autonomous Agents and Multi-Agent Systems"},{"key":"5038_CR29","first-page":"302","volume-title":"In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI).","author":"F Oliehoek","year":"2013","unstructured":"Oliehoek F. Sufficient plan-time statistics for decentralized POMDPs. In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). 2013, 302\u2013308"},{"key":"5038_CR30","first-page":"90","volume-title":"In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI).","author":"J Dibangoye","year":"2013","unstructured":"Dibangoye J, Amato C, Buffet O, Charpillet F. Optimally solving Dec-POMDPs as continuous-state MDPs. In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI). 2013, 90\u201396"}],"container-title":["Frontiers of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-015-5038-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11704-015-5038-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11704-015-5038-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,3]],"date-time":"2019-09-03T16:10:43Z","timestamp":1567527043000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11704-015-5038-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,19]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,8]]}},"alternative-id":["5038"],"URL":"https:\/\/doi.org\/10.1007\/s11704-015-5038-5","relation":{},"ISSN":["2095-2228","2095-2236"],"issn-type":[{"value":"2095-2228","type":"print"},{"value":"2095-2236","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,19]]}}}