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’s effectiveness on complex and diverse task and motion planning tasks including rearrangement planning and navigation among movable objects.
AlamiRLaumondJPSiméonT (1994) Two manipulation planning algorithms. In: Workshop on algorithmic foundations of robotics (WAFR 1994). Stanford, CA, USA, 12 May 1994, pp. 109–125. Natick, MA, USA: AK Peters, Ltd.
2.
AlamiRSiméonTLaumondJP (1990) A geometrical approach to planning manipulation tasks. the case of discrete placements and grasps. In: International symposium of robotic research (ISRR 1990). Tokyo, Japan, 28–31 August 1989, pp. 453–463. Cambridge, MA, USA: MIT Press.
3.
BäckströmCNebelB (1995) Complexity results for SAS+ planning. Computational Intelligence11: 625–655.
4.
BarryJKaelblingLPLozano-PérezT (2013) A hierarchical approach to manipulation with diverse actions. In: IEEE international conference on robotics and automation (ICRA 2013), Karlsruhe, Germany, 6 May 2013, pp. 1799–1806. IEEE Press: Piscataway.
5.
BlumALFurstML (1997) Fast planning through planning graph analysis. Artificial Intelligence90: 281–300.
6.
BonetBGeffnerH (1999) Planning as heuristic search: New results. In: 5th european conference on planning (ECP), Durham, UK, 8–10 September 1999, pp. 360–372. Berlin, Heidelberg: Springer.
7.
BonetBGeffnerH (2001) Planning as heuristic search. Artificial Intelligence129: 5–33.
8.
BylanderT (1994) The computational complexity of propositional STRIPS planning. Artificial Intelligence69: 165–204.
9.
CambonSAlamiRGravotF (2009) A hybrid approach to intricate motion, manipulation and task planning. International Journal of Robotics Research28: 104–126.
10.
ColesAColesAFoxMLongD (2013) A hybrid LP-RPG heuristic for modelling numeric resource flows in planning. Journal of Artificial Intelligence Research46: 343–412.
11.
DantamNTKingstonZChaudhuriSKavrakiLE (2016) Incremental task and motion planning: A constraint-based approach. In: Robotics: science and systems (RSS 2016). Ann Arbor, Michigan, USA, 18–22 June 2016. Available at: http://www.roboticsproceedings.org/rss12/p02.html
12.
de SilvaLPandeyAKGharbiMAlamiR (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–16 July 2014. Available at: https://arxiv.org/abs/1307.1482
13.
DiankovR (2010) Automated construction of robotic manipulation programs. PhD Thesis, Robotics Institute, Carnegie Mellon University, USA.
14.
DiankovRKuffnerJ (2008) OpenRAVE: A planning architecture for autonomous robotics. Technical Report CMU-RI-TR-08-34, Carnegie Mellon University, USA, July.
15.
DogarMRSrinivasaSS (2012) A planning framework for non-prehensile manipulation under clutter and uncertainty. Autonomous Robots33: 217–236.
16.
DornhegeCEyerichPKellerTTrügSBrennerMNebelB (2009) Semantic attachments for domain-independent planning systems. In: International conference on automated planning and scheduling (ICAPS 2009), Thessaloniki, Greece, 19–23 September 2009, pp. 114–121. xxx: AAAI Press. Palo Alto, California, USA:
17.
DornhegeCHertleANebelB (2013) Lazy evaluation and subsumption caching for search-based integrated task and motion planning. In: IEEE/RSJ international conference on intelligent robots and systems (IROS 2013). Tokyo, Japan, 3–8 November 2013. IROS Workshop on AI-Based Robotics.
18.
ErdemEHaspalamutgilKPalazCPatogluVUrasT (2011) Combining high-level causal reasoning with low-level geometric reasoning and motion planning for robotic manipulation. In: IEEE international conference on robotics and automation (ICRA 2011). Shanghai, China, 9 May 2011, pp. 4575–4581. Piscataway, NJ, USA: IEEE
19.
FikesRENilssonNJ (1971) STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence2: 189–208.
20.
GarrettCRLozano-PérezTKaelblingLP (2014) FFRob: An efficient heuristic for task and motion planning. In: Workshop on the algorithmic foundations of robotics (WAFR 2014). Istanbul, Turkey, 3–5 August 2014, pp. 179–195. New York, NY, USA: Springer International Publishing.
21.
GarrettCRLozano-PérezTKaelblingLP (2015) Backward-forward search for manipulation planning. In: IEEE/RSJ international conference on intelligent robots and systems (IROS 2015). Hamburg, Germany, 28 September 2015, pp. 6366–6373. Piscataway, NJ, USA: IEEE.
22.
GhallabMNauDSTraversoP (2004) Automated Planning: Theory and Practice. Amsterdam, Netherlands: Elsevier.
23.
GregoryPLongDFoxMBeckJC (2012) Planning modulo theories: Extending the planning paradigm. In: International conference on automated planning and scheduling (ICAPS 2012). Atibaia, So Paulo, Brazil, 25–29 June 2012, pp. 65–73. Palo Alto, CA, USA: AAAI.
24.
HauserKLatombeJ (2009) Integrating task and PRM motion planning: Dealing with many infeasible motion planning queries. In: ICAPS Workshop on Bridging the Gap between Task and Motion Planning. Thessaloniki, Greece, 19–23 September 2009.
25.
HauserKLatombeJC (2010) Multi-modal motion planning in non-expansive spaces. International Journal of Robotics Research29: 897–915.
26.
HauserKNg-Thow-HingV (2011) Randomized multi-modal motion planning for a humanoid robot manipulation task. International Journal of Robotics Research30: 676–698.
27.
HelmertM (2006) The fast downward planning system. Journal of Artificial Intelligence Research26: 191–246.
28.
HoffmannJNebelB (2001) The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research14: 253–302.
29.
KaelblingLPLozano-PérezT (2011) Hierarchical planning in the now. In: IEEE international conference on robotics and automation (ICRA 2011). Shanghai, China, 9 May 2011, pp. 1470–1477. Piscataway, NJ, USA: IEEE.
30.
KaramanSFrazzoliE (2011) Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research30: 846–894.
31.
KavrakiLEKolountzakisMNLatombeJC (1998) Analysis of probabilistic roadmaps for path planning. IEEE Transactions on Robotics and Automation14: 166–171.
32.
KavrakiLELatombeJC (1998) Probabilistic roadmaps for robot path planning. In: GuptaKPobilAP (eds) Practical Motion Planning in Robotics: Current Approaches and Future Directions. New York: John Wiley & Sons, pp. 33–53.
33.
KavrakiLELatombeJCMotwaniRRaghavanP (1995) Randomized query processing in robot path planning. In: 27th annual ACM symposium on theory of computing, Las Vegas, NV, USA, 29 May 1995, pp. 353–362. New York City, NY, USA: ACM Press.
34.
KavrakiLESvestkaPLatombeJCOvermarsMH (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation12: 566–580.
35.
KingJCognettiMSrinivasaS (2016) Rearrangement planning using object-centric and robot-centric action spaces. In: IEEE international conference on robotics and automation (ICRA 2016). Stockholm, Sweden, 16 May 2016, pp. 3940–3947. Piscataway, NJ, USA: IEEE.
36.
KrontirisABekrisKE (2015) Dealing with difficult instances of object rearrangement. In: Robotics: science and systems (RSS 2015), Rome, Italy, 13–17 July 2015. Available at: http://www.roboticsproceedings.org/rss11/p45.html
37.
KrontirisABekrisKE (2016) Efficiently solving general rearrangement tasks: A fast extension primitive for an incremental sampling-based planner. In: IEEE international conference on robotics and automation (ICRA 2016), Stockholm, Sweden. 16 May 2016, pp. 3924–3931. Piscataway, NJ, USA: IEEE.
38.
KuffnerJJJrLaValleSM (2000) RRT-Connect: An efficient approach to single-query path planning. In: IEEE international conference on robotics and automation (ICRA 2000). San Francisco, CA USA, 24–28 April 2000, Vol. 2, pp. 995–1001. Piscataway, NJ, USA: IEEE.
39.
LagriffoulFDimitrovDBidotJSaffiottiAKarlssonL (2014) Efficiently combining task and motion planning using geometric constraints. International Journal of Robotics Research: 33: 1726–1747.
40.
LagriffoulFDimitrovDSaffiottiAKarlssonL (2012) Constraint propagation on interval bounds for dealing with geometric backtracking. In: IEEE/RSJ international conference on intelligent robots and systems (IROS 2012). Vilamoura, Algarve, Portugal, 7 October 2012, pp. 957–964. Piscataway, NJ, USA: IEEE.
41.
LevenPHutchinsonS (2002) A framework for real-time path planning in changing environments. International Journal of Robotics Research21: 999–1030.
42.
Lozano-PérezT (1981) Automatic planning of manipulator transfer movements. IEEE Transactions on Systems, Man, and Cybernetics11: 681–698.
43.
Lozano-PérezTJonesJLMazerEO’DonnellPAGrimsonWELTournassoudPet al. (1987) Handey: A robot system that recognizes, plans, and manipulates. In: IEEE international conference on robotics and automation (ICRA 1987). Raleigh, NC, USA, 31 March3 April 1987, Vol. 4, pp. 843–849. Piscataway, NJ, USA: IEEE.
44.
Lozano-PérezTKaelblingLP (2014) A constraint-based method for solving sequential manipulation planning problems. In: IEEE/RSJ international conference on intelligent robots and systems (IROS 2014), pp. 3684–3691. Piscataway: IEEE Press. Chicago, IL, USA, 14 September 2014, pp. 3684–3691. Piscataway, NJ, USA: IEEE.
45.
McDermottDGhallabMHoweAKnoblockCRamAVelosoMet al. (1998) PDDL: The planning domain definition language. Technical Report, Yale Center for Computational Vision and Control, USA, October.
46.
NilssonNJ (1984) Shakey the robot. Technical Report 323, Artificial Intelligence Center, SRI International, USA, April.
47.
PandeyAKSautJPSidobreDAlamiR (2012) Towards planning human-robot interactive manipulation tasks: Task dependent and human oriented autonomous selection of grasp and placement. In: RAS/EMBS international conference on biomedical robotics and biomechatronics. Rome, Italy, 24 June 2012, pp. 1371–1376. Piscataway, NJ, USA: IEEE.
48.
PlakuEHagerG (2010) Sampling-based motion planning with symbolic, geometric, and differential constraints. In: IEEE international conference on robotics and automation (ICRA 2010). Anchorage, AK USA, 3 May 2010, pp. 5002–5008. Piscataway, NJ, USA: IEEE.
49.
SiméonTLaumondJPCortésJSahbaniA (2004) Manipulation planning with probabilistic roadmaps. International Journal of Robotics Research23: 729–746.
50.
SmithR (2005) Open dynamics engine. Available at: http://ode.org
51.
SrivastavaSFangERianoLChitnisRRussellSAbbeelP (2014). Combined task and motion planning through an extensible planner-independent interface layer. In: IEEE international conference on robotics and automation (ICRA 2014)Hong Kong, China, 31 May 2014, pp. 639–646. Piscataway, NJ, USA: IEEE.
52.
StilmanMKuffnerJJ (2006) Planning among movable obstacles with artificial constraints. International Journal of Robotics Research 11–12: 1295–1307.
53.
StilmanMSchamburekJUKuffnerJJAsfourT (2007) Manipulation planning among movable obstacles. In: IEEE international conference on robotics and automation (ICRA 2007). Rome, Italy, 10 April 2007, pp. 3327–3332. Piscataway, NJ, USA: IEEE.
54.
ToussaintM (2015) Logic-geometric programming: An optimization-based approach to combined task and motion planning. In: AAAI conference on artificial intelligence, Austin, Texas, USA, 24 June 2015, pp. 1930–1936. Palo Alto, California, USA: AAAI Press.
55.
Van Den BergJStilmanMKuffnerJLinMManochaD (2009) Path planning among movable obstacles: A probabilistically complete approach. In: ChirikjianGSChosetHMoralesMMurpheyT (eds) Algorithmic Foundation of Robotics VIII. New York: Springer, pp. 599–614.
56.
WilfongGT (1988) Motion planning in the presence of movable obstacles. In: Symposium on computational geometry, pp. 279–288. Urbana-Champaign, IL, USA, 6 June 1988, pp. 279-288. New York City, NY, USA: ACM.
