Any-angle Global Path Planning for Skid-Steered Mobile Robots on Heterogeneous Terrain

• Autorzy: Jaroszek P.

Identyfikatory

DOI

10.14313/JAMRIS_2-2016/15

• Języki publikacji: EN

Abstrakty

EN

The paper is concerned with selection of the algorithm of path planning for a skid-steered mobile robot operating on heterogeneous terrain. Methods of path searching were reviewed and their applicability to particular kinematic structure of a robot was assessed. The Theta* graph search algorithm was selected, because of its property of returning any-angle paths. Because in this method variable terrain type is not considered, necessary changes in algorithm structure were proposed to check homogeneity of the terrain. In order to enable choice of arbitrary optimization criterion, the model of cost dependent on terrain properties was introduced, which includes both longitudinal motion and turning. Operation of the modified algorithm with the introduced cost model was verified by means of simulation against A* reference algorithm often used in path planning tasks.

Słowa kluczowe

EN

spath planning; skid-steered mobile robot; Theta*; any-angle path planning; A*

• Wydawca: Łukasiewicz Industrial Research Institute for Automation and Measurements PIAP
• Czasopismo: Journal of Automation Mobile Robotics and Intelligent Systems
• Rocznik: 2016
• Tom: Vol. 10, No. 2
• Strony: 50--56
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Jaroszek P.

• Industrial Research Institute for Automation and Measurements (PIAP), Warsaw, 02-486, Poland

Bibliografia

• [1] Hwang, Y. K., Ahuja, N., “A potential field approach to path planning”, IEEE Transactions on Robotics and Automation, vol. 8, no. 1, 1992, 23–32. DOI:10.1109/70.127236.
• [2] Chung, W. K., Xu, Y., “A generalized 3-D path planning method for robots using Genetic Algorithm with an adaptive evolution process”. In: 2010 8th World Congress on Intelligent Control and Automation (WCICA), July 2010, 1354–1360.DOI:10.1109/WCICA.2010.5554851.
• [3] Cormen, T. H., Stein, C., Rivest, R. L., Leiserson, C. E., “Introduction to Algorithms”, 2nd ed. McGraw-Hill Higher Education, 2001.
• [4] Dijkstra, E. W., “A note on two problems in connexion with graphs”, Numerische Mathematik, vol. 1, no. 1, 1959, 269–271. DOI:10.1007/BF01386390.
• [5] Hart, P. E., Nilsson, N. J., Raphael, B., “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. DOI:10.1109/TSSC.1968.300136.
• [6] Nash, A., “Any-angle path planning”. University of Southern California, 2012.
• [7] Nash, A., Daniel, K., Koenig, S., Feiner, A., “Theta*: Any-angle Path Planning on Grids”. In: Proceedings of the 22Nd National Conference on Artificial Intelligence - Volume 2, Vancouver, British Columbia, Canada, 2007, 1177–1183.
• [8] Yap, P. K. Y., Burch, N., Holte, R. C., Schaeffer, J., “Abstract: Block A* and Any-Angle Path-Planning”. In: Fourth Annual Symposium on Combinatorial Search, July 5, 2011.
• [9] Ferguson, D., Stentz, A., “Field D*: An Interpolation-Based Path Planner and Replanner”.In: Robotics Research, 2007, 239–253.DOI:10.1007/978-3-540-48113-3_22.
• [10] Uras, T., Koenig, S., “An Empirical Comparison of Any-Angle Path-Planning Algorithms”. In: Eighth Annual Symposium on Combinatorial Search, May 14, 2015.
• [11] Choi, S., Yu, W., “Any-angle path planning on non-uniform costmaps”. In: 2011 IEEE International Conference on Robotics and Automation (ICRA), May 2011, 5615–5621. DOI:10.1109/ICRA.2011.5979769.
• [12] Bresenham, J. E., “Algorithm for computer control of a digital plotter”, IBM Systems Journal, vol. 4, no. 1, 1965, 25–30. DOI:10.1147/sj.41.0025.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.