2020

Integrated Task and Motion Planning

Garrett, Caelan Reed, Chitnis, Rohan, Holladay, Rachel et al.

Understand

The problem of planning for a robot that operates in environments containing a large number of objects, taking actions to move itself through the world as well as to change the state of the objects, is known as task and motion planning (TAMP).

TAMP problems contain elements of discrete task planning, discrete-continuous mathematical programming, and continuous motion planning, and thus cannot be effectively addressed by any of these fields directly.
In this paper, we define a class of TAMP problems and survey algorithms for solving them, characterizing the solution methods in terms of their strategies for solving the continuous-space subproblems and their techniques for integrating the discrete and continuous components of the search.

Built on

Fikes RE, Nilsson NJ. 1971. {STRIPS}: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence
1971
Earlier work this paper cites.
Lozano-Perez T, Wesley MA. 1979. An Algorithm for Planning Collision-Free Paths Among Polyhedral Obstacles. Communications of the ACM
1979
Earlier work this paper cites.
Nilsson NJ. 1984. Shakey the Robot. Tech. Rep. 323, Artificial Intelligence Center, SRI International
1984
Earlier work this paper cites.
Canny J. 1988. The complexity of robot motion planning. MIT press
1988
Earlier work this paper cites.
Alami R, Simeon T, Laumond JP. 1990. A geometrical approach to planning manipulation tasks: The case of discrete placements and grasps. In International Symposium on Robotics Research
1990
Earlier work this paper cites.
Wang LC, Chen CC. 1991. A combined optimization method for solving the inverse kinematics problems of mechanical manipulators. IEEE Transactions on Robotics and Automation
1991
Earlier work this paper cites.
McDermott D. 1991. Regression planning. International Journal of Intelligent Systems
1991
Earlier work this paper cites.
Dechter R. 1992. Constraint networks. Tech. rep., Information and Computer Science, University of California, Irvine
1992
Earlier work this paper cites.
Alami R, Laumond JP, Siméon T. 1994. Two manipulation planning algorithms. In Workshop on Algorithmic Foundations of Robotics
1994
Earlier work this paper cites.
Lin F, Reiter R. 1994. State constraints revisited. Journal of logic and computation
1994
Earlier work this paper cites.
Bacchus F, Yang Q. 1994. Downward refinement and the efficiency of hierarchical problem solving. Artificial Intelligence
1994
Earlier work this paper cites.
Alur R, Courcoubetis C, Halbwachs N, Henzinger TA, Ho PH, et al. 1995. The algorithmic analysis of hybrid systems. Theoretical computer science
1995
Earlier work this paper cites.
Bäckström C, Nebel B. 1995. Complexity results for SAS+ planning. Computational Intelligence
1995
Earlier work this paper cites.
Kavraki LE, Svestka P, Latombe JC, Overmars MH. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation
1996
Earlier work this paper cites.
Alur R, Henzinger TA, Lafferriere G, Pappas GJ. 2000. Discrete abstractions of hybrid systems. Proceedings of the IEEE
2000
Earlier work this paper cites.
Henzinger TA. 2000. The theory of hybrid automata. In Verification of Digital and Hybrid Systems
2000
Earlier work this paper cites.
Bohlin R, Kavraki LE. 2000. Path planning using lazy {PRM}. In IEEE International Conference on Robotics and Automation (ICRA)
2000
Earlier work this paper cites.
LaValle SM, Kuffner JJ. 2001. Randomized kinodynamic planning. International Journal of Robotics Research
2001
Earlier work this paper cites.
Bonet B, Geffner H. 2001. Planning as heuristic search. Artificial Intelligence
2001
Earlier work this paper cites.
Hoffmann J, Nebel B. 2001. The {FF} Planning System: Fast Plan Generation Through Heuristic Search. Journal Artificial Intelligence Research
2001
Earlier work this paper cites.
Branicky MS, Curtiss MM. 2002. Nonlinear and hybrid control via rrts. In Proc. Intl. Symp. on Mathematical Theory of Networks and Systems
2002
Earlier work this paper cites.
Fox M, Long D. 2003. PDDL2.1: An extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research
2003
Earlier work this paper cites.
Dechter R. 2003. Constraint processing. Morgan Kaufmann
2003
Earlier work this paper cites.
Siméon T, Laumond JP, Cortés J, Sahbani A. 2004. Manipulation planning with probabilistic roadmaps. International Journal of Robotics Research
2004
Earlier work this paper cites.
Edelkamp S. 2004. PDDL2.2: The language for the classical part of the 4th international planning competition. 4th International Planning Competition (IPC’04), at ICAPS’04
2004
Earlier work this paper cites.
Stilman M, Kuffner JJ. 2005. Navigation among movable obstacles: Real-time reasoning in complex environments. International Journal of Humanoid Robotics
2005
Earlier work this paper cites.
Thiébaux S, Hoffmann J, Nebel B. 2005. In defense of PDDL axioms. Artificial Intelligence
2005
Earlier work this paper cites.
Gravot F, Cambon S, Alami R. 2005. aSyMov: a planner that deals with intricate symbolic and geometric problems. In International Symposium on Robotics Research
2005
Earlier work this paper cites.
Branicky MS, Curtiss MM, Levine J, Morgan S. 2006. Sampling-based planning, control and verification of hybrid systems. IEE Proceedings-Control Theory and Applications
2006
Earlier work this paper cites.
Helmert M. 2006. The Fast Downward Planning System. Journal of Artificial Intelligence Research
2006
Earlier work this paper cites.
LaValle SM. 2006. Planning Algorithms. Cambridge University Press
2006
Earlier work this paper cites.
Fox M, Long D. 2006. Modelling Mixed Discrete-Continuous Domains for Planning. J. Artif. Intell. Res
2006
Earlier work this paper cites.
Stilman M, Kuffner JJ. 2006. Planning Among Movable Obstacles with Artificial Constraints. In Workshop on Algorithmic Foundations of Robotics (WAFR)
2006
Earlier work this paper cites.
Yoon SW, Fern A, Givan R. 2006. Learning Heuristic Functions from Relaxed Plans. In ICAPS
2006
Earlier work this paper cites.
Kocsis L, Szepesvári C. 2006. Bandit based {M}onte-{C}arlo planning. In European Conf. on Machine Learning
2006
Earlier work this paper cites.
Belta C, Bicchi A, Egerstedt M, Frazzoli E, Klavins E, Pappas GJ. 2007. Symbolic planning and control of robot motion [grand challenges of robotics]. IEEE Robotics & Automation Magazine
2007
Earlier work this paper cites.
Stilman M. 2007. Task constrained motion planning in robot joint space. In IEEE/RSJ International Conference on Intelligent Robots and Systems
2007
Earlier work this paper cites.
Stilman M, Schamburek JU, Kuffner JJ, Asfour T. 2007. Manipulation Planning Among Movable Obstacles. In IEEE International Conference on Robotics and Automation
2007
Earlier work this paper cites.
Liffiton MH, Sakallah KA. 2008. Algorithms for computing minimal unsatisfiable subsets of constraints. Journal of Automated Reasoning
2008
Earlier work this paper cites.
Yoon S, Fern A, Givan R. 2008. Learning control knowledge for forward search planning. The Journal of Machine Learning Research
2008
Earlier work this paper cites.
Ratliff N, Zucker M, Bagnell JA, Srinivasa S. 2009. CHOMP: Gradient optimization techniques for efficient motion planning. In IEEE International Conference on Robotics and Automation
2009
Earlier work this paper cites.
Berenson D, Srinivasa SS, Ferguson D, Kuffner JJ. 2009. Manipulation planning on constraint manifolds. In IEEE International Conference on Robotics and Automation
2009
Earlier work this paper cites.

Similar

Cambon S, Alami R, Gravot F. 2009. A hybrid approach to intricate motion, manipulation and task planning. International Journal of Robotics Research
2009
Cited alongside, same era.
Hauser K, Latombe JC. 2010. Multi-modal Motion Planning in Non-expansive Spaces. International Journal of Robotics Research
2010
Cited alongside, same era.
Hauser K. 2010. Randomized belief-space replanning in partially-observable continuous spaces. In Workshop on Algorithmic Foundations of Robotics
2010
Cited alongside, same era.
Stilman M. 2010. Global manipulation planning in robot joint space with task constraints. IEEE Transactions on Robotics
2010
Cited alongside, same era.
Berenson D, Srinivasa SS. 2010. Probabilistically complete planning with end-effector pose constraints. In International Conference on Robotics and Automation
2010
Cited alongside, same era.
Diankov R. 2010. Automated construction of robotic manipulation programs. Ph.D. thesis, Robotics Institute, Carnegie Mellon University
2010
Cited alongside, same era.
Plaku E, Hager G. 2010. Sampling-based Motion Planning with Symbolic, Geometric, and Differential Constraints. In IEEE International Conference on Robotics and Automation
2010
Cited alongside, same era.
Wolfe J, Marthi B, Russell S. 2010. Combined Task and Motion Planning for Mobile Manipulation. In International Conference on Automated Planning and Scheduling
2010
Cited alongside, same era.
Hauser K, Ng-Thow-Hing V, Gonzalez-Baños H. 2011. Randomized multi-modal motion planning for a humanoid robot manipulation task. International Journal of Robotics Research
2011
Cited alongside, same era.
Berenson D, Srinivasa S, Kuffner J. 2011. Task space regions: A framework for pose-constrained manipulation planning. International Journal of Robotics Research
2011
Cited alongside, same era.
Erdem E, Haspalamutgil K, Palaz C, Patoglu V, Uras T. 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
2011
Cited alongside, same era.
Kaelbling LP, Lozano-Perez T. 2011. Hierarchical task and motion planning in the now. In ICRA
2011
Cited alongside, same era.

Then

King J, Cognetti M, Srinivasa S. 2016. Rearrangement planning using object-centric and robot-centric action spaces. In IEEE International Conference on Robotics and Automation
2016
Later among the works it cites.
Plaku E, Karaman S. 2016. Motion planning with temporal-logic specifications: Progress and challenges. AI communications
2016
Later among the works it cites.
Dellin CM, Srinivasa SS. 2016. A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors. International Conference on Automated Planning and Scheduling (ICAPS)
2016
Later among the works it cites.
Lagriffoul F, Andres B. 2016. Combining task and motion planning: A culprit detection problem. The International Journal of Robotics Research
2016
Later among the works it cites.
Grey MX, Garrett CR, Liu CK, Ames AD, Thomaz AL. 2016. Humanoid Manipulation Planning using Backward-Forward Search. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)
2016
Later among the works it cites.
Dantam NT, Kingston Z, Chaudhuri S, Kavraki LE. 2016. Incremental Task and Motion Planning: A Constraint-Based Approach. In Robotics: Science and Systems
2016
Later among the works it cites.
Shoukry Y, Nuzzo P, Saha I, Sangiovanni-Vincentelli AL, Seshia SA, et al. 2016. Scalable lazy SMT-based motion planning. In IEEE Conference on Decision and Control
2016
Later among the works it cites.
Krontiris A, Bekris KE. 2016. Efficiently Solving General Rearrangement Tasks: A Fast Extension Primitive for an Incremental Sampling-based Planner. In International Conference on Robotics and Automation
2016
Later among the works it cites.
Akbari A, Rosell J. 2016. Task planning using physics-based heuristics on manipulation actions. In International Conference on Emerging Technologies and Factory Automation
2016
Later among the works it cites.
Vega-Brown W, Roy N. 2016. Asymptotically optimal planning under piecewise-analytic constraints. In Workshop on the Algorithmic Foundations of Robotics
2016
Later among the works it cites.
Kingston Z, Wells AM, Moll M, Kavraki LE. 2020. Informing Multi-Modal Planning with Synergistic Discrete Leads. In 2016 IEEE International Conference on Robotics and Automation
2016
Later among the works it cites.
Hadfield-Menell D, Lin C, Chitnis R, Russell S, Abbeel P. 2016. Sequential Quadratic Programming for Task Plan Optimization. In Intelligent Robots and Systems (IROS), 2016 IEEE/RSJ International Conference on
2016
Later among the works it cites.
Garrett CR, Kaelbling LP, Lozano-Perez T. 2016. Learning to Rank for Synthesizing Planning Heuristics. In Int. Joint Conf. on Artificial Intelligence (IJCAI)
2016
Later among the works it cites.
Silver D, Huang A, Maddison CJ, Guez A, Sifre L, et al. 2016. Mastering the game of go with deep neural networks and tree search. Nature
2016
Later among the works it cites.
Chitnis R, Hadfield-Menell D, Gupta A, Srivastava S, Groshev E, et al. 2016. Guided search for task and motion plans using learned heuristics. In 2016 IEEE International Conference on Robotics and Automation (ICRA)
2016
Later among the works it cites.
Toussaint M, Lopes M. 2017. Multi-bound tree search for logic-geometric programming in cooperative manipulation domains. In IEEE International Conference on Robotics and Automation
2017
Later among the works it cites.
Shoukry Y, Nuzzo P, Sangiovanni-Vincentelli AL, Seshia SA, Pappas GJ, Tabuada P. 2017. SMC: Satisfiability modulo convex optimization. In International Conference on Hybrid Systems: Computation and Control
2017
Later among the works it cites.
Ferrer-Mestres J, Francès G, Geffner H. 2017. Combined Task and Motion Planning as Classical AI Planning. arXiv preprint arXiv:1706.06927
Original
2017
Later among the works it cites.
Kingston Z, Moll M, Kavraki LE. 2018. Sampling-based methods for motion planning with constraints. Annual review of control, robotics, and autonomous systems
2018
Later among the works it cites.
Garrett CR, Lozano-Perez T, Kaelbling LP. 2018. Sampling-based methods for factored task and motion planning. The International Journal of Robotics Research
2018
Later among the works it cites.
Toussaint M, Allen K, Smith K, Tenenbaum JB. 2018. Differentiable physics and stable modes for tool-use and manipulation planning. Proc. of Robotics Science & Systems
2018
Later among the works it cites.
Dantam NT, Kingston ZK, Chaudhuri S, Kavraki LE. 2018. An incremental constraint-based framework for task and motion planning. The International Journal of Robotics Research
2018
Later among the works it cites.
Dantam NT, Chaudhuri S, Kavraki LE. 2018. The Task-Motion Kit: An Open Source, General-Purpose Task and Motion-Planning Framework. IEEE Robotics & Automation Magazine
2018
Later among the works it cites.
Shoukry Y, Nuzzo P, Sangiovanni-Vincentelli AL, Seshia SA, Pappas GJ, Tabuada P. 2018. SMC: Satisfiability Modulo Convex Programming. Proceedings of the IEEE
2018
Later among the works it cites.
Gaschler A, Petrick RPA, Khatib O, Knoll A. 2018. KABouM: Knowledge-level action and bounding geometry motion planner. Journal of Artificial Intelligence Research
2018
Later among the works it cites.
Fernández-González E, Williams B, Karpas E. 2018. Scottyactivity: Mixed discrete-continuous planning with convex optimization. Journal of Artificial Intelligence Research
2018
Later among the works it cites.
Lo SY, Zhang S, Stone P. 2018. PETLON: planning efficiently for task-level-optimal navigation. In International Conference on Autonomous Agents and MultiAgent Systems
2018
Later among the works it cites.
Kim B, Kaelbling LP, Lozano-Perez T. 2018. Guiding search in continuous state-action spaces by learning an action sampler from off-target search experience. In AAAI Conference on Artificial Intelligence
2018
Later among the works it cites.
Kingston Z, Moll M, Kavraki LE. 2019. Exploring implicit spaces for constrained sampling-based planning. International Journal of Robotics Research
2019
Later among the works it cites.
Karpas E, Magazzeni D. 2019. Automated Planning for Robotics. Annual Review of Control, Robotics, and Autonomous Systems
2019
Later among the works it cites.
Mandalika A, Choudhury S, Salzman O, Srinivasa S. 2019. Generalized lazy search for robot motion planning: Interleaving search and edge evaluation via event-based toggles. In Proceedings of the International Conference on Automated Planning and Scheduling
2019
Later among the works it cites.
Colledanchise M, Almeida D, Ögren P. 2019. Towards blended reactive planning and acting using behavior trees. In International Conference on Robotics and Automation
2019
Later among the works it cites.
Thomason W, Knepper RA. 2019. A unified sampling-based approach to integrated task and motion planning. In International Symposium on Robotics Research
2019
Later among the works it cites.
Kim B, Shimanuki L. 2019. Learning value functions with relational state representations for guiding task-and-motion planning. In Conference on Robot Learning
2019
Later among the works it cites.
Phiquepal C, Toussaint M. 2019. Combined task and motion planning under partial observability: An optimization-based approach. In 2019 International Conference on Robotics and Automation (ICRA)
2019
Later among the works it cites.
Wang Z, Garrett CR, Kaelbling LP, Lozano-Perez T. 2020. Learning compositional models of robot skills for task and motion planning
2020
Closest in time.
Garrett CR, Lozano-Perez T, Kaelbling LP. 2020. PDDLStream: Integrating Symbolic Planners and Blackbox Samplers. In International Conference on Automated Planning and Scheduling
2020
Closest in time.
Kim B, Lee K, Lim S, Kaelbling LP, Lozano-Perez T. 2020. Monte Carlo Tree Search in continuous spaces using Voronoi optimistic optimization with regret bounds. AAAI Conference on Artificial Intelligence
2020
Closest in time.
Garrett CR, Paxton C, Lozano-Perez T, Kaelbling LP, Fox D. 2020. Online Replanning in Belief Space for Partially Observable Task and Motion Problems. In International Conference on Robotics and Automation
2020
Closest in time.
Shen W, Trevizan F, Thiébaux S. 2020. Learning domain-independent planning heuristics with hypergraph networks. In Proceedings of the International Conference on Automated Planning and Scheduling
2020
Closest in time.
Driess D, Oguz O, Ha JS, Toussaint M. 2020. Deep Visual Heuristics: Learning Feasibility of Mixed-Integer Programs for Manipulation Planning
2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…