We present a new constraint-based framework for task and motion planning (TMP). Our approach is extensible, probabilistically complete, and offers improved performance and generality compared with a similar, state-of-the-art planner. The key idea is to leverage incremental constraint solving to efficiently incorporate geometric information at the task level. Using motion feasibility information to guide task planning improves scalability of the overall planner. Our key abstractions address the requirements of manipulation and object rearrangement. We validate our approach on a physical manipulator and evaluate scalability on scenarios with many objects and long plans, showing order-of-magnitude gains compared with the benchmark planner and improved scalability from additional geometric guidance. Finally, in addition to describing a new method for TMP and its implementation on a physical robot, we also put forward requirements and abstractions for the development of similar planners in the future.
AlamiRLaumondJPSiméonT (1995) Two manipulation planning algorithms. In: WAFR. AK Peters, Ltd., pp. 109–125.
2.
BarrettCConwayCLDetersMet al. (2011) CVC4. In: International Conference on Computer-Aided Verification (CAV). New York: Springer, pp. 171–177.
3.
BarrettCFontainePTinelliC (2015) The SMT-LIB Standard: Version 2.5. Technical report, Department of Computer Science, The University of Iowa, http://www.SMT-LIB.org.
4.
BeltaCIslerVPappasGJ (2005) Discrete abstractions for robot motion planning and control in polygonal environments. Transactions on Robotics21(5): 864–874.
5.
BhatiaAKavrakiLEVardiMY (2010) Motion planning with hybrid dynamics and temporal goals. In: Conference on Decision and Control (CDC). Atlanta, GA: IEEE, pp. 1108–1115.
6.
BhatiaAMalyMRKavrakiLEVardiMY (2011) Motion planning with complex goals. Robotics and Automation Magazine18(3): 55–64.
7.
BidotJKarlssonLLagriffoulFSaffiottiA (2015) Geometric backtracking for combined task and motion planning in robotic systems. Artificial Intelligence247: 229–265.
8.
BohlinRKavrakiLE (2000) Path planning using lazy PRM. In: International Conference on Robotics and Automation (ICRA), volume 1. IEEE, pp. 521–528.
9.
BohlinRKavrakiLE (2001) A Randomized Algorithm for Robot Path Planning Based on Lazy Evaluation. Dordrecht: Kluwer Academic Publishers, pp. 221–249.
10.
CambonSAlamiRGravotF (2009) A hybrid approach to intricate motion, manipulation and task planning. The International Journal of Robotics Research28(1): 104–126.
11.
CambonSGravotFAlamiR (2004) A robot task planner that merges symbolic and geometric reasoning. In: European Conference on Artificial Intelligence (ECAI), volume 16, p. 895.
12.
CashmoreMFoxMLongDMagazzeniD (2016) A compilation of the full PDDL+ language into SMT. In: Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling. AAAI Press, pp. 79–87.
13.
ChosetHLynchKMHutchinsonSet al. (2005) Principles of Robot Motion: Theory, Algorithms, and Implementation. Cambridge, MA: MIT Press.
14.
CohenBChittaSLikhachevM (2014) Single and dual-arm motion planning with heuristic search. The International Journal of Robotics Research3(2): 305–320.
15.
CresswellSCoddingtonAM (2004) Compilation of LTL goal formulas into PDDL. In: European Conference on Artificial Intelligence (ECAI).
ŞucanIAMollMKavrakiLE (2012) The open motion planning library. Robotics and Automation Magazine19(4): 72–82.
18.
DantamNTAmorHBChristensenHStilmanM (2014) Online camera registration for robot manipulation. In: International Symposium on Experimental Robotics. Berlin: Springer, pp. 179–194.
19.
DantamNTBøndergaardKJohanssonMAFuruholmTKavrakiLE (2016a) Unix philosophy and the real world: Control software for humanoid robots. Frontiers in Robotics and Artificial Intelligence3: 6. DOI: 10.3389/frobt.2016.00006.
20.
DantamNTKingstonZChaudhuriSKavrakiLE (2016b) Incremental task and motion planning: A constraint-based approach. In: Robotics: Science and Systems.
21.
DantamNTLofaroDMHereidAOhPAmesAStilmanM (2015) The ACH IPC library. Robotics and Automation Magazine22(1): 76–85.
22.
DantamNTStilmanM (2013) The motion grammar: Analysis of a linguistic method for robot control. Transactions on Robotics29(3): 704–718.
23.
De GiacomoGVardiMY (2000) Automata-theoretic approach to planning for temporally extended goals. In: Recent Advances in AI Planning. New York: Springer, pp. 226–238.
24.
De MouraLBjørnerN (2008) Z3: An efficient SMT solver. In: Tools and Algorithms for the Construction and Analysis of Systems. New York: Springer, pp. 337–340.
25.
De MouraLBjørnerN (2011) Satisfiability modulo theories: introduction and applications. Communications of the ACM54(9): 69–77.
26.
de SilvaLGharbiMPandeyAKAlamiR (2014) A new approach to combined symbolic-geometric backtracking in the context of human–robot interaction. In: International Conference on Robotics and Automation (ICRA). IEEE, pp. 3757–3763.
27.
de SilvaLPandeyAKAlamiR (2013a) An interface for interleaved symbolic-geometric planning and backtracking. In: International Conference on Intelligent Robots and Systems (IROS). IEEE, pp. 232–239.
28.
de SilvaLPandeyAKGharbiMAlamiR (2013b) Towards combining HTN planning and geometric task planning. In: Robotics: Science and Systems Workshop on Combined Robot Motion Planning and AI Planning for Practical Applications.
29.
DeshpandeAKaelblingLPLozano-PérezT (2016) Decidability of semi-holonomic prehensile task and motion planning. In: Workshop on the Algorithmic Foundations of Robotics.
DogarMSrinivasaS (2011) A framework for push-grasping in clutter. In: Robotics: Science and Systems (RSS).
32.
DornhegeCEyerichPKellerTTrügSBrennerMNebelB (2012) Semantic attachments for domain-independent planning systems. In: Towards Service Robots for Everyday Environments. Berlin: Springer, pp. 99–115.
33.
EdelkampSHoffmannJ (2004) PDDL2.2: The language for the classical part of the 4th international planning competition. Technical Report 195, Albert-Ludwigs-Universität Freiburg, Institut für Informatik.
34.
EnzmannnAYoungCKretzschmarL (1994) Ray tracing worlds with POV-Ray. Sams.
35.
ErdemEAkerEPatogluV (2012) Answer set programming for collaborative housekeeping robotics: representation, reasoning, and execution. Intelligent Service Robotics5(4): 275–291.
36.
ErdmannMLozano-PérezT (1987) On multiple moving objects. Algorithmica2(1-4): 477–521.
37.
ErolKHendlerJNauDS (1994) HTN planning: Complexity and expressivity. In: AAAI, volume 94, pp. 1123–1128.
38.
FikesRENilssonNJ (1972) STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence2(3): 189–208.
39.
FooteT (2013) tf: The transform library. In: Technologies for Practical Robot Applications (TePRA). IEEE, pp. 1–6.
40.
GarrettCRLozano-PérezTKaelblingLP (2015) FFRob: An efficient heuristic for task and motion planning. In: Algorithmic Foundations of Robotics XI. New York: Springer, pp. 179–195.
41.
GharbiMLallementRAlamiR (2015) Combining symbolic and geometric planning to synthesize human-aware plans: toward more efficient combined search. In: International Conference on Intelligent Robots and Systems (IROS). IEEE, pp. 6360–6365.
42.
GravotFCambonSAlamiR (2005) aSyMov: a planner that deals with intricate symbolic and geometric problems. In: International Symposium on Robotics Research (ISRR). New York: Springer, pp. 100–110.
43.
HartPENilssonNJRaphaelB (1968) A formal basis for the heuristic determination of minimum cost paths. Transactions on Systems Science and Cybernetics4(2): 100–107.
44.
HartenbergRSDenavitJ (1964) Kinematic Synthesis of Linkages. New York: McGraw-Hill.
HauserK (2013b) The minimum constraint removal problem with three robotics applications. The International Journal of Robotics Research33(1): 5–17.
47.
HeKLahijanianMKavrakiLEVardiMY (2015) Towards manipulation planning with temporal logic specifications. In: International Conference on Robotics and Automation (ICRA). Seattle, WA: IEEE, pp. 346–352.
48.
HelmertM (2006) The fast downward planning system. Journal Artificial Intelligence Research26: 191–246.
49.
HoffmannJ (2003) The Metric-FF planning system: Translating “ignoring delete lists” to numeric state variables. Journal of Artificial Intelligence Research20: 291–341.
50.
HoffmannJNebelB (2001) The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research14: 253–302.
51.
KaelblingLPLozano-PérezT (2011) Hierarchical task and motion planning in the now. In: International Conference on Robotics and Automation (ICRA). IEEE, pp. 1470–1477.
52.
KaelblingLPLozano-PérezT (2013) Integrated task and motion planning in belief space. The International Journal of Robotics Research32(9–10): 1194–1227.
53.
KaramanSFrazzoliE (2012) Sampling-based algorithms for optimal motion planning with deterministic -calculus specifications. In: American Control Conference (ACC). IEEE, pp. 735–742.
54.
KautzHSelmanB (1999) Unifying SAT-based and graph-based planning. In: International Joint Conference on Artifical Intelligence (IJCAI), volume 99, pp. 318–325.
55.
KavrakiLEŠvestkaPLatombeJCOvermarsMH (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. Transactions on Robotics and Automation12(4): 566–580.
56.
KoenigNHowardA (2004) Design and use paradigms for gazebo, an open-source multi-robot simulator. In: International Conference on Intelligent Robots and Systems (IROS), volume 3. IEEE, pp. 2149–2154.
57.
Kress-GazitHFainekosGEPappasGJ (2008) Translating structured English to robot controllers. Advanced Robotics22(12): 1343–1359.
58.
Kress-GazitHFainekosGEPappasGJ (2009) Temporal-logic-based reactive mission and motion planning. Transactions on Robotics25(6): 1370–1381.
59.
KrontirisABekrisKE (2015) Dealing with difficult instances of object rearrangement. In: Robotics: Science and Systems (RSS).
60.
KuffnerJJLaValleSM (2000) RRT-connect: An efficient approach to single-query path planning. In: International Conference on Robotics and Automation (ICRA), volume 2. IEEE, pp. 995–1001.
61.
KunzTStilmanM (2015) Kinodynamic RRTs with fixed time step and best-input extension are not probabilistically complete. In: Algorithmic Foundations of Robotics XI. New York: Springer, pp. 233–244.
62.
LagriffoulFAndresB (2016) Combining task and motion planning: A culprit detection problem. The International Journal of Robotics Research35(8): 890–927.
63.
LagriffoulFDimitrovDSaffiottiAKarlssonL (2012) Constraint propagation on interval bounds for dealing with geometric backtracking. In: International Conference on Intelligent Robots and Systems (IROS). IEEE, pp. 957–964.
64.
LaValleSM (2006) Planning Algorithms. Cambridge: Cambridge University Press.
65.
LaValleSMKuffnerJJ (2001) Rapidly-exploring random trees: Progress and prospects. In: DonaldBLynchKRusD (eds.) Algorithmic and Computational Robotics: New Directions. A.K. Peters/CRC Press, pp. 293–308.
66.
LevihnMScholzJStilmanM (2013) Hierarchical decision theoretic planning for navigation among movable obstacles. In: Algorithmic Foundations of Robotics X. New York: Springer, pp. 19–35.
67.
LifschitzV (1999) Answer set planning. In: Logic Programming and Nonmonotonic Reasoning. New York: Springer, pp. 373–374.
68.
LifschitzV (2008) What is answer set programming? In: AAAI, volume 8, pp. 1594–1597.
69.
Lozano-PérezTKaelblingLP (2014) A constraint-based method for solving sequential manipulation planning problems. In: International Conference on Intelligent Robots and Systems (IROS). IEEE, pp. 3684–3691.
70.
LyonsDMArbibMA (1989) A formal model of computation for sensory-based robotics. Transactions on Robotics and Automation5(3): 280–293.
71.
MatuszekCHerbstEZettlemoyerLFoxD (2013) Learning to parse natural language commands to a robot control system. In: Experimental Robotics. New York: Springer, pp. 403–415.
72.
McCarthyZBretlTHutchinsonS (2012) Proving path non-existence using sampling and alpha shapes. In: International Conference on Robotics and Automation (ICRA). IEEE, pp. 2563–2569.
NedunuriSPrabhuSMollMChaudhuriSKavrakiLE (2014) SMT-based synthesis of integrated task and motion plans from plan outlines. In: International Conference on Robotics and Automation (ICRA). IEEE, pp. 655–662.
75.
PanJChittaSManochaD (2012) FCL: A general purpose library for collision and proximity queries. In: International Conference on Robotics and Automation (ICRA). IEEE, pp. 3859–3866.
76.
PlakuEHagerGD (2010) Sampling-based motion and symbolic action planning with geometric and differential constraints. In: International Conference on Robotics and Automation (ICRA). IEEE, pp. 5002–5008.
77.
PlakuEKavrakiLEVardiMY (2010) Motion planning with dynamics by a synergistic combination of layers of planning. Transactions on Robotics26(3): 469–482.
78.
RintanenJ (2012a) Engineering efficient planners with SAT. In: European Conference on Artificial Intelligence (ECAI), pp. 684–689.
79.
RintanenJ (2012b) Planning as satisfiability: Heuristics. Artificial Intelligence193: 45–86.
80.
RintanenJ (2014) Madagascar: Scalable planning with sat. In: 8th International Planning Competition (IPC-2014), pp. 66–70.
81.
SchüllerPPatogluVErdemE (2013) Levels of integration between low-level reasoning and task planning. In: AAAI Workshop on Intelligent Robotic Systems.
82.
SchulmanJDuanYHoJet al. (2014) Motion planning with sequential convex optimization and convex collision checking. The International Journal of Robotics Research33(9): 1251–1270.
83.
SmitsRBruyninckxHAertbeliënE (2011) KDL: Kinematics and dynamics library. Available at: http://www.orocos.org/kdl.
84.
SrivastavaSFangERianoLChitnisRRussellSAbbeelP (2014) Combined task and motion planning through an extensible planner-independent interface layer. In: International Conference on Robotics and Automation (ICRA). IEEE, pp. 639–646.
85.
StilmanMKuffnerJJ (2005) Navigation among movable obstacles: Real-time reasoning in complex environments. International Journal of Humanoid Robotics2(4): 479–503.
86.
StilmanMSchamburekJUKuffnerJJAsfourT (2007) Manipulation planning among movable obstacles. In: International Conference on Robotics and Automation (ICRA). IEEE, pp. 3327–3332.
87.
TenorthMBeetzM (2015) Representations for robot knowledge in the KnowRob framework. Artificial Intelligence247: 151–169.
88.
VallatiMChrpaLGrzesMMcCluskeyTLRobertsMSannerS (2015) The 2014 international planning competition: Progress and trends. AI Magazine36(3): 90–98.
89.
Van Den BergJStilmanMKuffnerJJLinMManochaD (2010) Path planning among movable obstacles: a probabilistically complete approach. In: Algorithmic Foundation of Robotics VIII. New York: Springer, pp. 599–614.
90.
Vega-BrownWRoyN (2016) Asymptotically optimal planning under piecewise-analytic constraints. In: Workshop on the Algorithmic Foundations of Robotics.
91.
VidalV (2014) YAHSP3 and YAHSP3-MT in the 8th international planning competition. In: 8th International Planning Competition (IPC-2014), pp. 64–65.
92.
VijaykumarRVenkataramanSDakinGLyonsDM (1987) A task grammar approach to the structure and analysis of robot programs. In: Workshop on Languages for Automation. IEEE.
93.
WangYDantamNTChaudhuriSKavrakiLE (2016) Task and motion policy synthesis as liveness games. In: International Conference on Automated Planning and Scheduling (ICAPS). AAAI.
