Оптимизация движения мобильного робота на плоскости в поле конечного числа источников-репеллеров
Ключевые слова:
планирование пути, конфликтная среда, характерная вероятностная функция, оптимизация движенияАннотация
Рассматривается задача планирования движения мобильного робота в конфликтной среде, которая характеризуется наличием областей, препятствующих выполнению роботом поставленных задач. Дается обзор основных результатов планирования пути в конфликтных средах. Отдельное внимание уделяется подходам, основывающимся на функциях рисков и вероятностных методах. Рассматриваются конфликтные области, которые формируются точечными источниками, генерирующими в общем случае несимметричные поля непрерывного типа. Предлагается вероятностное описание таких полей, примерами которых являются вероятность обнаружения или поражения мобильного робота. В качестве характеристики поля вводится понятие характерной вероятности функции источника, которая позволяет оптимизировать движение робота в конфликтной среде. Показана связь характерной вероятности функции источника и функции риска, которая может быть использована для постановки и решения упрощенных оптимизационных задач. Разрабатывается алгоритм планирования пути мобильного робота, обеспечивающий заданную вероятность прохождения конфликтной среды. Получена верхняя оценка вероятности прохождения заданной среды при фиксированных граничных условиях. Предложена процедура оптимизации пути робота в конфликтной среде, которая характеризуется более высокой вычислительной эффективностью, достигаемой за счет ухода от поиска точного оптимального решения к субоптимальному. Предложенные алгоритмы реализованы в виде программного обеспечения симулятора группы наземных роботов и исследуются методами численного моделирования.
Литература
1. LaValle S.M. Planning Algorithms. Cambridge University Press. 2006. 842 p.
2. Yang L. et al. Survey of Robot 3D Path Planning Algorithms. Journal of Con-trol Science and Engineering. 2016. vol. 2016. pp. 22.
3. Qu Y., Zhang Y., Zhang Y. A Global Path Planning Algorithm for Fixed-wing UAVs. Journal of Intelligent & Robotic Systems. 2018. vol. 91(3-4). pp. 691–707.
4. Pshikhopov V.H., Medvedev M.Yu. [Group control of autonomous robots motion in uncertain environment via unstable modes]. Trudy SPIIRAN – SPIIRAS Proceedings. 2018. vol. 5(60). pp. 39–63. (In Russ.).
5. Pshikhopov V., Medvedev M. Motion Planning and Control Using Bionic Ap-proaches Based on Unstable Modes. Path Planning for Vehicles Operating in Uncertain 2D Environments. 2017. pp. 239–280.
6. Galyaev A.A. Evasion on plane from a single mobile observer in the conflict environment. Avtomatika i telemekhanika – Automation and Remote Control. 2014. vol. 6. pp. 39–48. (In Russ.).
7. Agrawal P., Agrawal H. Adaptive algorithm design for cooperative hunting in multi-robots. International Journal of Intelligent Systems and Applications. 2018. vol. 10(12). pp. 47–55.
8. Dai Y., Xiong H., Tao Y., Li G. A method for path planning of mobile robots based on threat assessment and biologically inspired neural network. Chinese High Technology Letters. 2019. vol. 29(6). pp. 585–593.
9. Ni T., Wei R., Zhao X., Xu Z. Neural Dynamic Collision-Avoidance Strategy for Robots Based on Evaluation of Threat Degree. Robot. 2017. vol. 39(6). pp. 853–859.
10. Krokhmal P., Zabarankin M., Uryasev S. Modeling and optimization of risk. Surveys in Operations Research and Management Science. 2001. vol. 16. pp. 49–66.
11. Zabarankin M., Uryasev S., Pardalos P. Optimal Risk Path Algorithms. Coop-erative Control and Optimizaton. 2002. pp. 273–298.
12. Galyaev A.A., Maslov E.P., Rubinovich E.Ya. [About one task of controlling the movement of an object in a conflict environment]. Izvestiya RAN. Teoriya i sistemy upravleniya – Proceedings of the RAS. Theory and control systems. 2009. vol. 3. pp. 134–140. (In Russ.).
13. Galyaev A.A., Maslov E.P. [Optimization of the laws of evasion of a moving object from detection]. Izvestiya RAN. Teoriya i sistemy upravleniya – Proceed-ings of the RAS. Theory and control systems. 2010. vol. 4. pp. 43–53. (In Russ.).
14. Abramyants T.G., Maslov E.P., Yahno V.P. [Evasion of a moving object from detection by a group of observers]. Problemy upravleniya – Control Sciences. 2010. vol. 5. pp. 73–79. (In Russ.).
15. Galyaev A.A. [The problem of evading a moving single observer on a plane in a conflict environment]. Avtomatika i telemekhanika – Automation and Remote Control. 2014. vol. 6. pp. 39–48. (In Russ.).
16. Abramyants T.G. et al. [Evasion of a moving object in a conflict environment from detection by a system of dissimilar observers]. Problemy upravleniya – Control Sciences. 2015. vol. 2. pp. 31–37. (In Russ.).
17. Korepanov V.O., Novikov D.A. [The diffuse bomb problem]. Problemy uprav-leniya – Control Sciences. 2011. vol. 5. pp. 66–73. (In Russ.).
18. Korepanov V.O., Novikov D.A. [Strategic behavior models in the diffuse bomb problem]. Problemy upravleniya – Control Sciences. 2015. vol. 2. pp. 38–44. (In Russ.).
19. Liu D., Cong M., Du Y. Episodic Memory-Based Robotic Planning under Un-certainty. IEEE Transactions on Industrial Electronics. 2017. vol. 64(2). pp. 1762–1772.
20. Yehoshua R., Agmon N., Kaminka G.A. Robotic adversarial coverage of known environments. International Journal of Robotics Research. 2016. vol. 35(12). pp. 1419–1444.
21. Zhang B., Lu Q., Wang J. A strategy for finding the most reliable path in uncer-tain environments. Proceedings of the 18th International Conference on Climb-ing and Walking Robots and the Support Technologies for Mobile Machines. 2015. pp. 677–684.
22. Agafonov A.A., Myasnikov V.V. [Method for reliable shortest path determina-tion in stochastic networks using parametrically defined stable probability dis-tributions]. Trudy SPIIRAN – SPIIRAS Proceedings. 2019. Issue 18(3). pp. 557–581. (In Russ.).
23. Khatib O. Real-Time Obstacles Avoidance for Manipulators and Mobile Ro-bots. Autonomous robot vehicles. 1986. pp. 396–404.
24. Montiel O., Orozco-Rosas U., Sepúlveda R. Path planning for mobile robots using Bacterial Potential Field for avoiding static and dynamic obstacles. Expert Systems with Applications. 2015. vol. 42(12). pp. 5177–5191.
25. Rasekhipour Y., Khajepour A., Chen S.-K., Litkouhi B. A Potential Field-Based Model Predictive Path-Planning Controller for Autonomous Road Vehicles. IEEE Transactions on Intelligent Transportation Systems. 2016. vol. 18(5). pp. 1255–1267.
26. Mabrouk M.H., McInnes C.R. Solving the potential field local minimum prob-lem using internal agent states. Robotics and Autonomous Systems. 2008. vol. 56(12). pp. 1050–1060.
27. Pshikhopov V., Medvedev M., Soloviev V. The Multicopter Control Algo-rithms with Unstable Modes. 2019 6th International Conference on Control, Decision and Information Technologies (CoDIT’19). 2019. pp. 1179–1184.
28. Bhattacharya S. Towards optimal path computation in a simplicial complex. International Journal of Robotics Research. 2019. vol. 38(8). pp. 981–1009.
29. Yu X. et al. ACO-A*: Ant Colony Optimization plus A* for 3D Traveling in Environments with Dense Obstacles. IEEE Transactions on Evolutionary Com-putation. 2018. vol. 23(4). pp. 617–631.
30. Sanchez-Lopez J.L. et al. A Real-Time 3D Path Planning Solution for Collision-Free Navigation of Multirotor Aerial Robots in Dynamic Environment. Journal of Intelligent & Robotic Systems. 2019. vol. 93(1-2). pp. 33–53.
31. Stentz A. Optimal and Efficient Path Planning for Partially-Known Environ-ments. IEEE Conference on Robotics and Automation. 1994. pp. 3310–3317.
32. Karkishchenko A.N., Pshikhopov V.Kh. [On finding the complexity of an environment for the operation of a mobile object on a plane]. Avtomatika i telemekhanika – Automation and Remote Control. 2019. vol. (5). pp. 136–154. (In Russ.).
33. Wentzel E.S. Teoriya veroyatnostej [Probability theory]. M.: Nauka. 1969. 576 p. (In Russ.).
34. Gradshtein I.S., Ryzhik I.M. Tablicy integralov ryadov summ i proizvedenij [Tables of integrals of series of sums and products]. M.: FIZMATLIT. 1963. 1108 p. (In Russ.).
35. Kudryavtsev L.D. Kurs matematicheskogo analiza [The course of mathematical analysis]. M.: Drofa. 2004. Issue 2. 720 p. (In Russ.).
36. Carsten J., Ferguson D., Stentz A. 3D Field D*: Improved Path Planning and Replanning in Three Dimensions. Proceedings of the 2006 IEEE/RSJ Interna-tional Conference on Intelligent Robots and Systems. 2006. pp. 3381–3386.
37. Koenig S., Likhachev M. Fast Replanning for Navigation in Unknown Terrain. Transactions on Robotics. 2005. vol. 21(3). pp. 354–363.
38. Koenig S., Likhachev M., Furcy D. Lifelong Planning A*. Artificial Intelli-gence. 2004. vol. 155(1-2). pp. 93–146.
39. Pshikhopov V., Medvedev M. Position-Path Control of a Vehicle. Path Planning for Vehicles Operating in Uncertain 2D Environments. 2017. pp. 1–23.
2. Yang L. et al. Survey of Robot 3D Path Planning Algorithms. Journal of Con-trol Science and Engineering. 2016. vol. 2016. pp. 22.
3. Qu Y., Zhang Y., Zhang Y. A Global Path Planning Algorithm for Fixed-wing UAVs. Journal of Intelligent & Robotic Systems. 2018. vol. 91(3-4). pp. 691–707.
4. Pshikhopov V.H., Medvedev M.Yu. [Group control of autonomous robots motion in uncertain environment via unstable modes]. Trudy SPIIRAN – SPIIRAS Proceedings. 2018. vol. 5(60). pp. 39–63. (In Russ.).
5. Pshikhopov V., Medvedev M. Motion Planning and Control Using Bionic Ap-proaches Based on Unstable Modes. Path Planning for Vehicles Operating in Uncertain 2D Environments. 2017. pp. 239–280.
6. Galyaev A.A. Evasion on plane from a single mobile observer in the conflict environment. Avtomatika i telemekhanika – Automation and Remote Control. 2014. vol. 6. pp. 39–48. (In Russ.).
7. Agrawal P., Agrawal H. Adaptive algorithm design for cooperative hunting in multi-robots. International Journal of Intelligent Systems and Applications. 2018. vol. 10(12). pp. 47–55.
8. Dai Y., Xiong H., Tao Y., Li G. A method for path planning of mobile robots based on threat assessment and biologically inspired neural network. Chinese High Technology Letters. 2019. vol. 29(6). pp. 585–593.
9. Ni T., Wei R., Zhao X., Xu Z. Neural Dynamic Collision-Avoidance Strategy for Robots Based on Evaluation of Threat Degree. Robot. 2017. vol. 39(6). pp. 853–859.
10. Krokhmal P., Zabarankin M., Uryasev S. Modeling and optimization of risk. Surveys in Operations Research and Management Science. 2001. vol. 16. pp. 49–66.
11. Zabarankin M., Uryasev S., Pardalos P. Optimal Risk Path Algorithms. Coop-erative Control and Optimizaton. 2002. pp. 273–298.
12. Galyaev A.A., Maslov E.P., Rubinovich E.Ya. [About one task of controlling the movement of an object in a conflict environment]. Izvestiya RAN. Teoriya i sistemy upravleniya – Proceedings of the RAS. Theory and control systems. 2009. vol. 3. pp. 134–140. (In Russ.).
13. Galyaev A.A., Maslov E.P. [Optimization of the laws of evasion of a moving object from detection]. Izvestiya RAN. Teoriya i sistemy upravleniya – Proceed-ings of the RAS. Theory and control systems. 2010. vol. 4. pp. 43–53. (In Russ.).
14. Abramyants T.G., Maslov E.P., Yahno V.P. [Evasion of a moving object from detection by a group of observers]. Problemy upravleniya – Control Sciences. 2010. vol. 5. pp. 73–79. (In Russ.).
15. Galyaev A.A. [The problem of evading a moving single observer on a plane in a conflict environment]. Avtomatika i telemekhanika – Automation and Remote Control. 2014. vol. 6. pp. 39–48. (In Russ.).
16. Abramyants T.G. et al. [Evasion of a moving object in a conflict environment from detection by a system of dissimilar observers]. Problemy upravleniya – Control Sciences. 2015. vol. 2. pp. 31–37. (In Russ.).
17. Korepanov V.O., Novikov D.A. [The diffuse bomb problem]. Problemy uprav-leniya – Control Sciences. 2011. vol. 5. pp. 66–73. (In Russ.).
18. Korepanov V.O., Novikov D.A. [Strategic behavior models in the diffuse bomb problem]. Problemy upravleniya – Control Sciences. 2015. vol. 2. pp. 38–44. (In Russ.).
19. Liu D., Cong M., Du Y. Episodic Memory-Based Robotic Planning under Un-certainty. IEEE Transactions on Industrial Electronics. 2017. vol. 64(2). pp. 1762–1772.
20. Yehoshua R., Agmon N., Kaminka G.A. Robotic adversarial coverage of known environments. International Journal of Robotics Research. 2016. vol. 35(12). pp. 1419–1444.
21. Zhang B., Lu Q., Wang J. A strategy for finding the most reliable path in uncer-tain environments. Proceedings of the 18th International Conference on Climb-ing and Walking Robots and the Support Technologies for Mobile Machines. 2015. pp. 677–684.
22. Agafonov A.A., Myasnikov V.V. [Method for reliable shortest path determina-tion in stochastic networks using parametrically defined stable probability dis-tributions]. Trudy SPIIRAN – SPIIRAS Proceedings. 2019. Issue 18(3). pp. 557–581. (In Russ.).
23. Khatib O. Real-Time Obstacles Avoidance for Manipulators and Mobile Ro-bots. Autonomous robot vehicles. 1986. pp. 396–404.
24. Montiel O., Orozco-Rosas U., Sepúlveda R. Path planning for mobile robots using Bacterial Potential Field for avoiding static and dynamic obstacles. Expert Systems with Applications. 2015. vol. 42(12). pp. 5177–5191.
25. Rasekhipour Y., Khajepour A., Chen S.-K., Litkouhi B. A Potential Field-Based Model Predictive Path-Planning Controller for Autonomous Road Vehicles. IEEE Transactions on Intelligent Transportation Systems. 2016. vol. 18(5). pp. 1255–1267.
26. Mabrouk M.H., McInnes C.R. Solving the potential field local minimum prob-lem using internal agent states. Robotics and Autonomous Systems. 2008. vol. 56(12). pp. 1050–1060.
27. Pshikhopov V., Medvedev M., Soloviev V. The Multicopter Control Algo-rithms with Unstable Modes. 2019 6th International Conference on Control, Decision and Information Technologies (CoDIT’19). 2019. pp. 1179–1184.
28. Bhattacharya S. Towards optimal path computation in a simplicial complex. International Journal of Robotics Research. 2019. vol. 38(8). pp. 981–1009.
29. Yu X. et al. ACO-A*: Ant Colony Optimization plus A* for 3D Traveling in Environments with Dense Obstacles. IEEE Transactions on Evolutionary Com-putation. 2018. vol. 23(4). pp. 617–631.
30. Sanchez-Lopez J.L. et al. A Real-Time 3D Path Planning Solution for Collision-Free Navigation of Multirotor Aerial Robots in Dynamic Environment. Journal of Intelligent & Robotic Systems. 2019. vol. 93(1-2). pp. 33–53.
31. Stentz A. Optimal and Efficient Path Planning for Partially-Known Environ-ments. IEEE Conference on Robotics and Automation. 1994. pp. 3310–3317.
32. Karkishchenko A.N., Pshikhopov V.Kh. [On finding the complexity of an environment for the operation of a mobile object on a plane]. Avtomatika i telemekhanika – Automation and Remote Control. 2019. vol. (5). pp. 136–154. (In Russ.).
33. Wentzel E.S. Teoriya veroyatnostej [Probability theory]. M.: Nauka. 1969. 576 p. (In Russ.).
34. Gradshtein I.S., Ryzhik I.M. Tablicy integralov ryadov summ i proizvedenij [Tables of integrals of series of sums and products]. M.: FIZMATLIT. 1963. 1108 p. (In Russ.).
35. Kudryavtsev L.D. Kurs matematicheskogo analiza [The course of mathematical analysis]. M.: Drofa. 2004. Issue 2. 720 p. (In Russ.).
36. Carsten J., Ferguson D., Stentz A. 3D Field D*: Improved Path Planning and Replanning in Three Dimensions. Proceedings of the 2006 IEEE/RSJ Interna-tional Conference on Intelligent Robots and Systems. 2006. pp. 3381–3386.
37. Koenig S., Likhachev M. Fast Replanning for Navigation in Unknown Terrain. Transactions on Robotics. 2005. vol. 21(3). pp. 354–363.
38. Koenig S., Likhachev M., Furcy D. Lifelong Planning A*. Artificial Intelli-gence. 2004. vol. 155(1-2). pp. 93–146.
39. Pshikhopov V., Medvedev M. Position-Path Control of a Vehicle. Path Planning for Vehicles Operating in Uncertain 2D Environments. 2017. pp. 1–23.
Опубликован
2020-02-14
Как цитировать
Медведев, М. Ю., Костюков, В. А., & Пшихопов, В. Х. (2020). Оптимизация движения мобильного робота на плоскости в поле конечного числа источников-репеллеров. Труды СПИИРАН, 19(1), 43-78. https://doi.org/10.15622/sp.2020.19.1.2
Раздел
Робототехника, автоматизация и системы управления
Copyright (c) 2020 Михаил Юрьевич Медведев, Владимир Александрович Костюков, Вячеслав Хасанович Пшихопов
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).