{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T15:15:07Z","timestamp":1784128507453,"version":"3.55.0"},"reference-count":69,"publisher":"SAGE Publications","issue":"13-14","license":[{"start":{"date-parts":[[2019,10,10]],"date-time":"2019-10-10T00:00:00Z","timestamp":1570665600000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1122374"],"award-info":[{"award-number":["1122374"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1420316"],"award-info":[{"award-number":["1420316"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1523767"],"award-info":[{"award-number":["1523767"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1723381"],"award-info":[{"award-number":["1723381"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-17-1-0165"],"award-info":[{"award-number":["FA9550-17-1-0165"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-14-1-0486"],"award-info":[{"award-number":["N00014-14-1-0486"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2018,12]]},"abstract":"<jats:p>This paper presents a general-purpose formulation of a large class of discrete-time planning problems, with hybrid state and control-spaces, as factored transition systems. Factoring allows state transitions to be described as the intersection of several constraints each affecting a subset of the state and control variables. Robotic manipulation problems with many movable objects involve constraints that only affect several variables at a time and therefore exhibit large amounts of factoring. We develop a theoretical framework for solving factored transition systems with sampling-based algorithms. The framework characterizes conditions on the submanifold in which solutions lie, leading to a characterization of robust feasibility that incorporates dimensionality-reducing constraints. It then connects those conditions to corresponding conditional samplers that can be composed to produce values on this submanifold. We present two domain-independent, probabilistically complete planning algorithms that take, as input, a set of conditional samplers. We demonstrate the empirical efficiency of these algorithms on a set of challenging task and motion planning problems involving picking, placing, and pushing.<\/jats:p>","DOI":"10.1177\/0278364918802962","type":"journal-article","created":{"date-parts":[[2018,10,10]],"date-time":"2018-10-10T12:15:19Z","timestamp":1539173719000},"page":"1796-1825","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":64,"title":["Sampling-based methods for factored task and motion planning"],"prefix":"10.1177","volume":"37","author":[{"given":"Caelan Reed","family":"Garrett","sequence":"first","affiliation":[{"name":"MIT CSAIL, Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom\u00e1s","family":"Lozano-P\u00e9rez","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leslie Pack","family":"Kaelbling","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Cambridge, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2018,10,10]]},"reference":[{"key":"bibr1-0278364918802962","volume-title":"Workshop on Algorithmic Foundations of Robotics (WAFR)","author":"Alami R","year":"1994"},{"key":"bibr2-0278364918802962","volume-title":"International Symposium of Robotic Research (ISRR)","author":"Alami R","year":"1990"},{"key":"bibr3-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00202-T"},{"key":"bibr4-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/5.871304"},{"key":"bibr5-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.1995.tb00052.x"},{"key":"bibr6-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1177\/027836499701600604"},{"key":"bibr7-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630814"},{"key":"bibr8-0278364918802962","volume-title":"Manipulation with Diverse Actions","author":"Barry JL","year":"2013"},{"key":"bibr9-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509694"},{"key":"bibr10-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"bibr11-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00108-4"},{"key":"bibr12-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908097884"},{"key":"bibr13-0278364918802962","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2016.XII.002"},{"key":"bibr14-0278364918802962","volume-title":"RSS Workshop on Combined Robot Motion Planning and AI Planning for Practical Applications","author":"de Silva L","year":"2013"},{"key":"bibr15-0278364918802962","unstructured":"Dechter R (1992) Constraint networks. Technical Report, Information and Computer Science, University of California, Irvine. Available at: http:\/\/www.ics.uci.edu\/~csp\/r17-survey.pdf (accessed 9 September 2018)."},{"key":"bibr16-0278364918802962","volume-title":"International Conference on Automated Planning and Scheduling (ICAPS)","author":"Dellin CM","year":"2016"},{"key":"bibr17-0278364918802962","volume-title":"Workshop on Algorithmic Foundations of Robotics (WAFR)","author":"Deshpande A","year":"2016"},{"key":"bibr18-0278364918802962","volume-title":"Automated Construction of Robotic Manipulation Programs","author":"Diankov R","year":"2010"},{"key":"bibr19-0278364918802962","unstructured":"Diankov R, Kuffner J (2008) Openrave: A planning architecture for autonomous robotics. Technical Report CMU-RI-TR-08-34, Robotics Institute, Carnegie Mellon University."},{"key":"bibr20-0278364918802962","first-page":"114","volume-title":"International Conference on Automated Planning and Scheduling (ICAPS)","author":"Dornhege C","year":"2009"},{"key":"bibr21-0278364918802962","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) Workshop on AI-based robotics","author":"Dornhege C","year":"2013"},{"key":"bibr22-0278364918802962","volume-title":"4th International Planning Competition (IPC\u201904), at ICAPS\u201904","author":"Edelkamp S","year":"2004"},{"key":"bibr23-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980160"},{"key":"bibr24-0278364918802962","first-page":"1123","volume-title":"Proceedings of the Twelfth National Conference on Artificial Intelligence","volume":"2","author":"Erol K","year":"1994"},{"key":"bibr25-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(71)90010-5"},{"key":"bibr26-0278364918802962","volume-title":"Workshop on the Algorithmic Foundations of Robotics (WAFR)","author":"Garrett CR","year":"2014"},{"key":"bibr27-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2015.7354287"},{"key":"bibr28-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1177\/0278364917739114"},{"key":"bibr29-0278364918802962","unstructured":"Garrett CR, Lozano-P\u00e9rez T, Kaelbling LP (2017b) Strips planning in infinite domains. Preprint arXiv:1701.00287."},{"key":"bibr30-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1177\/0278364909352098"},{"key":"bibr31-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1177\/0278364910386985"},{"key":"bibr32-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1705"},{"key":"bibr33-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59615-5_13"},{"key":"bibr34-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1613\/jair.855"},{"key":"bibr35-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1997.619371"},{"key":"bibr36-0278364918802962","volume-title":"An Introduction to Bayesian Networks","volume":"210","author":"Jensen FV","year":"1996"},{"key":"bibr37-0278364918802962","volume-title":"IEEE International Conference on Robotics and Automation (ICRA)","author":"Kaelbling LP","year":"2011"},{"key":"bibr38-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr39-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/70.660866"},{"key":"bibr40-0278364918802962","volume-title":"Practical Motion Planning in Robotics: Current Approaches and Future Directions","author":"Kavraki LE","year":"1998"},{"key":"bibr41-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225159"},{"key":"bibr42-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"bibr43-0278364918802962","volume-title":"Robotics: Science and Systems (RSS)","author":"Krontiris A","year":"2015"},{"key":"bibr44-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487581"},{"key":"bibr45-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"bibr46-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914545811"},{"key":"bibr47-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2012.6385972"},{"key":"bibr48-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0036069"},{"key":"bibr49-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"bibr50-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1981.4308589"},{"key":"bibr51-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1987.1087847"},{"key":"bibr52-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6943079"},{"key":"bibr53-0278364918802962","unstructured":"McDermott D, Ghallab M, Howe A, et al. (1998) PDDL: The planning domain definition language. Technical Report, Yale Center for Computational Vision and Control."},{"key":"bibr54-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/BioRob.2012.6290776"},{"key":"bibr55-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509563"},{"key":"bibr56-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045471"},{"key":"bibr57-0278364918802962","unstructured":"Smith R (2005) ODE: Open Dynamics Engine User Guide. Available at: http:\/\/ode.org\/ode-latest-userguide.pdf"},{"key":"bibr58-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6906922"},{"key":"bibr59-0278364918802962","volume-title":"Workshop on Algorithmic Foundations of Robotics (WAFR)","author":"Stilman M","year":"2006"},{"key":"bibr60-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363986"},{"key":"bibr61-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2005.05.004"},{"key":"bibr62-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2001.980716"},{"key":"bibr63-0278364918802962","first-page":"1930","volume-title":"AAAI Conference on Artificial Intelligence","author":"Toussaint M","year":"2015"},{"key":"bibr64-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989464"},{"key":"bibr65-0278364918802962","volume-title":"An Introduction to Manifolds","author":"Tu LW","year":"2010"},{"key":"bibr66-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00312-7_37"},{"key":"bibr67-0278364918802962","volume-title":"Workshop on the Algorithmic Foundations of Robotics (WAFR)","author":"Vega-Brown W","year":"2016"},{"key":"bibr68-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16595-0_37"},{"key":"bibr69-0278364918802962","doi-asserted-by":"publisher","DOI":"10.1145\/73393.73422"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364918802962","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364918802962","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364918802962","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364918802962","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:45Z","timestamp":1777457745000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364918802962"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,10]]},"references-count":69,"journal-issue":{"issue":"13-14","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.1177\/0278364918802962"],"URL":"https:\/\/doi.org\/10.1177\/0278364918802962","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,10]]}}}