FDA* : a focused single‐query grid based path planning algorithm

• Autorzy: Boumediene Mouad , Lamine Mehennaoui Lamine , Lachouri Abderazzak

Identyfikatory

DOI

10.14313/JAMRIS/3‐2021/17

• Języki publikacji: EN

Abstrakty

EN

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 hyperrectangle, 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 the classic A* and thus other graph‐based planning algorithms, and at the same time, the resulting path cost is less than that of regular RRT based algorithms.

Słowa kluczowe

EN

motion planning; grid‐based; path planning; mobile robots

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2021
• Tom: Vol. 15, No. 3
• Strony: 37--43
• Opis fizyczny: Bibliogr. 21 poz., rys.

Twórcy

autor

Boumediene Mouad

• Laboratoire Automatique Skikda, Road Elhadaiek, BP.26, Skikda, Algeria, www: http://vrpg.univ‑skikda.dz/las/

autor

Lamine Mehennaoui Lamine

• Laboratoire Automatique Skikda, Road Elhadaiek, BP.26, Skikda, Algeria, www: http://vrpg.univ‑skikda.dz/las/

autor

Lachouri Abderazzak

• Laboratoire Automatique Skikda, Road Elhadaiek, BP.26, Skikda, Algeria, www: http://vrpg.univ‑skikda.dz/las/

Bibliografia

• [1] 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.
• [2] 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.
• [3] E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik, vol. 1, no. 1, 1959, 269–271,10.1007/BF01386390.
• [4] 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.
• [5] 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.
• [6] 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.
• [7] 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.
• [8] S. Karaman and E. Frazzoli, “Sampling‑based algorithms for optimal motion planing”, The International Journal of Robotics Research, vol. 30, no. 7, 2011, 846–894, 10.1177/0278364911406761.
• [9] 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.
• [10] 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.
• [11] 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.
• [12] S. M. Lavalle. “Rapidly‑Exploring Random Trees: A New Tool for Path Planning”. Technical report, 1998.
• [13] S. M. LaValle, Planning Algorithms, Cambridge University Press: Cambridge, 2006, 10.1017/CBO9780511546877.
• [14] 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.
• [15] 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.
• [16] 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.
• [17] A. Stentz. “The D* Algorithm for Real‑Time Planning of Optimal Traverses”. Technical report,Carnegie Mellon University, 1994.
• [18] 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.
• [19] D. Thalmann and S. Raupp Musse, Crowd Simulation, Springer London: London, 2007, 10.1007/978‑1‑84628‑825‑8.
• [20] 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.
• [21] 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.