A systematic analysis of levels of integration between high-level task planning and low-level feasibility checks

Abstract

We provide a systematic analysis of levels of integration between discrete high-level reasoning and continuous low-level feasibility checks to address hybrid planning problems in robotic applications. We identify four distinct strategies for such an integration: (i) low-level checks are done for all possible cases in advance and the results are used during plan generation; (ii) low-level checks are done exactly when they are needed during the search for a plan; (iii) low-level checks are done after a plan is computed, and if the plan is found infeasible then a new plan is computed; (iv) similar to the previous strategy but the results of previous low-level checks are used during computation of a new plan. We analyze the usefulness of these strategies and their combinations by experiments on hybrid planning problems in different robotic application domains, in terms of computational efficiency and plan quality (relative to its feasibility).

Keywords

Task planning motion planning hybrid planning knowledge representation and reasoning answer set programming cognitive robotics experimental analysis

Get full access to this article

View all access options for this article.

References

[1]

Aker,

Patoglu and

Erdem, Answer set programming for reasoning with semantic knowledge in collaborative housekeeping robotics, in: Proc. of SYROCO, 2012.

[2]

Brewka,

Eiter and

Truszczynski, Answer set programming at a glance, Commun. ACM54(12) (2011), 92–103.

[3]

Bylander, The computational complexity of propositional STRIPS planning, Artificial Intelligence69(1–2) (1994), 165–204.

[4]

Caldiran,

Haspalamutgil,

Ok,

Palaz,

Erdem and

Patoglu, Bridging the gap between high-level reasoning and low-level control, in: Proc. of LPNMR, 2009.

[5]

Choset,

K.M.

Lynch,

Hutchinson,

G.A.

Kantor,

Burgard,

L.E.

Kavraki and

Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations, MIT Press, 2005.

[6]

Dimopoulos,

Nebel and

Koehler, Encoding planning problems in nonmonotonic logic programs, in: Proc. of ECP, 1997.

[7]

Dornhege,

Eyerich,

Keller,

Trüg,

Brenner and

Nebel, Semantic attachments for domain-independent planning systems, in: Proc. of ICAPS, 2009.

[8]

Eiter,

Fink,

Ianni,

Krennwallner,

Redl and

Schüller, A model building framework for answer set programming with external computations, Theory and Practice of Logic Programming (2015), to appear.

[9]

Eiter,

Ianni,

Schindlauer and

Tompits, A uniform integration of higher-order reasoning and external evaluations in answer-set programming, in: Proc. of IJCAI, 2005.

10.

[10]

Eiter,

Ianni,

Schindlauer and

Tompits, Effective integration of declarative rules with external evaluations for semantic-web reasoning, in: Proc. of ESWC, 2006.

11.

[11]

Erdem,

Aker and

Patoglu, Answer set programming for collaborative housekeeping robotics: Representation, reasoning, and execution, Intelligent Service Robotics5 (2012), 275–291.

12.

[12]

Erdem,

Haspalamutgil,

Palaz,

Patoglu and

Uras, Combining high-level causal reasoning with low-level geometric reasoning and motion planning for robotic manipulation, in: Proc. of ICRA, 2011.

13.

[13]

Erdem,

Haspalamutgil,

Patoglu and

Uras, Causality-based planning and diagnostic reasoning for cognitive factories, in: Proc. 17th IEEE Int. Conf. Emerging Technologies and Factory Automation (ETFA), 2012.

14.

[14]

Erdem,

D.G.

Kisa,

Oztok and

Schüller, A general formal framework for pathfinding problems with multiple agents, in: Proc. of AAAI, 2013.

15.

[15]

Erdem,

Patoglu and

Z.G.

Saribatur, Integrating hybrid diagnostic reasoning in plan execution monitoring for cognitive factories with multiple robots, in: Proc. of ICRA, 2015. Finalist for Best Conference Paper Award, Finalist for Best Cognitive Robotics Paper Award.

16.

[16]

Erdem,

Patoglu,

Z.G.

Saribatur,

Schüller and

Uras, Finding optimal plans for multiple teams of robots through a mediator: A logic-based approach, Theory and Practice of Logic Programming13(4–5) (2013), 831–846.

17.

[17]

Erdem,

Patoglu and

Schüller, Levels of integration between low-level reasoning and task planning, in: Proc. AAAI 2013 Workshop on Intelligent Robotic Systems, 2013.

18.

[18]

Erdem,

Patoglu and

Schüller, A systematic analysis of levels of integration between low-level reasoning and task planning, in: Proc. ICRA 2013 Workshop on Combining Task and Motion Planning, 2013.

19.

[19]

Erdem,

Patoglu and

Schüller, A systematic analysis of levels of integration between high-level task planning and low-level feasibility checks, in: Proc. of RCRA, 2014.

20.

[20]

Erol,

D.S.

Nau and

V.S.

Subrahmanian, Complexity, decidability and undecidability results for domain-independent planning, Artificial Intelligence76(1–2) (1995), 75–88.

21.

[21]

Eyerich,

Mattmüller and

Röger, Using the context-enhanced additive heuristic for temporal and numeric planning, in: Proc. of ICAPS, 2009.

22.

[22]

R.E.

Fikes and

N.J.

Nilsson, STRIPS: A new approach to the application of theorem proving to problem solving, in: Proc. of IJCAI, 1971.

23.

[23]

Fox and

Long, PDDL2.1: An extension to PDDL for expressing temporal planning domains, J. Artif. Intell. Res. (JAIR)20 (2003), 61–124.

24.

[24]

Gaschler,

R.P.A.

Petrick,

Giuliani,

Rickert and

Knoll, KVP: A knowledge of volumes approach to robot task planning, in: Proc. of IROS, 2013.

25.

[25]

Gebser,

Kaminski,

Kaufmann,

Ostrowski,

Schaub and

Thiele, Engineering an incremental ASP solver, in: Proc. of ICLP, 2008.

26.

[26]

Gebser,

Kaufmann,

Neumann and

Schaub, Clasp: A conflict-driven answer set solver, in: Proc. of LPNMR, 2007.

27.

[27]

Gebser,

Schaub and

Thiele, Gringo: A new grounder for answer set programming, in: Proc. of LPNMR, 2007.

28.

[28]

Gelfond and

Lifschitz, The stable model semantics for logic programming, in: Proc. of ICLP, 1988.

29.

[29]

Gelfond and

Lifschitz, Classical negation in logic programs and disjunctive databases, New Generation Computing9 (1991), 365–385.

30.

[30]

Gelfond and

Lifschitz, Action languages, Electronic Transactions on Artificial Intelligence2 (1998), 193–210.

31.

[31]

Giunchiglia,

Lee,

Lifschitz,

McCain and

Turner, Nonmonotonic causal theories, Artificial Intelligence (AIJ)153(1–2) (2004), 49–104.

32.

[32]

Gravot,

Cambon and

Alami, aSyMov: A planner that deals with intricate symbolic and geometric problems, in: Robotics Research the Eleventh International Symposium, Springer Tracts in Advanced Robotics, Vol. 15, 2005.

33.

[33]

Hauser and

J.-C.

Latombe, Integrating task and PRM motion planning: Dealing with many infeasible motion planning queries, in: Workshop on Bridging the Gap Between Task and Motion Planning at ICAPS, 2009.

34.

[34]

Havur,

Haspalamutgil,

Palaz,

Erdem and

Patoglu, A case study on the tower of hanoi challenge: Representation, reasoning and execution, in: Proc. of ICRA, 2013.

35.

[35]

Havur,

Ozbilgin,

Erdem and

Patoglu, Geometric rearrangement of multiple movable objects on cluttered surfaces: A hybrid reasoning approach, in: Proc. of ICRA, 2014.

36.

[36]

Hertle,

Dornhege,

Keller and

Nebel, Planning with semantic attachments: An object-oriented view, in: Proc. of ECAI, 2012.

37.

[37]

Hoffmann and

Nebel, The FF planning system: Fast plan generation through heuristic search, J. Artif. Intell. Res.14 (2001), 253–302.

38.

[38]

L.P.

Kaelbling and

Lozano-Pérez, Hierarchical task and motion planning in the now, in: Proc. of ICRA, 2011.

39.

[39]

L.P.

Kaelbling and

Lozano-Pérez, Integrated task and motion planning in belief space, International Journal of Robotics Research32(9–10) (2013), 1194–1227.

40.

[40]

H.A.

Kautz and

Selman, Planning as satisfiability, in: Proc. of ECAI, 1992.

41.

[41]

KuffnerJr. and

LaValle, RRT-connect: An efficient approach to single-query path planning, in: Proc. of ICRA, Vol. 2, 2000.

42.

[42]

Lagriffoul,

Dimitrov,

Bidot,

Saffiotti and

Karlsson, Efficiently combining task and motion planning using geometric constraints, International Journal of Robotics Research33(14) (2014), 1726–1747.

43.

[43]

Lagriffoul,

Karlsson,

Bidot and

Saffiotti, Combining task and motion planning is not always a good idea, in: Proc. RSS 2013 on Combined Robot Motion Planning and AI Planning for Practical Applications, 2013.

44.

[44]

S.M.

LaValle, Planning Algorithms, Cambridge University Press, Cambridge, UK, 2006, available at: http://planning.cs.uiuc.edu/.

45.

[45]

Lifschitz, Action languages, answer sets and planning, in: The Logic Programming Paradigm: A 25-Year Perspective, Springer Verlag, 1999, pp. 357–373.

46.

[46]

Lifschitz, Answer set programming and plan generation, Artificial Intelligence138 (2002), 39–54.

47.

[47]

Lifschitz, What is answer set programming?, in: Proc. of AAAI, 2008.

48.

[48]

Liu and

Singh, ConceptNet: A practical commonsense reasoning toolkit, BT Technology Journal22(4) (2004), 211–226.

49.

[49]

Marek and

Truszczyński, Stable models and an alternative logic programming paradigm, in: The Logic Programming Paradigm: A 25-Year Perspective, Springer Verlag, 1999, pp. 375–398.

50.

[50]

McCain and

Turner, Causal theories of action and change, in: Proc. of AAAI/IAAI, 1997.

51.

[51]

Mccarthy and

P.J.

Hayes, Some philosophical problems from the standpoint of artificial intelligence, in: Machine Intelligence, Edinburgh University Press, 1969, pp. 463–502.

52.

[52]

Mcdermott,

Ghallab,

Howe,

Knoblock,

Ram,

Veloso,

Weld and

Wilkins, Pddl – the planning domain definition language, Technical Report TR-98-003, Yale Center for Computational Vision and Control, 1998.

53.

[53]

D.S.

Nau,

Muñoz-Avila,

Cao,

Lotem and

Mitchell, Total-order planning with partially ordered subtasks, in: Proc. of IJCAI, 2001.

54.

[54]

Niemelä, Logic programs with stable model semantics as a constraint programming paradigm, Annals of Mathematics and Artificial Intelligence25 (1999), 241–273.

55.

[55]

Nogueira,

Balduccini,

Gelfond,

Watson and

Barry, An A-Prolog decision support system for the space shuttle, in: Proc. of PADL, 2001.

56.

[56]

Pan,

Chitta and

Manocha, FCL: A general purpose library for collision and proximity queries, in: Proc. of ICRA, 2012.

57.

[57]

R.P.A.

Petrick and

Bacchus, A knowledge-based approach to planning with incomplete information and sensing, in: Proc. of AIPS, 2002.

58.

[58]

R.P.A.

Petrick and

Bacchus, Extending the knowledge-based approach to planning with incomplete information and sensing, in: Proc. of ICAPS, 2004.

59.

[59]

Plaku, From high-level tasks to low-level motions: Motion planning for high-dimensional nonlinear hybrid robotic systems, PhD dissertation, Rice University, TX, USA, 2008.

60.

[60]

Plaku, Planning in discrete and continuous spaces: From LTL tasks to robot motions, in: Proc. of TAROS, 2012.

61.

[61]

Plaku and

G.D.

Hager, Sampling-based motion and symbolic action planning with geometric and differential constraints, in: Proc. of ICRA, 2010.

62.

[62]

Reif, Complexity of the mover’s problem and generalizations, in: Proc. of SOCS, 1979.

63.

[63]

Ricca,

Grasso,

Alviano,

Manna,

Lio,

Iiritano and

Leone, Team-building with answer set programming in the Gioia-Tauro seaport, Theory and Practice of Logic Programming12(3) (2012), 361–381.

64.

[64]

Srivastava,

Fang,

Riano,

Chitnis,

Russell and

Abbeel, Combined task and motion planning through an extensible planner-independent interface layer, in: Proc. of ICRA, 2014.

65.

[65]

V.S.

Subrahmanian and

Zaniolo, Relating stable models and AI planning domains, in: Proc. of ICLP, 1995.

66.

[66]

I.A.

Sucan and

Chitta, MoveIt! Available at: http://moveit.ros.org.

67.

[67]

I.A.

Sucan,

Moll and

L.E.

Kavraki, The open motion planning library, Robotics & Automation Magazine, IEEE19(4) (2012), 72–82.

68.

[68]

Tiihonen,

Soininen and

Sulonen, A practical tool for mass-customising configurable products, in: Proc. of ICED, 2003.

69.

[69]

R.W.

Weyhrauch, Prolegomena to a theory of formal reasoning, Technical report, Stanford University, 1978.

70.

[70]

Wolfe,

Marthi and

Russell, Combined task and motion planning for mobile manipulation, in: Proc. of ICAPS, 2010.