Методика планирования траектории движения группы мобильных роботов в неизвестной замкнутой среде с препятствиями

Системы управления,связи и безопасности №3. 2021

Systems of Control, Communication and Security ISSN 2410-9916

УДК 004.896

Методика планирования траектории движения группы мобильных роботов в неизвестной замкнутой среде

с препятствиями

Павлов А. С.

Постановка задачи: групповое применение мобильных роботов в сложных прикладных задачах позволяет существенно увеличить эффективность решения таких задач. При этом возможности группового применения мобильных роботов в неизвестных средах определяются, в первую очередь, уровнем развития методов группового децентрализованного управления. Известные алгоритмы планирования траектории движения группы мобильных роботов в неизвестной среде обладают высокой вычислительной сложностью или не позволяют найти траекторию, оптимальную по длине пути, с соблюдением безопасной дистанции до препятствий и других роботов группы. Целью работы является повышение эффективности решения задачи планирования траектории движения группы мобильных роботов из начального положения в конечное в неизвестной среде с препятствиями с учетом ограниченных возможностей (сенсорных и вычислительных) мобильных роботов и специфики децентрализованного управления. Используемые методы: решение поставленной задачи осуществлено на основе пошаговой оптимизации текущего положения каждого робота группы относительно заданной цели. В предложенной методике анализируется возможность движения каждого робота группы в направлениях, определяемых средствами аналитической геометрии на основе измерений бортовых датчиков расстояния. В случае невозможности движения ни в одном из направлений, производится оценка положения соседних роботов группы и выбирается положение лидера в качестве промежуточного состояния, при этом осуществляется корректировка траектории на основе измерений бортовых датчиков расстояния при наличии препятствий. Описанная последовательность действий в предложенной методике итеративно повторяется для движения каждого робота группы из начального состояния в промежуточное, и из промежуточного в конечное. Критерием остановки является достижение каждым роботом группы целевой позиции. Новизна: элементом новизны в данной работе является процедура расчета сегментов траектории на основе выбора промежуточного состояния и корректировки траектории с учетом измерений бортовых датчиков расстояния мобильных роботов группы. Результат: предложенная методика позволяет выполнять поиск траектории движения группы мобильных роботов в неизвестной среде с обеспечением заданной дистанции до препятствий и других роботов группы. Использование представленных алгоритмов позволяет группе роботов сохранять высокую эффективность выполнения задачи при функционировании в условиях информационной недостаточности. Достоверность результатов подтверждена в ходе программного моделирования. Практическая значимость: решение задачи с учетом указанных особенностей позволило снизить вычислительную сложность метода, а также снять ограничения по применению алгоритмов планирования траектории для мобильных роботов с низко производительными бортовыми сенсорами и вычислительными устройствами. Представленные алгоритмы реализованы в виде программного обеспечения на языке программирования Python, которое может быть использовано при моделировании децентрализованных систем управления группой мобильных роботов.

Ключевые слова: планирование траектории, обход препятствия, мультиагентные системы, децентрализованное управление, мобильные роботы.

Библиографическая ссылка на статью:

Павлов А. С. Методика планирования траектории движения группы мобильных роботов в неизвестной замкнутой среде с препятствиями // Системы управления, связи и безопасности. 2021. № 3. С. 38-59. DOI: 10.24412/2410-9916-2021-3-38-59 Reference for citation:

Pavlov A. S. Methodology for Planning the Trajectory of a Group of Mobile Robots in Unknown Closed Environment with Obstacles. Systems of Control, Communication and Security, 2021, no. 3, pp. 38-59 (in Russian). DOI: 10.24412/2410-9916-2021-3-38-59

DOI: 10.24412/2410-9916-2021-3-38-59

Системы управления,связи и безопасности №3. 2021

Systems of Control, Communication and Security ISSN 2410-9916

Введение

В настоящее время роботы и робототехнические системы (РТС) получили широкое практическое применение во многих сферах человеческой деятельности. Этот факт обусловлен тем, что данные системы позволяют автоматизировать ряд трудоемких и рутинных задач: мониторинг и ликвидация чрезвычайных ситуаций, спасательные операции, подводные исследования, сельскохозяйственные работы, разведывательные операции, а также многие другие. При этом возникает вопрос эффективности применения РТС в задачах, предполагающих автономное функционирование в течение продолжительного времени (например, исследование больших территорий) или выполнение работ в агрессивных средах (под водой, в космосе, в зонах радиационного загрязнения). В подобных условиях становится актуальным применение нескольких роботов совместно, то есть в группе. При такой модели управления РТС будет отличаться повышенной надежностью и устойчивостью к внешним возмущениям, а также возможностью масштабирования численности роботов группы в зависимости от сложности решаемой задачи. Для обеспечения указанных преимуществ подобные РТС должны иметь распределённую систему управления для обеспечения высокой степени автономности, что, в свою очередь, приводит к появлению ряда специфических проблем управления. Исходя из анализа исследовательских работ [1-5], можно сделать вывод, что одной из ключевых проблем, возникающих при функционировании группы мобильных роботов (МР) в неизвестной среде, является планирование безопасных траекторий движения, позволяющих строить безаварийные маршруты, близкие к оптимальным (кратчайшим).

Задача планирования траекторий движения группы МР в неизвестной среде может быть решена с применением дополнительного оборудования, например, системы технического зрения, или использования гетерогенной группы роботов с различным бортовым оснащением. Так, в работе [6] предложена двухуровневая интеллектуальная система планирования движений мобильных роботов, в которой поиск траектории осуществляется на двух уровнях - грубой и точной подсистемах планирования. Для построения грубой подсистемы используются генетические алгоритмы, для построения точной - нечеткая логика. Недостаточная разрешающая способность систем технического зрения на верхнем уровне компенсируется бортовыми сенсорами роботов. Предложенный подход обеспечивает снижение требуемых вычислительных ресурсов бортовых систем и оптимизацию маршрутов движения всех членов группы для достижения цели. В работе [7] представлены результаты моделирования взаимодействия группы роботов в трехмерной среде для навигации через лабиринт методами вероятностной дорожной карты и одновременной локализации и картографирования. Результаты данных работ демонстрируют высокую эффективность такого подхода, однако, в реальных сценариях использования групповой робототехники не всегда есть возможность использования специализированного оборудования.

С другой стороны, большая часть работ направлена на решение задачи планирования траектории с использованием только бортовых датчиков и сен-

DOI: 10.24412/2410-9916-2021-3-38-59

Системы управления,связи и безопасности №3. 2021

Systems of Control, Communication and Security ISSN 2410-9916

соров роботов группы. В работе [8] предложен метод планирования траектории движения группы мобильных роботов с помощью нейронной сети Хопфилда. Данный метод позволяет строить гладкие безопасные траектории перемещения роботов при наличии препятствий, выявляемых в процессе движения бортовыми датчиками робота. Продемонстрированы результаты моделирования метода в централизованном, децентрализованном и гибридном вариантах реализации. Однако, как отмечает автор работы, при невысокой производительности бортовых вычислительных устройств роботов и ограниченной дальности действия бортовых датчиков может наблюдаться уменьшение плавности обхода препятствий, а также снижение качества построенной траектории при обходе препятствий сложной формы. В работе [9] предложен рекурсивный алгоритм планирования траектории, основная идея которого заключается в аппроксимации траектории кусочно-линейной функцией и последовательном увеличении количества её отрезков до тех пор, пока заданные ограничения по обходу препятствия не будут выполнены. Однако, в данной работе рассматривается детерминированная среда, а применение метода для управления роботом в неизвестной среде с несколькими препятствиями потребует некоторой модификации.

В работе [10] для управления группами мобильных роботов, в том числе в среде с препятствиями, предложен метод на основе искусственных потенциальных полей. В основу данного подхода положена следующая идея: все действующие объекты (роботы группы, цели, препятствия) наделяются некоторыми виртуальными полями, физическим аналогом которых являются потенциальные поля. Те объекты, которые должны избегать чрезмерного сближения и столкновения наделяются полями одного «заряда», а те объекты, которые должны двигаться друг к другу - наделяются полями противоположного «заряда» (понятие «заряд» при этом тоже принято условно). Движение каждого робота определяется влиянием результирующей силы, полученной суммированием векторов всех сил притяжения и отталкивания, действующих на этого робота. Преимуществом метода является низкая вычислительная сложность, что делает возможным его использование при локальном планировании траектории движения робота в режиме реального времени. Однако в неизвестной среде с большим количеством препятствий существует вероятность того, что робот может попасть в точку локального минимума и в конечном счете не достичь цели.

В качестве аналога в данной работе рассматривается алгоритм PSOFS (Particle Swarm Optimization (PSO) with Fringe Search (FS)), описанный в статье [11]. Данный интегрированный алгоритм представляется собой комбинацию алгоритма роя частиц [12] и алгоритма «Fringe Search» [13]. Основная идея алгоритма заключается в итеративном поиске опорных точек траектории с учетом наличия препятствий, в качестве критериев эффективности выступают расстояние до цели, гладкость траектории, а также расстояние до препятствий. Последовательность решения задачи планирования траектории с применением данного метода можно описать следующим образом. Сначала в направлении цели происходит поиск опорной точки с помощью алгоритма роя частиц. Инициализируется группа из i частиц случайным образом, после чего в ходе выполнения заданного количества итераций выполняется поиск оптимального решения. На

DOI: 10.24412/2410-9916-2021-3-38-59

Systems of Control, Communication and Security

ISSN 2410-9916

каждой из итераций частицы обновляют свое положение на основе двух параметров: pi - лучшее из известных положений частицы /; g - наилучшее известное состояние роя в целом. Когда оптимальные значения pi и g найдены, обновляются скорости частиц по формуле:

V, = ы + есои(0,1)[г, - х, ] + ежи(0,1)[рг - хг ],

где vi - вектор скорости частицы, ^ - лучшее найденное частицей положение, pi - лучшее положение из найденных всеми частицами роя, xi - текущее положение частицы, функция U возвращает случайное число от 0 до 1 включительно, коэффициенты ccog и csoc определяют значимость для частицы своего лучшего положения и лучшего среди всего роя положения, коэффициент си характеризует инерционные свойства частиц [14].

После расчета скорости частиц вычисляется их местоположение: X = X + V •

В случае, если расстояние от найденной опорной точки до препятствия меньше заданного, то выполняется повторный поиск с помощью алгоритма FS, который находит путь с наименьшей стоимостью от текущего узла и до промежуточных узлов и'. Список узлов рассчитывается посредством клеточной декомпозиции известной части среды. Также предполагается, что характеристики препятствий (длины сторон и их координаты) могут быть определены при первом попадании препятствия в область видимости робота. Оценка стоимости пути f до каждого из промежуточных узлов производится по формуле: / = g + ^

где g - оценка стоимости пути, И - оценка расстояния до целевой точки.

Результаты моделирования демонстрируют высокую эффективность данного алгоритма для планирования безопасной траектории движения робота, однако, авторами не учитывается дальность действия бортовых датчиков и сенсоров, которая существенно ограничивает область видимости робота, вследствие чего невозможно точно идентифицировать характеристики препятствия, которое встречает робот в процессе движения.

Исходя из анализа существующих решений, можно сделать вывод о том, что разработка методики планирования траектории движения группы мобильных роботов с учетом специфики децентрализованного управления и ограниченных возможностей МР является актуальной и своевременной задачей.

Постановка задачи

В работе рассматривается двухколесный мобильный робот с дифференциальным приводом, кинематическая схема которого представлена на рис. 1.

На рис. 1 х и у обозначают положение центра оси робота в глобальной системе координат, в обозначает направление движения мобильного робота относительно оси х в глобальной системе координат. Переменная есть радиус колес робота, а В - расстояние между колесами. И наконец, V и w являются линейной и угловой скоростью соответственно, а WL и WR - скорость вращения левого и правого колес соответственно.

DOI: 10.24412/2410-9916-2021-3-38-59

Системы управления,связи и безопасности №3. 2021

Systems of Control, Communication and Security ISSN 2410-9916

У

Гw

я

x

Рис. 1. Кинематическая схема мобильного робота

Данная модель в глобальной системе координат является одной из самых простых и минималистических представлений двухколесного мобильного робота. В данной модели, робот представлен тремя степенями свободы с вектором:

q = [ х, у,в\

Математическую модель МР можно представить, как:

i = \>cos в,

/л V /

V — vsin в.

Взаимосвязь между линейной и угловой скоростью и скоростями каждого из колес можно выразить следующим образом:

V = w + WL ),

W = rW (WR - WL )'

Подставив уравнения (1) в выражение (2), получаем следующую кинематическую модель робота [15]:

x = cosв(wR+wL),-^,

£>

В данной работе рассматривается группа Я, состоящая из N гомогенных мобильных роботов ггЕЯ, /={1, ..., N1, при этом:

- каждый робот ггЕЯ оснащен бортовыми устройством управления и датчиками расстояния (лидаром);

- каждый робот г^ЕЯ имеет ограниченную область видимости Ьг-, которую можно представить в виде окружности заданного радиуса гь с центром, совпадающим с позицией робота. Данные о наличии препятствий огЕО, получаемые от датчиков расстояния, и определение позиции соседних роботов г^-ЕЯ осуществляются только в области видимости Ь/ робота;

DOI: 10.24412/2410-9916-2021-3-38-59

Systems of Control, Communication and Security

ISSN 2410-9916

- под неизвестной замкнутой средой будем понимать ситуацию, когда препятствиями также считаются границы рабочей области группы роботов;

- в глобальной системе координат известны положение целевой точки х^у^ а также собственные координаты х(),у() каждого робота г группы в текущий момент времени I.

Процесс планирования движения группы МР предлагается рассмотреть как задачу пошаговой оптимизации текущего положения робота х1(С),у1(С) относительно целевой точки х^у^ Предполагаем, что время ? изменяется дискретно и принимает целочисленные значения 0,1,...,£, которые представляют собой интервалы между соседними дискретными моментами времени срабатывания бортовых устройств управления роботов ^ группы.

Состояние каждого робота riER описывается вектором, компонентами которого являются координаты текущей позиции в глобальной системе координат и угол поворота:

Х

В каждый момент времени ? на каждого из роботов оказывается управляющее воздействие посредством вектора управления, компонентами которого являются линейная и угловая скорости каждого робота riER^.

щ

Таким образом, в каждый момент времени ? состояние системы характеризуется вектором а управляющее воздействие - вектором и(). Под влиянием выбранного в момент ? управления (принятого решения) система переходит в следующий момент времени в новое состояние. Зависимость между выражениями (3) и (4) можно описать соотношением:

Х

Расстояние, которое характеризуется разницей между координатами робота на текущем и предыдущем шагах ? и соответственно будем называть сегментом траектории. Тогда общую длину траектории, пройденную группой роботов при движении к цели можно представить как сумму сегментов траектории, которые необходимо пройти на каждом шаге:

У = / + /г* + •••+/ •

С целью предотвращения коллизий между МР и столкновений с препятствиями вводятся ограничения на позицию роботов:

/ > -| > А,,(г * у;и] = ) ^

}Х - о\ >Ао,

где Ad - минимально допустимая дистанция между соседними роботами, А0 -минимально допустимая дистанция между роботом riER и препятствием, находящемся в области видимости Ь робота.

В качестве показателя эффективности примем длину траектории, необходимую для перемещения всех роботов группы из начального положения в целевое. Подставив выражения (5) в (6), получим аддитивную целевую функцию:

DOI: 10.24412/2410-9916-2021-3-38-59

Systems of Control, Communication and Security

ISSN 2410-9916

k

Y = ХЛ h

t=1

Таким образом, задачу пошаговой оптимизации процесса планирования траектории движения группы мобильных роботов в неизвестной замкнутой среде с препятствиями можно сформулировать так: определить для каждого робота группы riER набор управлений ui(1), ui(2), ... ,ui(k), переводящих систему из начального состояния s,(0), i={1,...,N} в конечное состояние Si(k), i={1,...,N} с учетом ограничений (7) так, чтобы целевая функция (8) достигла минимума:

Y ^ min.

Методика планирования траектории движения группы мобильных роботов в неизвестной замкнутой среде с препятствиями

Процесс планирования траектории движения группы мобильных роботов предлагается декомпозировать на две процедуры. Первая процедура - выбор управления - предполагает обработку результатов измерений датчиков расстояния, на основе которых рассчитывается промежуточная позиция в направлении цели так, чтобы обеспечить безаварийное движение робота.

Суть процедуры выбора управления состоит в следующем. В начале счи-тываются измерения датчиков расстояния, которые можно записать как вектор: L

где m - количество датчиков расстояний, установленных на корпусе каждого из роботов под углом а друг от друга. Предполагается, что один из датчиков lm измеряет расстояние до препятствия в направлении, совпадающим с ориентацией робота 6t (рисунок 2).

Рис. 2. Иллюстрация расположения датчиков расстояния

Углы 0т, определяющие направление измерений датчиков расстояний, могут быть рассчитаны следующим образом:

в.=—

та

Далее необходимо рассчитать координаты точек рт=(хт, Ут) в каждом из направлений вт, определяющих новый сегмент траектории движения робота гг-.

DOI: 10.24412/2410-9916-2021-3-38-59

Systems of Control, Communication and Security

ISSN 2410-9916

Координаты точек хт,ут рассчитываются на заданном расстоянии И от текущей позиции робота г-:

Хт = Хг (г) + к С0* 0т ,

уm = У, (г) + к ^0т •

Предполагается, что величина И задается изначально, при этом ее значение не должно превышать безопасную дистанцию до соседних роботов Д^ так как на шаге 1+1 их траектории могут пересекать друг друга, а также не должно превышать безопасную дистанцию до препятствий Д0:

Ь <Ао •

После этого необходимо найти наименьшее расстояние от каждой из точек рт до цели х& yg и выбрать соответствующую точку в качестве нового сегмента траектории движения р- робота г{.

^ =j

Vdm :

где dm - расстояние от точки рт до цели Xg, yg.

Тогда посредством применения ПИД-контроллера [16] можно рассчитать управляющий вектор для робота г-:

иг

где кр - коэффициент пропорционального звена регулятора, к - коэффициент интегрального звена, kd - коэффициент дифференциального звена, е(?) - сигнал ошибки, 2({) - текущее значение выходного сигнала, z(t-1) - предыдущее значение выходного сигнала.

Таким образом, блок-схема описанной выше процедуры для выбора управления представлена на рис. 3.

Однако, применение процедуры выбора управления может быть достаточно для эффективного планирования траектории движения в неизвестной замкнутой среде для одного мобильного робота. В случае группы роботов, где N>2 могут возникнуть ситуации, когда ни одна из возможных позиций при расчете нового сегмента траектории не соответствует ограничению (7). Так, на рис. 4 представлен пример проблемной ситуации, когда левый нижний робот оказался заблокирован между препятствиями и другими роботами группы: синие линии показывают возможные направления движения в соответствии с измерениями датчиков расстояния, а красные линии - направления движения, которые заблокированы препятствиями или другими агентами.

DOI: 10.24412/2410-9916-2021-3-38-59

Systems of Control, Communication and Security

ISSN 2410-9916

Рис. 3. Блок-схема процедуры выбора управления

Рис. 4. Иллюстрация проблемной ситуации

Для того, чтобы решить подобную проблемную ситуацию в рамках данной методики предлагается вторая процедура - выбор лидера, предназначенная для динамического определения индивидуального лидера для каждого из роботов ггЕЯ. Процедура состоит из следующих шагов. Вначале определяется множество позиций соседних роботов г^ группы, входящих в область видимости Ъ, Щ; /,У=(1, 2, ..., К), путем расчета расстояния до каждого из соседних роботов согласно формуле (11). Далее в качестве индивидуального лидера выбирается тот робот, позиция которого: 1) удовлетворяет ограничению (7); 2) имеет наименьшее расстояние до текущего робота (рассчитывается аналогично выражению (12)). Таким образом, позиция выбранного лидера считается новым

DOI: 10.24412/2410-9916-2021-3-38-59

Системы управления,связи и безопасности №3. 2021

Systems of Control, Communication and Security ISSN 2410-9916

сегментом траектории и на ее основе рассчитается управляющий вектор для робота г- по формуле (13). Данная процедура повторяется до выхода из проблемной ситуации, т.е. до того момента, когда появится возможность запустить процедуру выбора управления на основе измерений бортовых датчиков расстояния.

Однако, возможна ситуация, когда несколько роботов выберут одного и того же лидера на шаге t. Для избежания столкновения в подобной ситуации предлагается использовать процедуру выбора управления, описанную ранее, с целью корректировки позиции относительно индивидуального лидера, соседних роботов группы и препятствий. Блок-схема процедуры выбора лидера представлена на рис. 5.

Рис. 5. Блок-схема процедуры выбора лидера

DOI: 10.24412/2410-9916-2021-3-38-59

Systems of Control, Communication and Security

ISSN 2410-9916

Таким образом, блок-схема предложенной методики (рис. 6) состоит из условно последовательного использования процедур выбора лидера и управления. Критерием останова является достижение цели группой роботов.

Рис. 6. Блок-схема методики планирования траектории движения группы мобильных роботов в неизвестной замкнутой среде с препятствиями

Согласно обзору, проведенному в работе [17], наиболее объективными критериями оценки траектории движения робота являются длина и гладкость траектории, а также ее безопасность - расстояние до препятствий.

Длина траектории представляет собой общее расстояние, пройденное роботом от начальной точки до целевой. Математически этот критерий заключается в нахождении расстояния между двумя точками, которое рассчитывается с использованием формулы (11). Чем короче путь, тем меньше времени требуется роботу для перемещения от начальной точки к конечной.

Гладкость траектории можно определить как среднее значение углов поворота, которые необходимо сделать роботу при перемещении от начальной точки к конечной. Математически этот критерий заключается в определении угла между двумя линиями по формуле, показанной в уравнении (14). Кроме того, перед нахождением угла между любыми двумя линиями, углы поворота вычисляются по формуле, показанной в уравнении (15). Наконец, среднее значение угла поворота для оценки гладкости траектории можно найти по формуле (16). Меньший средний угол означает, что траектория довольно гладкая, чтобы робот мог перемещаться от начальной точки к конечной, не делая слишком много поворотов, особенно крутых.

Р'

tanö ' =

Р =

1+p Xt )p '

y. (t ) - y (t -1) (t ) - (t -1)'

DOI: 10.24412/2410-9916-2021-3-38-59

Systems of Control, Communication and Security

ISSN 2410-9916

—

k t=i

v kt=I

Оценка безопасности траектории заключается в вычислении кратчайшего расстояния от робота до препятствий, а также до других роботов. Кратчайшая дистанция до препятствий может быть получена на основе измерений датчиков расстояния согласно выражению (10):

[С, = а^тт ( Щ) ),

^l

I obs m

^ lobs lm

Аналогично в рамках процедуры выбора управления может быть получено значение минимальной дистанции до соседних роботов группы г^ по формулам (11) и (12).

Результаты моделирования метода

Для апробации предложенной методики была выполнена программная реализация на языке программирования Python. Визуализация траектории движения группы МР в неизвестной замкнутой среде с препятствиями, а также формирование графиков для оценки эффективности предложенной методики выполнены с помощью библиотеки Matplotlib. При проведении симуляции был использован компьютер со следующими характеристиками: процессор Intel Core i7-8550U с тактовой частотой 1,8 ГГц, 8 ГБ оперативной памяти. Использованы параметры моделирования, указанные в таблице 2. Моделирование предполагало серию экспериментов из 20 симуляций как для одного агента, так и для группы, состоящей из 5 роботов.

Таблица 2 - Параметры моделирования

Наименование параметра Значение

Количество роботов N 1 / 5

Количество экспериментов 20 / 20

Количество датчиков расстояния т 16

Расстояние между колесами робота В 0,2 м

Радиус колеса г^ 0,04 м

Коэффициент пропорционального звена ПИД-регулятора кр 1

Коэффициент интегрального звена ПИД-регулятора к 0,01

Коэффициент дифференциального звена ПИД-регулятора ка 0,1

Максимальная скорость движения V 0,4 м/с

Координаты стартовой точки (10, 2) =0,6

Координаты целевой точки

Минимальное расстояние до препятствий Ао 1,2 м

Минимальное расстояние до соседних роботов Аа 0,6 м

Область видимости Ь 3 м

Пример траекторий, полученных при моделировании одного агента с использованием предложенной методики (proposed methodology - PM) и алгоритма PSOFS представлены на рис. 7.

DOI: 10.24412/2410-9916-2021-3-38-59

Systems of Control, Communication and Security

ISSN 2410-9916

и  - PSOFS - РМ

II

II V Vi

II

II

-2 0 2 4 6 8 10 12

х[т]

Рис. 7. Визуализация траекторий движения мобильного робота в сравнении с алгоритмом РБОББ

Как видно из рис. 7, характеристики полученных траектории близки друг к другу, что также подтверждается графиками, отражающими усредненные результаты 20 экспериментов. Графически полученные результаты представлены на рис. 8.

— гЬОгЬ РМ

\ / \ / \ / \

\ /

5 10

Номер эксперимента

о

g 12.0 О)

га

Q-Ь

« 11.9

— PSOFS

/

у

\

- V

5 10 15

Номер эксперимента

а) б)

Рис. 8. Сравнительные результаты моделирования 20 экспериментов: а) плавность траектории движения мобильного робота; б) длина траектории

Среднее значение длины траектории 11,74 для предложенной методики означает, что в среднем для 20 экспериментов общее расстояние, пройденное роботом от начальной точки до цели, составило 11,74 м. Плавность траектории 0,62 означает, что путь достаточно плавный, чтобы робот мог перемещаться от начальной точки к цели, не делая слишком много поворотов, особенно крутых. Безопасность пути 1,2 означает, что кратчайшее расстояние от робота до любого из препятствий составляет не менее 1,2 м. Для сравнения с аналогом интерес также представляют максимальные и минимальные значения показателей качества планирования траектории, представленные в таблице 3.

DOI: 10.24412/2410-9916-2021-3-38-59

Systems of Control, Communication and Security

ISSN 2410-9916

Таблица 3 - Показатели качества планирования траектории для одного _мобильного робота в сравнении с алгоритмом РБОРБ_

Критерий PSOFS PM

Пройденное расстояние

Максимальное значение 12,23 11,76

Среднее значение 11,95 11,74

Минимальное значение 11,68 11,68

Гладкость траектории

Максимальное значение 0,99 0,63

Среднее значение 0,83 0,62

Минимальное значение 0,76 0,61

Расстояние до препятствий

Общее значение 1,2 1,2

Согласно данным, представленным в таблице 3, предложенная методика при использовании для одного агента позволяет генерировать практически равные по длине траектории движения робота (с разницей до 0,47 м в пользу предложенного метода). Однако разница в гладкости траектории (от 0,15 до 0,36 в пользу предложенного метода) говорит о том, что полученная траектория имеет меньше крутых поворотов, соответственно угловая скорость робота будет изменяться меньше и, как следствие, время, затраченное на осуществление перемещения будет меньше. Выигрыш в гладкости траектории можно объяснить тем фактом, что в предложенной методике отсутствует стохастическая компонента (коэффициенты с^ и Сое в алгоритме РБОРБ). Критерий безопасного движения робота относительно препятствий составил равное значение (1,2 м).

При проведении экспериментов с группой роботов было введено следующее изменение: в каждом эксперименте начальные позиции роботов группы генерировались случайным образом в окрестности стартовой точки (таблица 2) с соблюдением минимального расстояния до соседних роботов Аа. Визуализация траекторий, построенных при моделировании группы из 5 роботов с использованием сравниваемых методов, представлена на рис. 9.

ь  i — 1——1 -В-1 1—В-1 - PSOF5 - РМ

\  в

в

2 0 2 4 6 8 10 12

х[т]

Рис. 9. Визуализация траекторий движения группы из 5 мобильных роботов в сравнении с алгоритмом РБОРБ

DOI: 10.24412/2410-9916-2021-3-38-59

Systems of Control, Communication and Security

ISSN 2410-9916

Необходимо отметить тот факт, что при использовании алгоритма РБОББ в ряде случаев наблюдалось такое явление, как зацикливание робота вокруг одной точки (петля вокруг целевой точки на рис. 9), в результате чего роботам группы приходилось корректировать траекторию движения, тем самым увеличивая ее длину и снижая гладкость. Графически результаты моделирования траектории движения группы мобильных роботов в сравнении с аналогом представлены на рис. 10.

14.0 -

13.5 -

s

о. 13.0 -

о

1?

ш

(О CL 12.5 -

<П

S 12.0 -

¿t

11.5 -

11.0 -

— PSOFS РМ

\ / 1

—

5 10 15

Номер эксперимента

а) б)

Рис. 10. Сравнительные результаты моделирования траекторий движения группы мобильных роботов: а) длина траектории; б) гладкость траектории

Также алгоритм РБОББ не всегда обеспечивает требуемую безопасность траектории движения группы мобильных роботов как в отношении препятствий, так и других роботов группы (рис. 11). Однако, стоит отметить, что при моделировании рассматриваемых решений ни в одном из экспериментов не было выявлено наличия столкновений.

V \ — — >SOFS M

А V \ А

\1 \

5 10 15

Номер эксперимента

о 0.00090 ч

PSOFS РМ

-

1

Номер эксперимента

а) б)

Рис. 11. Безопасность траектории движения группы мобильных роботов: а) дистанция до других роботов; б) дистанция до препятствий

DOI: 10.24412/2410-9916-2021-3-38-59

Системы управления,связи и безопасности №3. 2021

Systems of Control, Communication and Security ISSN 2410-9916

Сравнение максимальных и минимальных значений показателей качества планирования траектории рассматриваемых решений представлено в таблице 4.

Таблица 4 - Результаты моделирования группы из 5 роботов

Критерий PSOFS PM

Пройденное расстояние, м

Максимальное значение 14,27 12,89

Среднее значение 13,19 12,03

Минимальное значение 11,59 10,85

Гладкость траектории

Максимальное значение 1,07 1,02

Среднее значение 0,98 0,89

Минимальное значение 0,92 0,78

Расстояние до препятствий, м

Максимальное значение 1,20 1,20

Среднее значение 1,19 1,20

Минимальное значение 1,19 1,20

Расстояние до других агентов, м

Максимальное значение 0,67 0,79

Среднее значение 0,46 0,68

Минимальное значение 0,32 0,53

Как видно из полученных результатов (таблица 4), применение предложенной методики для планирования траектории движения группы МР в неизвестной замкнутой среде дает существенное преимущество как по длине полученной траектории (от 0,74 до 1,38 м), так и по ее гладкости (разница показателя гладкости траектории от 0,05 до 0,14) по сравнению с алгоритмом РБОРБ. Разница в оценка расстояния до препятствий (0,01 м) может быть вызвана вычислительной погрешностью, поэтому предполагается, что сравниваемые решения одинаково эффективны при обходе препятствий. При этом предложенная методика в среднем обеспечивает требуемое расстояние до других роботов Аа, в отличие от аналога. Погрешность соблюдения дистанции до соседних роботов группы составляет до 0,07 м (12%) и 0,28 м (47%) для предложенной методики и алгоритма РБОРБ соответственно.

Выводы

Представленная методика позволяет осуществлять планирование траектории движения группы МР в неизвестной замкнутой среде с препятствиями с учетом ограниченной производительности бортовых датчиков и вычислительных устройств МР, а также специфики децентрализованного управления.

Элементом новизны предложенного решения является декомпозиция процесса планирования траектории движения группы МР на две условно последовательные процедуры выбора лидера и управления, отличающиеся от существующих методов низкой вычислительной сложностью и способом расчета сегментов траектории на основе измерений бортовых датчиков МР.

К исследованиям, в которых предлагается решение аналогичной задачи, можно отнести работы [8, 11]. В работе Б.С. Юдинцева [8] для решения задачи

DOI: 10.24412/2410-9916-2021-3-38-59

Системы управления,связи и безопасности №3. 2021

Systems of Control, Communication and Security ISSN 2410-9916

планирования траектории используется подход на основе искусственных нейронных сетей Хопфилда. Применение указанного математического аппарата накладывает существенные ограничения на минимальные системные требования вычислительной платформы МР, что исключает возможность реализации метода на устройствах с ограниченными вычислительными ресурсами (например, микроконтроллеры AVR или STM с разрядностью процессора менее 32-х бит). В случае использования МР с двухплатформенной конструкцией, как в работе [8], необходимо отметить возможность интеграции предложенных алгоритмов с другими алгоритмами поиска пути. Например, на стратегическом уровне (Raspberry) может быть реализовано вычисление «грубой» дискретной траектории движения, а перемещение робота по опорным точкам может осуществляется с помощью ресурсов исполнительного уровня (STM), используя предложенную методику. Подобный вариант реализации системы управления позволит освободить ресурсы вычислительной платформы стратегического уровня для выполнения задач картографии, распознавания, распределения задач между роботами группы и т.п.

Наиболее близкой работой по подходу к решению задачи, представленному в данной статье, является работа [11]. Данная работа направлена преимущественно на уменьшение расстояния, которое необходимо пройти роботам при планировании траектории в неизвестной среде, с соблюдением безопасной дистанции до препятствий. Однако авторами не учитывается маневрирование роботов при совместном обходе препятствий, что повышает вероятность столкновения не только робота с препятствиями, но и другими роботами.

На основе методики планирования траектории движения группы МР, предложенной в данной работе, планируется разработка методов и алгоритмов для выполнения мониторинга замкнутых территорий группой МР с поддержанием заданного строя с целью максимизации охвата территории бортовыми датчиками и сенсорами. Дополнительно планируется модификация представленной методики для возможности применения в трехмерном пространстве. В дальнейшем планируется разработка испытательного стенда для проведения полунатурных экспериментов по использованию предложенной методики и ее модификаций совместно с алгоритмами одновременной локализации и картографирования.

Литература

1. Гайдук А. Р., Капустян С. Г., Шаповалов И. О. Алгоритм управления движением группы мобильных роботов в условиях неопределенности // Инженерный вестник Дона. 2018. № 3 (50). С. 1-13.

2. Градецкий В. Г., Ермолов И. Л., Князьков М. М., Семёнов Е. А., Собольников С. А., Суханов А. Н. Вопросы взаимодействия роботов в группе при выполнении единой транспортной задачи // Материалы 10-й Всероссийской мультиконференции по проблемам управления (МКПУ-2017). - Дивноморское, 2017. - С. 265-267.

3. Васильев С. Н., Браништов С. А., Бузиков М. Э., Морозов Н. Ю. Групповое управление автономными мобильными аппаратами // Материалы

DOI: 10.24412/2410-9916-2021-3-38-59

Системы управления,связи и безопасности №3. 2021

Systems of Control, Communication and Security ISSN 2410-9916

10-й Всероссийской мультиконференции по проблемам управления (МКПУ2017). - Дивноморское, 2017. - С. 251-252.

4. Ющенко А. С., Михайлов Б. Б., Назарова А. В. Автономные мобильные роботы - навигация и управление // Известия Южного федерального университета. 2016. № 2 (175). С. 48-65.

5. Халимов Н. Р., Мефедов А. В. Распределенная сетецентрическая система управления группой ударных беспилотных летательных аппаратов // Системы управления, связи и безопасности. 2019. №3. С. 1-13. DOI: 10.24411/2410-9916-2019-10301.

6. Даринцев О. В., Мигранов А. Б. Двухуровневая интеллектуальная система планирования движений мобильных роботов // Труды Института механики им. Р.Р. Мавлютова Уфимского научного центра РАН. 2014. Т. 10. С. 50-54. DOI: 10.21662/uim2014.1.009.

7. Афанасьев И. М., Сагитов А. Г., Данилов И. Ю., Магид Е. А. Навигация гетерогенной группы роботов (БПЛА и БНР) через лабиринт в 3D симуляторе Gazebo методом вероятностной дорожной карты // Второй Всероссийский научно-практический семинар «Беспилотные транспортные средства с элементами искусственного интеллекта» Труды семинара. - Санкт-Петербург Политехника-сервис, 2015. - С. 18-25.

8. Юдинцев Б. С. Синтез нейросетевой системы планирования траекторий для группы мобильных роботов // Системы управления, связи и безопасности. 2019. № 4. С. 163-186. DOI: 10.24411/2410-9916-2019-10406.

9. Антонов В. О., Гурчинский М. М., Петренко В. И., Тебуева Ф. Б. Метод планирования траектории движения точки в пространстве с препятствием на основе итеративной кусочно-линейной аппроксимации // Системы управления, связи и безопасности. 2018. № 1. С. 168-182.

10. Пшихопов В. Х., Медведев М. Ю. Планирование движения группы подвижных объектов в двумерной среде с препятствиями // Известия Южного федерального университета. Технические науки. 2016. №2 (175). C. 6-22.

11. Wahab M. N. A., Lee C. M., Akbar M. F., Hassan F. H. Path Planning for Mobile Robot Navigation in Unknown Indoor Environments Using Hybrid PSOFS Algorithm // IEEE Access. 2020. Vol. 8. P. 161805-161815. DOI: 10.1109/ACCESS.2020.3021605.

12. Kennedy J., Eberhart R. Particle swarm optimization // Proceedings of ICNN'95 - International Conference on Neural Networks. 1995. Vol. 4. P. 19421948. DOI: 10.1109/ICNN.1995.488968.

13. Bjomsson Y., Enzenberger M., Holte R., Schaeffer J. Fringe Search: Beating A* at Pathfinding on Game Maps // Proceedings of the 2005 IEEE Symposium on Computational Intelligence and Games (CIG05). - Colchester, Essex, UK, 2005. - P. 125-132.

14. Павлов А. С., Рябцев С. С., Ахмедов С. Р., Трофимюк О. И. Разработка алгоритма децентрализованного управления группой беспилотных автомобилей на основе метода роя частиц // Труды VI Всероссийской научной конференции «Информационные технологии интеллектуальной поддержки принятия решений». - Уфа, 2018. - С. 168-173.

55

Системы управления,связи и безопасности №3. 2021

Systems of Control, Communication and Security ISSN 2410-9916

15. Петренко В. И., Тебуева Ф. Б., Павлов А. С., Антонов В. О. Метод планирования пути при формировании конфигурации многофункционального модульного робота с использованием роевой стратегии управления // Труды VII Всероссийской научной конференции «Информационные технологии интеллектуальной поддержки принятия решений». - Уфа, 2019. - С. 184-189.

16. Бройнль Т. Встраиваемые робототехнические системы: проектирование и применение мобильных роботов со встроенными системами управления. Ижевск: Ижевский институт компьютерных исследований, 2012. 520 с.

17. Zhang H.-Y., Lin W.-M., Chen A.-X. Path planning for the mobile robot: A review // Symmetry. 2018. Vol. 10. P. 434-450. DOI: 10.3390/sym10100450.

References

1. Gajduk A. R., Kapustyan S. G., Shapovalov I. O. Motion control algorithm for a group of mobile robots under conditions of uncertainty. Engineering journal of Don, 2018, no. 3, pp. 1-13 (in Russian).

2. Gradeckij V. G., Ermolov I. L., Knyaz'kov M. M., Semyonov E. A., Sobol'nikov S. A., Suhanov A. N. Voprosy vzaimodejstviya robotov v gruppe pri vypolnenii edinoj transportnoj zadachi [Issues of interaction of robots in a group when performing a transport task]. Materialy 10 Vserossijskoj mul'tikonferencii po problemam upravleniya (MKPU-2017) [Proceedings of the 10th All-Russian Multiconference on Control Problems (MMP-2017)]. Divnomorskoe, 2017, pp. 265267 (in Russian).

3. Vasil'ev S. N., Branishtov S. A., Buzikov M. E., Morozov N. Yu. Gruppovoe upravlenie avtonomnymi mobilnymi apparatami [Control of autonomous mobile robot groups]. Materialy 10 Vserossijskoj mul'tikonferencii po problemam upravleniya (MKPU-2017) [Proceedings of the 10th All-Russian Multiconference on Control Problems (MMP-2017)]. Divnomorskoe, 2017, pp. 251-252 (in Russian).

4. Yushchenko A. S., Mihajlov B. B., Nazarova A. V. Avtonomnye mobilnye roboty navigatsiya i upravlenie [Autonomous mobile robots - navigation and control]. Izvestiya SFedU. Engineering Sciences, 2016, no. 2, pp. 48-65 (in Russian).

5. Halimov N. R., Mefedov A. V. The distributed network-centric control system of an attacking unmanned aerial vehicles group. Systems of Control, Communication and Security, 2019, no. 3, pp. 1-13. DOI: 10.24411/2410-9916-201910301 (in Russian).

6. Darincev O. V., Migranov A. B. Dvuhurovnevaya intellektual'naya sistema planirovaniya dvizhenij mobil'nyh robotov [Two-level intelligent motion planning system for mobile robots]. Trudy Instituta mekhaniki im. R.R. Mavlyutova Ufimskogo nauchnogo centra RAN, 2014, t. 10, pp. 50-54. DOI: 10.21662/uim2014.1.009 (in Russian).

7. Afanas'ev I. M., Sagitov A. G., Danilov I. YU., Magid E. A. Navigaciya geterogennoj gruppy robotov (BPLA i BNR) cherez labirint v 3D simulyatore Gazebo metodom veroyatnostnoj dorozhnoj karty [Navigation of a heterogeneous group of robots (UAV and UGR) through the maze in 3D Gazebo simulator using the probabilistic roadmap method]. Vtoroj Vserossijskij nauchno-prakticheskij seminar

DOI: 10.24412/2410-9916-2021-3-38-59

Системы управления,связи и безопасности №3. 2021

Systems of Control, Communication and Security ISSN 2410-9916

«Bespilotnye transportnye sredstva s elementami iskusstvennogo intellekta» Trudy seminara [Second All-Russian Scientific and Practical Seminar "Unmanned Vehicles with Artificial Intelligence Elements" Seminar Proceedings]. Sankt-Peterburg Politekhnika-servis, 2015. Pp. 18-25. (in Russian).

8. Yudintsev B. S. Synthesis of a neural network path planning system for a group of mobile robots. Systems of Control, Communication and Security, 2019, no. 4, pp. 163-186. DOI: 10.24411/2410-9916-2019-10406 (in Russian).

9. 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. Systems of Control, Communication and Security, 2018, no. 1, pp. 168-182 (in Russian).

10. Pshikhopov V. Kh., Medvedev M. Yu. Planirovanie dvizheniya gruppy podvizhnyh ob'ektov v dvumernoj srede s prepyatstviyami [Path planning for a group of vehicles in the 2D environment with obstacles]. Izvestiya SFedU. Engineering Sciences, 2016, vol. 2 (175), pp. 6-22 (in Russian).

11. Wahab M. N. A., Lee C. M., Akbar M. F., Hassan F. H. Path Planning for Mobile Robot Navigation in Unknown Indoor Environments Using Hybrid PSOFS Algorithm. IEEE Access, 2020, vol. 8, pp. 161805-161815. DOI: 10.1109/ACCESS.2020.3021605.

12. Kennedy J., Eberhart R. Particle swarm optimization. Proceedings of ICNN'95 - International Conference on Neural Networks, 1995, vol. 4, pp. 19421948. DOI: 10.1109/ICNN.1995.488968.

13. Bjornsson Y., Enzenberger M., Holte R., Schaeffer J. Fringe Search: Beating A* at Pathfinding on Game Maps. Proceedings of the 2005 IEEE Symposium on Computational Intelligence and Games (CIG05). Colchester, Essex, UK, 2005, pp. 125-132.

14. Pavlov A. S., Ryabcev S. S., Ahmedov S. R., Trofimyuk O. I. Razrabotka algoritma decentralizovannogo upravleniya gruppoj bespilotnyh avtomobilej na osnove metoda roya chastic [Development of an algorithm for decentralized control of a group of unmanned vehicles based on the particle swarm method]. Trudy VI Vserossijskoj nauchnoj konferencii «Informacionnye tekhnologii intellektual'noj podderzhki prinyatiya reshenij» [The 6th All-Russian Scientific Conference on Information Technologies for Intelligent Decision Making Support]. Ufa, 2018, pp. 168-173 (in Russian).

15. Petrenko V. I., Tebueva F. B., Pavlov A. S., Antonov V. O. Metod planirovaniya puti pri formirovanii konfiguracii mnogofunkcional'nogo modul'nogo robota s ispol'zovaniem roevoj strategii upravleniya [Path planning method forming the configuration of a multifunctional modular robot using a swarm control strategy]. Trudy VII Vserossijskoj nauchnoj konferencii «Informacionnye tekhnologii intellektual'noj podderzhki prinyatiya reshenij» (s priglasheniem zarubezhnyh uchenyh) [The 7th All-Russian Scientific Conference on Information Technologies for Intelligent Decision Making Support]. Ufa, 2019, pp. 184-189 (in Russian).

16. Brojnl' T. Vstraivaemye robototekhnicheskie sistemy: proektirovanie i primenenie mobil'nyh robotov so vstroennymi sistemami upravleniya [Embedded

DOI: 10.24412/2410-9916-2021-3-38-59

Системы управления,связи и безопасности №3. 2021

Systems of Control, Communication and Security ISSN 2410-9916

robotic systems: design and use of mobile robots with embedded control systems]. Izhevsk, 2012. 520 p. (in Russian).

17. Zhang H.-Y., Lin W.-M., Chen A.-X. Path planning for the mobile robot: A review. Symmetry, 2018, vol. 10, pp. 434-450. DOI: 10.3390/sym10100450.

Статья поступила 23 апреля 2021 г.

Информация об авторе

Павлов Андрей Сергеевич - соискатель ученой степени кандидата технических наук. Преподаватель кафедры прикладной математики и компьютерной безопасности. Федеральное государственное автономное образовательное учреждение высшего образования «Северо-Кавказский федеральный университет». Область научных интересов: робототехника, искусственный интеллект, математическое моделирование, системный анализ. E-mail: losde5530@gmail.com

Адрес: 355017, Россия, Ставрополь, ул. Пушкина, д. 1.

Methodology for Planning the Trajectory of a Group of Mobile Robots in Unknown Closed Environment with Obstacles

A. S. Pavlov

Purpose. Use of group of mobile robots in complex applied problems can significantly increase the efficiency of solving such problems. At the same time, the possibilities of group application of mobile robots in unknown environments are determined, first of all, by the level of development of methods of group decentralized control. The well-known algorithms for trajectory planning of a group of mobile robots in an unknown environment have high computational complexity or do not allow finding the trajectory that is optimal along the path length while maintaining a safe distance from obstacles and other robots in the group. The aim of the work is to increase the efficiency of solving the problem of the trajectory planning of a group of mobile robots from the initial position to the final one in an unknown environment with obstacles, taking into account the limited capabilities (sensory and computational) of mobile robots and the specifics of decentralized control. Methods. The solution to the problem is carried out on the basis of step-by-step optimization of the current position of each robot in the group with respect to a given goal. The proposed method analyzes the possibility of movement of each robot in a group in directions determined by means of analytical geometry based on measurements of on-board distance sensors. If it is impossible to move in any of the directions, the position of the neighboring robots of the group is assessed and the position of the leader is selected as an intermediate state, while the trajectory is adjusted based on measurements of the on-board distance sensors in the presence of obstacles. The described sequence of actions in the proposed method is iteratively repeated for the movement of each robot in the group from the initial state to the intermediate state, and from the intermediate to the final one. The stopping criterion is the achievement of the target position by each robot in the group. Novelty. Element of novelty in this work is the procedure for calculating trajectory segments based on the choice of an intermediate state and correcting the trajectory taking into account the measurements of the onboard distance sensors of the group's mobile robots. Results. The proposed method makes it possible to search for the trajectory of a group of mobile robots in an unknown environment while ensuring a given distance to obstacles and other robots in the group. The use of the presented algorithms allows a group of robots to maintain a high efficiency of task performance while functioning in conditions of information deficiency. The reliability of the results was confirmed in the course of software simulation. Practical relevance. The solution of the problem taking into account the specified features made it possible to reduce the computational complexity of the method, as well as to remove restrictions on the use of trajectory planning algorithms for mobile robots with low-performance on-board sensors and computing devices. The pre-

DOI: 10.24412/2410-9916-2021-3-38-59

Системы управления,связи и безопасности №3. 2021

Systems of Control, Communication and Security ISSN 2410-9916

sented algorithms are implemented as software in the Python programming language which can be used in the modeling of decentralized control systems for a group of mobile robots.

Key words: trajectory planning, obstacle avoidance, multi-agent systems, decentralized control, mobile robots.

Information about Author

Andrey Sergeevich Pavlov - Doctoral Student. Lecturer at the Department of Applied Mathematics and Computer Security. Federal Autonomous Educational Institution of Higher Education North Caucasus Federal University. Field of research: robotics, artificial intelligence, mathematical modeling, systems analysis. E-mail: losde5530@gmail.com

Address: Russia, 355017, Stavropol, Pushkina str. 1.

DOI: 10.24412/2410-9916-2021-3-38-59