FDA*: A Focused Single-Query Grid Based Path Planning Algorithm
Authors
Abstract
Square grid representations of the state‐space are a commonly used tool in path planning. With applications in a variety of disciplines, including robotics, computational biology, game development, and beyond. However, in large scale and/or high dimensional environments the creation and manipulation of such structures become too expensive, especially in applications when an accurate representation is needed.
In this paper, we present a method for reducing the cost of single‐query grid‐based path planning, by focusing the search to a smaller subset, that contains
the optimal solution. This subset is represented by a hyper‐rectangle, the location, and dimensions of which are calculated departing from an initial feasible path found by a fast search using the RRT* algorithm. We also present an implementation of this focused discretization method called FDA*, a resolution optimal algorithm, where the A* algorithm is employed in searching the resulting graph for an optimal solution. We also demonstrate through simulation results, that the FDA* algorithm uses less memory and has a shorter run‐time compared to classic A* and thus other graph based planning algorithms, and in the same time, the resulting path cost is less than that of regular RRT based algorithms.
References
I. Al‑Bluwi, T. Siméon, and J. Cortés, “Motion planning algorithms for molecular simulations: A survey”, Computer Science Review, vol. 6, no. 4, 2012, 125–143, 10.1016/j.cosrev.2012.07.002.
V. Bulitko, Y. Björnsson, N. R. Sturtevant, and R. Lawrence. “Real‑Time Heuristic Search for Pathfinding in Video Games”. In: P. A. González‑ Calero and M. A. Gómez‑Martı́n, eds., Artificial Intelligence for Computer Games, 1–30. 2011. 10.1007/978‑1‑4419‑8188‑2_1.
E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik, vol. 1, no. 1, 1959, 269–271, 10.1007/BF01386390.
D. Ferguson and A. Stentz, “Field D*: An Interpolation‑Based Path Planner and Replanner”. In: S. Thrun, R. Brooks, and H. Durrant‑Whyte, eds., Robotics Research, Berlin, Heidelberg, 2007, 239–253, 10.1007/978‑3‑540‑48113‑3_22.
J. D. Gammell, S. S. Srinivasa, and T. D. Barfoot, “Informed RRT*: Optimal sampling‑based path planning focused via direct sampling of an admissible ellipsoidal heuristic”. In: 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014, 2997–3004, 10.1109/IROS.2014.6942976.
P. E. Hart, N. J. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, 1968, 100–107, 10.1109/TSSC.1968.300136.
B. Ichter, J. Harrison, and M. Pavone, “Learning Sampling Distributions for Robot Motion Planning”. In: 2018 IEEE International Conference on Robotics and Automation (ICRA), 2018, 7087–7094, 10.1109/ICRA.2018.8460730.
S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning”, The International Journal of Robotics Research, vol. 30, no. 7, 2011, 846–894, 10.1177/0278364911406761.
O. Khatib. “Real‑Time Obstacle Avoidance for Manipulators and Mobile Robots”. In: I. J. Cox and G. T. Wilfong, eds., Autonomous Robot Vehicles, 396–404. 1990. 10.1007/978‑1‑4613‑8997‑2_29.
S. Koenig and M. Likhachev, “Fast replanning for navigation in unknown terrain”, IEEE Transactions on Robotics, vol. 21, no. 3, 2005, 354–363, 10.1109/TRO.2004.838026.
S. Koenig, M. Likhachev, and D. Furcy, “Lifelong Planning A∗”, Artificial Intelligence, vol. 155, no. 1, 2004, 93–146, 10.1016/j.artint.2003.12.001.
S. M. Lavalle. “Rapidly‑Exploring Random Trees: A New Tool for Path Planning”. Technical report, 1998.
S. M. LaValle, Planning Algorithms, Cambridge University Press: Cambridge, 2006, 10.1017/CBO9780511546877.
M. C. Lin, A. Sud, J. Van den Berg, R. Gayle, S. Curtis, H. Yeh, S. Guy, E. Andersen, S. Patil, J. Sewall, and D. Manocha, “Real‑Time Path Planning and Navigation for Multi‑agent and Crowd Simulations”. In: A. Egges, A. Kamphuis, and M. Overmars, eds., Motion in Games, Berlin, Heidelberg, 2008, 23–32, 10.1007/978‑3‑540‑89220‑5_3.
M. Otte and N. Correll, “C‑FOREST: Parallel Shortest Path Planning With Superlinear Speedup”, IEEE Transactions on Robotics, vol. 29, no. 3, 2013, 798–806, 10.1109/TRO.2013.2240176.
A. H. Qureshi, A. Simeonov, M. J. Bency, and M. C. Yip, “Motion Planning Networks”. In: 2019 International Conference on Robotics and Automation (ICRA), Montreal, QC, Canada, 2019, 2118–2124, 10.1109/ICRA.2019.8793889.
A. Stentz. “The D* Algorithm for Real‑Time Planning of Optimal Traverses”. Technical report, Carnegie Mellon University, 1994.
X. Tang, B. Kirkpatrick, S. Thomas, G. Song, and N. M. Amato, “Using Motion Planning to Study RNA Folding Kinetics”, Journal of Computational Biology, vol. 12, no. 6, 2005, 862–881, 10.1089/cmb.2005.12.862.
D. Thalmann and S. Raupp Musse, Crowd Simulation, Springer London: London, 2007, 10.1007/978‑1‑84628‑825‑8.
C. Zhang, J. Huh, and D. D. Lee, “Learning Implicit Sampling Distributions for Motion Planning”. In: 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2018, 3654–3661, 10.1109/IROS.2018.8594028.
T. Zhang, J. Wang, and M. Q.‑H. Meng, “Generative Adversarial Network Based Heuristics for Sampling‑Based Path Planning”, IEEE/CAA Journal of Automatica Sinica, vol. 9, no. 1, 2022, 64–74, 10.1109/JAS.2021.1004275.
Downloads
How to Cite
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
The authors wishing to publish in JAMRIS journal must sign the license to publish upon paper acceptance. The license governs in detail the commercial and non-commercial use of papers published by our journal and determines user and author rights.
