{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,22]],"date-time":"2026-07-22T09:02:59Z","timestamp":1784710979697,"version":"3.55.0"},"reference-count":56,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2017,11,12]],"date-time":"2017-11-12T00:00:00Z","timestamp":1510444800000},"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":[[2018,1]]},"abstract":"<jats:p>Mobile manipulation problems involving many objects are challenging to solve due to the high dimensionality and multi-modality of their hybrid configuration spaces. Planners that perform a purely geometric search are prohibitively slow for solving these problems because they are unable to factor the configuration space. Symbolic task planners can efficiently construct plans involving many variables but cannot represent the geometric and kinematic constraints required in manipulation. We present the FFRob algorithm for solving task and motion planning problems. First, we introduce extended action specification (EAS) as a general purpose planning representation that supports arbitrary predicates as conditions. We adapt existing heuristic search ideas for solving strips planning problems, particularly delete-relaxations, to solve EAS problem instances. We then apply the EAS representation and planners to manipulation problems resulting in FFRob. FFRob iteratively discretizes task and motion planning problems using batch sampling of manipulation primitives and a multi-query roadmap structure that can be conditionalized to evaluate reachability under different placements of movable objects. This structure enables the EAS planner to efficiently compute heuristics that incorporate geometric and kinematic planning constraints to give a tight estimate of the distance to the goal. Additionally, we show FFRob is probabilistically complete and has a finite expected runtime. Finally, we empirically demonstrate FFRob\u2019s effectiveness on complex and diverse task and motion planning tasks including rearrangement planning and navigation among movable objects.<\/jats:p>","DOI":"10.1177\/0278364917739114","type":"journal-article","created":{"date-parts":[[2017,11,13]],"date-time":"2017-11-13T02:26:46Z","timestamp":1510540006000},"page":"104-136","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":103,"title":["FFRob: Leveraging symbolic planning for efficient task and motion planning"],"prefix":"10.1177","volume":"37","author":[{"given":"Caelan Reed","family":"Garrett","sequence":"first","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom\u00e1s","family":"Lozano-P\u00e9rez","sequence":"additional","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leslie Pack","family":"Kaelbling","sequence":"additional","affiliation":[{"name":"Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2017,11,12]]},"reference":[{"key":"bibr1-0278364917739114","first-page":"109","volume-title":"Workshop on algorithmic foundations of robotics (WAFR 1994)","author":"Alami R","year":"1994"},{"key":"bibr2-0278364917739114","first-page":"453","volume-title":"International symposium of robotic research (ISRR 1990)","author":"Alami R","year":"1990"},{"key":"bibr3-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8640.1995.tb00052.x"},{"key":"bibr4-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630814"},{"key":"bibr5-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00047-1"},{"key":"bibr6-0278364917739114","first-page":"360","volume-title":"5th european conference on planning (ECP)","author":"Bonet B","year":"1999"},{"key":"bibr7-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00108-4"},{"key":"bibr8-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90081-7"},{"key":"bibr9-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908097884"},{"key":"bibr10-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1613\/jair.3788"},{"key":"bibr11-0278364917739114","unstructured":"Dantam NT, Kingston Z, Chaudhuri S, Kavraki LE (2016) Incremental task and motion planning: A constraint-based approach. In: Robotics: science and systems (RSS 2016). Ann Arbor, Michigan, USA, 18\u201322 June 2016. Available at: http:\/\/www.roboticsproceedings.org\/rss12\/p02.html"},{"key":"bibr12-0278364917739114","unstructured":"de Silva L, Pandey AK, Gharbi M, Alami R (2013) Towards combining HTN planning and geometric task planning. In: RSS workshop on combined robot motion planning and AI planning for practical applications. Berkeley, CA, USA, 12\u201316 July 2014. Available at: https:\/\/arxiv.org\/abs\/1307.1482"},{"key":"bibr13-0278364917739114","unstructured":"Diankov R (2010) Automated construction of robotic manipulation programs. PhD Thesis, Robotics Institute, Carnegie Mellon University, USA."},{"key":"bibr14-0278364917739114","author":"Diankov R","year":"2008","journal-title":"Technical Report CMU-RI-TR-08-34, Carnegie Mellon University, USA"},{"key":"bibr15-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-012-9306-z"},{"key":"bibr16-0278364917739114","first-page":"114","volume-title":"International conference on automated planning and scheduling (ICAPS 2009)","author":"Dornhege C","year":"2009"},{"key":"bibr17-0278364917739114","volume-title":"IEEE\/RSJ international conference on intelligent robots and systems (IROS 2013)","author":"Dornhege C","year":"2013"},{"key":"bibr18-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980160"},{"key":"bibr19-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(71)90010-5"},{"key":"bibr20-0278364917739114","first-page":"179","volume-title":"Workshop on the algorithmic foundations of robotics (WAFR 2014)","author":"Garrett CR","year":"2014"},{"key":"bibr21-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2015.7354287"},{"key":"bibr22-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1016\/B978-155860856-6\/50004-1"},{"key":"bibr23-0278364917739114","first-page":"65","volume-title":"International conference on automated planning and scheduling (ICAPS 2012)","author":"Gregory P","year":"2012"},{"key":"bibr24-0278364917739114","volume-title":"ICAPS Workshop on Bridging the Gap between Task and Motion Planning","author":"Hauser K","year":"2009"},{"key":"bibr25-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1177\/0278364909352098"},{"key":"bibr26-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1177\/0278364910386985"},{"key":"bibr27-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1705"},{"key":"bibr28-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1613\/jair.855"},{"key":"bibr29-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980391"},{"key":"bibr30-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr31-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/70.660866"},{"key":"bibr32-0278364917739114","first-page":"33","volume-title":"Practical Motion Planning in Robotics: Current Approaches and Future Directions","author":"Kavraki LE","year":"1998"},{"key":"bibr33-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225159"},{"key":"bibr34-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"bibr35-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487583"},{"key":"bibr36-0278364917739114","doi-asserted-by":"crossref","unstructured":"Krontiris A, Bekris KE (2015) Dealing with difficult instances of object rearrangement. In: Robotics: science and systems (RSS 2015), Rome, Italy, 13\u201317 July 2015. Available at: http:\/\/www.roboticsproceedings.org\/rss11\/p45.html","DOI":"10.15607\/RSS.2015.XI.045"},{"key":"bibr37-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487581"},{"key":"bibr38-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"bibr39-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914545811"},{"key":"bibr40-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2012.6385972"},{"key":"bibr41-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1177\/0278364902021012001"},{"key":"bibr42-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1981.4308589"},{"key":"bibr43-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1987.1087847"},{"key":"bibr44-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6943079"},{"key":"bibr45-0278364917739114","author":"McDermott D","year":"1998","journal-title":"Technical Report, Yale Center for Computational Vision and Control, USA"},{"key":"bibr46-0278364917739114","author":"Nilsson NJ","year":"1984","journal-title":"Technical Report 323, Artificial Intelligence Center, SRI International, USA"},{"key":"bibr47-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/BioRob.2012.6290776"},{"key":"bibr48-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509563"},{"key":"bibr49-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045471"},{"key":"bibr50-0278364917739114","unstructured":"Smith R (2005) Open dynamics engine. Available at: http:\/\/ode.org"},{"key":"bibr51-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6906922"},{"key":"bibr52-0278364917739114","first-page":"1295","volume":"12","author":"Stilman M","year":"2006","journal-title":"International Journal of Robotics Research"},{"key":"bibr53-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363986"},{"key":"bibr54-0278364917739114","first-page":"1930","volume-title":"AAAI conference on artificial intelligence","author":"Toussaint M","year":"2015"},{"key":"bibr55-0278364917739114","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00312-7_37"},{"key":"bibr56-0278364917739114","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\/0278364917739114","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364917739114","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364917739114","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:37Z","timestamp":1777457737000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364917739114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,12]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1177\/0278364917739114"],"URL":"https:\/\/doi.org\/10.1177\/0278364917739114","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,12]]}}}