{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T16:18:37Z","timestamp":1783700317474,"version":"3.55.0"},"reference-count":116,"publisher":"Annual Reviews","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Annu. Rev. Control Robot. Auton. Syst."],"published-print":{"date-parts":[[2018,5,28]]},"abstract":"<jats:p> Robots with many degrees of freedom (e.g., humanoid robots and mobile manipulators) have increasingly been employed to accomplish realistic tasks in domains such as disaster relief, spacecraft logistics, and home caretaking. Finding feasible motions for these robots autonomously is essential for their operation. Sampling-based motion planning algorithms are effective for these high-dimensional systems; however, incorporating task constraints (e.g., keeping a cup level or writing on a board) into the planning process introduces significant challenges. This survey describes the families of methods for sampling-based planning with constraints and places them on a spectrum delineated by their complexity. Constrained sampling-based methods are based on two core primitive operations: ( a) sampling constraint-satisfying configurations and ( b) generating constraint-satisfying continuous motion. Although this article presents the basics of sampling-based planning for contextual background, it focuses on the representation of constraints and sampling-based planners that incorporate constraints. <\/jats:p>","DOI":"10.1146\/annurev-control-060117-105226","type":"journal-article","created":{"date-parts":[[2018,2,5]],"date-time":"2018-02-05T17:29:30Z","timestamp":1517851770000},"page":"159-185","source":"Crossref","is-referenced-by-count":170,"title":["Sampling-Based Methods for Motion Planning with Constraints"],"prefix":"10.1146","volume":"1","author":[{"given":"Zachary","family":"Kingston","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rice University, Houston, Texas 77005, USA;, ,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mark","family":"Moll","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rice University, Houston, Texas 77005, USA;, ,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lydia E.","family":"Kavraki","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Rice University, Houston, Texas 77005, USA;, ,"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"22","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5979830"},{"key":"B2","volume-title":"The Complexity of Robot Motion Planning","author":"Canny JF","year":"1988"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500106"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1177\/027836499101000604"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1109\/70.163777"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915594029"},{"key":"B7","volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementations","author":"Choset H","year":"2005"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-015-9440-5"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(75)90007-7"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1981.4308708"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1109\/JRA.1987.1087068"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1109\/70.345948"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1109\/TMMS.1969.299896"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1080\/2151237X.2005.10129202"},{"key":"B16","unstructured":"16.\u2002  Beeson  P,  Hart  S,  Gee  S.  2016.  Cartesian motion planning & task programming with CRAFTSMAN.  Poster presented at Robot. Sci. Syst. Workshop Task Motion Plan.  Cambridge, MA,  July 15"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.65"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1109\/21.148404"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913488805"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980280"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914528132"},{"key":"B23","unstructured":"23.\u2002  Dong  J,  Mukadam  M,  Dellaert  F,  Boots  B.  2016.  Motion planning as probabilistic inference using Gaussian processes and factor graphs. In  Robotics: Science and Systems XII, ed.  D Hsu, N Amato, S Berman, S Jacobs, chap. 1. N.p.: Robot. Sci. Syst. Found."},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1177\/02783649922067753"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-anchem-062011-143024"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1109\/ARSO.2017.8025204"},{"key":"B27","volume-title":"A Comprehensive Introduction to Differential Geometry","author":"Spivak M","year":"1999"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2010.2044949"},{"key":"B29","unstructured":"29.\u2002  Berenson  D.  2011.  Constrained manipulation planning.  PhD Thesis, Carnegie Mellon Univ.,  Pittsburgh, PA"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1109\/70.976030"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2012.2222272"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2016.7759083"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1142\/S0219843605000594"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045471"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908098447"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6224555"},{"key":"B37","unstructured":"37.\u2002  Reid  W,  Fitch  R,  G\u00f6ktogan  AH,  Sukkarieh  S.  2016.  Motion planning for reconfigurable mobile robots using hierarchical fast marching trees.  Presented at Workshop Algorithmic Found. Robot., 12th, San Francisco, Dec.  18\u201320.  Paper available at http:\/\/wafr2016.berkeley.edu\/program.html"},{"key":"B38","unstructured":"38.\u2002  Dantam  NT,  Kingston  ZK,  Chaudhuri  S,  Kavraki  LE.  2016.  Incremental task and motion planning: a constraint-based approach. In  Robotics: Science and Systems XII, ed.  D Hsu, N Amato, S Berman, S Jacobs, chap. 2. N.p.: Robot. Sci. Syst. Found."},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6943079"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980391"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2014.2302442"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2004.824649"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6225300"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000285"},{"key":"B48","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2005.I.031"},{"key":"B49","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2160466"},{"key":"B50","first-page":"155","volume-title":"Robotics: The Algorithmic Perspective","author":"Amato N","year":"1999"},{"key":"B51","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1999.772447"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1999.772448"},{"key":"B53","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2003.1242285"},{"key":"B54","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2014.2331983"},{"key":"B55","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045481"},{"key":"B56","first-page":"1135","volume-title":"Handbook of Discrete and Computational Geometry","author":"Andoni A","year":"2017","edition":"3"},{"key":"B57","doi-asserted-by":"publisher","DOI":"10.1145\/325165.325242"},{"key":"B58","first-page":"403","volume-title":"Robotics Research: The Tenth International Symposium","author":"S\u00e1nchez G","year":"2001"},{"key":"B59","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2009.5354403"},{"key":"B60","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2012.2205651"},{"key":"B61","doi-asserted-by":"publisher","DOI":"10.1177\/0278364907079280"},{"key":"B62","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"B63","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139620"},{"key":"B64","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631301"},{"key":"B65","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6942793"},{"key":"B66","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631299"},{"key":"B67","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2602363"},{"key":"B68","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915614386"},{"key":"B69","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913498292"},{"key":"B70","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2015.2448276"},{"key":"B71","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"B72","doi-asserted-by":"publisher","DOI":"10.1126\/science.290.5500.2319"},{"key":"B73","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15552-9_53"},{"key":"B74","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.95.15.8431"},{"key":"B75","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2006.07.032"},{"key":"B76","doi-asserted-by":"publisher","DOI":"10.1145\/2516971.2516977"},{"key":"B77","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914527855"},{"key":"B78","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-52844-0"},{"key":"B79","volume-title":"Robotics Research: The 18th International Symposium (ISRR)","author":"Kingston Z","year":"2018"},{"key":"B80","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139537"},{"key":"B81","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989463"},{"key":"B82","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-68405-3_18"},{"key":"B83","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696513"},{"key":"B84","volume-title":"Numerical Methods for Unconstrained Optimization and Nonlinear Equations","author":"Dennis J","year":"1983"},{"key":"B85","volume-title":"Numerical Recipes in C: The Art of Scientific Computing","author":"Press WH","year":"1992","edition":"2"},{"key":"B86","unstructured":"86.\u2002  Mirabel  J,  Lamiraux  F.  2017.  Manipulation planning: building paths on constrained manifolds.  Tech. Rep., LAAS-GEPETTO \u2013 \u00c9quipe Mouvement des Syst\u00e8mes Anthropomorphes, Toulouse, Fr."},{"key":"B87","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-987X(199906)20:8<819::AID-JCC8>3.0.CO;2-Y"},{"key":"B88","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2002.1014856"},{"key":"B89","doi-asserted-by":"publisher","DOI":"10.1109\/IRDS.2002.1043993"},{"key":"B90","first-page":"1875","volume-title":"2005 IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Yao Z","year":"2005"},{"key":"B91","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2012.6385587"},{"key":"B92","doi-asserted-by":"publisher","DOI":"10.1080\/01691864.2015.1105150"},{"key":"B93","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2017.2708134"},{"key":"B94","doi-asserted-by":"publisher","DOI":"10.1109\/ICHR.2007.4813913"},{"key":"B95","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2009.5354287"},{"key":"B96","first-page":"2965","volume-title":"2015 IEEE International Conference on Robotics and Automation","author":"Vendittelli M","year":"2009"},{"key":"B97","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6697190"},{"key":"B98","doi-asserted-by":"publisher","DOI":"10.1186\/1472-6807-13-S1-S9"},{"key":"B99","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1004361"},{"key":"B100","unstructured":"100.\u2002  Fonseca  R,  Budday  D,  van dem Bedem  H.  2016.  Collision-free Poisson motion planning in ultra high-dimensional molecular conformation spaces.  arXiv: 1607.07483"},{"key":"B101","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127402004498"},{"key":"B102","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(96)00204-0"},{"key":"B103","doi-asserted-by":"publisher","DOI":"10.1017\/S0263574714001234"},{"key":"B104","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2013.2260679"},{"key":"B105","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2013.04.012"},{"key":"B106","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"B107","unstructured":"107.\u2002  Bordalba  R,  Ros  L,  Porta  JM.  2017.  Kinodynamic planning on constraint manifolds.  arXiv: 1705.07637"},{"key":"B108","unstructured":"108.\u2002  Voss  C,  Moll  M,  Kavraki  LE.  2017.  Atlas + X: sampling-based planners on constraint manifolds.  Tech. Rep. 17-02, Dep. Comput. Sci., Rice Univ., Houston, TX"},{"key":"B109","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908097211"},{"key":"B110","unstructured":"110.\u2002  McMahon  T.  2016.  Sampling based motion planning with reachable volumes.  PhD Thesis, Texas A&M Univ., College Station"},{"key":"B111","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013219111657"},{"key":"B112","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630792"},{"key":"B113","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17452-0_1"},{"key":"B114","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2012.6386092"},{"key":"B115","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139284"},{"key":"B116","unstructured":"116.\u2002  Hauser  K.  2016.  Continuous pseudoinversion of a multivariate function: application to global redundancy resolution.  Presented at Workshop Algorithmic Found. Robot., 12th, San Francisco, Dec.  18\u201320.  Paper available at http:\/\/wafr2016.berkeley.edu\/program.html"}],"container-title":["Annual Review of Control, Robotics, and Autonomous Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.annualreviews.org\/doi\/pdf\/10.1146\/annurev-control-060117-105226","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,8]],"date-time":"2021-10-08T10:50:20Z","timestamp":1633690220000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.annualreviews.org\/doi\/10.1146\/annurev-control-060117-105226"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,28]]},"references-count":116,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,5,28]]}},"alternative-id":["10.1146\/annurev-control-060117-105226"],"URL":"https:\/\/doi.org\/10.1146\/annurev-control-060117-105226","relation":{},"ISSN":["2573-5144","2573-5144"],"issn-type":[{"value":"2573-5144","type":"print"},{"value":"2573-5144","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,28]]}}}