Оптимизация алгоритма планирования пути A-Star

Дмитрий Сергеевич Пискорский, Фаиль Хамидуллович Абдуллин, Алиса Робертовна Николаева

Аннотация


Введение. Автономные мобильные роботы должны уметь самостоятельно планировать глобальную и локальную траектории своего движения. Алгоритм планирования пути A-star позволяет вычислить кратчайший путь между начальной и конечной точками на карте местности с известными статичными препятствиями. В реальных условиях при введении дополнительной информации о карте местности (труднопроходимые или опасные участки, участки с ограничением скорости) и учете затрат на их преодоление алгоритм может приводить к неоптимальному для данных условий решению задачи. Цель исследования. Рассмотреть варианты оптимизации алгоритма планирования пути A-star для применения в различных условиях, имеющих ограничения по количеству поворотов, привязку к критическим точкам на карте местности, труднопроходимые и опасные участки. Оценить качество проведенной оптимизации. Материалы и методы. Исследования проводятся путем компьютерного моделирования алгоритма A-star и вариантов его оптимизации в среде MATLAB. Критериями оценки качества оптимизации алгоритма являются скорость расчета пути и его оптимальность относительно выбранных параметров. Результаты. Приводятся результаты расчета пути, выполненные с помощью алгоритма A-star до и после оптимизации. В обоих случаях оцениваются и сравниваются: время расчета, количество проанализированных полигонов, число поворотов и длина пути. Заключение. В большинстве случаях в результате оптимизации алгоритма увеличивается длина пути и время расчета, но незначительно. При этом новый путь соответствует заданным условиям, является кратчайшим в этих условиях и, следовательно, оптимальным. Предложенные в статье варианты оптимизации позволяют вычислить путь с учетом дополнительной информации, оценить длину пути и скорость расчета. На основе этих оценок можно выбрать метод планирования пути, подходящий для отдельного сценария.


Ключевые слова


планирование пути; алгоритм A-star; оптимизация траектории движения; мобильный робот; стоимость пути

Полный текст:

PDF (English)

Литература


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.




DOI: http://dx.doi.org/10.14529/ctcr200115

Ссылки

  • На текущий момент ссылки отсутствуют.