Применение разностных схем к решению задачи о погоне
Ключевые слова:
дифференциальные игры, задача о преследовании, метод погони, кривая погони, численные методы, разностные схемы, метод Эйлера, «задача о трех жуках», MathcadАннотация
В работе рассматривается один из аспектов задачи о преследовании: построение траекторий движения преследователя для случая, когда преследование осуществляется по методу погони, то есть касательная, проведенная к траектории движения преследователя в любой момент времени, проходит через положение точки, которая ассоциируется с преследуемым. Предлагается новый подход построения кривых погони путем использования разностных схем. Данная методика позволяет отказаться от необходимости составлять дифференциальные уравнения для описания кривых погони, что бывает достаточно сложно сделать в общем случае. Кроме того, применение разностных схем обосновано в ситуации, когда нахождение аналитического решения уже имеющегося дифференциального уравнения затруднительно, и дает возможность получить кривую погони численным способом. Построены различные модификации разностных схем, являющиеся аналогами схем на основе методов Эйлера, Адамса — Башфорта и Милна. Осуществлена их программная реализация с помощью математического пакета Mathcad. Рассмотрен случай равномерного прямолинейного движения преследуемого, для которого известно дифференциальное уравнение, описывающее траекторию преследователя, и его аналитическое решение. Проведен сравнительный анализ полученных разными методами численных решений и известного аналитического решения. Найдена погрешность полученных численных реализаций. Рассмотрено применение построенных разностных схем для более общего случая произвольной траектории преследуемого. Также описан алгоритм распространения предложенного метода для случая циклического преследования с несколькими участниками в трехмерном пространстве. В частности, построена разностная схема, аналогичная методу Эйлера, для трехмерного аналога «задачи о жуках». Полученные результаты продемонстрированы на анимационных примерах как для двумерного, так и трехмерного случаев.
Дополнительный контент
Литература
1. Petrosyan L.A., Mazalov V.V. Recent Advances in Game Theory and Applications // Springer International Publishing. 2016. 284 p.
2. Mazalov V., Chirkova J.V. Networking Games. Network Forming Games and Games on Networks // Academic Press. 2019. 322 p.
3. Petrosyan L.A. Differential Games of Pursuit // World Scientific. 1993. 332 p.
4. Isaacs R. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization // Courier Corporation. 1999. 416 p.
5. Kumkov S.S., Le Menec S., Patsko V.S. Zero-sum pursuit-evasion differential games with many objects: survey of publications // Dynamic Games and Applications. 2017. vol. 7. no. 4. pp. 609–633.
6. Ramana M.V., Kothari M. Pursuit-evasion games of high speed evade // Journal of Intelligent & Robotic Systems. 2017. vol. 85. no. 2. pp. 293–306.
7. Паньков С.Я., Забураев Е.Ю., Матвеев А.М. Теория и методика управления авиацией // Ульяновск: УВАУ ГА. 2006. 190 с.
8. Barton J.C., Eliezer C.J. On pursuit curves // The ANZIAM Journal. 2000. vol. 41. no. 3. pp. 358–371.
9. Самоявчева М.В., Федоров Л.И. Задача о погоне // Вестник Московского государственного университета. Серия: Физика-Математика. 2011. № 1. C. 65–69.
10. Pták P., Tkadlec J. The Dog-and-Rabbit Chase Revisited // Acta Polytechnica. 1996. vol. 36. pp. 5–10.
11. Mungan C.A. A Classic Chase Problem Solved from a Physics Perspective // European Journal of Physics. 2005. vol. 26. no. 6. pp. 985–990.
12. Сигаладзе З.К., Чащина О.И. Задача преследования зайца волком как упражнение элементарной кинематики // Вестник НГУ. Серия: Физика. 2010. Т. 5. № 2. С. 111–115.
13. Погребская Т.Н., Солтаханов Ш.Х. Управление преследованием цели по методу погони как неголономная задача механики // Вестник Санкт-Петербургского университета. Серия 1. Математика. Механика. Астрономия. 2007. Вып. 1. С. 117–126.
14. Кузьмина Л.И., Осипов Ю.В. Расчет длины траектории для задачи преследования // Вестник МГСУ. 2013. № 12. С. 20–26.
15. Азамов А.А., Кучкаров А.Ш., Саматов Б.О. О связи между задачами преследования, управляемости и устойчивости в целом в линейных системах с разнотипными ограничениями // Прикладная математика и механика. 2007. Т. 71. Вып. 2. С. 259–263.
16. Иванов А.А., Шмаков О.А. Алгоритм определения внутренней геометрии манипулятора змеевидного типа при движении лидирующего звена по наращиваемой траектории // Труды СПИИРАН. 2016. Вып. 6(49). С. 190–207.
17. Лазарев В.С., Агаджанов Д.Э. Использование графоаналитических методов для формирования траектории группы подвижных объектов в двумерной среде // Труды СПИИРАН. 2016. Вып. 2(45). С. 45–57.
18. Shan Y. et al. CF-Pursuit: A Pursuit Method with a Clothoid Fitting and a Fuzzy Controller for Autonomous Vehicles // International Journal of Advanced Robotic Systems. 2015. vol. 12. no. 9. pp. 134.
19. Amer N.H., Zamzuri H., Hudha K., Kadir Z.A. Modelling and Control Strategies in Path Tracking Control for Autonomous Ground Vehicles: A Review of State of the Art and Challenges // Journal of Intelligent & Robotic Systems. 2017. vol. 86. no. 2. pp. 225–254.
20. Spakov O. et al. PursuitAdjuster: an exploration into the design space of smooth pursuit-based widgets // Proceedings of the Ninth Biennial ACM Symposium on Eye Tracking Research & Applications. 2016. pp. 287–290.
21. Khamis M. et al. Eyescout: Active Eye Tracking for Position and Movement Independent Gaze Interaction with Large Public Displays // Proceedings of the 30th Annual ACM Symposium on User Interface Software and Technology (UIST 2017). 2017. pp. 155–166.
22. Bardi M., Falcone M., Soravia P. Numerical Methods for Pursuit-Evasion Games via Viscosity Solutions // Stochastic and Differential Game. 1999. pp. 105–175.
23. Kumkov S., Ménec S., Patsko V. Zero-Sum Pursuit-Evasion Differential Games with Many Objects: Survey of Publications // Dynamic Games and Applications. 2017. vol. 7. no. 4. pp. 609–633.
24. Мунц Н.В., Кумков С.C. О совпадении минимаксного решения и функции цены игры быстродействия с линией жизни // Труды Института математики и механики УрО РАН. 2018. Вып. 24(2). С. 200–214.
25. Alimov K.N., Mamatov M.S. Solving a Pursuit Problem in High-order Controlled Distributed Systems // Siberian Advances in Mathematics. 2014. vol. 24(4). pp. 229–239.
26. Казаков Ю.В. Задача о преследовании на вращающемся диске. URL: http://old.exponenta.ru/EDUCAT/ systemat/kasakov/pursuit/index.asp (дата обращения: 16.03.2019).
27. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы // БИНОМ. Лаборатория знаний. 2008. 636 с.
28. Очков В.Ф. Mathcad 14 для студентов, инженеров и конструкторов // БХВ-Петербург. 2007. 368 с.
29. Очков В.Ф., Богомолова Е.П., Иванов Д.А. Физико-математические этюды с Mathcad и Интернет: учебное пособие // Лань. 2018. 560 с.
30. Пономарев А.А. Аппроксимация обратной связи в регуляторе «Предиктор-корректор» явной функцией // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. 2017. № 2. С. 193–208.
31. Ma Y.J. Reconstruction of a Robin coefficient by a predictor-corrector method // Mathematical Problems in Engineering. 2015. vol. 11. pp 1–7.
32. Binder A.J., Luskin M., Ortner C. Analysis of a predictor-corrector method for computationally efficient modeling of surface effects in 1D. 2016. URL: https://arxiv.org/pdf/1605.05750v1.pdf (дата обращения: 16.03.2019).
33. Onwubuoya C., Akinyemi S.T., Odabi O.I., Odachi G.N. Numerical simulation of a computer virus transmission model using Euler predictor-corrector method // IDOSR Journal of Applied Sciences. 2018. vol. 3(1). pp. 16–28.
34. Abdullahi Y.A., Omar Z., Kuboye J.O. Derivation of block predictor – block corrector method for direct solution of third order ordinary differential equations // Global Journal of Pure and Applied Mathematics. 2016. vol. 12(1). pp. 343–350.
35. Daftardar-Gejji V., Sukale Y., Bhalekar S. A new predictor-corrector method for fractional differential equations // Applied Mathematics and Computation. 2014. vol. 244. pp. 158–182.
36. Ndanusa A., Tafida F.U. Predictor-corrector methods of high order for numerical integration of initial value problems // International Journal of Scientific and Innovative Mathematical Research (IJSIMR). 2016. vol. 4. no. 2. pp. 47–55.
37. Oghonyon J.,Okunuga S.A., Lyase S.A. Milne’s implementation on block predictor-corrector methods // Journal of Applied Sciences. 2016. vol. 16. no. 5. pp. 236–241.
38. Söderlind G. Multistep Methods // Encyclopedia of Applied and Computational Mathematics. 2015. 10 p.
39. Islam M.A. A comparative study on numerical solutions of initial value problems for ordinary differential equations with Euler and Runge Kutta methods // American Journal of Computational Mathematics. 2015. vol. 5. no. 3. pp. 393–404.
40. Fathoni M.F., Wuryandari A.I. Comparison between Euler, Heun, Runge-Kutta and Adams-Bashforth-Moulton integration methods in the particle dynamic simulation // 2015 4th International Conference on Interactive Digital Media (ICIDM). 2015. pp. 1–7.
41. Kuchkarov A.S. Solution of simple pursuit-evasion problem when evader moves on a given curve // International Game Theory Review. 2010. vol. 12. no. 3. pp. 223–238.
42. Galloway K.S., Justh E.W., Krishnaprasad P.S. Cyclic pursuit in three dimensions // 49th IEEE Conference on Decision and Control (CDC). 2010. pp. 7141–7146.
43. Galloway K.S., Justh E.W., Krishnaprasad P.S. Geometry of cyclic pursuit // Proceedings of the 48th IEEE Conference on Decision and Control (CDC). 2009. pp. 7485–7490.
44. Mukherjee D., Kumar S. Finite-time heterogeneous cyclic pursuit with application to target interception. 2018. URL: https://arxiv.org/pdf/1811.10827.pdf (дата обращения: 16.03.2019).
45. Arnold M., Baryshnikov Y., Liberzon D. Cyclic pursuit without coordinates: convergence to regular polygon formations // 53rd IEEE Conference on Decision and Control. 2014. pр. 6191–6196.
46. Marshall J.A., Brouck M.E., Francis B.A. Pursuit formations of unicycles // Automatica. 2006. vol. 42. no. 1. pp. 3–12.
47. Sharma B., Ramakrishnan S., Kumar M. Cyclic pursuit in a multi-agent robotic system with double-integrator dynamics under linear interactions // Robotica. 2013. vol. 31. no. 7. pp. 1037–1050.
48. Arnold M., Zharnitsky V. Cyclic evasion in the three bug problem // The American Mathematical Monthly. 2015. vol. 122. no. 4. pp. 377–380.
49. Chapman S.J., Lottes J., Trefethen L.N. Four bugs on a rectangle // Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2010. vol. 467. no. 2127. pp. 881–896.
50. Ding W., Yan G., Lin Z. Formations on Two-Layer Pursuit Systems // 2009 IEEE International Conference on Robotics and Automation. 2009. pp. 3496–3501.
2. Mazalov V., Chirkova J.V. Networking Games. Network Forming Games and Games on Networks // Academic Press. 2019. 322 p.
3. Petrosyan L.A. Differential Games of Pursuit // World Scientific. 1993. 332 p.
4. Isaacs R. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization // Courier Corporation. 1999. 416 p.
5. Kumkov S.S., Le Menec S., Patsko V.S. Zero-sum pursuit-evasion differential games with many objects: survey of publications // Dynamic Games and Applications. 2017. vol. 7. no. 4. pp. 609–633.
6. Ramana M.V., Kothari M. Pursuit-evasion games of high speed evade // Journal of Intelligent & Robotic Systems. 2017. vol. 85. no. 2. pp. 293–306.
7. Паньков С.Я., Забураев Е.Ю., Матвеев А.М. Теория и методика управления авиацией // Ульяновск: УВАУ ГА. 2006. 190 с.
8. Barton J.C., Eliezer C.J. On pursuit curves // The ANZIAM Journal. 2000. vol. 41. no. 3. pp. 358–371.
9. Самоявчева М.В., Федоров Л.И. Задача о погоне // Вестник Московского государственного университета. Серия: Физика-Математика. 2011. № 1. C. 65–69.
10. Pták P., Tkadlec J. The Dog-and-Rabbit Chase Revisited // Acta Polytechnica. 1996. vol. 36. pp. 5–10.
11. Mungan C.A. A Classic Chase Problem Solved from a Physics Perspective // European Journal of Physics. 2005. vol. 26. no. 6. pp. 985–990.
12. Сигаладзе З.К., Чащина О.И. Задача преследования зайца волком как упражнение элементарной кинематики // Вестник НГУ. Серия: Физика. 2010. Т. 5. № 2. С. 111–115.
13. Погребская Т.Н., Солтаханов Ш.Х. Управление преследованием цели по методу погони как неголономная задача механики // Вестник Санкт-Петербургского университета. Серия 1. Математика. Механика. Астрономия. 2007. Вып. 1. С. 117–126.
14. Кузьмина Л.И., Осипов Ю.В. Расчет длины траектории для задачи преследования // Вестник МГСУ. 2013. № 12. С. 20–26.
15. Азамов А.А., Кучкаров А.Ш., Саматов Б.О. О связи между задачами преследования, управляемости и устойчивости в целом в линейных системах с разнотипными ограничениями // Прикладная математика и механика. 2007. Т. 71. Вып. 2. С. 259–263.
16. Иванов А.А., Шмаков О.А. Алгоритм определения внутренней геометрии манипулятора змеевидного типа при движении лидирующего звена по наращиваемой траектории // Труды СПИИРАН. 2016. Вып. 6(49). С. 190–207.
17. Лазарев В.С., Агаджанов Д.Э. Использование графоаналитических методов для формирования траектории группы подвижных объектов в двумерной среде // Труды СПИИРАН. 2016. Вып. 2(45). С. 45–57.
18. Shan Y. et al. CF-Pursuit: A Pursuit Method with a Clothoid Fitting and a Fuzzy Controller for Autonomous Vehicles // International Journal of Advanced Robotic Systems. 2015. vol. 12. no. 9. pp. 134.
19. Amer N.H., Zamzuri H., Hudha K., Kadir Z.A. Modelling and Control Strategies in Path Tracking Control for Autonomous Ground Vehicles: A Review of State of the Art and Challenges // Journal of Intelligent & Robotic Systems. 2017. vol. 86. no. 2. pp. 225–254.
20. Spakov O. et al. PursuitAdjuster: an exploration into the design space of smooth pursuit-based widgets // Proceedings of the Ninth Biennial ACM Symposium on Eye Tracking Research & Applications. 2016. pp. 287–290.
21. Khamis M. et al. Eyescout: Active Eye Tracking for Position and Movement Independent Gaze Interaction with Large Public Displays // Proceedings of the 30th Annual ACM Symposium on User Interface Software and Technology (UIST 2017). 2017. pp. 155–166.
22. Bardi M., Falcone M., Soravia P. Numerical Methods for Pursuit-Evasion Games via Viscosity Solutions // Stochastic and Differential Game. 1999. pp. 105–175.
23. Kumkov S., Ménec S., Patsko V. Zero-Sum Pursuit-Evasion Differential Games with Many Objects: Survey of Publications // Dynamic Games and Applications. 2017. vol. 7. no. 4. pp. 609–633.
24. Мунц Н.В., Кумков С.C. О совпадении минимаксного решения и функции цены игры быстродействия с линией жизни // Труды Института математики и механики УрО РАН. 2018. Вып. 24(2). С. 200–214.
25. Alimov K.N., Mamatov M.S. Solving a Pursuit Problem in High-order Controlled Distributed Systems // Siberian Advances in Mathematics. 2014. vol. 24(4). pp. 229–239.
26. Казаков Ю.В. Задача о преследовании на вращающемся диске. URL: http://old.exponenta.ru/EDUCAT/ systemat/kasakov/pursuit/index.asp (дата обращения: 16.03.2019).
27. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы // БИНОМ. Лаборатория знаний. 2008. 636 с.
28. Очков В.Ф. Mathcad 14 для студентов, инженеров и конструкторов // БХВ-Петербург. 2007. 368 с.
29. Очков В.Ф., Богомолова Е.П., Иванов Д.А. Физико-математические этюды с Mathcad и Интернет: учебное пособие // Лань. 2018. 560 с.
30. Пономарев А.А. Аппроксимация обратной связи в регуляторе «Предиктор-корректор» явной функцией // Вестник Санкт-Петербургского университета. Серия 10. Прикладная математика. Информатика. Процессы управления. 2017. № 2. С. 193–208.
31. Ma Y.J. Reconstruction of a Robin coefficient by a predictor-corrector method // Mathematical Problems in Engineering. 2015. vol. 11. pp 1–7.
32. Binder A.J., Luskin M., Ortner C. Analysis of a predictor-corrector method for computationally efficient modeling of surface effects in 1D. 2016. URL: https://arxiv.org/pdf/1605.05750v1.pdf (дата обращения: 16.03.2019).
33. Onwubuoya C., Akinyemi S.T., Odabi O.I., Odachi G.N. Numerical simulation of a computer virus transmission model using Euler predictor-corrector method // IDOSR Journal of Applied Sciences. 2018. vol. 3(1). pp. 16–28.
34. Abdullahi Y.A., Omar Z., Kuboye J.O. Derivation of block predictor – block corrector method for direct solution of third order ordinary differential equations // Global Journal of Pure and Applied Mathematics. 2016. vol. 12(1). pp. 343–350.
35. Daftardar-Gejji V., Sukale Y., Bhalekar S. A new predictor-corrector method for fractional differential equations // Applied Mathematics and Computation. 2014. vol. 244. pp. 158–182.
36. Ndanusa A., Tafida F.U. Predictor-corrector methods of high order for numerical integration of initial value problems // International Journal of Scientific and Innovative Mathematical Research (IJSIMR). 2016. vol. 4. no. 2. pp. 47–55.
37. Oghonyon J.,Okunuga S.A., Lyase S.A. Milne’s implementation on block predictor-corrector methods // Journal of Applied Sciences. 2016. vol. 16. no. 5. pp. 236–241.
38. Söderlind G. Multistep Methods // Encyclopedia of Applied and Computational Mathematics. 2015. 10 p.
39. Islam M.A. A comparative study on numerical solutions of initial value problems for ordinary differential equations with Euler and Runge Kutta methods // American Journal of Computational Mathematics. 2015. vol. 5. no. 3. pp. 393–404.
40. Fathoni M.F., Wuryandari A.I. Comparison between Euler, Heun, Runge-Kutta and Adams-Bashforth-Moulton integration methods in the particle dynamic simulation // 2015 4th International Conference on Interactive Digital Media (ICIDM). 2015. pp. 1–7.
41. Kuchkarov A.S. Solution of simple pursuit-evasion problem when evader moves on a given curve // International Game Theory Review. 2010. vol. 12. no. 3. pp. 223–238.
42. Galloway K.S., Justh E.W., Krishnaprasad P.S. Cyclic pursuit in three dimensions // 49th IEEE Conference on Decision and Control (CDC). 2010. pp. 7141–7146.
43. Galloway K.S., Justh E.W., Krishnaprasad P.S. Geometry of cyclic pursuit // Proceedings of the 48th IEEE Conference on Decision and Control (CDC). 2009. pp. 7485–7490.
44. Mukherjee D., Kumar S. Finite-time heterogeneous cyclic pursuit with application to target interception. 2018. URL: https://arxiv.org/pdf/1811.10827.pdf (дата обращения: 16.03.2019).
45. Arnold M., Baryshnikov Y., Liberzon D. Cyclic pursuit without coordinates: convergence to regular polygon formations // 53rd IEEE Conference on Decision and Control. 2014. pр. 6191–6196.
46. Marshall J.A., Brouck M.E., Francis B.A. Pursuit formations of unicycles // Automatica. 2006. vol. 42. no. 1. pp. 3–12.
47. Sharma B., Ramakrishnan S., Kumar M. Cyclic pursuit in a multi-agent robotic system with double-integrator dynamics under linear interactions // Robotica. 2013. vol. 31. no. 7. pp. 1037–1050.
48. Arnold M., Zharnitsky V. Cyclic evasion in the three bug problem // The American Mathematical Monthly. 2015. vol. 122. no. 4. pp. 377–380.
49. Chapman S.J., Lottes J., Trefethen L.N. Four bugs on a rectangle // Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2010. vol. 467. no. 2127. pp. 881–896.
50. Ding W., Yan G., Lin Z. Formations on Two-Layer Pursuit Systems // 2009 IEEE International Conference on Robotics and Automation. 2009. pp. 3496–3501.
Опубликован
2019-12-04
Как цитировать
Очков, В. Ф., & Васильева, И. Е. (2019). Применение разностных схем к решению задачи о погоне. Труды СПИИРАН, 18(6), 1407-1433. https://doi.org/10.15622/sp.2019.18.6.1407-1433
Раздел
Математическое моделирование и прикладная математика
Copyright (c) 2019 Валерий Федорович Очков, Инна Евгеньевна Васильева
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).