{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:51:48Z","timestamp":1777715508871,"version":"3.51.4"},"reference-count":50,"publisher":"SAGE Publications","issue":"8","license":[{"start":{"date-parts":[[2015,8,21]],"date-time":"2015-08-21T00:00:00Z","timestamp":1440115200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2016,7]]},"abstract":"<jats:p>We present new parallel algorithms that solve continuous-state partially observable Markov decision process (POMDP) problems using the GPU (gPOMDP) and a hybrid of the GPU and CPU (hPOMDP). We choose the Monte Carlo value iteration (MCVI) method as our base algorithm and parallelize this algorithm using the multi-level parallel formulation of MCVI. For each parallel level, we propose efficient algorithms to utilize the massive data parallelism available on modern GPUs. Our GPU-based method uses the two workload distribution techniques, compute\/data interleaving and workload balancing, in order to obtain the maximum parallel performance at the highest level. Here we also present a CPU\u2013GPU hybrid method that takes advantage of both CPU and GPU parallelism in order to solve highly complex POMDP planning problems. The CPU is responsible for data preparation, while the GPU performs Monte Cacrlo simulations; these operations are performed concurrently using the compute\/data overlap technique between the CPU and GPU. To the best of the authors\u2019 knowledge, our algorithms are the first parallel algorithms that efficiently execute POMDP in a massively parallel fashion utilizing the GPU or a hybrid of the GPU and CPU. Our algorithms outperform the existing CPU-based algorithm by a factor of 75\u201399 based on the chosen benchmark.<\/jats:p>","DOI":"10.1177\/0278364915594856","type":"journal-article","created":{"date-parts":[[2015,8,21]],"date-time":"2015-08-21T21:50:24Z","timestamp":1440193824000},"page":"928-942","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":13,"title":["Massively parallel motion planning algorithms under uncertainty using POMDP"],"prefix":"10.1177","volume":"35","author":[{"given":"Taekhee","family":"Lee","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Ewha Womans University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Young J.","family":"Kim","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Ewha Womans University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2015,8,21]]},"reference":[{"key":"bibr1-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17452-0_11"},{"key":"bibr2-0278364915594856","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2011.VII.001"},{"key":"bibr3-0278364915594856","volume-title":"Dynamic Programming","author":"Bellman RE","year":"1957"},{"key":"bibr4-0278364915594856","volume-title":"Proceedings of robotics: science and systems","author":"Berg JVD","year":"2010"},{"key":"bibr5-0278364915594856","volume-title":"Proceedings of international symposium of robotics research (ISRR)","author":"Berg JVD","year":"2011"},{"key":"bibr6-0278364915594856","volume-title":"Proceedings of AAAI conference on artificial intelligence","author":"Berg JVD","year":"2012"},{"key":"bibr7-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1177\/0278364912456319"},{"key":"bibr8-0278364915594856","volume-title":"2007 IEEE international conference on robotics and automation","author":"Brendan B","year":"2007"},{"key":"bibr9-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2006.05.007"},{"key":"bibr10-0278364915594856","volume-title":"International symposium on artificial intelligence and mathematics","author":"Brunskill E","year":"2008"},{"key":"bibr11-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.1996.571080"},{"key":"bibr12-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1023\/B:DISC.0000028199.78776.c4"},{"key":"bibr13-0278364915594856","volume-title":"Proceedings of the international workshop on the algorithmic foundations of robotics","author":"Guibas LJ","year":"2008"},{"key":"bibr14-0278364915594856","volume-title":"International conference on automated planning and scheduling","author":"Hansen E","year":"2003"},{"key":"bibr15-0278364915594856","first-page":"211","volume-title":"Proceedings of AAAI conference on artificial intelligence","author":"Hansen EA","year":"1998"},{"key":"bibr16-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1613\/jair.678"},{"key":"bibr17-0278364915594856","volume-title":"Proceedings of international conference on vision systems","author":"Hoey J","year":"2007"},{"key":"bibr18-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2008.4543611"},{"key":"bibr19-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00023-X"},{"key":"bibr20-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1177\/0278364910386986"},{"key":"bibr21-0278364915594856","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2008.IV.009"},{"key":"bibr22-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"bibr23-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631227"},{"key":"bibr24-0278364915594856","volume-title":"Advances in neural information processing systems (NIPS)","author":"Lim ZW","year":"2011"},{"key":"bibr25-0278364915594856","doi-asserted-by":"crossref","unstructured":"Luebke D, Harris M, Kr\u00fcger J, Purcell T, Govindaraju N, Buck I, (2004) \u2018GPGPU: general purpose computation on graphics hardware\u2019. In: SIGGRAPH\u201904: ACM SIGGRAPH 2004 Course Notes.","DOI":"10.1145\/1103900.1103933"},{"key":"bibr26-0278364915594856","volume-title":"Proceedings of 16th national conference of the American Association for Artificial Intelligence","author":"Madani O","year":"1999"},{"key":"bibr27-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2006.1641882"},{"key":"bibr28-0278364915594856","unstructured":"NVIDIA (2012) Cuda programming guide 4.2. http:\/\/developer.nvidia.com\/cuda\/nvidia-gpu-computing-documentation."},{"key":"bibr29-0278364915594856","unstructured":"NVIDIA (2014) NVIDIA GRID. http:\/\/www.nvidia.com\/object\/nvidia-grid.html."},{"key":"bibr30-0278364915594856","doi-asserted-by":"crossref","unstructured":"Pan J, Manocha D (2010) GPU-based parallel collision detection for real-time motion planning. In: Workshop on algorithmic foundation of robotics (WAFR).","DOI":"10.1007\/978-3-642-17452-0_13"},{"key":"bibr31-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911429335"},{"key":"bibr32-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1287\/moor.12.3.441"},{"key":"bibr33-0278364915594856","volume-title":"International conference on automated planning and scheduling (ICAPS)","author":"Park C","year":"2012"},{"key":"bibr34-0278364915594856","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2011.VII.033"},{"key":"bibr35-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6224727"},{"key":"bibr36-0278364915594856","first-page":"477","volume-title":"Proceedings of the conference on uncertainty in artificial intelligence","author":"Pineau J","year":"2003"},{"key":"bibr37-0278364915594856","first-page":"2329","volume":"7","author":"Porta JM","year":"2006","journal-title":"Journal of Machine Learning Research"},{"key":"bibr38-0278364915594856","volume-title":"International symposium on artificial intelligence and mathematics","author":"Prentice S","year":"2007"},{"key":"bibr39-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1613\/jair.2567"},{"key":"bibr40-0278364915594856","volume-title":"Finding Approximate POMDP solutions Through Belief Compression","author":"Roy N","year":"2003"},{"key":"bibr41-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1109\/TSMCB.2009.2034015"},{"key":"bibr42-0278364915594856","volume-title":"Proceedings of the international joint conference on artificial intelligence","author":"Shani G","year":"2007"},{"key":"bibr43-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-012-9200-2"},{"key":"bibr44-0278364915594856","first-page":"1080","volume-title":"Proceedings of the international joint conference on artificial intelligence","author":"Simmons R","year":"1995"},{"issue":"5","key":"bibr45-0278364915594856","first-page":"1071","volume":"21","author":"Smallwood RD","year":"1973","journal-title":"Artificial Intelligence"},{"key":"bibr46-0278364915594856","volume-title":"Proceedings of the conference on uncertainty in artificial intelligence","author":"Smith T","year":"2005"},{"key":"bibr47-0278364915594856","volume-title":"The optimal control of partially observable Markov processes","author":"Sondik EJ","year":"1971"},{"key":"bibr48-0278364915594856","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1307420"},{"key":"bibr49-0278364915594856","volume-title":"Proceedings of the IEEE\/RSJ international conference on robotics and automation","author":"Theocharous G","year":"2002"},{"key":"bibr50-0278364915594856","first-page":"1064","volume-title":"Advances in Neural Information Processing Systems 12","author":"Thrun S","year":"2000"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915594856","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364915594856","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915594856","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:22Z","timestamp":1777457722000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364915594856"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,21]]},"references-count":50,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2016,7]]}},"alternative-id":["10.1177\/0278364915594856"],"URL":"https:\/\/doi.org\/10.1177\/0278364915594856","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,21]]}}}