This paper presents a generalization of the classic A* algorithm to the domain of sampling-based motion planning. The root assumptions of the A* algorithm are examined and reformulated in a manner that enables a direct use of the search strategy as the driving force behind the generation of new samples in a motion graph. Formal analysis is presented to show probabilistic completeness and convergence of the method. This leads to a highly exploitative method which does not sacrifice entropy. Many improvements are presented to this versatile method, most notably, an optimal connection strategy, a bias towards the goal region via an Anytime A* heuristic, and balancing of exploration and exploitation on a simulated annealing schedule. Empirical results are presented to assess the proposed method both qualitatively and quantitatively in the context of high-dimensional planning problems. The potential of the proposed methods is apparent, both in terms of reliability and quality of solutions found.
BelghithKKabanzaFHartmanLNkambouR (2006) Anytime dynamic path-planning with flexible probabilistic roadmaps. In: Proceedings of the 2006 IEEE international conference on robotics and automation (ICRA’06), Orlando, FL, pp. 2372–2377.
2.
BergJVDFergusonDKuffnerJJ (2006) Anytime path planning and replanning in dynamic environments. In: Proceedings of the 2006 IEEE international conference on robotics and automation (ICRA’06), Orlando, FL, pp. 2366–2371.
3.
BranickyMSLaValleSMOlsonKYangL (2001) Quasi-randomized path planning. In: Proceedings of the 2001 IEEE international conference on robotics and automation (ICRA’01), vol. 2, Seoul, Korea, pp. 1481–1487.
4.
BurnsBBrockO (2005) Sampling-based motion planning using predictive models. In: Proceedings of the 2005 IEEE international conference on robotics and automation (ICRA’05), Barcelona, Spain, pp. 3120–3125.
5.
BurnsBBrockO (2007) Single-query motion planning with utility-guided random trees. In: Proceedings of the 2007 IEEE international conference on robotics and automation (ICRA’07), Roma, Italy, pp. 3307–3312.
6.
ChowdhuryRA (2007) Algorithms and Data Structures for Cache-efficient Computation: Theory and Experimental Evaluation. PhD Thesis, University of Texas at Austin.
7.
FergusonDKalraNStentzA (2006) Replanning with RRTs. In: Proceedings of the 2006 IEEE international conference on robotics and automation (ICRA’06), Orlando, FL, pp. 1243–1248.
8.
FuAWCChanPMSCheungYLMoonYS (2000) Dynamic VP-tree indexing for N-nearest neighbor search given pair-wise distances. The Very Large Data Bases Journal (VLDB)9: 154–173.
9.
GeraertsRJOvermarsMH (2002) A Comparative Study of Probabilistic Roadmap Planners. Technical Report, Utrecht University: Information and Computer Science, Utrecht, The Netherlands.
10.
GonzalezJPLikhachevM (2011) Search-based planning with provable suboptimality bounds for continuous state spaces. In: Proceedings of the fourth international symposium on combinatorial search (SoCS’11), Castell de Cardona, Barcelona, Spain. AAAI Press, pp. 60–67.
11.
HartPENilssonNJRaphaelB (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics4(2): 100–107.
12.
HersheyJROlsenPA (2007) Approximating the Kullback–Leibler divergence between Gaussian mixture models. In: IEEE international conference on acoustics, speech and signal processing, volume 4, Honolulu, HI, pp. 317–320.
13.
HsuD (2000) Randomized Single-Query Motion Planning in Expansive Spaces. PhD Thesis. Department of Computer Science, Stanford University, Stanford, CA, pp. 71–90.
14.
HsuDLatombeJCMotwaniR (1999) Path planning in expansive configuration spaces. International Journal of Computational Geometry & Applications09(4/5): 495–512.
15.
IngberL (1996) Adaptive simulated annealing (ASA): lessons learned. Journal of Control and Cybernetics25: 33–54.
16.
JamriskaOSykoraDHornungA (2012) Cache-efficient graph cuts on structured grids. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR’12). IEEE Computer Society Press, pp. 3673–3680.
17.
KaramanSFrazzoliE (2011) Sampling-based algorithms for optimal motion planning. The international journal of robotics research30(7): 846–894.
18.
KaramanSWalterMRPerezAFrazzoliETellerS (2011) Anytime motion planning using the RRT*. In: IEEE international conference on robotics and automation (ICRA), Shanghai, China, pp. 1478–1483.
19.
KasheffZ (2004) Cache-Oblivious Dynamic Search Trees. M.Eng. Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology.
20.
KavrakiLELatombeJC (1998) Probabilistic roadmaps for robot path plannings. In: Motion Planning in Robotics. New York: John Wiley & Sons.
21.
KavrakiLESvestkaPLatombeJCOvermarsMH (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation12(4): 566–580.
22.
KuffnerJJLaValleSM (2000) RRT-Connect: an efficient approach to single-query path planning. In: Proceedings of the 2000 IEEE international conference on robotics and automation (ICRA’00), vol. 2, San Francisco, CA, pp. 995–1001.
23.
KullbackSLeiblerRA (1951) On information and sufficiency. Annals of Mathematical Statistics22(1): 79–86.
24.
LaValleSM (1998) Rapidly-exploring Random Tree: A New Tool for Path Planning. Technical Report 98-11, Department of Computer Science. Iowa State University.
25.
LaValleSMKuffnerJJ (2001) Randomized kinodynamic planning. The International Journal of Robotics Research20: 378–400.
26.
LikhachevMFergusonDGordonGStentzAThrunS (2005) Anytime dynamic A*: An anytime, replanning algorithm. In: Proceedings of the international conference on automated planning and scheduling (ICAPS), Monterey, CA. AAAI Press, pp. 262–271.
27.
LikhachevMGordonGThrunS (2003) ARA*: Anytime A* with provable bounds on sub-optimality. In: Proceedings of the 2003 conference in advances in neural information processing systems (NIPS), Whistler, BC, Canada. Cambridge, MA: MIT Press, pp. 767–774.
28.
PhillipsJMBedrossianNKavrakiLE (2004) Guided expansive spaces trees: a search strategy for motion- and cost-constrained state spaces. In: Proceedings of the 2004 IEEE international conference on robotics and automation (ICRA’04), vol. 4, New Orleans, LA, pp. 3968–3973.
29.
PlakuE (2012) Guiding sampling-based motion planning by forward and backward discrete search. In: SuCYRakhejaSLiuH (eds.), Intelligent Robotics and Applications (Lecture Notes in Computer Science, vol. 7508). Berlin: Springer, pp. 289–298.
30.
RickertMBrockOKnollA (2008) Balancing Exploration and Exploitation in Motion Planning. In: IEEE international conference on robotics and automation (ICRA), Pasadena, CA, pp. 2812–2817.
31.
SanchezGLatombeJC (2001) A single-query bi-directional probabilistic roadmap planner with lazy collision checking. In: JarvisRZelinskyA (eds.), International Symposium on Robotics Research (Springer Tracts in Advanced Robotics, vol. 6). Berlin: Springer, pp. 403–417.
32.
SucanIKavrakiL (2012) A sampling-based tree planner for systems with complex dynamics. IEEE Transactions on Robotics28(1): 116–131.
33.
SucanIAKavrakiLE (2010) On the implementation of single-query sampling-based motion planners. In: Proceedings of the 2010 IEEE international conference on robotics and automation (ICRA’10), Anchorage, AK, pp. 2005–2011.
34.
Vazquez-OteroAFaiglJMunuzuriAP (2012) Path planning based on reaction–diffusion process. In: IEEE/RSJ international conference on intelligent robots and systems, Vilamoura, Algarve, Portugal, pp. 896–901.
35.
ZuckerMRatliffNDraganA. (2013) CHOMP: Covariant Hamiltonian Optimization for Motion Planning. The International Journal of Robotics Research32(11): 1164–1193.
