Sage Journals: Discover world-class research

Abstract

Integrating task and motion planning is becoming increasingly important due to the recognition that a growing number of robotics applications in navigation, search-and-rescue missions, manipulation, and medicine involve reasoning with both discrete abstractions and continuous motions. The problem poses unique computational challenges: a vast hybrid discrete/continuous space must be searched while accounting for complex geometries, motion dynamics, collision avoidance and temporal goals. This paper takes the position that continued progress relies on integrative approaches that bring together techniques from robotics and AI. In this context, the paper examines robot motion planning with temporal-logic specifications and discusses open challenges and directions for future research. The paper aims to promote a continuing dialog between robotics and AI communities.

Keywords

Task planning discrete search motion planning temporal logic sampling-based algorithm

Get full access to this article

View all access options for this article.

References

[1]

Aine and

Likhachev, Anytime truncated D^∗: Anytime replanning with truncation, in: Annual Symposium on Combinatorial Search, 2013, pp. 2–10.

[2]

Alterovitz and

Goldberg, Motion Planning in Medicine: Optimization and Simulation Algorithms for Image-Guided Procedures, Springer Tracts in Advanced Robotics, 2008.

[3]

Bacchus and

Kabanza, Planning for temporally extended goals, Annals of Mathematics and Artificial Intelligence 22(1,2) (1998), 5–27.

[4]

K.E.

Bekris and

L.E.

Kavraki, Greedy but safe replanning under kinodynamic constraints, in: IEEE International Conference on Robotics and Automation, 2007, pp. 704–710.

[5]

Belta,

Bicchi,

Egerstedt,

Frazzoli,

Klavins and

G.J.

Pappas, Symbolic planning and control of robot motion, IEEE Robotics and Automation Magazine 14(1) (2007), 61–71.

[6]

Bhatia,

L.E.

Kavraki and

M.Y.

Vardi, Sampling-based motion planning with temporal goals, in: IEEE International Conference on Robotics and Automation, 2010, pp. 2689–2696.

[7]

Bhatia,

Maly,

Kavraki and

Vardi, Motion planning with complex goals, IEEE Robotics Automation Magazine 18 (2011), 55–64.

[8]

M.S.

Branicky, Universal computation and other capabilities of continuous and hybrid systems, Theoretical Computer Science 138(1) (1995), 67–100.

[9]

Bruce and

Veloso, Real-time multi-robot motion planning with safe dynamics, Multi-Robot Systems: From Swarms to Intelligent Automata 3 (2005), 159–170.

10.

[10]

Cambon,

Alami and

Gravot, A hybrid approach to intricate motion, manipulation and task planning, International Journal of Robotics Research 1 (2009), 104–126.

11.

[11]

Canny, The Complexity of Robot Motion Planning, MIT Press, Cambridge, MA, 1988.

12.

[12]

Cashmore,

Fox,

Larkworthy,

Long and

Magazzeni, Planning inspection tasks for AUVs, in: OCEANS, 2013, pp. 1–8.

13.

[13]

Chen,

Ding,

Stefanescu and

Belta, A formal approach to the deployment of distributed robotic teams, IEEE Transactions on Robotics 28(1) (2012), 158–171.

14.

[14]

Chen,

Tŭmová,

Ulusoy and

Belta, Temporal logic robot control based on automata learning of environmental dynamics, International Journal of Robotics Research 32(5) (2013), 547–565.

15.

[15]

Cheng,

Pappas and

Kumar, Decidability of motion planning with differential constraints, in: IEEE International Conference on Robotics and Automation, 2007, pp. 1826–1831.

16.

[16]

Choi and

Amir, Combining planning and motion planning, in: IEEE International Conference on Robotics and Automation, 2009, pp. 238–244.

17.

[17]

Choset,

K.M.

Lynch,

Hutchinson,

Kantor,

Burgard,

L.E.

Kavraki and

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

18.

[18]

E.M.

Clarke,

Grumberg and

D.A.

Peled, Model Checking, MIT Press, 2000.

19.

[19]

J.A.

DeCastro and

Kress-Gazit, Synthesis of nonlinear continuous controllers for verifiably correct high-level, reactive behaviors, The International Journal of Robotics Research 34(3) (2015), 378–394.

20.

[20]

Doherty,

Kvarnström and

Heintz, A temporal logic-based planning and execution monitoring framework for unmanned aircraft systems, Autonomous Agents and Multi-Agent Systems 19(3) (2009), 332–377.

21.

[21]

Donald,

Xavier,

Canny and

Reif, Kinodynamic motion planning, Journal of the ACM 40 (1993), 1048–1066.

22.

[22]

Edelkamp and

Plaku, Multi-goal motion planning with physics-based game engines, in: IEEE Conference on Computational Intelligence and Games, 2014, pp. 115–122.

23.

[23]

E.A.

Emerson and

J.Y.

Halpern, Decision procedures and expressiveness in the temporal logic of branching time, Journal of Computer and System Sciences 30(1) (1985), 1–24.

24.

[24]

E.A.

Emerson and

C.S.

Jutla, Tree automata, mu-calculus and determinacy, in: Proceedings of the Symposium on Foundations of Computer Science, 1991, pp. 168–377.

25.

[25]

Erdem,

Haspalamutgil,

Palaz,

Patoglu and

Uras, 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, pp. 4575–4581.

26.

[26]

G.E.

Fainekos,

Girard,

Kress-Gazit and

G.J.

Pappas, Temporal logic motion planning for dynamic mobile robots, Automatica 45(2) (2009), 343–352.

27.

[27]

Ferguson and

Stentz, Anytime RRTs, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2006, pp. 5369–5375.

28.

[28]

Gochev,

Safonova and

Likhachev, Planning with adaptive dimensionality for mobile manipulation, in: IEEE International Conference on Robotics and Automation, 2012, pp. 2944–2951.

29.

[29]

Guo,

K.H.

Johansson and

D.V.

Dimarogonas, Revising motion planning under linear temporal logic specifications in partially known workspaces, in: IEEE International Conference on Robotics and Automation, 2013, pp. 5025–5032.

30.

[30]

Hart and

Sharir, Probabilistic propositional temporal logics, Information and Control 70(2) (1986), 97–155.

31.

[31]

Hsu,

Kindel,

J.C.

Latombe and

Rock, Randomized kinodynamic motion planning with moving obstacles, International Journal of Robotics Research 21(3) (2002), 233–255.

32.

[32]

Johnson and

Kress-Gazit, Probabilistic guarantees for high-level robot behavior in the presence of sensor error, Autonomous Robots 33(3) (2012), 309–321.

33.

[33]

Kaelbling and

Lozano-Pérez, Hierarchical task and motion planning in the now, in: IEEE International Conference on Robotics and Automation, 2011, pp. 1470–1477.

34.

[34]

Karaman and

Frazzoli, Sampling-based motion planning with deterministic μ-calculus specifications, in: IEEE Conference on Decision and Control, 2009, pp. 2222–2229.

35.

[35]

Karaman and

Frazzoli, Optimal kinodynamic motion planning using incremental sampling-based methods, in: IEEE Conference on Decision and Control, 2010, pp. 7681–7687.

36.

[36]

Karaman and

Frazzoli, Sampling-based algorithms for optimal motion planning with deterministic μ-calculus specifications, in: American Control Conference, 2012, pp. 735–742.

37.

[37]

Karaman,

M.R.

Walter,

Perez,

Frazzoli and

Teller, Anytime motion planning using the RRT^∗, in: IEEE International Conference on Robotics and Automation, 2011, pp. 1478–1483.

38.

[38]

L.E.

Kavraki,

Švestka,

J.C.

Latombe and

M.H.

Overmars, Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Transactions on Robotics and Automation 12(4) (1996), 566–580.

39.

[39]

Keller, Numerical Methods for Two-Point Boundary-Value Problems, Dover, New York, NY, 1992.

40.

[40]

Kloetzer and

Belta, Temporal logic planning and control of robotic swarms by hierarchical abstractions, IEEE Transactions on Robotics 23(2) (2007), 320–331.

41.

[41]

Koenig and

Likhachev, Fast replanning for navigation in unknown terrain, IEEE Transactions on Robotics 21(3) (2005), 354–363.

42.

[42]

Koymans, Specifying real-time properties with metric temporal logic, Real-time Systems 2(4) (1990), 255–299.

43.

[43]

Kress-Gazit,

G.E.

Fainekos and

G.J.

Pappas, Temporal logic-based reactive mission and motion planning, IEEE Transactions on Robotics 25(6) (2009), 1370–1381.

44.

[44]

Kress-Gazit,

Wongpiromsarn and

Topcu, Correct, reactive robot control from abstraction and temporal logic specifications, IEEE Robotics & Automation Magazine 18(3) (2011), 65–74.

45.

[45]

Kuffner,

Kagami,

Nishiwaki,

Inaba and

Inoue, Dynamically-stable motion planning for humanoid robots, Autonomous Robots 12(1) (2002), 105–118.

46.

[46]

Kupferman and

Vardi, Model checking of safety properties, Formal Methods in System Design 19(3) (2001), 291–314.

47.

[47]

Kvarnström and

Doherty, TALplanner: A temporal logic based forward chaining planner, Annals of Mathematics and Artificial Intelligence 30(1–4) (2000), 119–169.

48.

[48]

Lagriffoul,

Dimitrov,

Saffiotti and

Karlsson, Constraint propagation on interval bounds for dealing with geometric backtracking, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2012, pp. 957–964.

49.

[49]

Lahijanian,

S.B.

Andersson and

Belta, Temporal logic motion planning and control with probabilistic satisfaction guarantees, IEEE Transactions on Robotics 28(2) (2012), 396–409.

50.

[50]

S.M.

LaValle, Planning Algorithms, Cambridge Univ. Press, Cambridge, MA, 2006.

51.

[51]

S.M.

LaValle and

J.J.

Kuffner, Randomized kinodynamic planning, International Journal of Robotics Research 20(5) (2001), 378–400.

52.

[52]

Leonard,

How,

Teller,

Berger,

Campbell,

Fiore,

Fletcher,

Frazzoli,

Huang,

Karaman,

Koch,

Kuwata,

Moore,

Olson,

Peters,

Teo,

Truax,

Walter,

Barrett,

Epstein,

Maheloni,

Moyer,

Jones,

Buckley,

Antone,

Galejs,

Krishnamurthy and

Williams, A perception driven autonomous urban vehicle, Journal of Field Robotics 25(10) (2008), 727–774.

53.

[53]

S.C.

Livingston,

R.M.

Murray and

J.W.

Burdick, Backtracking temporal logic synthesis for uncertain environments, in: IEEE International Conference on Robotics and Automation, 2012, pp. 5163–5170.

54.

[54]

Marthi,

Russell and

Wolfe, Angelic semantics for high-level actions, in: International Conference on Automated Planning and Scheduling, 2007, pp. 232–239.

55.

[55]

M.C.

Mayer,

Limongelli,

Orlandini and

Poggioni, Linear temporal logic as an executable semantics for planning languages, Journal of Logic, Language and Information 16(1) (2007), 63–89.

56.

[56]

McMahon and

Plaku, Sampling-based tree search with discrete abstractions for motion planning with dynamics and temporal logic, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014, pp. 3726–3733.

57.

[57]

McMahon and

Plaku, Robot motion planning with task specifications via regular languages, Robotica (2015), to appear. DOI: 10.1017/S0263574715000417.

58.

[58]

Molloy and

Shehu, Elucidating the ensemble of functionally-relevant transitions in protein systems with a robotics-inspired method, BMC Structural Biology 13 (2013), S8.

59.

[59]

R.M.

Murray and

S.S.

Sastry, Nonholonomic motion planning: Steering using sinusoids, IEEE Transactions on Automatic Control 38(5) (1993), 700–716.

60.

[60]

Plaku, Planning in discrete and continuous spaces: From LTL tasks to robot motions, in: Towards Autonomous Robotic Systems, LNCS, Vol. 7429, 2012, pp. 331–342.

61.

[61]

Plaku, Region-guided and sampling-based tree search for motion planning with dynamics, IEEE Transactions on Robotics 31 (2015), 723–735.

62.

[62]

Plaku and

G.D.

Hager, Sampling-based motion and symbolic action planning with geometric and differential constraints, in: IEEE International Conference on Robotics and Automation, 2010, pp. 5002–5008.

63.

[63]

Plaku,

Kavraki and

Vardi, Falsification of LTL safety properties in hybrid systems, International Journal on Software Tools and Technology Transfer 15(4) (2013), 305–320.

64.

[64]

Plaku,

L.E.

Kavraki and

M.Y.

Vardi, Falsification of LTL safety properties in hybrid systems, in: International Conference on Tools and Algorithms for the Construction and Analysis of Systems, Vol. 5505, 2009, pp. 368–382.

65.

[65]

Plaku,

L.E.

Kavraki and

M.Y.

Vardi, Motion planning with dynamics by a synergistic combination of layers of planning, IEEE Transactions on Robotics 26(3) (2010), 469–482.

66.

[66]

Plaku and

McMahon, Motion planning and decision making for underwater vehicles operating in constrained environments in the littoral, in: Towards Autonomous Robotic Systems, LNCS, Vol. 8069, 2014, pp. 328–339.

67.

[67]

Pnueli, The temporal logic of programs, in: IEEE Symposium on Foundations of Computer Science, 1977, pp. 46–57.

68.

[68]

Rashidian,

Plaku and

Edelkamp, Motion planning with rigid-body dynamics for generalized traveling salesman tours, in: ACM SIGGRAPH Motion in Games, 2014, pp. 87–96.

69.

[69]

Reif, Complexity of the mover’s problem and generalizations, in: IEEE Symposium on Foundations of Computer Science, 1979, pp. 421–427.

70.

[70]

Russle and

Norvig, Artificial Intelligence: A Modern Approach, 2nd edn, Prentice-Hall, 2002.

71.

[71]

Sarid,

Xu and

Kress-Gazit, Guaranteeing high-level behaviors while exploring partially known maps, in: Robotics: Science and Systems, 2012, pp. 377–384.

72.

[72]

J.T.

Schwartz and

Sharir, A survey of motion planning and related geometric algorithms, Artificial Intelligence 37 (1988), 157–169.

73.

[73]

Sistla, Safety, liveness and fairness in temporal logic, Formal Aspects of Computing 6 (1994), 495–511.

74.

[74]

I.A.

Şucan and

L.E.

Kavraki, Mobile manipulation: Encoding motion planning options using task motion multigraphs, in: IEEE International Conference on Robotics and Automation, 2011, pp. 5492–5498.

75.

[75]

I.A.

Şucan and

L.E.

Kavraki, A sampling-based tree planner for systems with complex dynamics, IEEE Transactions on Robotics 28(1) (2012), 116–131.

76.

[76]

Tapia,

Thomas and

N.M.

Amato, A motion planning approach to studying molecular motions, Communications in Information and Systems 10(1) (2010), 53–68.

77.

[77]

Thomas, Automata on infinite objects, Handbook of Theoretical Computer Science 2 (1990), 133–192.

78.

[78]

Tilbury,

R.M.

Murray and

S.S.

Sastry, Trajectory generation for the N-trailer problem using Goursat normal form, IEEE Transactions on Automatic Control 40(5) (1995), 1–18.

79.

[79]

Ulusoy,

Marrazzo and

Belta, Receding horizon control in dynamic environments from temporal logic specifications, in: Robotics: Science and Systems, 2013.

80.

[80]

C.I.

Vasile and

Belta, Sampling-based temporal logic path planning, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2013, pp. 4817–4822.

81.

[81]

Wallar,

Plaku and

Sofge, Reactive motion planning for unmanned aerial surveillance of risk-sensitive areas, IEEE Transactions on Automated Science and Engineering 12 (2015), 969–980.

82.

[82]

Wolfe,

Marthi and

Russell, Combined task and motion planning for mobile manipulation, in: International Conference on Automated Planning and Scheduling, 2010, pp. 254–258.

83.

[83]

E.M.

Wolff,

Topcu and

R.M.

Murray, Optimal control with weighted average costs and temporal logic specifications, in: Robotics: Science and Systems, 2012.

84.

[84]

E.M.

Wolff,

Topcu and

R.M.

Murray, Automaton-guided controller synthesis for nonlinear systems with temporal logic, in: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2013, pp. 4332–4339.

85.

[85]

Wongpiromsarn,

Topcu and

R.M.

Murray, Receding horizon control for temporal logic specifications, in: ACM International Conference on Hybrid Systems: Computation and Control, 2010, pp. 101–110.

Motion planning with temporal-logic specifications: Progress and challenges

Abstract

Keywords

Get full access to this article

References