{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:58:08Z","timestamp":1777715888517,"version":"3.51.4"},"reference-count":39,"publisher":"SAGE Publications","issue":"2-3","license":[{"start":{"date-parts":[[2020,7,20]],"date-time":"2020-07-20T00:00:00Z","timestamp":1595203200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"name":"ONR Global and AFRL grant","award":["N62909-18-1-2023"],"award-info":[{"award-number":["N62909-18-1-2023"]}]},{"name":"NUS AcRF Tier 1 grant","award":["R-252-000-A87-114"],"award-info":[{"award-number":["R-252-000-A87-114"]}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:p>Robust planning under uncertainty is critical for robots in uncertain, dynamic environments, but incurs high computational cost. State-of-the-art online search algorithms, such as DESPOT, have vastly improved the computational efficiency of planning under uncertainty and made it a valuable tool for robotics in practice. This work takes one step further by leveraging both CPU and GPU parallelization in order to achieve real-time online planning performance for complex tasks with large state, action, and observation spaces. Specifically, Hybrid Parallel DESPOT (HyP-DESPOT) is a massively parallel online planning algorithm that integrates CPU and GPU parallelism in a multi-level scheme. It performs parallel DESPOT tree search by simultaneously traversing multiple independent paths using multi-core CPUs; it performs parallel Monte Carlo simulations at the leaf nodes of the search tree using GPUs. HyP-DESPOT provably converges in finite time under moderate conditions and guarantees near-optimality of the solution. Experimental results show that HyP-DESPOT speeds up online planning by up to a factor of several hundred in several challenging robotic tasks in simulation, compared with the original DESPOT algorithm. It also exhibits real-time performance on a robot vehicle navigating among many pedestrians.<\/jats:p>","DOI":"10.1177\/0278364920937074","type":"journal-article","created":{"date-parts":[[2020,7,20]],"date-time":"2020-07-20T04:08:52Z","timestamp":1595218132000},"page":"558-573","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":35,"title":["HyP-DESPOT: A hybrid parallel algorithm for online planning under uncertainty"],"prefix":"10.1177","volume":"40","author":[{"given":"Panpan","family":"Cai","sequence":"first","affiliation":[{"name":"School of Computing, National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9804-6204","authenticated-orcid":false,"given":"Yuanfu","family":"Luo","sequence":"additional","affiliation":[{"name":"School of Computing, National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2309-4535","authenticated-orcid":false,"given":"David","family":"Hsu","sequence":"additional","affiliation":[{"name":"School of Computing, National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wee Sun","family":"Lee","sequence":"additional","affiliation":[{"name":"School of Computing, National University of Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2020,7,20]]},"reference":[{"key":"bibr1-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139219"},{"key":"bibr2-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1109\/CIG.2014.6932879"},{"key":"bibr3-0278364920937074","doi-asserted-by":"publisher","DOI":"10.21236\/ADA459559"},{"key":"bibr4-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6095053"},{"key":"bibr5-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2017.2715835"},{"key":"bibr6-0278364920937074","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2018.XIV.004"},{"key":"bibr7-0278364920937074","first-page":"93","volume-title":"Proceedings of the Computer Games Workshop","author":"Cazenave T","year":"2007"},{"key":"bibr8-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1993.292122"},{"key":"bibr9-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87608-3_6"},{"key":"bibr10-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2000.912059"},{"key":"bibr11-0278364920937074","author":"Coquelin PA","year":"2007","journal-title":"arXiv preprint cs\/0703062"},{"key":"bibr12-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1613\/jair.3171"},{"key":"bibr13-0278364920937074","unstructured":"Intel Corporation (2018) Intel 64 and IA-32 architectures optimization reference manual. https:\/\/intel.ly\/2lgN4rc."},{"key":"bibr14-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631304"},{"key":"bibr15-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32467-8_31"},{"key":"bibr16-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017932429737"},{"key":"bibr17-0278364920937074","volume-title":"Algorithmic Foundations of Robotics XII\u2014Proceedings of International Workshop on the Algorithmic Foundations of Robotics (WAFR)","author":"Koval M","year":"2016"},{"key":"bibr18-0278364920937074","author":"Kurniawati H","year":"2008","journal-title":"Proceedings of Robotics: Science and Systems"},{"key":"bibr19-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915594856"},{"key":"bibr20-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2016.7759839"},{"key":"bibr21-0278364920937074","first-page":"1287","volume-title":"Advances in Neural Information Processing Systems","volume":"24","author":"Lim Z","year":"2011"},{"key":"bibr22-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1991.131722"},{"key":"bibr23-0278364920937074","unstructured":"Luitjens J (2011) GPU computing webinar. https:\/\/bit.ly\/2YUvefG."},{"key":"bibr24-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918780322"},{"key":"bibr25-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2018.2852793"},{"key":"bibr26-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-0909-0"},{"key":"bibr27-0278364920937074","unstructured":"NVIDIA Corporation (2017) NVIDIA CUDA C programming guide. Version 8.0. https:\/\/bit.ly\/1IyiYCS."},{"key":"bibr28-0278364920937074","first-page":"1025","volume-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence","author":"Pineau J","year":"2003"},{"key":"bibr29-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2005.847599"},{"key":"bibr30-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1177\/0278364909341659"},{"key":"bibr31-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2011.370"},{"key":"bibr32-0278364920937074","first-page":"2592","volume-title":"Proceedings of the 20th International Joint Conference on Artifical Intelligence","author":"Ross S","year":"2007"},{"key":"bibr33-0278364920937074","volume-title":"Artificial Intelligence: A Modern Approach","author":"Russell SJ","year":"2002","edition":"2"},{"key":"bibr34-0278364920937074","first-page":"2164","volume-title":"Advances in Neural Information Processing Systems","volume":"23","author":"Silver D","year":"2010"},{"key":"bibr35-0278364920937074","first-page":"520","volume-title":"Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence","author":"Smith T","year":"2004"},{"issue":"9","key":"bibr36-0278364920937074","first-page":"661","volume":"23","author":"Stanley TS","year":"2006","journal-title":"Journal Robotics System"},{"key":"bibr37-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406562"},{"key":"bibr38-0278364920937074","first-page":"95","volume-title":"AAAI Fall Symposium on Sequential Decision Making for Intelligent Agents (SDMIA)","author":"Wray KH","year":"2015"},{"key":"bibr39-0278364920937074","doi-asserted-by":"publisher","DOI":"10.1613\/jair.5328"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364920937074","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364920937074","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364920937074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:46Z","timestamp":1777457806000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364920937074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,20]]},"references-count":39,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["10.1177\/0278364920937074"],"URL":"https:\/\/doi.org\/10.1177\/0278364920937074","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,20]]}}}