1932

Abstract

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 article, 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.

Loading

Article metrics loading...

/content/journals/10.1146/annurev-control-091420-084139
2021-05-03
2024-06-15
Loading full text...

Full text loading...

/deliver/fulltext/control/4/1/annurev-control-091420-084139.html?itemId=/content/journals/10.1146/annurev-control-091420-084139&mimeType=html&fmt=ahah

Literature Cited

  1. 1. 
    Wang Z, Garrett CR, Kaelbling LP, Lozano-Pérez T. 2020. Learning compositional models of robot skills for task and motion planning. arXiv:2006.06444 [cs.RO]
  2. 2. 
    Fikes RE, Nilsson NJ. 1971. STRIPS: a new approach to the application of theorem proving to problem solving. Artif. Intell. 2:189–208
    [Google Scholar]
  3. 3. 
    Nilsson NJ. 1984. Shakey the robot Tech. Rep. 323 Artif. Intell. Cent., SRI Int. Menlo Park, CA:
    [Google Scholar]
  4. 4. 
    Lozano-Pérez T, Wesley MA. 1979. An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM 22:560–70
    [Google Scholar]
  5. 5. 
    Kavraki LE, Svestka P, Latombe JC, Overmars MH. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12:566–80
    [Google Scholar]
  6. 6. 
    LaValle SM, Kuffner JJ. 2001. Randomized kinodynamic planning. Int. J. Robot. Res. 20:378–400
    [Google Scholar]
  7. 7. 
    Ratliff N, Zucker M, Bagnell JA, Srinivasa S. 2009. CHOMP: gradient optimization techniques for efficient motion planning. 2009 IEEE International Conference on Robotics and Automation489–94 Piscataway, NJ: IEEE
    [Google Scholar]
  8. 8. 
    Schulman J, Duan Y, Ho J, Lee A, Awwal I et al. 2014. Motion planning with sequential convex optimization and convex collision checking. Int. J. Robot. Res. 33:1251–70
    [Google Scholar]
  9. 9. 
    Alami R, Simeon T, Laumond JP. 1990. A geometrical approach to planning manipulation tasks: the case of discrete placements and grasps. Robotics Research: The Fifth International Symposium453–63 Cambridge, MA: MIT Press
    [Google Scholar]
  10. 10. 
    Alami R, Laumond JP, Siméon T. 1994. Two manipulation planning algorithms. Proceedings of the Workshop on Algorithmic Foundations of Robotics109–25 Natick, MA: A.K. Peters
    [Google Scholar]
  11. 11. 
    Branicky MS, Curtiss MM 2002. Nonlinear and hybrid control via RRTs. Electronic Proceedings of the 15th International Symposium on Mathematical Theory of Networks and Systems DS Gilliam, J Rosenthal Notre Dame, IN: Univ. Notre Dame. https://www3.nd.edu/∼mtns/papers/13040_1.pdf
    [Google Scholar]
  12. 12. 
    Branicky MS, Curtiss MM, Levine J, Morgan S. 2006. Sampling-based planning, control and verification of hybrid systems. IEE Proc. Control Theory Appl. 153:575–590
    [Google Scholar]
  13. 13. 
    Hauser K, Latombe JC. 2010. Multi-modal motion planning in non-expansive spaces. Int. J. Robot. Res. 29:897–915
    [Google Scholar]
  14. 14. 
    Hauser K, Ng-Thow-Hing V, Gonzalez-Baños H. 2011. Randomized multi-modal motion planning for a humanoid robot manipulation task. Int. J. Robot. Res. 30:678–98
    [Google Scholar]
  15. 15. 
    Ghallab M, Nau DS, Traverso P. 2016. Automated Planning and Acting Cambridge, UK: Cambridge Univ. Press
    [Google Scholar]
  16. 16. 
    Bonet B, Geffner H. 2001. Planning as heuristic search. Artif. Intell. 129:5–33
    [Google Scholar]
  17. 17. 
    Hoffmann J, Nebel B. 2001. The FF planning system: fast plan generation through heuristic search. J. Artif. Intell. Res. 14:253–302
    [Google Scholar]
  18. 18. 
    Helmert M. 2006. The fast downward planning system. J. Artif. Intell. Res. 26:191–246
    [Google Scholar]
  19. 19. 
    Deshpande A, Kaelbling LP, Lozano-Pérez T 2016. Decidability of semi-holonomic prehensile task and motion planning. Algorithmic Foundations of Robotics XII: Proceedings of the Twelfth Workshop on the Algorithmic Foundations of Robotics K Goldberg, P Abbeel, K Bekris, L Miller 544–59 Cham, Switz: Springer
    [Google Scholar]
  20. 20. 
    Vendittelli M, Laumond JP, Mishra B 2015. Decidability of robot manipulation planning: three disks in the plane. Algorithmic Foundations of Robotics XI: Selected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics H Akin, N Amato, V Isler, A van der Stappen 641–57 Cham, Switz: Springer
    [Google Scholar]
  21. 21. 
    Garrett CR, Lozano-Pérez T, Kaelbling LP. 2017. FFRob: leveraging symbolic planning for efficient task and motion planning. Int. J. Robot. Res. 37:104–36
    [Google Scholar]
  22. 22. 
    Siméon T, Laumond JP, Cortés J, Sahbani A. 2004. Manipulation planning with probabilistic roadmaps. Int. J. Robot. Res. 23:729–46
    [Google Scholar]
  23. 23. 
    Stilman M, Kuffner JJ. 2005. Navigation among movable obstacles: real-time reasoning in complex environments. Int. J. Humanoid Robot. 2:479–503
    [Google Scholar]
  24. 24. 
    King J, Cognetti M, Srinivasa S. 2016. Rearrangement planning using object-centric and robot-centric action spaces. 2016 IEEE International Conference on Robotics and Automation3940–47 Piscataway, NJ: IEEE
    [Google Scholar]
  25. 25. 
    Belta C, Bicchi A, Egerstedt M, Frazzoli E, Klavins E, Pappas GJ. 2007. Symbolic planning and control of robot motion. IEEE Robot. Autom. Mag. 14:161–70
    [Google Scholar]
  26. 26. 
    Plaku E, Karaman S. 2016. Motion planning with temporal-logic specifications: progress and challenges. AI Commun 29:151–62
    [Google Scholar]
  27. 27. 
    Canny J. 1988. The Complexity of Robot Motion Planning Cambridge, MA: MIT Press
    [Google Scholar]
  28. 28. 
    LaValle SM. 2006. Planning Algorithms Cambridge, UK: Cambridge Univ. Press
    [Google Scholar]
  29. 29. 
    Hauser K 2010. Randomized belief-space replanning in partially-observable continuous spaces. Algorithmic Foundations of Robotics IX: Selected Contributions of the Ninth International Workshop on the Algorithmic Foundations of Robotics D Hsu, V Isler, JC Latombe, MC Lin 193–209 Berlin: Springer
    [Google Scholar]
  30. 30. 
    Barry J, Kaelbling LP, Lozano-Pérez T. 2013. A hierarchical approach to manipulation with diverse actions. 2013 IEEE International Conference on Robotics and Automation1799–806 Piscataway, NJ: IEEE
    [Google Scholar]
  31. 31. 
    Stilman M. 2007. Task constrained motion planning in robot joint space. 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems3074–81 Piscataway, NJ: IEEE
    [Google Scholar]
  32. 32. 
    Stilman M. 2010. Global manipulation planning in robot joint space with task constraints. IEEE Trans. Robot. 26:576–84
    [Google Scholar]
  33. 33. 
    Berenson D, Srinivasa SS, Ferguson D, Kuffner JJ. 2009. Manipulation planning on constraint manifolds. 2009 IEEE International Conference on Robotics and Automation625–32 Piscataway, NJ: IEEE
    [Google Scholar]
  34. 34. 
    Berenson D, Srinivasa SS. 2010. Probabilistically complete planning with end-effector pose constraints. 2010 IEEE International Conference on Robotics and Automation2724–30 Piscataway, NJ: IEEE
    [Google Scholar]
  35. 35. 
    Berenson D, Srinivasa S, Kuffner J. 2011. Task space regions: a framework for pose-constrained manipulation planning. Int. J. Robot. Res. 30:1435–60
    [Google Scholar]
  36. 36. 
    Kingston Z, Moll M, Kavraki LE. 2018. Sampling-based methods for motion planning with constraints. Annu. Rev. Control Robot. Auton. Syst. 1:159–85
    [Google Scholar]
  37. 37. 
    Kingston Z, Moll M, Kavraki LE. 2019. Exploring implicit spaces for constrained sampling-based planning. Int. J. Robot. Res. 38:1151–78
    [Google Scholar]
  38. 38. 
    Alur R, Courcoubetis C, Halbwachs N, Henzinger TA, Ho PH et al. 1995. The algorithmic analysis of hybrid systems. Theor. Comput. Sci. 138:3–34
    [Google Scholar]
  39. 39. 
    Alur R, Henzinger TA, Lafferriere G, Pappas GJ. 2000. Discrete abstractions of hybrid systems. Proc. IEEE 88:971–84
    [Google Scholar]
  40. 40. 
    Henzinger TA 2000. The theory of hybrid automata. Verification of Digital and Hybrid Systems MK Inan, RP Kurshan 265–92 Berlin: Springer
    [Google Scholar]
  41. 41. 
    Wang LC, Chen CC. 1991. A combined optimization method for solving the inverse kinematics problems of mechanical manipulators. IEEE Trans. Robot. Autom. 7:489–99
    [Google Scholar]
  42. 42. 
    Diankov R. 2010. Automated construction of robotic manipulation programs. PhD Thesis, Robot. Inst. Carnegie Mellon Univ. Pittsburgh, PA:
    [Google Scholar]
  43. 43. 
    Karpas E, Magazzeni D. 2019. Automated planning for robotics. Annu. Rev. Control Robot. Auton. Syst. 3:417–39
    [Google Scholar]
  44. 44. 
    Bäckström C, Nebel B. 1995. Complexity results for SAS+ planning. Comput. Intell. 11:622–55
    [Google Scholar]
  45. 45. 
    McDermott D. 1991. Regression planning. Int. J. Intell. Syst. 6:357–416
    [Google Scholar]
  46. 46. 
    Fox M, Long D. 2003. PDDL2.1: an extension to PDDL for expressing temporal planning domains. J. Artif. Intell. Res. 20:61–124
    [Google Scholar]
  47. 47. 
    Edelkamp S. 2004. PDDL2.2: the language for the classical part of the 4th international planning competition. Tech. Rep. 195, Inst. Inform Albert-Ludwigs-Univ. Freiburg Freiburg, Ger:.
  48. 48. 
    Fox M, Long D. 2006. Modelling mixed discrete-continuous domains for planning. J. Artif. Intell. Res.235–97
    [Google Scholar]
  49. 49. 
    Bryce D, Gao S, Musliner DJ, Goldman RP. 2015. SMT-based nonlinear PDDL+ planning. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence3247–53 Palo Alto, CA: AAAI Press
    [Google Scholar]
  50. 50. 
    Coles AJ, Coles AI, Fox M, Long D. 2012. COLIN: planning with continuous linear numeric change. J. Artif. Intell. Res. 44:1–96
    [Google Scholar]
  51. 51. 
    Lin F, Reiter R. 1994. State constraints revisited. J. Logic Comput. 4:655–77
    [Google Scholar]
  52. 52. 
    Thiébaux S, Hoffmann J, Nebel B. 2005. In defense of PDDL axioms. Artif. Intell. 168:38–69
    [Google Scholar]
  53. 53. 
    Dechter R. 1992. Constraint networks. Tech. Rep. Dep. Inf. Comput. Sci., Univ. Calif., Irvine
    [Google Scholar]
  54. 54. 
    Dechter R. 2003. Constraint Processing San Francisco, CA: Morgan Kaufmann
    [Google Scholar]
  55. 55. 
    Garrett CR, Lozano-Pérez T, Kaelbling LP. 2018. Sampling-based methods for factored task and motion planning. Int. J. Robot. Res. 37:1796–825
    [Google Scholar]
  56. 56. 
    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. Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling745–53 Palo Alto, CA: AAAI Press
    [Google Scholar]
  57. 57. 
    Bohlin R, Kavraki LE. 2000. Path planning using lazy PRM. 2000 IEEE International Conference on Robotics and Automation, Vol. 1521–28 Piscataway, NJ: IEEE
    [Google Scholar]
  58. 58. 
    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. Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling459–67 Palo Alto, CA: AAAI Press
    [Google Scholar]
  59. 59. 
    Bacchus F, Yang Q. 1994. Downward refinement and the efficiency of hierarchical problem solving. Artif. Intell. 71:43–100
    [Google Scholar]
  60. 60. 
    Srivastava S, Fang E, Riano L, Chitnis R, Russell S, Abbeel P. 2014. Combined task and motion planning through an extensible planner-independent interface layer. 2014 IEEE International Conference on Robotics and Automation639–46 Piscataway, NJ: IEEE
    [Google Scholar]
  61. 61. 
    Toussaint M. 2015. Logic-geometric programming: an optimization-based approach to combined task and motion planning. Proceedings of the 24th International Conference on Artificial Intelligence1930–36 Palo Alto, CA: AAAI Press
    [Google Scholar]
  62. 62. 
    Dornhege C, Eyerich P, Keller T, Trüg S, Brenner M, Nebel B. 2009. Semantic attachments for domain-independent planning systems. Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling114–21 Palo Alto, CA: AAAI Press
    [Google Scholar]
  63. 63. 
    Dornhege C, Gissler M, Teschner M, Nebel B. 2009. Integrating symbolic and geometric planning for mobile manipulation. 2009 IEEE International Workshop on Safety Piscataway, NJ: IEEE https://doi.org/10.1109/SSRR.2009.5424160
    [Crossref] [Google Scholar]
  64. 64. 
    Dornhege C. 2015. Task planning for high-level robot control PhD Thesis Univ. Freiburg Freiburg, Ger:.
    [Google Scholar]
  65. 65. 
    Lagriffoul F, Dimitrov D, Saffiotti A, Karlsson L. 2012. Constraint propagation on interval bounds for dealing with geometric backtracking. 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems957–64 Piscataway, NJ: IEEE
    [Google Scholar]
  66. 66. 
    Lagriffoul F, Dimitrov D, Bidot J, Saffiotti A, Karlsson L. 2014. Efficiently combining task and motion planning using geometric constraints. Int. J. Robot. Res. 33:1726–47
    [Google Scholar]
  67. 67. 
    Lagriffoul F, Andres B. 2016. Combining task and motion planning: a culprit detection problem. Int. J. Robot. Res. 35:890–927
    [Google Scholar]
  68. 68. 
    Toussaint M, Lopes M. 2017. Multi-bound tree search for logic-geometric programming in cooperative manipulation domains. 2017 IEEE International Conference on Robotics and Automation4044–51 Piscataway, NJ: IEEE
    [Google Scholar]
  69. 69. 
    Toussaint M, Allen K, Smith K, Tenenbaum JB 2018. Differentiable physics and stable modes for tool-use and manipulation planning. Robotics: Science and Systems XIV H Kress-Gazit, S Srinivasa, T Howard, N Atanasov, pap. 44: N.p.: Robot. Sci. Syst. Found .
    [Google Scholar]
  70. 70. 
    Garrett CR, Lozano-Pérez T, Kaelbling LP. 2015. Backward-forward search for manipulation planning. 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems6366–73 Piscataway, NJ: IEEE
    [Google Scholar]
  71. 71. 
    Grey MX, Garrett CR, Liu CK, Ames AD, Thomaz AL. 2016. Humanoid manipulation planning using backward-forward search. 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems5467–73 Piscataway, NJ: IEEE
    [Google Scholar]
  72. 72. 
    Garrett CR, Lozano-Pérez T, Kaelbling LP 2017. Sample-based methods for factored task and motion planning. Robotics: Science and Systems XIII N Amato, S Srinivasa, N Ayanian, S Kuindersma, pap. 39. N.p.: Robot. Sci. Syst. Found .
    [Google Scholar]
  73. 73. 
    Garrett CR, Lozano-Pérez T, Kaelbling LP. 2020. PDDLStream: integrating symbolic planners and blackbox samplers. Proceedings of the 30th International Conference on Automated Planning and Scheduling440–48 Palo Alto, CA: AAAI Press
    [Google Scholar]
  74. 74. 
    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. 2011 IEEE International Conference on Robotics and Automation4575–81 Piscataway, NJ: IEEE
    [Google Scholar]
  75. 75. 
    Erdem E, Patoglu V, Saribatur ZG. 2015. Integrating hybrid diagnostic reasoning in plan execution monitoring for cognitive factories with multiple robots. 2015 IEEE International Conference on Robotics and Automation2007–13 Piscataway, NJ: IEEE
    [Google Scholar]
  76. 76. 
    Srivastava S, Riano L, Russell S, Abbeel P. 2013. Using classical planners for tasks with continuous operators in robotics. Paper presented at the Workshop on Planning and Robotics, 23rd International Conference on Automated Planning and Scheduling Rome, June 10–14
    [Google Scholar]
  77. 77. 
    Dantam NT, Kingston Z, Chaudhuri S, Kavraki LE 2016. Incremental task and motion planning: a constraint-based approach. Robotics: Science and Systems XII D Hsu, N Amato, S Berman, S Jacobs, pap. 2. N.p.: Robot. Sci. Syst. Found .
    [Google Scholar]
  78. 78. 
    Dantam NT, Kingston ZK, Chaudhuri S, Kavraki LE. 2018. An incremental constraint-based framework for task and motion planning. Int. J. Robot. Res. 37:1134–51
    [Google Scholar]
  79. 79. 
    Dantam NT, Chaudhuri S, Kavraki LE. 2018. The Task-Motion Kit: an open source, general-purpose task and motion-planning framework. IEEE Robot. Autom. Mag. 25:361–70
    [Google Scholar]
  80. 80. 
    Liffiton MH, Sakallah KA. 2008. Algorithms for computing minimal unsatisfiable subsets of constraints. J. Autom. Reason. 40:1–33
    [Google Scholar]
  81. 81. 
    Shoukry Y, Nuzzo P, Saha I, Sangiovanni-Vincentelli AL, Seshia SA et al. 2016. Scalable lazy SMT-based motion planning. 2016 IEEE 55th Conference on Decision and Control6683–88 Piscataway, NJ: IEEE
    [Google Scholar]
  82. 82. 
    Shoukry Y, Nuzzo P, Sangiovanni-Vincentelli AL, Seshia SA, Pappas GJ, Tabuada P. 2017. SMC: Satisfiability Modulo Convex optimization. Proceedings of the 20th International Conference on Hybrid Systems: Computation and Control19–28 New York: ACM
    [Google Scholar]
  83. 83. 
    Shoukry Y, Nuzzo P, Sangiovanni-Vincentelli AL, Seshia SA, Pappas GJ, Tabuada P. 2018. SMC: Satisfiability Modulo Convex programming. Proc. IEEE 106:1655–79
    [Google Scholar]
  84. 84. 
    Ferrer-Mestres J, Francès G, Geffner H. 2017. Combined task and motion planning as classical AI planning. arXiv:1706.06927 [cs.RO]
  85. 85. 
    Ferrer-Mestres J, Es G, Geffner H. 2015. Planning with state constraints and its application to combined task and motion planning. Paper presented at the Workshop on Planning and Robotics, 25th International Conference on Automated Planning and Scheduling, Jerusalem June 7–11
    [Google Scholar]
  86. 86. 
    Garrett CR, Lozano-Pérez T, Kaelbling LP 2014. FFRob: an efficient heuristic for task and motion planning. Algorithmic Foundations of Robotics XI: Selected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics H Akin, N Amato, V Isler, A van der Stappen 179–95 Cham, Switz: Springer
    [Google Scholar]
  87. 87. 
    Krontiris A, Bekris KE 2015. Dealing with difficult instances of object rearrangement. Robotics: Science and Systems XI LE Kavraki, D Hsu, J Buchli, pap. 45. N.p.: Robot. Sci. Syst. Found .
    [Google Scholar]
  88. 88. 
    Krontiris A, Bekris KE. 2016. Efficiently solving general rearrangement tasks: a fast extension primitive for an incremental sampling-based planner. 2016 IEEE International Conference on Robotics and Automation3924–31 Piscataway, NJ: IEEE
    [Google Scholar]
  89. 89. 
    Akbari A, Rosell J. 2016. Task planning using physics-based heuristics on manipulation actions. 2016 IEEE 21st International Conference on Emerging Technologies and Factory Automation Piscataway, NJ: IEEE https://doi.org/10.1109/ETFA.2016.7733599
    [Crossref] [Google Scholar]
  90. 90. 
    Vega-Brown W, Roy N 2016. Asymptotically optimal planning under piecewise-analytic constraints. Algorithmic Foundations of Robotics XII: Proceedings of the Twelfth Workshop on the Algorithmic Foundations of Robotics K Goldberg, P Abbeel, K Bekris, L Miller 528–43 Cham, Switz: Springer
    [Google Scholar]
  91. 91. 
    Dornhege C, Hertle A, Nebel B. 2013. Lazy evaluation and subsumption caching for search-based integrated task and motion planning. Paper presented at the Workshop on AI-Based RoboticsIEEE/RSJ International Conference on Intelligent Robots and Systems Tokyo, Nov:3–7
    [Google Scholar]
  92. 92. 
    Gaschler A, Petrick RPA, Giuliani M, Rickert M, Knoll A. 2013. KVP: a knowledge of volumes approach to robot task planning. 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems202–8 Piscataway, NJ: IEEE
    [Google Scholar]
  93. 93. 
    Gaschler A, Kessler I, Petrick RPA, Knoll A. 2015. Extending the knowledge of volumes approach to robot task planning with efficient geometric predicates. 2015 IEEE International Conference on Robotics and Automation3061–66 Piscataway, NJ: IEEE
    [Google Scholar]
  94. 94. 
    Gaschler A, Petrick RPA, Khatib O, Knoll A. 2018. KABouM: knowledge-level action and bounding geometry motion planner. J. Artif. Intell. Res. 61:323–62
    [Google Scholar]
  95. 95. 
    Colledanchise M, Almeida D, Ögren P. 2019. Towards blended reactive planning and acting using behavior trees. 2019 International Conference on Robotics and Automation8839–45 Piscataway, NJ: IEEE
    [Google Scholar]
  96. 96. 
    Gravot F, Cambon S, Alami R 2005. aSyMov: a planner that deals with intricate symbolic and geometric problems. Robotics Research: The Eleventh International Symposium P Dario, R Chatila 100–10 Berlin: Springer
    [Google Scholar]
  97. 97. 
    Cambon S, Alami R, Gravot F. 2009. A hybrid approach to intricate motion, manipulation and task planning. Int. J. Robot. Res. 28:104–26
    [Google Scholar]
  98. 98. 
    Stilman M, Kuffner JJ 2006. Planning among movable obstacles with artificial constraints. Algorithmic Foundation of Robotics VIII: Selected Contributions of the Eighth International Workshop on the Algorithmic Foundations of Robotics GS Chirikjian, H Choset, M Morales, T Murphey 599–614 Berlin: Springer
    [Google Scholar]
  99. 99. 
    Stilman M, Schamburek JU, Kuffner JJ, Asfour T. 2007. Manipulation planning among movable obstacles. 2007 IEEE International Conference on Robotics and Automation3327–32 Piscataway, NJ: IEEE
    [Google Scholar]
  100. 100. 
    Plaku E, Hager G. 2010. Sampling-based motion planning with symbolic, geometric, and differential constraints. 2010 IEEE International Conference on Robotics and Automation5002–8 Piscataway, NJ: IEEE
    [Google Scholar]
  101. 101. 
    Kaelbling LP, Lozano-Pérez T. 2011. Hierarchical task and motion planning in the now. 2011 IEEE International Conference on Robotics and Automation1470–77 Piscataway, NJ: IEEE
    [Google Scholar]
  102. 102. 
    Kaelbling LP, Lozano-Pérez T. 2013. Integrated task and motion planning in belief space. Int. J. Robot. Res. 32:1194–227
    [Google Scholar]
  103. 103. 
    Barry J, Hsiao K, Kaelbling LP, Lozano-Pérez T 2012. Manipulation with multiple action types. Experimental Robotics: The 13th International Symposium on Experimental Robotics J Desai, G Dudek, O Khatib, V Kumar 531–45 Heidelberg, Ger: Springer
    [Google Scholar]
  104. 104. 
    Barry JL. 2013. Manipulation with diverse actions PhD Thesis Mass. Inst. Technol. Cambridge, MA:
    [Google Scholar]
  105. 105. 
    Thomason W, Knepper RA. 2019. A unified sampling-based approach to integrated task and motion planning. International Symposium on Robotics Research (ISRR), Vol. 5:48–76 New York: Wiley-Interscience
    [Google Scholar]
  106. 106. 
    Kim B, Shimanuki L 2019. Learning value functions with relational state representations for guiding task-and-motion planning. Proceedings of the Conference on Robot Learning LP Kaelbling, D Kragic, K Sugiura 955–68 Proc. Mach. Learn. Res. 100. N.p.: PMLR
    [Google Scholar]
  107. 107. 
    Kim B, Lee K, Lim S, Kaelbling LP, Lozano-Pérez T. 2020. Monte Carlo tree search in continuous spaces using Voronoi optimistic optimization with regret bounds. The Thirty-Fourth AAAI Conference on Artificial Intelligence9916–24 Palo Alto, CA: AAAI Press
    [Google Scholar]
  108. 108. 
    Kingston Z, Wells AM, Moll M, Kavraki LE. 2020. Informing multi-modal planning with synergistic discrete leads. 2020 IEEE International Conference on Robotics and Automation3199–205 Piscataway, NJ: IEEE
    [Google Scholar]
  109. 109. 
    Fernández-González E, Williams B, Karpas E. 2018. ScottyActivity: mixed discrete-continuous planning with convex optimization. J. Artif. Intell. Res. 62:579–664
    [Google Scholar]
  110. 110. 
    Pandey AK, Saut JP, Sidobre D, Alami R. 2012. Towards planning human-robot interactive manipulation tasks. 2012 4th IEEE RAS and EMBS International Conference on Biomedical Robotics and Biomechatronics1371–76 Piscataway, NJ: IEEE
    [Google Scholar]
  111. 111. 
    de Silva L, Pandey AK, Gharbi M, Alami R. 2013. Towards combining HTN planning and geometric task planning. Paper presented at the Workshop on Combined Robot Motion Planning and AI Planning for Practical Applications, Robotics: Science and Systems IX, Berlin June 24–28
    [Google Scholar]
  112. 112. 
    Lozano-Pérez T, Kaelbling LP. 2014. A constraint-based method for solving sequential manipulation planning problems. 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems3684–91 Piscataway, NJ: IEEE
    [Google Scholar]
  113. 113. 
    Lo SY, Zhang S, Stone P. 2018. PETLON: Planning Efficiently for Task-Level-Optimal Navigation. Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems220–28 Richland, SC: Int. Found. Auton. Agents Multiagent Syst.
    [Google Scholar]
  114. 114. 
    Wolfe J, Marthi B, Russell S 2010. Combined task and motion planning for mobile manipulation. Proceedings of the Twentieth International Conference on Automated Planning and Scheduling254–57 Palo Alto, CA: AAAI Press
    [Google Scholar]
  115. 115. 
    Hadfield-Menell D, Lin C, Chitnis R, Russell S, Abbeel P. 2016. Sequential quadratic programming for task plan optimization. 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems5040–47 Piscataway, NJ: IEEE
    [Google Scholar]
  116. 116. 
    Hadfield-Menell D, Groshev E, Chitnis R, Abbeel P. 2015. Modular task and motion planning in belief space. 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems4991–98 Piscataway, NJ: IEEE
    [Google Scholar]
  117. 117. 
    Phiquepal C, Toussaint M. 2019. Combined task and motion planning under partial observability: an optimization-based approach. 2019 International Conference on Robotics and Automation9000–6 Piscataway, NJ: IEEE
    [Google Scholar]
  118. 118. 
    Garrett CR, Paxton C, Lozano-Pérez T, Kaelbling LP, Fox D. 2020. Online replanning in belief space for partially observable task and motion problems. 2020 IEEE International Conference on Robotics and Automation5678–84 Piscataway, NJ: IEEE
    [Google Scholar]
  119. 119. 
    Yoon SW, Fern A, Givan R 2006. Learning heuristic functions from relaxed plans. Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling162–70 Palo Alto, CA: AAAI Press
    [Google Scholar]
  120. 120. 
    Shen W, Trevizan F, Thiébaux S 2020. Learning domain-independent planning heuristics with hypergraph networks. Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling574–84 Palo Alto, CA: AAAI Press
    [Google Scholar]
  121. 121. 
    Yoon S, Fern A, Givan R. 2008. Learning control knowledge for forward search planning. J. Mach. Learn. Res. 9:683–718
    [Google Scholar]
  122. 122. 
    Garrett CR, Kaelbling LP, Lozano-Pérez T. 2016. Learning to rank for synthesizing planning heuristics. Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence3089–95 Palo Alto, CA: AAAI Press
    [Google Scholar]
  123. 123. 
    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 529:484–89
    [Google Scholar]
  124. 124. 
    Driess D, Oguz O, Ha JS, Toussaint M. 2020. Deep visual heuristics: learning feasibility of mixed-integer programs for manipulation planning. 2020 IEEE International Conference on Robotics and Automation9563–69 Piscataway, NJ: IEEE
    [Google Scholar]
  125. 125. 
    Chitnis R, Hadfield-Menell D, Gupta A, Srivastava S, Groshev E et al. 2016. Guided search for task and motion plans using learned heuristics. 2016 IEEE International Conference on Robotics and Automation447–54 Piscataway, NJ: IEEE
    [Google Scholar]
  126. 126. 
    Kocsis L, Szepesvári C 2006. Bandit based Monte-Carlo planning. Machine Learning: ECML 2006. J Fürnkranz, T Scheffer, M Spiliopoulou 282–93 Berlin: Springer
    [Google Scholar]
  127. 127. 
    Browne C, Powley EJ, Whitehouse D, Lucas SM, Cowling PI et al. 2012. A survey of Monte Carlo tree search methods. IEEE Trans. Comput. Intell. AI Games 4:1–43
    [Google Scholar]
  128. 128. 
    Munos R. 2014. From bandits to Monte-Carlo tree search: the optimistic principle applied to optimization and planning. Found. Trends Mach. Learn. 7:1–129
    [Google Scholar]
  129. 129. 
    Kim B, Kaelbling LP, Lozano-Pérez T. 2018. Guiding search in continuous state-action spaces by learning an action sampler from off-target search experience. The Thirty-Second AAAI Conference on Artificial Intelligence6509–16 Palo Alto, CA: AAAI Press
    [Google Scholar]
/content/journals/10.1146/annurev-control-091420-084139
Loading
/content/journals/10.1146/annurev-control-091420-084139
Loading

Data & Media loading...

  • Article Type: Review Article
This is a required field
Please enter a valid email address
Approval was a Success
Invalid data
An Error Occurred
Approval was partially successful, following selected items could not be processed due to error