Sage Journals: Discover world-class research

Abstract

Rapidly-exploring Random Trees (RRTs) are data structures and search algorithms designed to be used in continuous path planning problems. They are one of the most successful state-of-the-art techniques in motion planning, as they offer a great degree of flexibility and reliability. However, their use in other fields in which search is a commonly used approach has not been thoroughly analyzed. In this work we propose the use of RRTs as a search algorithm for automated planning. We analyze the advantages and disadvantages that this approach has over previously used search algorithms and the challenges of adapting RRTs for implicit and discrete search spaces.

Keywords

Automated planning heuristic search random sampling

Get full access to this article

View all access options for this article.

References

[1]

Alcázar,

Borrajo,

Fernández and

Fuentetaja, Revisiting regression in planning, in: International Joint Conference on Artificial Intelligence, 2013, pp. 2254–2260.

[2]

Alcázar,

M.M.

Veloso and

Borrajo, Adapting a rapidly-exploring random tree for automated planning, in: Symposium on Combinatorial Search, 2011, pp. 2–9.

[3]

Aurenhammer, Voronoi diagrams – A survey of a fundamental geometric data structure, ACM Computing Surveys 23(3) (1991), 345–405.

[4]

Bibai,

Savéant,

Schoenauer and

Vidal, An evolutionary metaheuristic based on state decomposition for domain-independent satisficing planning, in: International Conference on Automated Planning and Scheduling, AAAI, 2010, pp. 18–25.

[5]

Bonet and

Geffner, Planning as heuristic search, Artificial Intelligence 129(1,2) (2001), 5–33.

[6]

Brélaz, New methods to color the vertices of a graph, Communications of the ACM 22(4) (1979), 251–256.

[7]

Bruce and

Veloso, Real-time randomized path planning for robot navigation, in: International Conference on Intelligent Robots and Systems, October 2002, 2002, pp. 288–295.

[8]

Bruce and

M.M.

Veloso, Real-time randomized motion planning for multiple domains, in: RoboCup,

Lakemeyer,

Sklar,

D.G.

Sorrenti and

Takahashi, eds, Lecture Notes in Computer Science, Vol. 4434, 2006, pp. 532–539.

[9]

Burfoot,

Pineau and

Dudek, RRT-plan: A randomized algorithm for STRIPS planning, in: International Conference on Automated Planning and Scheduling, 2006, pp. 362–365.

10.

[10]

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

11.

[11]

Choset,

K.M.

Lynch,

Hutchinson,

G.A.

Kantor,

Burgard,

L.E.

Kavraki and

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

12.

[12]

Christie,

Machap,

J.-M.

Normand,

Olivier and

Pickering, Virtual camera planning: A survey, in: Smart Graphics,

Butz,

Fisher,

Krüger and

Olivier, eds, Lecture Notes in Computer Science, Vol. 3638, Springer, Heidelberg, 2005, pp. 40–52.

13.

[13]

Cortés,

Siméon,

V.R.

De Angulo,

Guieysse,

Remaud-Siméon and

Tran, A path planning approach for computing large-amplitude motions of flexible molecules, Bioinformatics 21(Suppl. 1) (2005), i116–i125.

14.

[14]

J.C.

Culberson and

Schaeffer, Pattern databases, Comput. Intell. 14(3) (1998), 318–334.

15.

[15]

Da Xu,

Wang,

Bi and

Yu, AutoAssem: An automated assembly planning system for complex products, IEEE Transactions on Industrial Informatics 8(3) (2012), 669–678.

16.

[16]

Fuentetaja,

Borrajo and

Linares López, A unified view of cost-based heuristics, in: Proceedings of the 2nd Workshop on Heuristics for Domain-Independent Planning. Conference on Automated Planning and Scheduling (ICAPS’09), Thessaloniki, Greece, 2009.

17.

[17]

Gerevini and

Serina, LPG: A planner based on local search for planning graphs with action costs, in: Conference on Artificial Intelligence Planning Systems, AAAI, 2002, pp. 13–22.

18.

[18]

R.M.

Haralick and

G.L.

Elliott, Increasing tree search efficiency for constraint satisfaction problems, Artificial Intelligence 14(3) (1980), 263–313.

19.

[19]

Haslum, Additive and reversed relaxed reachability heuristics revisited, in: Proceedings of the 6th International Planning Competition, 2008.

20.

[20]

Haslum, h^m(P) = h¹(P^m): Alternative characterisations of the generalisation from h^max to h^m, in: International Conference on Automated Planning and Scheduling, 2009, pp. 354–357.

21.

[21]

Helmert, The Fast Downward planning system, J. Artif. Intell. Res. (JAIR) 26 (2006), 191–246.

22.

[22]

Helmert, Concise finite-domain representations for PDDL planning tasks, Artificial Intelligence 173(5,6) (2009), 503–535.

23.

[23]

Hoffmann and

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

24.

[24]

Hoffmann,

Porteous and

Sebastia, Ordered landmarks in planning, J. Artif. Intell. Res. (JAIR) 22 (2004), 215–278.

25.

[25]

L.E.

Kavraki,

Svestka,

J.-C.

Latombe and

M.H.

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

26.

[26]

Koehler and

Hoffmann, On reasonable and forced goal orderings and their use in an agenda-driven planning algorithm, J. Artif. Intell. Res. (JAIR) 12 (2000), 338–386.

27.

[27]

J.J.

Kuffner and

S.M.

LaValle, RRT-connect: An efficient approach to single-query path planning, in: ICRA, IEEE, 2000, pp. 995–1001.

28.

[28]

S.M.

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

29.

[29]

S.M.

LaValle and

J.J.

Kuffner, Randomized kinodynamic planning, in: International Conference on Robotics and Automation, 1999, pp. 473–479.

30.

[30]

Linares López and

Borrajo, Adding diversity to classical heuristic planning, in: Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS’10), Atlanta, USA, 2010, pp. 73–80.

31.

[31]

Lu,

Xu,

Huang and

Chen, The Roamer planner: Random-walk assisted best-first search, in: The 2011 International Planning Competition, 2011.

32.

[32]

Massey, Directions in planning: Understanding the flow of time in planning, PhD thesis, Computational Intelligence Research Laboratory, University of Oregon, 1999.

33.

[33]

Morgan and

M.S.

Branicky, Sampling-based planning for discrete spaces, in: International Conference on Intelligent Robots and Systems, 2004, pp. 1938–1945.

34.

[34]

Nakhost and

Müller, Monte-Carlo exploration for deterministic planning, in: International Joint Conference on Artificial Intelligence, 2009, pp. 1766–1771.

35.

[35]

Richter,

J.T.

Thayer and

Ruml, The joy of forgetting: Faster anytime search via restarting, in: International Conference on Automated Planning and Scheduling,

R.I.

Brafman,

Geffner,

Hoffmann and

H.A.

Kautz, eds, 2010, pp. 137–144.

36.

[36]

Richter and

Westphal, The LAMA planner: Guiding cost-based anytime planning with landmarks, J. Artif. Intell. Res. (JAIR) 39 (2010), 127–177.

37.

[37]

Rintanen, Planning as satisfiability: Heuristics, Artificial Intelligence 193 (2012), 45–86.

38.

[38]

Röger and

Helmert, The more, the merrier: Combining heuristic estimators for satisficing planning, in: International Conference on Automated Planning and Scheduling, 2010, pp. 246–249.

39.

[39]

M.M.

Veloso, Learning by analogical reasoning in general problem solving, PhD thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, 1992.

40.

[40]

Vidal, A lookahead strategy for heuristic search planning, in: International Conference on Automated Planning and Scheduling,

Zilberstein,

Koehler and

Koenig, eds, 2004, pp. 150–160.

41.

[41]

Xie,

Müller and

Holte, Adding local exploration to greedy best-first search in satisficing planning, in: AAAI Conference on Artificial Intelligence, 2014, pp. 2388–2394.

42.

[42]

Xie,

Nakhost and

Müller, Planning via random walk-driven local search, in: International Conference on Automated Planning and Scheduling, 2012, pp. 181–189.

43.

[43]

H.L.S.

Younes and

R.G.

Simmons, VHPOP: Versatile heuristic partial order planner, J. Artif. Intell. Res. (JAIR) 20 (2003), 405–430.

44.

[44]

Zilles and

R.C.

Holte, The computational complexity of avoiding spurious states in state space abstraction, Artificial Intelligence 174(14) (2010), 1072–1092.