{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:49:57Z","timestamp":1760708997570,"version":"3.38.0"},"reference-count":56,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2016,2,3]],"date-time":"2016-02-03T00:00:00Z","timestamp":1454457600000},"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,4]]},"abstract":"<jats:p> In this paper, we consider a class of continuous-time, continuous-space stochastic optimal control problems. Using the Markov chain approximation method and recent advances in sampling-based algorithms for deterministic path planning, we propose a novel algorithm called the incremental Markov Decision Process to incrementally compute control policies that approximate arbitrarily well an optimal policy in terms of the expected cost. The main idea behind the algorithm is to generate a sequence of finite discretizations of the original problem through random sampling of the state space. At each iteration, the discretized problem is a Markov Decision Process that serves as an incrementally refined model of the original problem. We show that with probability one, (i) the sequence of the optimal value functions for each of the discretized problems converges uniformly to the optimal value function of the original stochastic optimal control problem, and (ii) the original optimal value function can be computed efficiently in an incremental manner using asynchronous value iterations. Thus, the proposed algorithm provides an anytime approach to the computation of optimal control policies of the continuous problem. The effectiveness of the proposed approach is demonstrated on motion planning and control problems in cluttered environments in the presence of process noise. <\/jats:p>","DOI":"10.1177\/0278364915616866","type":"journal-article","created":{"date-parts":[[2016,2,4]],"date-time":"2016-02-04T03:10:20Z","timestamp":1454555420000},"page":"305-333","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":8,"title":["An incremental sampling-based algorithm for stochastic optimal control"],"prefix":"10.1177","volume":"35","author":[{"given":"Vu Anh","family":"Huynh","sequence":"first","affiliation":[{"name":"Laboratory of Information and Decision Systems, Massachusetts Institute of Technology, USA"}]},{"given":"Sertac","family":"Karaman","sequence":"additional","affiliation":[{"name":"Laboratory of Information and Decision Systems, Massachusetts Institute of Technology, USA"}]},{"given":"Emilio","family":"Frazzoli","sequence":"additional","affiliation":[{"name":"Laboratory of Information and Decision Systems, Massachusetts Institute of Technology, USA"}]}],"member":"179","published-online":{"date-parts":[[2016,2,3]]},"reference":[{"key":"bibr1-0278364915616866","doi-asserted-by":"crossref","unstructured":"Alterovitz R, Simeon T, Goldberg K (2007) The stochastic motion roadmap: A sampling framework for planning with markov motion uncertainty. In: Proceedings of Robotics: Science and Systems. Atlanta: MIT Press, pp. 233\u2013240. Available at: http:\/\/robotics.cs.unc.edu\/publications\/Alterovitz2007_RSS.pdf","DOI":"10.7551\/mitpress\/7830.003.0031"},{"key":"bibr2-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1017\/S000186780000001X"},{"key":"bibr3-0278364915616866","volume-title":"Dynamic Programming and Optimal Control, Two Volume Set","author":"Bertsekas DP","year":"2001","edition":"2"},{"volume-title":"Parallel and distributed computation: Numerical methods","year":"1989","author":"Bertsekas DP","key":"bibr4-0278364915616866"},{"volume-title":"Neuro-Dynamic Programming (Optimization and Neural Computation Series, 3)","year":"1996","author":"Bertsekas DP","key":"bibr5-0278364915616866"},{"key":"bibr6-0278364915616866","volume-title":"Convergence of probability measures","volume":"493","author":"Billingsley P","year":"2009"},{"key":"bibr7-0278364915616866","volume-title":"Probability and measure","volume":"939","author":"Billingsley P","year":"2012"},{"key":"bibr8-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1016\/S0005-1098(00)00050-9"},{"key":"bibr9-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814068"},{"key":"bibr10-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139167383"},{"key":"bibr11-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2003.10.002"},{"key":"bibr12-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441"},{"key":"bibr13-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1110.1377"},{"key":"bibr14-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1090.0796"},{"key":"bibr15-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1137\/050640515"},{"key":"bibr16-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2012.6426014"},{"key":"bibr17-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2013.6580549"},{"key":"bibr18-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1109\/9.133184"},{"key":"bibr19-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1137\/S0363012994267789"},{"volume-title":"Partial Differential Equations (Graduate Studies in Mathematics, Volume 19)","year":"1998","author":"Evans LC","key":"bibr20-0278364915616866"},{"key":"bibr21-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-4266(03)00138-9"},{"key":"bibr22-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1137\/0109045"},{"key":"bibr23-0278364915616866","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198572237.001.0001","volume-title":"Probability and Random Processes","author":"Grimmett GR","year":"2001","edition":"3"},{"key":"bibr24-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050241"},{"key":"bibr25-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6225158"},{"journal-title":"arXiv preprint arXiv:1312.7602","year":"2013","author":"Huynh VA","key":"bibr26-0278364915616866"},{"key":"bibr27-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2014.7039669"},{"key":"bibr28-0278364915616866","first-page":"188","volume-title":"American Control Conference","author":"Jeon J","year":"2013"},{"key":"bibr29-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr30-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631297"},{"key":"bibr31-0278364915616866","volume-title":"Brownian Motion and Stochastic Calculus (Graduate Texts in Mathematics)","author":"Karatzas I","year":"1991","edition":"2"},{"key":"bibr32-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"bibr33-0278364915616866","first-page":"2200","volume-title":"International Conference on Robotics and Automation (ICRA)","author":"Kim J","year":"2003"},{"key":"bibr34-0278364915616866","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2008.IV.009"},{"volume-title":"Numerical Methods for Stochastic Control Problems in Continuous Time (Stochastic Modelling and Applied Probability)","year":"2000","author":"Kushner HJ","key":"bibr35-0278364915616866"},{"key":"bibr36-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1109\/TCST.2008.2012116"},{"key":"bibr37-0278364915616866","unstructured":"LaValle SM (1998) Rapidly-exploring random trees: A new tool for path planning. Technical report, Computer Science Department, Iowa State University, Iowa."},{"key":"bibr38-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"bibr39-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696590"},{"key":"bibr40-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75225-7_18"},{"key":"bibr41-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1137\/0327031"},{"issue":"2","key":"bibr42-0278364915616866","first-page":"291","volume":"49","author":"Munos R","year":"2001","journal-title":"Machine Learning"},{"key":"bibr43-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02847-6"},{"journal-title":"Nonlinear control of underactuated mechanical systems with application to robotics and aerospace vehicles","year":"2001","author":"Olfati-Saber R","key":"bibr44-0278364915616866"},{"key":"bibr45-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"bibr46-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6094800"},{"key":"bibr47-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696587"},{"key":"bibr48-0278364915616866","doi-asserted-by":"crossref","unstructured":"Rust J (1997a) A comparison of policy iteration methods for solving continuous-state, infinite-horizon markovian decision problems using random, quasi-random, and deterministic discretizationsComputational Economics, pp. 1\u201350. Available at: http:\/\/econwpa.repec.org\/eps\/comp\/papers\/9704\/9704001.pdf","DOI":"10.2139\/ssrn.37768"},{"key":"bibr49-0278364915616866","doi-asserted-by":"publisher","DOI":"10.2307\/2171751"},{"key":"bibr50-0278364915616866","volume-title":"Optimal Control Theory: Applications to Management Science and Economics","author":"Sethi SP","year":"2006","edition":"2"},{"key":"bibr51-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1137\/1101022"},{"volume-title":"Stochastic geometry and its applications","year":"1995","author":"Stoyan D","key":"bibr52-0278364915616866"},{"volume-title":"Probabilistic Robotics (Intelligent Robotics and Autonomous Agents)","year":"2005","author":"Thrun S","key":"bibr53-0278364915616866"},{"key":"bibr54-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1162\/0899766053491887"},{"key":"bibr55-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024980623095"},{"key":"bibr56-0278364915616866","doi-asserted-by":"publisher","DOI":"10.1023\/B:WINE.0000013081.09837.c0"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915616866","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364915616866","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915616866","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T11:08:20Z","timestamp":1740827300000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364915616866"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,3]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["10.1177\/0278364915616866"],"URL":"https:\/\/doi.org\/10.1177\/0278364915616866","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"type":"print","value":"0278-3649"},{"type":"electronic","value":"1741-3176"}],"subject":[],"published":{"date-parts":[[2016,2,3]]}}}