О построении маршрутов в динамической среде с использованием решений уравнения эйконала
Ключевые слова:
задача маршрутизации, оптимизация, оптико-геометрический подход, уравнение эйконала, вычислительный алгоритм
Аннотация
Рассматривается задача маршрутизации транспорта, который движется в среде с динамически изменяющимися свойствами. Постановка задачи очень актуальна в современных условиях, когда стоимость доставки имеет устойчивую тенденцию к росту и, зачастую, сопоставима со стоимостью самого товара. Отличительной особенностью исследования является то, что в качестве критерия оптимальности принимается минимум времени доставки, а не пройденное при этом расстояние, как в большинстве работ, посвященных данной тематике. В качестве инструмента исследования применяется развиваемый авторами оптико-геометрический подход, основанный на аналогии между распространением света в оптически неоднородной среде и минимизацией интегрального функционала. При этом для описания волновых фронтов используются точные и приближенные решения уравнений эйконала. Предложены и программно реализованы два оригинальных численных алгоритма построения маршрута. Выполнен вычислительный эксперимент, показавший эффективность предложенного модельно-алгоритмического инструментария.
Литература
1. Gutin G., Punnen A. The traveling salesman problem and its variations. Boston: Springer, 2007.
https://doi.org/10.1007/b101971
2. Toth P., Vigo D. Vehicle routing: problems, methods, and applications. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2014.
https://doi.org/10.1137/1.9781611973594
3. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: УМЦ УПИ, 2016.
4. Ченцов А.Г., Ченцов П.А. К вопросу об оптимизации точки старта в задаче маршрутизации с ограничениями // Известия Института математики и информатики Удмуртского государственного университета. 2020. Т. 55. С. 135-154.
https://doi.org/10.35634/2226-3594-2020-55-09
5. Beresneva E., Avdoshin S. Analysis of mathematical formulations of capacitated vehicle routing problem and methods for their solution // Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. Issue 3. P. 233-250.
https://doi.org/10.15514/ISPRAS-2018-30(3)-17
6. Atyabi A., Powers D.M.W. Review of classical and heuristic-based navigation and path planning approaches // International Journal of Advancements in Computing Technology. 2013. Vol. 5. P. 1-14.
7. Yang L., Qi J., Song D., Xiao J., Han J., Xia Y. Survey of robot 3D path planning algorithms // Journal of Control Science and Engineering. 2016. Vol. 2016. Article ID: 7426913.
https://doi.org/10.1155/2016/7426913
8. Injarapu A.S.H.H.V., Gawre S.K. A survey of autonomous mobile robot path planning approaches // 2017 International Conference on Recent Innovations in Signal processing and Embedded Systems (RISE). 2017. P. 624-628.
https://doi.org/10.1109/RISE.2017.8378228
9. Youakim D., Ridao P. Motion planning survey for autonomous mobile manipulators underwater manipulator case study // Robotics and Autonomous Systems. 2018. Vol. 107. P. 20-44.
https://doi.org/10.1016/j.robot.2018.05.006
10. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische mathematik. 1959. Vol. 1. No. 1. P. 269-271.
https://doi.org/10.1007/BF01386390
11. Floyd R.W. Algorithm 97: Shortest path // Communications of the ACM. 1962. Vol. 5. No. 6. P. 345.
https://doi.org/10.1145/367766.368168
12. Warshall S. A theorem on boolean matrices // Journal of the ACM. 1962. Vol. 9. No. 1. P. 11-12.
https://doi.org/10.1145/321105.321107
13. Matthews J. Basic A* pathfinding made simple // AI Game Programming Wisdom. Boston: Charles River Media, 2002. P. 105-113.
14. Stentz A. Optimal and efficient path planning for partially-known environments // Proceedings of the 1994 IEEE International Conference on Robotics and Automation. 1994. P. 3310-3317.
https://doi.org/10.1109/ROBOT.1994.351061
15. Kunz T., Reiser U., Stilman M., Verl A. Real-time path planning for a robot arm in changing environments // 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2010. P. 5906-5911.
https://doi.org/10.1109/IROS.2010.5653275
16. Веремей Е.И., Сотникова М.В. Алгоритмы оптимизации маршрутов движения с учетом погодных условий // International Journal of Open Information Technologies. 2016. Т. 4. № 3. С. 55-61.
http://injoit.org/index.php/j1/article/view/247/222
17. Shin Y.W., Abebe M., Noh Y., Lee S., Lee I., Kim D., Bae J., Kim K.C. Near-optimal weather routing by using improved A* algorithm // Applied Sciences. 2020. Vol. 10. Issue 17. 6010.
https://doi.org/10.3390/app10176010
18. Pennino S., Gaglione S., Innac A., Piscopo V., Scamardella A. Development of a new ship adaptive weather routing model based on seakeeping analysis and optimization // Journal of Marine Science and Engineering. 2020. Vol. 8. Issue 4. 270.
https://doi.org/10.3390/jmse8040270
19. El Khaili M. Path planning in a dynamic environment // International Journal of Advanced Computer Science and Applications. 2014. Vol. 5. Issue 8. P. 86-92.
https://doi.org/10.14569/IJACSA.2014.050813
20. Сарапулов А.В. Методы решения задачи построения траектории для беспилотного летательного аппарата в динамической среде // Ракетно-космическая техника. 2017. Т. 1. № 2 (10). С. 92-99.
https://www.elibrary.ru/item.asp?id=32544216
21. Vemula A., Muelling K., Oh J. Path planning in dynamic environments with adaptive dimensionality // arXiv: 1605.06853 [cs.RO]. 2016.
https://arxiv.org/abs/1605.06853v1
22. Gochev K., Cohen B., Butzke J., Safonova A., Likhachev M. Path planning with adaptive dimensionality // The Fourth International Symposium on Combinatorial Search (SoCS-2011). 2011.
https://repository.upenn.edu/hms/175
23. Jia D., Hu C., Qin K., Cui X. Planar waypoint generation and path finding in dynamic environment // 2014 International Conference on Identification, Information and Knowledge in the Internet of Things. 2014. P. 206-211.
https://doi.org/10.1109/IIKI.2014.49
24. Zhu W., Jia D., Wan H., Yang T., Hu C., Qin K., Cui X. Waypoint graph based fast pathfinding in dynamic environment // International Journal of Distributed Sensor Networks. 2015. Vol. 11. Issue 8. Article ID: 238727.
https://doi.org/10.1155/2015/238727
25. Ng M.-K., Chong Y.-W., Ko K.-m., Park Y.-H., Leau Y.-B. Adaptive path finding algorithm in dynamic environment for warehouse robot // Neural Computing and Applications. 2020. Vol. 32. P. 13155-13171.
https://doi.org/10.1007/s00521-020-04764-3
26. Masehian E., Katebi Y. Robot motion planning in dynamic environments with moving obstacles and target // World Academy of Science, Engineering and Technology. 2007. Vol. 29. P. 107-112.
27. Du Toit N.E., Burdick J.W. Robot motion planning in dynamic, uncertain environments // IEEE Transactions on Robotics. 2012. Vol. 28. No. 1. P. 101-115.
https://doi.org/10.1109/TRO.2011.2166435
28. Abiyev R.H., Akkaya N., Aytac E. Navigation of mobile robot in dynamic environments // 2012 IEEE International Conference on Computer Science and Automation Engineering (CSAE). 2012. P. 480-484.
https://doi.org/10.1109/CSAE.2012.6272997
29. Гилимьянов Р.Ф., Рапопорт Л.Б. Метод деформации пути в задачах планирования движения роботов при наличии препятствий // Проблемы управления. 2012. Вып. 1. С. 70-76.
http://mi.mathnet.ru/pu698
30. Бычков И.В., Кензин М.Ю., Максимкин Н.Н. Двухуровневый эволюционный подход к маршрутизации группы подводных роботов в условиях периодической ротации состава // Труды СПИИРАН. 2019. Т. 18. № 2. С. 267-301.
https://doi.org/10.15622/sp.18.2.267-301
31. Ulyanov S., Bychkov I., Maksimkin N. Event-based path-planning and path-following in unknown environments for underactuated autonomous underwater vehicles // Applied Sciences. 2020. Vol. 10. Issue 21. 7894.
https://doi.org/10.3390/app10217894
32. Гэн К., Чулин Н.А. Алгоритм наведения движения для квадрокоптера с возможностью облета препятствий и отслеживания запланированного маршрута на основе управления нормальным ускорением // Проблемы современной науки и образования. 2016. № 31 (73). С. 6-28.
33. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. Вып. 7. С. 50-57.
http://mi.mathnet.ru/at2243
34. Фейнман Р., Лейтон Р., Сэндс М. Фейнмановские лекции по физике. Т. 3. Излучение. Волны. Кванты. М.: Эдиториал УРСС, 2004.
35. Cassel K.W. Variational methods with applications in science and engineering. Cambridge: Cambridge University Press, 2013.
36. Боровских А.В. Двумерное уравнение эйконала // Сибирский математический журнал. 2006. Т. 47. № 5. С. 993-1018.
http://mi.mathnet.ru/smj926
37. Borovskikh A.V. Eikonal equation for anisotropic media // Journal of Mathematical Sciences. 2014. Vol. 197. P. 248-289.
https://doi.org/10.1007/s10958-014-1714-5
38. Кабанихин С.И., Криворотько О.И. Численное решение уравнения эйконала // Сибирские электронные математические известия. 2013. Т. 10. С. 28-34.
http://mi.mathnet.ru/semr435
https://doi.org/10.1007/b101971
2. Toth P., Vigo D. Vehicle routing: problems, methods, and applications. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2014.
https://doi.org/10.1137/1.9781611973594
3. Гимади Э.Х., Хачай М.Ю. Экстремальные задачи на множествах перестановок. Екатеринбург: УМЦ УПИ, 2016.
4. Ченцов А.Г., Ченцов П.А. К вопросу об оптимизации точки старта в задаче маршрутизации с ограничениями // Известия Института математики и информатики Удмуртского государственного университета. 2020. Т. 55. С. 135-154.
https://doi.org/10.35634/2226-3594-2020-55-09
5. Beresneva E., Avdoshin S. Analysis of mathematical formulations of capacitated vehicle routing problem and methods for their solution // Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. Issue 3. P. 233-250.
https://doi.org/10.15514/ISPRAS-2018-30(3)-17
6. Atyabi A., Powers D.M.W. Review of classical and heuristic-based navigation and path planning approaches // International Journal of Advancements in Computing Technology. 2013. Vol. 5. P. 1-14.
7. Yang L., Qi J., Song D., Xiao J., Han J., Xia Y. Survey of robot 3D path planning algorithms // Journal of Control Science and Engineering. 2016. Vol. 2016. Article ID: 7426913.
https://doi.org/10.1155/2016/7426913
8. Injarapu A.S.H.H.V., Gawre S.K. A survey of autonomous mobile robot path planning approaches // 2017 International Conference on Recent Innovations in Signal processing and Embedded Systems (RISE). 2017. P. 624-628.
https://doi.org/10.1109/RISE.2017.8378228
9. Youakim D., Ridao P. Motion planning survey for autonomous mobile manipulators underwater manipulator case study // Robotics and Autonomous Systems. 2018. Vol. 107. P. 20-44.
https://doi.org/10.1016/j.robot.2018.05.006
10. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische mathematik. 1959. Vol. 1. No. 1. P. 269-271.
https://doi.org/10.1007/BF01386390
11. Floyd R.W. Algorithm 97: Shortest path // Communications of the ACM. 1962. Vol. 5. No. 6. P. 345.
https://doi.org/10.1145/367766.368168
12. Warshall S. A theorem on boolean matrices // Journal of the ACM. 1962. Vol. 9. No. 1. P. 11-12.
https://doi.org/10.1145/321105.321107
13. Matthews J. Basic A* pathfinding made simple // AI Game Programming Wisdom. Boston: Charles River Media, 2002. P. 105-113.
14. Stentz A. Optimal and efficient path planning for partially-known environments // Proceedings of the 1994 IEEE International Conference on Robotics and Automation. 1994. P. 3310-3317.
https://doi.org/10.1109/ROBOT.1994.351061
15. Kunz T., Reiser U., Stilman M., Verl A. Real-time path planning for a robot arm in changing environments // 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2010. P. 5906-5911.
https://doi.org/10.1109/IROS.2010.5653275
16. Веремей Е.И., Сотникова М.В. Алгоритмы оптимизации маршрутов движения с учетом погодных условий // International Journal of Open Information Technologies. 2016. Т. 4. № 3. С. 55-61.
http://injoit.org/index.php/j1/article/view/247/222
17. Shin Y.W., Abebe M., Noh Y., Lee S., Lee I., Kim D., Bae J., Kim K.C. Near-optimal weather routing by using improved A* algorithm // Applied Sciences. 2020. Vol. 10. Issue 17. 6010.
https://doi.org/10.3390/app10176010
18. Pennino S., Gaglione S., Innac A., Piscopo V., Scamardella A. Development of a new ship adaptive weather routing model based on seakeeping analysis and optimization // Journal of Marine Science and Engineering. 2020. Vol. 8. Issue 4. 270.
https://doi.org/10.3390/jmse8040270
19. El Khaili M. Path planning in a dynamic environment // International Journal of Advanced Computer Science and Applications. 2014. Vol. 5. Issue 8. P. 86-92.
https://doi.org/10.14569/IJACSA.2014.050813
20. Сарапулов А.В. Методы решения задачи построения траектории для беспилотного летательного аппарата в динамической среде // Ракетно-космическая техника. 2017. Т. 1. № 2 (10). С. 92-99.
https://www.elibrary.ru/item.asp?id=32544216
21. Vemula A., Muelling K., Oh J. Path planning in dynamic environments with adaptive dimensionality // arXiv: 1605.06853 [cs.RO]. 2016.
https://arxiv.org/abs/1605.06853v1
22. Gochev K., Cohen B., Butzke J., Safonova A., Likhachev M. Path planning with adaptive dimensionality // The Fourth International Symposium on Combinatorial Search (SoCS-2011). 2011.
https://repository.upenn.edu/hms/175
23. Jia D., Hu C., Qin K., Cui X. Planar waypoint generation and path finding in dynamic environment // 2014 International Conference on Identification, Information and Knowledge in the Internet of Things. 2014. P. 206-211.
https://doi.org/10.1109/IIKI.2014.49
24. Zhu W., Jia D., Wan H., Yang T., Hu C., Qin K., Cui X. Waypoint graph based fast pathfinding in dynamic environment // International Journal of Distributed Sensor Networks. 2015. Vol. 11. Issue 8. Article ID: 238727.
https://doi.org/10.1155/2015/238727
25. Ng M.-K., Chong Y.-W., Ko K.-m., Park Y.-H., Leau Y.-B. Adaptive path finding algorithm in dynamic environment for warehouse robot // Neural Computing and Applications. 2020. Vol. 32. P. 13155-13171.
https://doi.org/10.1007/s00521-020-04764-3
26. Masehian E., Katebi Y. Robot motion planning in dynamic environments with moving obstacles and target // World Academy of Science, Engineering and Technology. 2007. Vol. 29. P. 107-112.
27. Du Toit N.E., Burdick J.W. Robot motion planning in dynamic, uncertain environments // IEEE Transactions on Robotics. 2012. Vol. 28. No. 1. P. 101-115.
https://doi.org/10.1109/TRO.2011.2166435
28. Abiyev R.H., Akkaya N., Aytac E. Navigation of mobile robot in dynamic environments // 2012 IEEE International Conference on Computer Science and Automation Engineering (CSAE). 2012. P. 480-484.
https://doi.org/10.1109/CSAE.2012.6272997
29. Гилимьянов Р.Ф., Рапопорт Л.Б. Метод деформации пути в задачах планирования движения роботов при наличии препятствий // Проблемы управления. 2012. Вып. 1. С. 70-76.
http://mi.mathnet.ru/pu698
30. Бычков И.В., Кензин М.Ю., Максимкин Н.Н. Двухуровневый эволюционный подход к маршрутизации группы подводных роботов в условиях периодической ротации состава // Труды СПИИРАН. 2019. Т. 18. № 2. С. 267-301.
https://doi.org/10.15622/sp.18.2.267-301
31. Ulyanov S., Bychkov I., Maksimkin N. Event-based path-planning and path-following in unknown environments for underactuated autonomous underwater vehicles // Applied Sciences. 2020. Vol. 10. Issue 21. 7894.
https://doi.org/10.3390/app10217894
32. Гэн К., Чулин Н.А. Алгоритм наведения движения для квадрокоптера с возможностью облета препятствий и отслеживания запланированного маршрута на основе управления нормальным ускорением // Проблемы современной науки и образования. 2016. № 31 (73). С. 6-28.
33. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. Вып. 7. С. 50-57.
http://mi.mathnet.ru/at2243
34. Фейнман Р., Лейтон Р., Сэндс М. Фейнмановские лекции по физике. Т. 3. Излучение. Волны. Кванты. М.: Эдиториал УРСС, 2004.
35. Cassel K.W. Variational methods with applications in science and engineering. Cambridge: Cambridge University Press, 2013.
36. Боровских А.В. Двумерное уравнение эйконала // Сибирский математический журнал. 2006. Т. 47. № 5. С. 993-1018.
http://mi.mathnet.ru/smj926
37. Borovskikh A.V. Eikonal equation for anisotropic media // Journal of Mathematical Sciences. 2014. Vol. 197. P. 248-289.
https://doi.org/10.1007/s10958-014-1714-5
38. Кабанихин С.И., Криворотько О.И. Численное решение уравнения эйконала // Сибирские электронные математические известия. 2013. Т. 10. С. 28-34.
http://mi.mathnet.ru/semr435
Поступила в редакцию
2021-10-25
Опубликована 2021-11-20
Опубликована 2021-11-20