from 01.01.2019 to 01.01.2022
Rostov-on-Don, Rostov-on-Don, Russian Federation
Rostov-on-Don, Russian Federation
UDK 007.52 не содержащие человека в качестве звена системы, роботы, автоматы
A mobile robot is a complex system capable of receiving information about the outside world and using it to move safely in a purposeful way. The work information subsystem can determine its position using sensors, as well as the location of static and dynamic objects in the workspace. The robot's movement to the target point is carried out according to various algorithms. These algorithms implement various methods of planning the trajectory of movement to the target point: to prevent the robot from colliding with barriers, to reduce the travel time and distance traveled to save battery power. Mobile robots can function in a dynamic environment with a significant degree of uncertainty. One of the main tasks of a mobile robot is planning trajectories by controlling the movement of the robot to reach target point. This article proposes a method for planning trajectory of a mobile robot by controlling its movement. The method is based on simulation of the movement of a mobile robot in an environment with fixed and movable barriers. It is assumed that the direction of dynamic obstacles can change randomly.
wheeled mobile robot, robot trajectory planning, stochastic control, collision prediction, robot motion control
Введение. Роботы успешно применяются в машиностроении, при производстве автомобилей и в ряде других областей. В ближайшем будущем роботы будут широко использоваться в сельском хозяйстве, горнодобывающей индустрии и сфере услуг. Эти роботы будут обладать значительной мобильностью и способностью самостоятельно принимать решения по своему поведению. Следовательно, для обеспечения безопасности таких мобильных роботов и их успешного функционирования необходимы алгоритмы планирования действий и движений. Мобильный робот должен быть способен извлекать информацию из окружающей среды и использовать ее для безопасного перемещения целенаправленным образом. Для этого роботы могут использовать различные типы датчиков или получать необходимую информацию от внешних информационных систем. Задачи планирования безопасных траекторий движения робота рассматривались многими исследователями [1–7] и эти работы продолжаются, поскольку условия, в которых функционируют роботы очень разнообразны.
Чтобы избежать столкновений с препятствиями, необходимо знать положение препятствий и предсказывать траекторию их движения. В определенной мере методы, использующие локализацию и картографирование (SLAM) [8] для определения местоположения мобильного робота в режиме реального времени и нанесения на карту окружающей зоны обнаруженных препятствий, позволяют решить эту задачу. К недостаткам данной группы относится отсутствие механизмов прогнозирования и планирования движения к целевой точке.
Известные методы планирования траектории могут быть эффективны для определённых условий и неприменимы для других условий. Они могут иметь различную вычислительную сложность, что не позволит использовать их в системах, где планирование траектории должно осуществляться в реальном масштабе времени для быстро движущихся объектов.
В данной статье рассмотрены наиболее распространенные методы планирования траектории движения робота. Также в статье предлагается метод планирования движения мобильного робота и управления его перемещением в среде с подвижными и неподвижными препятствиями.
Анализ известных методов планирования траекторий мобильных роботов. Известно значительное количество методов планирования траекторий движения мобильных роботов на основе теории графов [1–3, 9]. Обычно узлы графа отражают состояния, в которых может находиться робот. Переходы между состояниями могут быть оценены некоторой функцией затрат. В этом случае возможно нахождение пути, который имеет минимальные суммарные затраты при перемещении робота в целевую точку. Эти методы в общем случае относятся к группе глобальных и позволяют определить наилучшую траекторию к целевой точке в детерминированных условиях движения робота. Методы на основе графов малоэффективны при планировании траекторий движения робота при наличии динамических препятствий.
Еще одной группой методов планирования являются методы на основе клеточной декомпозиции. В этих методах выполняется разбиение рабочего пространства на области («клетки»). Каждая клетка рабочего пространства может быть свободна для перемещения туда робота или занята. Планирование траектории предполагает нахождение последовательности перемещения робота через смежные свободные клетки в целевую точку. Метод имеет серьезный недостаток: увеличение трудоемкости при уменьшении шагов сетки. Также нет эффективных способов учитывать случайный характер движения препятствий. Методы на основе клеточной декомпозиции малоэффективны при планировании траекторий движения робота в условиях случайных процессов, при стохастичности вектора скорости препятствий.
Планирование траекторий робота на основе оптимизационных методов основаны на рассмотрении динамики движения, либо оптимизационном решении задач при групповом управлении. Поэтому подход, основанный на оптимальном управлении, эффективен для простых (линейных) детерминированных систем [10–12]. Методы не обеспечивают эффективности при планировании траекторий в условиях подвижных препятствий с неопределенным характером движения.
Для планирования траекторий движения в недетерминированных условиях ряд методов, использует элементы искусственного интеллекта [13–16]. Среди них можно выделить биоинспирированные алгоритмы: роевой интеллект, «муравьиный» алгоритм, метод роя частиц, а также генетические и эволюционные алгоритмы. Методы ориентированы на решение задач управления группой роботов неприменимы или неэффективны при планировании траекторий одиночного робота в условиях изменяющейся обстановки [17].
Еще одной большой группой методов, применяемых для управления роботом при наличии различных препятствий, являются методы на основе потенциальных полей. Методы используются достаточно широко как для двухмерных, так и для трехмерных случаев. Движение планируется вдоль линий векторного поля [1, 10], потенциальная функция которого определяется расположением препятствий и их формой. В качестве потенциальной функции наиболее часто методы используют:
• виртуальное силовое поле;
• Ньютоновское потенциальное поле;
• супербиквадратное потенциальное поле;
• гармоническое векторное поле;
Робот рассматривается как материальная точка, движущаяся под действием силы притяжения к целевой точке и сил отталкивания от препятствий. Потенциальная функция [1] может быть записана в виде следующего уравнения.
(1)
где 
– притягивающая потенциальная функция, заданная для точки 
; 
– слагаемые отталкивающей потенциальной функции, соответствующие отдельным препятствиям. Притягивающая потенциальная функция может быть задана как уравнение
(2)
где 
– коэффициент, определяющий силу притяжения к целевой точке 
, которое может быть описано следующим образом
(3)
Для каждого 
-го препятствия потенциальная функция может быть описана уравнениями 4 и 5
(4)
(5)
Суперпозиция векторной суммы, притягивающей и отталкивающих сил определяет направление движения робота. Под действием этих сил робот объезжает препятствия и движется к целевой точке. Известны различные модификации метода потенциальных функций в зависимости от особенностей применения и условий реализации.
К основным недостаткам методов на основе потенциальных полей относятся возможность попадания робота в локальные минимумы между препятствиями, а также возможность «осцилляций траектории». Известны модификации метода потенциальных полей для устранения таких недостатков в условиях динамической среды [9, 18, 19]. Методы на основе потенциальных полей малоэффективны при планировании траекторий движения робота в условиях подвижных препятствий с неопределенными параметрами.
Планирование и управление движением робота с учетом стохастичности параметров препятствий. На основе анализа известных методов планирования траекторий движения мобильных роботов были сделаны выводы о том, что для управления движением мобильного робота в среде с подвижными и неподвижными препятствиями необходимо разработать метод планирования, в основе которого должен лежать учет вероятности достижения роботом конкретных точек на местности с учетом вероятности возможных столкновений с препятствиями [20].
При разработке метода авторы исходили из того, что при наличии подвижных препятствий наилучшая траектория не может быть найдена до начала движения. Несмотря на наличие некоторой априорной информации о положении и параметрах движения подвижных препятствий их стохастичность обуславливает уменьшение надежности прогноза столкновений с увеличением интервала прогнозирования. В этом случае планироваться может перемещение робота на определенном временном интервале, при соответствующем уровне прогнозной оценки вероятности столкновения на данном интервале. Планирование и управление движением мобильного робота могут быть осуществлены при наличии: навигационной информации о собственном положении, текущем положении препятствий, движущихся «случайным» образом [4, 21, 22, 23]; определенных на планируемый интервал времени параметрах стохастических оценках направления движения подвижных препятствий.
Задачи исследования были сформулированы следующим образом:
- разработать метод планирования траекторий движения мобильного робота в среде со статическими и динамическими препятствиями в условиях неопределенности движения препятствий;
- разработать метод управления траекторным движением мобильного робота с учетом изменяющейся текущей обстановки;
- создать дискретно-непрерывную имитационную модель движения объектов в рабочей области с учетом стохастичности параметров движения препятствий;
- разработать метод динамического планирования траектории движения мобильного робота с изменяемым временем прогноза событий;
- провести вычислительный эксперимент (моделирование) по планированию траекторий и движению мобильного робота на основе предложенных решений при наличии динамических препятствий.
Метод. В данной статье предлагается метод планирования траектории движения мобильного робота на основе имитационного моделирования изменяющейся обстановки. Будем считать, что положение целевой точки, куда должен прибыть робот, известно и не изменяется. Также введем некоторые допущения:
- динамические препятствия могут изменять направление своего движения случайным образом;
- параметры законов распределения случайных величин (направления и движения) известны и определяются математическим ожиданием Μαo, среднеквадратическим отклонением ϭαo сигма, и дисперсией угла направления движения Dαo;
- скорость движения препятствий известна;
- координаты и вектор скорости каждого препятствия доступны для измерения через некоторый интервал времени tизм.
Авторами поставленные задачи были решены с учетом следующих допущений и
условий – координаты статических препятствий априорно известны; динамические препятствии имеют известную скорость движения; динамические препятствия могут изменять направление своего движения случайным образом; для динамических препятствий параметры законов распределения случайных величин известны; координаты и вектор скорости динамических препятствий «доступны для измерения» в дискретные моменты времени через некоторый интервал времени.
Указанные допущения справедливы в предположении, что системой управления робота (или внешней системой) осуществляется мониторинг области, где происходит движение робота. Практическая реализация такого мониторинга возможна на основе лазерных дальнометрических датчиков, системы технического зрения или лидаров. В ходе такого мониторинга выполняется оценка текущего положения каждого препятствия и параметров его движения, в предположении что вектор скорости может быть описан нормальным законом распределения случайной величины. Следует отметить, что для системы управления робота информация о препятствиях обновляется через интервал времени tизм, который превышает интервал времени принятия решений о параметрах движения робота. tр.
С точки зрения процесса имитационного моделирования рассмотрим движение робота к целевой точке с координатами Xg, Yg в условиях неподвижных и подвижных препятствий. Каждое препятствие определено своими координатами Xoi, Yoi и параметрами движения Voi, Μαoi, Dαoi, ϭαoi. Где Voi – текущая оценка скорости движения каждого препятствия, Μαoi, Dαoi, ϭαoi – математическое ожидание, дисперсия и среднеквадратическое отклонение направления движения каждого подвижного препятствия. Имитационная модель разработана и реализована в среде Matlab.
Введем понятие горизонта событий, под которым будем понимать интервал времени t0 для которого будет выполняться прогноз движения препятствий и оцениваться вероятность столкновения с ними мобильного робота. Выбор «наилучшего значения» t0 является нетривиальной задачей и в данной статье не рассматривается.
Поясним логику принятия решений и действий на уровне бортовой системы управления роботом соответствующую положению объектов в рабочей области, показанной на рисунке 1.
Рис. 1. Расположение мобильного робота и препятствий на планируемом интервале времени 
Светлыми окружностями обозначены начальные положения препятствий, темными – положения препятствий в конце интервала прогнозирования 
. Конечное положение препятствий определяется как результат его движения с вероятностными характеристиками, известными в момент времени 
. Чем больше будет величина горизонта прогноза , тем меньше надежность прогноза. Следовательно, возрастает вероятность не обнаружения возможного столкновения. Однако, уменьшение прогнозируемого интервала значительно меньше величины 
из-за возрастания вычислительных издержек системы управления без адекватного (соответствующего) роста качества планирования траектории движения робота. В общем случае выбор значения зависит от скоростных и динамических характеристик робота, имеющегося времени информационно-измерительной подсистемы.
Логика предлагаемого метода планирования траектории робота и его движения к целевой точке иллюстрируется алгоритмом, приведенном на рисунке 2.
В момент времени t, на основе текущих данных о расположении целевой точки, робота, препятствий и параметров их движения выполняется оценка положения препятствий к моменту времени t+t0. Для робота выбирается направление движения на целевую точку и прогнозируется его положение в момент времени t+t0. Движение робота на интервале времени t0 произойдет без столкновений с препятствиями, если при перемещениях робота и препятствий выполняются условия
(6)
где 
– радиус зоны безопасности вокруг робота, 
– радиус зоны безопасности вокруг соответствующего препятствия, 
, 
- текущие координаты робота, 
, 
– координаты препятствий.
Если существует вероятность столкновения робота, то возможны два решения. Если столкновение может произойти с неподвижным препятствием, то выполняется его обход, критерием выбора лучшего варианта при этом является минимальный путь (время) обхода. Если столкновение возможно с движущимся препятствием, то выполняется изменение планируемой скорости движения робота и еще раз выполняется прогноз возможности столкновения.
Рис. 2. Общий алгоритм достижения целевой точки
Результаты. Результаты планирования траектории движения мобильного робота на основе имитационного моделирования изменяющейся обстановки приведены ниже. На рисунке 3 показано построение траектории движения робота при наличии в рабочей зоне неподвижных препятствия. На каждом интервале планирования определялась промежуточная точка, в которую робот должен переместиться за время t0 (определяется горизонтом событий).
Результаты планирования траектории движения мобильного робота на основе имитационного моделирования изменяющейся обстановки приведены ниже. На рисунке 3 показано построение траектории движения робота при наличии в рабочей зоне неподвижных препятствия. На каждом интервале планирования определялась промежуточная точка, в которую робот должен переместиться за время t0 (определяется горизонтом событий).
Проверка работоспособности метода для случая статических и динамических препятствий иллюстрируется на рисунке 4. Кроме неподвижных препятствий в рабочей зоне имеются подвижные препятствия, направление движения которых изменяется случайным образом. Траектории движения препятствий показаны синими линиями.
Рис. 3. Планирование и движение по траектории при статических препятствиях
Рис. 4. Планирование и движение по траектории при статических и динамических препятствиях
На рисунке видно, что на втором интервале планирования движения, было обнаружена возможность столкновения робота с подвижным препятствием, движущимся из начальной точки х=650, у=560. Для предотвращения столкновения была уменьшена скорость робота. И еще раз выполнен прогноз возможности столкновения. Если столкновения не произойдет, робот перемещается в новую промежуточную точку. После этого осуществляется планирование траектории движения мобильного робота на новом интервале времени, определяющим горизонт событий.
Обсуждение результатов. В предложенном методе планирования и управления движением робота учитывается случайный характер движения динамических препятствий. Для ситуаций возможного столкновения реализовано несколько стратегий, обеспечивающих безопасное движение робота. В зависимости от сложившейся ситуации реализуются различные алгоритмы поведения робота. Стратегии поведения робота отличаются для ситуаций при его опасном сближении с неподвижными и подвижными препятствиями.
Предложенный метод обеспечивает безопасное перемещение робота в целевую точку.
Метод позволяет задавать величину зоны безопасности при планировании траектории движения робота и при необходимости изменять ее в зависимости от принятого времени прогнозирования – горизонта событий.
Объезд неподвижных препятствий осуществляется наилучшим образом для минимизации времени движения к целевой точке.
Дальнейшие улучшения предложенного метода будут включать следующие решения:
Определение наилучшей промежуточной точки для движения при объезде статических и динамических препятствий с учетом прогноза изменения их расположения на интервале, превышающем принятое время прогнозирования;
Реализация долгосрочного прогнозирования изменений обстановки в зоне движения мобильного робота для принятия стратегических и тактических решений. Это позволит избегать ситуаций, не имеющих решения и планировать близкие к оптимальной траектории безопасного движения мобильного робота.
Выводы. Выполненные эксперименты с математическим моделирование процессов планирования и управления движением мобильного робота позволяют сделать следующие выводы.
- Разработан метод планирования траектории движения мобильного робота в среде с неподвижными и подвижными препятствиями, в том числе имеющими случайный характер изменения векторов скорости подвижных препятствий; Метод учитывает возможные столкновения на заданном временном интервале горизонта прогноза;
- Разработанный метод реализует несколько стратегий предотвращения столкновений, в том числе для объезда неподвижных и подвижных препятствий с изменением собственной скорости и направления движения;
- Разработана имитационная модель, реализующая дискретно-непрерывный процесс движения объектов в некоторой области;
- Результаты моделирования показали эффективность планирования траекторий и управления движением робота в условиях неподвижных и подвижных препятствий.
1. Liu V. Methods of path planning in an environment with obstacles (review). Mathematics and mathematical modeling: a network scientific publication. Moscow: MGTU. 2018. No. 01. Pp. 15-58. DOI: 10.24108 / mathm.0118.0000098.
2. Lim C. W., Yong L. S., Ang M.H. Hybrid of global path planning and local navigation implemented on a mobile robot in indoor environment. Proceedings of the IEEE International Symposium on Intelligent Control (ISIC). Vancouver, Canada. 2002. Pp. 821-826. DOI:https://doi.org/10.1109/ISIC.2002.1157868.
3. Zhenyu W., Lin F. Obstacle prediction-based dynamic path planning for a mobile robot. International Journal of Advancements in Computing Technology. 2012. Vol. 4. No. 3. Pp. 118-124.
4. Hoang D. T., Pyrkin A. A. Trajectory control of a mobile robot under uncertainty [Trayektornoye upravleniye mobil'nym robotom v usloviyakh neopredelennosti]. Izv. vuzov. Instrumentation. 2021. Vol. 64. No.8. Pp. 608-619. (rus)
5. Das N.Ch., Skakun A.D., Zim Z.Kh., Uddin R. Algorithm for planning the trajectory of a mobile robot [Algoritm planirovaniya trayektorii mobil'nogo robota]. Mezhdunarodnaya konferentsiya po myagkim vychisleniyam i izmereniyam. 2021. Vol. 1. Pp. 228-231. (rus)
6. Fedorov V.M., Sharlay A.S. A review of known methods for constructing a navigation system to implement the possibility of autonomous movement of mobile robots in an environment with obstacles [Obzor izvestnykh metodov postroyeniya sistemy navigatsii dlya realizatsii vozmozhnosti avtonomnogo peremeshcheniya mobil'nykh robotov v srede s prepyatstviyami]. V sbornike: informatsionnyye tekhnologii v sovremennom inzhenernom obrazovanii. materialy mezhvuzovskoy nauchno-prakticheskoy konferentsii. Sankt-Peterburg, 2020. Pp. 241-245. (rus)
7. Strashnov E.V., Torgashev M.A. Modeling the movement of wheeled robots on a flat surface in virtual environment systems [Modelirovaniye dvizheniya kolesnykh robotov po rovnoy poverkhnosti v sistemakh virtual'nogo okruzheniya]. V sbornike: Virtual'noye modelirovaniye, prototipirovaniye i promyshlennyy dizayn. Materialy VI Mezhdunarodnoy nauchno-prakticheskoy konferentsii. 2020. Pp. 149-154. (rus)
8. Qin Ch. Investigation of slam robot’s algorithm based on graph optimization [Issledovaniye algoritma slam robotov na osnove optimizatsii grafov]. StudNet. 2021. Vol. 4. No7. Pp. 63-76. (rus)
9. Karpasyuk I.V. Modification of the method of potentials for finding paths on a weighted graph [Modifikatsiya metoda potentsialov dlya poiska putey na vzveshennom grafe]. V sbornike: Tekhnicheskiye sredstva sistem upravleniya i svyazi = International Scientific Forum on Control and Engineering. Mezhdunarodnyy nauchnyy forum. Materialy V Mezhdunarodnoy konferentsii «Informatsionnyye tekhnologii i tekhnicheskiye sredstva upravleniya» (ICCT-2021), 14-y Mezhdunarodnoy konferentsii «Akustoopticheskiye i radiolokatsionnyye metody izmereniy i obrabotki informatsii» (ARMIMP-2021). Astrakhan', 2021. Pp. 248-250. (rus)
10. Jing R., McIsaac K.A., Patel R.V. Modified Newton's method applied to potential field-based navigation for mobile robots. IEEE Transactions on Robotics. 2006. Vol. 22. No. 2. Pp. 384-391.
11. Shiltagh N., Jalal L. Optimal path planning for intelligent mobile robot navigation using modified particle swarm optimization. International Journal of Engineering and Advanced Technology. 2013. Vol. 2. No. 4. Pp. 260-267.
12. Yee Z.C., Ponnambalam S.G. Mobile robot path planning using ant colony optimization. IEEE/ASME International Conference on Advanced Intelligent Mechatronics. Singapore, 2009. Pp. 851-856. DOI:https://doi.org/10.1109/AIM.2009.5229903.
13. Moreno J.A., Castro M. Heuristic algorithm for robot path planning based on a growing elastic net. Progress in artificial intelligence: 12th Portuguese conf. on artificial intelligence: EPIA 2005 (Covilhã, Portugal, December 5-8, 2005): Proc. B.: Springer, 2005. Vol. 3808. Pp. 447-454. DOI:https://doi.org/10.1007/11595014_44.
14. Antonov V. O., Gurchinsky M. M., Petrenko V. I., Tebueva F. B. Numerical method of planning a trajectory of pass obstacles based on an iterative piecewise-linear approximation [Metod planirovaniya trayektorii dvizheniya tochki v prostranstve s prepyatstviyem na osnove iterativnoy kusochno-lineynoy approksimatsii]. Systems of Control, Communication and Security. 2018. No. 1. Pp. 168-182. (rus)
15. Medvedev M., Pshikhopov V. Path planning of mobile robot group based on neural networks. Lecture Notes in Computer Science 2020. T. 12144LNAI. Pp. 51-62. DOI:https://doi.org/10.1007/978-3-030-55789-8_5.
16. Pshikhopov V.Kh., Gurenko B.V., Medvedev M.Yu. Algorithms of adaptive position-trajectory control systems of moving objects. Control problems. 2015. No. 4. Pp. 66-75.
17. Skorospekhov Yu.V., Kudelin A.S., Grigoriev G.K. Problems of autonomous control and orientation in space of military robotic complexes [Problemy avtonomnogo upravleniya i oriyentatsii v prostranstve voyennykh robototekhnicheskikh kompleksov]. V sbornike: nauchnaya sessiya guap: gumanitarnyye nauki. Sbornik dokladov traditsionnoy Nauchnoy sessii, posvyashchennoy Vsemirnomu dnyu aviatsii i kosmonavtiki. Sankt-Peterburg, 2020. Pp. 160-163. (rus)
18. Ge S.S., Cui Y.J. New potential functions for mobile robot path planning. IEEE Trans. on Robotics and Automation. 2000. vol. 16. No. 5. Pp. 615-620. DOI:https://doi.org/10.1109/70.880813
19. Jing R., McIsaac K.A., Patel R.V. Modified Newton's method applied to potential fieldbased navigation for mobile robots. IEEE Trans. on Robotics. 2006. vol. 22. No. 2. Pp. 384-391. DOI:https://doi.org/10.1109/TRO.2006.870668
20. Yakovlev D.S., Tachkov A.A. The probability of an autonomous mobile robot colliding with an obstacle [Veroyatnost' stolknoveniya avtonomnogo mobil'nogo robota s prepyatstviyem]. Mechatronics, automation, control. 2021. Vol. 22. No. 3. Pp. 125-133. (rus)
21. Zvonarev I.S., Karavaev Yu.L. Analysis of control systems of mobile robots with intelligent control elements [Analiz sistem upravleniya mobil'nykh robotov s elementami intellektual'nogo upravleniya]. V sbornike: "Vystavka innovatsiy - 2021" (osennyaya sessiya). Sbornik materialov XXXII Respublikanskoy vystavki-sessii studencheskikh innovatsionnykh proyektov. Izhevsk, 2021. Pp. 62-67. (rus)
22. Lapshinov S.A., Shakhnov V.A., Yudin A.V. Directions of intellectualization of motion control of a mobile robot [Napravleniya intellektualizatsii upravleniya dvizheniyem mobil'nogo robota]. Neurocomputers: development, application. 2021. Vol. 23. No.1. Pp. 50-62. (rus)
23. Bazhenov E.I., Mokrushin S.A., Okhapkin S.I. Analysis and choice of the principle of constructing the orientation system of a mobile robot [Analiz i vybor printsipa postroyeniya sistemy oriyentatsii mobil'nogo robota]. Control systems and information technologies. 2021. No. 2(84). Pp. 27-30. (rus)
