Application of Difference Schemes to Decision the Pursuit Problem
Keywords:
Differential Games, Pursuit Problem, Pursuit Curve, Numerical Methods, Difference Methods, the Euler MethodAbstract
The problem of the pursuit curve construction in the case when the tangent to pursuer’s motion trajectory passes at any time through the point representing the pursued is considered. A new approach to construct the pursuit curves using difference schemes is proposed. The proposed technique eliminates the need to derive the differential equations for the description of the pursuit curves, which is quite difficult task in the general case. In addition, the application of difference methods is justified in a situation where it is complicated to find the analytical solution of an existing differential equation and it is possible to obtain the pursuit curve only numerically. Various modifications of difference schemes respectively equivalent to the Euler, to the Adams – Bashforth and to the Milne methods are constructed. Their software implementation is realized by using the mathematical package Mathcad. We consider the case of a uniform rectilinear motion of the pursued whose differential equation describing the path of the pursuer and its analytical solution are known. We compare the numerical solutions obtained by the different methods with the well-known analytical solution. The error of the obtained numerical solutions is examined. Moreover, an application is considered illustrating the construction of the difference schemes for the case of an arbitrary trajectory of the pursued. Also, we extend the proposed method to the case of cyclic pursuit with several participants in the three-dimensional space. In particular, we construct a difference scheme equivalent to the Euler method for a three-dimensional analogue of the "bugs problem". The results obtained are demonstrated by means of animated examples for either two-dimensional or three-dimensional cases.
Additional content
References
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. Pankov S.Ya., Zaburaev E.Yu., Matveev A.M. Teoriya i metodika upravleniya aviatsiei [Theory and Methods of Aviation Control]. Ulyanovsk: UVAU GA. 2006. 190 p. (In Russ.).
8. Barton J.C., Eliezer C.J. On pursuit curves. The ANZIAM Journal. 2000. vol. 41. no. 3. pp. 358–371.
9. Samoyavcheva M.V., Fedorov L.I. [The pursuit problem]. Vestnik moskovskogo gosudarstvennogo oblastnogo universiteta. Seriya: Fizika-matematika – Bulletin of the Moscow Region State University. Series: Physics-Mathematics. 2011. no. 1. pp. 65–69. (In Russ.).
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. Sigaladze Z.K., Chashina O.I. [The problem of pursuing a hare by a wolf as an exercise of elementary kinematics]. Vestnik NGU. Seriya "Fizika" – Siberian Journal of Physics. 2010. Issue 5. vol. 2. pp. 111–115. (In Russ.).
13. Pogrebskaya T.N., Soltakhanov Sh.Kh. [The control of chasing a target by the pursuit method as a nonholonomic problem in mechanics]. Vestnik Sankt-Peterburgskogo universiteta. Seriya 1. Matematika. Mekha-nika. Astronomiya – Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy. 2007. vol. 1. pp. 117–126. (In Russ.).
14. Kuzmina L.I., Osipov Yu.V. [Calculation of the length of the trajectory for the problem of pursuit]. Vestnik MGSU – Vestnik MGSU. 2013. vol 12. pp. 20–26. (In Russ.).
15. Azamov A.A., Kuchkarov A.Sh., Samatov B.O. [The relation between problems of pursuit, controllability and stability in the large in linear systems with different types of constraints]. Prikladnaya matematika i mehanika Journal of Applied Mathematics and Mechanics. 2007. Issue 71. vol. 2. pp. 259–263. (In Russ.).
16. Ivanov A.A., Shmakov O.A. [Algorithm for defining the inner geometry of a snakelike manipulator in case of leading link movements along the incremental trajectory]. Trudy SPIIRAN – SPIIRAS Proceedings. 2016. vol. 6(49). pp. 190–207. (In Russ.).
17. Lazarev V.S., Agadjanov D.E. [Using graphic-analytical methods for robots group movement trajectories formation in the two-dimensional environment]. Trudy SPIIRAN – SPIIRAS Proceedings. 2016. vol. 2(45). pp. 45–57. (In Russ.).
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. Munts N., Kumkov S. [On the coincidence of the minimax solution and the value function in a time-optimal game with a lifeline]. Trudy Instituta Matematiki i Mekhaniki UrO RAN – Proceedings of Krasovskii Institute of Mathematics and Mechanics. 2018. vol. 24(2). pp. 200–214. (In Russ.).
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. Kazakov Yu.V. Zadacha o presledovanii na vrashchayushchemsya diske [Chase problem on a turntable]. Available at: http://old.exponenta.ru/EDUCAT/systemat/kasakov/pursuit/index.asp (accessed: 16.03.2019). (In Russ.).
27. Bakhvalov N.S., Zhidkov N.P., Kobelkov G.M. Chislennyie metodyi [Numerical Methods]. BINOM. Laboratoriya znaniy. 2008. 636 p. (In Russ.).
28. Ochkov V.F. Mathcad 14 dlya studentov, inzhenerov и construktorov [Mathcad 14 for Students, Engineers and Designers]. BHV-Peterburg. 2007. 368 p. (In Russ.).
29. Ochkov V.F., Bogomolova E.P., Ivanov D.A. Fiziko-matematicheskie etyudy s Mathcad i Internet: Uchebnoe posobie [Physics and Mathematics Studies with Mathcad and Internet: Tutorial]. Lan Publ. 2018. 560 p. (In Russ.).
30. Ponomarev A.A. [Suboptimal control construction for the model predictive controller]. Vestnik Sankt-Peterburgskogo universiteta. Seriya 10. Prikladnaya matematika. Informatika. Processy upravleniya – Vestnik of Saint Peterburg University Applied Mathematics. Computer Science. Control Processes. 2017. vol. 2. pp. 193–208. (In Russ.).
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. Available at: https://arxiv.org/pdf/1605.05750v1.pdf (accessed: 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. Available at: https://arxiv.org/pdf/1811.10827.pdf (accessed: 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. Pankov S.Ya., Zaburaev E.Yu., Matveev A.M. Teoriya i metodika upravleniya aviatsiei [Theory and Methods of Aviation Control]. Ulyanovsk: UVAU GA. 2006. 190 p. (In Russ.).
8. Barton J.C., Eliezer C.J. On pursuit curves. The ANZIAM Journal. 2000. vol. 41. no. 3. pp. 358–371.
9. Samoyavcheva M.V., Fedorov L.I. [The pursuit problem]. Vestnik moskovskogo gosudarstvennogo oblastnogo universiteta. Seriya: Fizika-matematika – Bulletin of the Moscow Region State University. Series: Physics-Mathematics. 2011. no. 1. pp. 65–69. (In Russ.).
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. Sigaladze Z.K., Chashina O.I. [The problem of pursuing a hare by a wolf as an exercise of elementary kinematics]. Vestnik NGU. Seriya "Fizika" – Siberian Journal of Physics. 2010. Issue 5. vol. 2. pp. 111–115. (In Russ.).
13. Pogrebskaya T.N., Soltakhanov Sh.Kh. [The control of chasing a target by the pursuit method as a nonholonomic problem in mechanics]. Vestnik Sankt-Peterburgskogo universiteta. Seriya 1. Matematika. Mekha-nika. Astronomiya – Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy. 2007. vol. 1. pp. 117–126. (In Russ.).
14. Kuzmina L.I., Osipov Yu.V. [Calculation of the length of the trajectory for the problem of pursuit]. Vestnik MGSU – Vestnik MGSU. 2013. vol 12. pp. 20–26. (In Russ.).
15. Azamov A.A., Kuchkarov A.Sh., Samatov B.O. [The relation between problems of pursuit, controllability and stability in the large in linear systems with different types of constraints]. Prikladnaya matematika i mehanika Journal of Applied Mathematics and Mechanics. 2007. Issue 71. vol. 2. pp. 259–263. (In Russ.).
16. Ivanov A.A., Shmakov O.A. [Algorithm for defining the inner geometry of a snakelike manipulator in case of leading link movements along the incremental trajectory]. Trudy SPIIRAN – SPIIRAS Proceedings. 2016. vol. 6(49). pp. 190–207. (In Russ.).
17. Lazarev V.S., Agadjanov D.E. [Using graphic-analytical methods for robots group movement trajectories formation in the two-dimensional environment]. Trudy SPIIRAN – SPIIRAS Proceedings. 2016. vol. 2(45). pp. 45–57. (In Russ.).
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. Munts N., Kumkov S. [On the coincidence of the minimax solution and the value function in a time-optimal game with a lifeline]. Trudy Instituta Matematiki i Mekhaniki UrO RAN – Proceedings of Krasovskii Institute of Mathematics and Mechanics. 2018. vol. 24(2). pp. 200–214. (In Russ.).
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. Kazakov Yu.V. Zadacha o presledovanii na vrashchayushchemsya diske [Chase problem on a turntable]. Available at: http://old.exponenta.ru/EDUCAT/systemat/kasakov/pursuit/index.asp (accessed: 16.03.2019). (In Russ.).
27. Bakhvalov N.S., Zhidkov N.P., Kobelkov G.M. Chislennyie metodyi [Numerical Methods]. BINOM. Laboratoriya znaniy. 2008. 636 p. (In Russ.).
28. Ochkov V.F. Mathcad 14 dlya studentov, inzhenerov и construktorov [Mathcad 14 for Students, Engineers and Designers]. BHV-Peterburg. 2007. 368 p. (In Russ.).
29. Ochkov V.F., Bogomolova E.P., Ivanov D.A. Fiziko-matematicheskie etyudy s Mathcad i Internet: Uchebnoe posobie [Physics and Mathematics Studies with Mathcad and Internet: Tutorial]. Lan Publ. 2018. 560 p. (In Russ.).
30. Ponomarev A.A. [Suboptimal control construction for the model predictive controller]. Vestnik Sankt-Peterburgskogo universiteta. Seriya 10. Prikladnaya matematika. Informatika. Processy upravleniya – Vestnik of Saint Peterburg University Applied Mathematics. Computer Science. Control Processes. 2017. vol. 2. pp. 193–208. (In Russ.).
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. Available at: https://arxiv.org/pdf/1605.05750v1.pdf (accessed: 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. Available at: https://arxiv.org/pdf/1811.10827.pdf (accessed: 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.
Published
2019-12-04
How to Cite
Ochkov, V., & Vasileva, I. (2019). Application of Difference Schemes to Decision the Pursuit Problem. SPIIRAS Proceedings, 18(6), 1407-1433. https://doi.org/10.15622/sp.2019.18.6.1407-1433
Section
Mathematical Modeling and Applied Mathematics
Copyright (c) 2019 Валерий Федорович Очков, Инна Евгеньевна Васильева
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms: Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).