Optimization of A-Star Search Algorithm
DOI:
https://doi.org/10.14529/ctcr200115Keywords:
path planning, A-star algorithm, motion path optimization, mobile robotic, path cost, modelAbstract
Introduction. Autonomous mobile robots must be able to plan global and local motion paths. The A-star path planning algorithm allows us to calculate the shortest path between the starting and end points on a map with known static obstacles. In real conditions, when additional information about the area is entered (difficult or dangerous sections, areas with speed limits) and the cost of overcoming them is taken into account, A-star can lead to a non-optimal, for these conditions, solution of the problem. Aim. Consider options for optimizing the A-star path planning algorithm for use in various conditions with restrictions on the number of turns, linking to critical points on a map of the area, difficult and dangerous areas and аssess the quality of the optimization. Materials and methods. Research is carried out by computer simulation of the A-star algorithm and options for its optimization in the MATLAB environment. The criteria for evaluating the quality of optimization are focused primarily on computational time and the path optimality with respect to the selected parameters. Results. The results of path calculation performed using the A-star algorithm before and after optimization are presented. In both cases, the following are estimated and compared: calcul ation time, number of analyzed polygons, number of turns and path length. Conclusion. In most cases, the optimization of the algorithm increases the path length and calculation time, but not significantly. Moreover, the new path corresponds to the given conditions, is the shortest in these conditions and, therefore, is optimal. The considered optimization options allow you to calculate the path taking into account additional information, estimate the path length and computational time. On the basis of these evaluations, it is possible to choose path planning method suitable for individual scenario.
References
Noskov V.P., Rubtsov V.I., Rubtsov I.V. Matematicheskie modeli dvizheniya i sistemy tekhnicheskogo zreniya mobil'nykh robototekhnicheskikh kompleksov. Uchebnoe posobie [Mathematical Models of Motion and Systems of Technical Vision of Mobile Robotic Complexes]. Moscow, 2015, 94 p.
Koenig S., Likhachev M., Furcy D. Lifelong Planning A*. Artificial Intelligence, 2004, vol. 155, no. 1, pp. 93–146. DOI: 10.1016/j.artint.2003.12.001
Kilibarda G., Kudryavtsev V.B., Ushchyumlich Sh. [The Independent Systems of Automata in the Labyrinth]. Discrete Mathematics, 2003, vol. 15, iss. 2, pp. 3–39. (in Russ.)
Maksimova E.I. [Comparison of the Quality of the Results of the A-Star Algorithm and its Modifications for the Road Network when Choosing a Route, Taking into Account the Direction of Movement at the Intersection]. Siberian Science Bulletin, 2014, no. 4, pp. 117–123. (in Russ.)
Dan B. Marghitu. Mechanisms and Robots Analysis with MATLAB. Springer-Verlag London Limited, 2009, 479 p. DOI 10.1007/978-1-84800-391-0
Zeng W., Church R.L. Finding Shortest Paths on Real Road Networks: the Case for A*. International Journal of Geographical Information Science, 2009, vol. 23, no. 4, pp. 531–543. DOI: 10.1080/13658810801949850
Lei T., Songyi D., Gangxu G., Kunli Zh. A Novel Potential Field Method for Obstacle Avoidance and Path Planning of Mobile Robot. 3rd IEEE International Conference Computer Science and Information Technology, 2010, vol. 9, 6 p. DOI: 10.1109/ICCSIT.2010.5565069
Choset H., Lynch K., Hutchinson S., Kantor G., Burgard W., Kavraki L., Thrun S. Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press, 2005, 603 p.
Liu V. Methods of Path Planning in an Environment with Obstacles (Review). Mathematics and Mathematical Modeling, 2018, no. 1, pp. 15–58. (in Russ.) DOI: 10.24108/mathm.0118.0000098
Lavrenova P.O., Afanasyeva I.M., Magid E.A. [Route Planning for an Unmanned Ground Robot Taking into Account Many Optimization Criteria]. Results of Scientific-Practical Seminar “Unmanned Vehicles with Elements of Artificial Intelligence”, 2015, pp. 10–20. (in Russ.)
Alonzo Kelly. Mobile Robotics. Mathematics, Models and Methods. Cambridge University, 2013, 716 p. DOI: 10.1017/CBO9781139381284
Spyros G. Tzafestas. Introduction to Mobile Robot Control. School of Electrical and Computer Engineering National Technical University of Athens, 2014, 691 p. DOI: 10.1016/B978-0-12-417049-0.00004-3
Wallgrun J.O. Voronoi Graph Matching for Robot Localization and Mapping. Transactions on Computational Science IX. Springer, 2010, pp. 76–108. DOI: 10.1007/978-3-642-16007-3_4
Gonzalez R., Mahulea C. and Kloetzer M. A Matlab-Based Interactive Simulator for Teaching Mobile Robotics. IEEE 2015: Int. Conf. on Autom. Science and Engineering, 2015, pp. 310–315. DOI: 10.1109/CoASE.2015.7294097
Goldshtein A.L. Optimizatsiya v srede MATLAB: ucheb. posobie [Optimization in MATLAB: Textbook]. Perm, Publishing Perm National Research Polytechnic University, 2015, 192 p.
