eng
Выпуск #4/2020
А. ТОЛОК, М. ЛОКТЕВ, А. СЫЧЕВА, П. ХАРЛАНОВА, Л. СИЗОВА
МОДЕЛИРОВАНИЕ АЛГОРИТМОВ УПРАВЛЕНИЯ ГРУППАМИ МОБИЛЬНЫХ РОБОТОВ СРЕДСТВАМИ ФУНКЦИОНАЛЬНО-ВОКСЕЛЬНОГО МЕТОДА
МОДЕЛИРОВАНИЕ АЛГОРИТМОВ УПРАВЛЕНИЯ ГРУППАМИ МОБИЛЬНЫХ РОБОТОВ СРЕДСТВАМИ ФУНКЦИОНАЛЬНО-ВОКСЕЛЬНОГО МЕТОДА
Просмотры: 1274
DOI: 10.22184/2499-9407.2020.21.04.76.81
Рассматривается пример описания одного из алгоритмов децентрализованной навигации больших групп агентов ORCA средствами функционально-воксельного метода, а также случай построения области допустимых скоростей для предотвращения столкновений для двух мобильных роботов. На основе графических образ-моделей разработан подход к построению области допустимых скоростей роботов на плоскости.
Рассматривается пример описания одного из алгоритмов децентрализованной навигации больших групп агентов ORCA средствами функционально-воксельного метода, а также случай построения области допустимых скоростей для предотвращения столкновений для двух мобильных роботов. На основе графических образ-моделей разработан подход к построению области допустимых скоростей роботов на плоскости.
Теги: functional voxel method (fvm) mobile robots multi-agent systems navigation algorithms orca algorithm алгоритм orca алгоритмы навигации многоагентные системы мобильные роботы функционально-воксельный метод (фвм)
Моделирование алгоритмов управления группами мобильных роботов средствами функционально-воксельного метода
Алексей ТОЛОК, Михаил ЛОКТЕВ, Анастасия СЫЧЕВА,
Полина ХАРЛАНОВА, Людмила СИЗОВА
Рассматривается пример описания одного из алгоритмов децентрализованной навигации больших групп агентов ORCA средствами функционально-воксельного метода, а также случай построения области допустимых скоростей для предотвращения столкновений для двух мобильных роботов. На основе графических образ-моделей разработан подход к построению области допустимых скоростей роботов на плоскости.
Введение
Принципы, решающие задачи навигации в многоагентных системах, сопоставимы со взаимодействием социальных общественных групп. Их тоже можно делить на централизованные и децентрализованные [1]. При централизованном подходе действия агентов зачастую рассматриваются с точки зрения выполнения совместной цели общими усилиями. В этом случае агентов собирают в группы, зачастую выбирая лидера, и решают задачу совместным взаимодействием команды. Однако, существует ряд ситуаций, при которых требуется децентрализованная система планирования действий агентов [2], в том числе и система децентрализованной навигации. В таких системах у каждого агента присутствует собственная цель (например, агенты службы доставки). Алгоритм решения такой задачи предполагает учет обстановки по всей сцене и принимает самостоятельное решение относительно поведения остальных агентов. И так происходит с каждым отдельно взятым агентом. Такой алгоритм обязательно применяет оптимизацию решения относительно поставленной цели и множества возникающих ограничений на его пути.
Подобный принцип используется при применении стратегии стайного поведения [3]. В стае достигается более плотное расположение агентов, в результате этого группа занимает меньший объем пространства. Группа по своей форме может быть вытянута вдоль траектории движения или иметь неправильную форму, но члены группы могут вступать в нее или выходить в любой момент, в зависимости от степени совпадения направления движения группы и собственной цели члена группы.
Децентрализованный алгоритм навигации ORCA
Одним из представителей алгоритмов подобного класса является алгоритм ORCA. Он базируется на построении линейных полупространств относительно каждого агента, формирующих на пересечении область возможных решений для применения оптимизационных принципов линейного математического программирования. В работе рассмотрен подход к построению алгоритма ORCA средствами функционально-воксельного моделирования на основе аналитических принципов R-функционального построения области сложной геометрии [4]. На этом этапе открываются новые задачи по эффективной реализации такой модели на программно-техническом уровне.
Алгоритм ORCA впервые был представлен в 2011 году [5] как принцип децентрализованной навигации для больших групп агентов, который обеспечивает достаточное условие для избегания столкновений между агентами с индивидуальными целями. Более того, каждый агент принимает на себя минимум половину «ответственности» за избежание столкновения с другим агентом [1]. Данный принцип базируется на более ранней работе [6], посвященной формированию области столкновений – скоростного препятствия VO (Velocity Obstacles). Скоростным препятствием является область, образованная векторами скоростей и приводящая к столкновению агентов в заданном промежутке времени.
Последующие научные исследования других авторских коллективов использовали алгоритм ORCA при решении различных прикладных задач. Так, в работе [7] рассматривается применение различных алгоритмов навигации для взаимного локального уклонения виртуальных агентов в видеоиграх. Симуляция автомобильного движения на перекрестке на основе алгоритма ORCA рассматривается в работе [8]. Помимо этого, разрабатывались собственные модифицированные алгоритмы. В работе [9] представлен новый безаварийный подход к навигации неголономных роботов на основе ORCA, учитывающий особенности кинематики исследуемых роботов.
Функционально-воксельное моделирование в задачах навигации
Представленные работы основаны на значительном количестве сложных геометрических расчетов на каждом этапе работы алгоритма ORCA. Более того, для большой группы агентов требуется производить взаимный расчет возможных скоростей смещения для каждой пары роботов с последующим вычислением на их основе новой скорости с помощью линейного программирования.
Упрощение математических операций традиционно считается преимуществом функционально-воксельного моделирования, когда часть вычислений заменяется формированием графического образа с заложенной в нем всей необходимой локальной информацией. Метод функционально-воксельного моделирования (ФВМ), описанный в монографии А.В. Толока [10], позволяет организовать компьютерное представление области функции соразмерными воксельными образами на основе разложения функции на локальные геометрические характеристики в каждой точке воксельного пространства.
Данный подход основан на графическом представлении данных об объекте, которое использует аналитический способ описания моделей. При этом функционально-воксельное представление области функции значительно упрощает дальнейшую компьютерную обработку применительно к задачам компьютерного геометрического моделирования с сохранением преимуществ полноты представления геометрии объекта.
Подобные исследования успешно проводились при реализации задач локальной оптимизации пути к цели с обходом препятствий [11]. Также следует отметить успехи в разработке функционально-воксельного моделирования задач математического программирования [12]. На основе предложенного подхода уже были реализованы различные постановки задачи поиска пути [13–14], представленные на рис. 1.
На рис. 1а представлен пример градиентного спуска, как способа определения траектории к цели из любой точки пространства. На рис. 1б продемонстрирован пример так называемой вариативной трассировки, когда на основе анализа функционального пространства определяются характерные элементы рельефа функции (хребты-лощины), по которым и будут проходить возможные маршруты, плавно огибающие препятствия.
Функционально-воксельное представление области столкновения может быть рассчитано предварительно, а в ходе работы алгоритма будут применяться лишь простые вычисления над полученными локальными геометрическими характеристиками модели, что значительно упрощает вычислительный процесс. Такую модель можно построить единожды и далее использовать как графический шаблон при моделировании отношений двух роботов, заданных в пространстве.
Аналитическое представление скоростного препятствия
Рассмотрим конкретный пример взаимного расположения роботов A и B со своими эффективными радиусами RA и RB, равными единице, где PB (–2, 3) и PA (2, –3) (рис. 2). Привяжем положение роботов к системе скоростных координат. Для этого перенесем начало координат в точку PA, тогда изменит свои координаты PB (–4, 6). Начальные скорости обоих роботов определяются векторами vA (vAx=1,5, vAy= 1,0) и vB (vBx=3,0, vBy= –1,5), а разность этих векторов, образующая вектор сближения роботов, определяется вектором v(A-B) (v(A-B)x= ‒ 1,5, v(A-B)y= 2,5), как показано на рис. 3.
Разность координат центров агентов даст новую точку (PA–PB), которая в данном случае будет совпадать с положением агента B. В этой точке построим новую окружность с общим радиусом двух роботов (RA+RB). Прямые Pr1(x, y) и Pr2(x, y) определяют полупространства (RA+RB) для прямых – касательных к окружности с радиусом исходящих из начала координат. Чтобы описать их местоположение, достаточно вычислить углы и
.
Уравнения прямых Pr1(x, y) и Pr2(x, y) примут вид:
Pr1 (x,y)=y–tg(α+β)x, (1)
Pr2 (x,y)=tg(α–β)x–y. (2)
Образуемая между ними область определяет зону возможного столкновения при попадании в нее вектора разности скоростей v(A–B). Однако следует учитывать динамику происходящего процесса. Для этого стоит ввести параметр временного промежутка взаимодействия роботов τ, позволяющий уточнить положение критической зоны с учетом расстояния между двумя роботами. Введение такого параметра позволяет уточнить зону предупреждения столкновения. Введем значение τ = 2,0, как промежуток заведомого (запасного) времени, для которого требуется определить область возможных столкновений. Положение новой окружности, определяющей начало опасной зоны, задается точкой центра (PA–PB)/τ и радиусом (PA+PB)/τ (рис. 4). Полученная окружность будет определять ближайшую к роботу А границу зоны столкновения с роботом В на промежутке времени τ.
Для построения алгоритма определения принадлежности конечной точки вектора разности скоростей v(A–B) области полученной зоны столкновения необходимо эту зону разбить на два участка. Первый участок контролирует попадание вектора v(A–B) в зону , ограниченную прямыми: Pr1, Pr2, Pr3 и Pr4, где Pr3 и Pr4 – перпендикуляры, опущенные на прямые Pr1, Pr2 из центра окружности с радиусом (рис. 4). Уравнения этих прямых описываются так:
, (3)
. (4)
На начальном этапе алгоритма (условие 1) вычисляем значения Pr1(v(A–B)x, v(A–B)y) и Pr2(v(A–B)x,
v(A–B)y) с помощью уравнений (1) и (2). Если оба значения положительны, то точка с координатами (v(A–B)x, v(A–B)y) располагается между прямыми Pr1 и Pr2, а значит, подлежит дальнейшему изучению. В противном случае эта точка не попадает в зону и робот А может двигаться относительно робота В с той же скоростью и в том же направлении.
В случае, если точка (v(A–B)x, v(A–B)y) оказалась между этими прямыми, то следует уточнить ее положение проверкой на положительный знак значения любого из выражений (условие 2): Pr3(v(A–B)x, v(A–B)y)≥0 или Pr4(v(A–B)x, v(A–B)y)≥0. Выполнения второго условия достаточно, чтобы приступить к определению направления нормали к ближайшей границе искомой области ORCAA|B для вычисления вектора корректировки скорости робота А, требуемого для обеспечения выхода из зоны . Обозначим такой вектор корректировки . Направление совпадает с направлением , а длина определяется расстоянием до ближайшей границы зоны . Ближайшая граница в этом случае рассматривается как минимальное расстояние до прямых Pr1 и Pr2:
, (5)
, (6)
, (7)
, (8)
, (9)
, (10)
d(dx,dy)=min(d1 (dx1,dy1),d2 (dx2,dy2 )). (11)
Область ORCAA|B здесь определяется уравнением прямой, параллельной выбранной границе (например, Pr1(x,y)), перенесенной в точку с координатами (vAx+dx,vAy+dy):
ORCAA|B(x,y)=(y–(vAy+dy))–tg(α+β)(x–(vAx+dx)). (12)
Если после выполнения первого условия не выполняется второе, следует продолжить рассматривать другие условия, позволяющие уточнить отношение точки (v(A–B)x, v(A–B)y) к области .
Уравнение Circleτ (x, y) представляет собой уравнение окружности с радиусом (RA+RB)/τ и центром в точке (PA+PB)/τ, а значит, описывается выражением:
. (13)
Часть этой окружности, не входящая в рассмотренную ранее область , продолжает описывать ее границу. Поэтому выражение Circleτ (v(A–B)x, v(A–B)y)≥0 обеспечивает третье условие принадлежности области как проверку принадлежности точки (v(A–B)x, v(A–B)y) области окружности Circleτ (x, y).
При выполнении третьего условия ближайшей точкой на границе для точки (v(A–B)x, v(A–B)y) является точка на окружности с радиусом (RA+RB)/τ. Чтобы определить направление к такой точке как направление нормали, достаточно построить прямую, ортогональную прямой, проходящей через точки (v(A–B)x, v(A–B)y) и (xB/τ, yB/τ), и перенести ее в точку вектора vA, смещенную на координаты (wcosγ,wsinγ), где:
,
.
В результате имеем:
. (14)
Как видно из рассуждений, представленный алгоритм позволяет описать ситуацию взаимной корректировки скорости для робота по отношению к одному из встречных роботов. Полная картина определяется пересечением всех областей ORCA, построенных для каждого из ближайших роботов сцены, влияющих на корректировку окончательного направления и скорости движения. Полученная область возможных решений требует применения средств оптимизации для получения единственно верного вектора скорости. Любая оптимизационная постановка имеет целевую функцию, которая выражается основным направлением к цели. Такая постановка вполне разрешима средствами линейного математического программирования [12].
Для проверки реализации расчета области на конкретно заданном примере была промоделирована область в системе функционально-воксельного моделирования RANOK. Для этого к описанию областей был применен R-функциональный аппарат теоретико-множественных операций над функциями [15], позволивший выделить области с положительным знаком значений:
VOA|B=Pr1∧Pr2∧(Pr3∨Pr4 )∨Circleτ. (15)
На рис. 5 демонстрируется объединение в пространстве скоростей области и области ORCAA|B, наглядно демонстрирующих результат вычислений поставленной задачи.
На рис. 6 представлены графические образ-модели (М-образы), описывающие локальное уравнение в точках области столкновений. М-образы являются одним из ключевых инструментов графического анализа метода функционально-воксельного моделирования [16]. Каждый из этих образов характеризует компоненту нормали, построенную в 4-мерном пространстве. Чтобы описать такое локальное уравнение, необходимо нормальный вектор в каждой точке рассматриваемого пространства представить в четвертом измерении.
Для получения угла наклона области достаточно в точке приложения вектора разности скоростей рассмотреть компоненту двухмерного нормального вектора на оси X (т.е. cosαo2), перенормированную по формуле:
cosα 4x+cosβ 4y+cosγ 4z=cosδ 4, (16)
. (17)
Заключение
Проведенные исследования доказали возможность рассматривать задачу управления группой автономных мобильных роботов (или других агентов) с помощью функционально-воксельного метода. Полученная функционально-воксельная модель выступает в роли шаблона, которая несет полную информацию о локальных геометрических характеристиках в каждой точке пространства. Эта информация позволяет без труда определять необходимое направление области допустимых скоростей . Система управления мобильного робота может использовать данный шаблон для определения направления движения, что позволит отказаться от ряда численных вычислений по сравнению с классическим описанием алгоритма. Применение представленных аналитических подходов делает возможным рассмотрение подобных задач без привязки к размерности пространства.
Литература
1. Дергачев С. А. Экспериментальное исследование реактивного алгоритма навигации для групп агентов – ORCA // Сборник научных трудов 17-й национальной конференции по искусственному интеллекту с международным участием (КИИ-2019), г. Ульяновск. Т. 1. 21–25 октября 2019. С. 102.
2. Яковлев К. С., Баскин Е. С., Андрейчук А. А. Метод автоматического планирования совокупности траекторий для навигации беспилотных транспортных средств // Управление большими системами. Выпуск. – М.: ИПУ РАН, 2015.
3. Харланова П. М. Исследование применения стратегии стайного поведения в ограниченных пространствах // Труды 16-й Всероссийской школы-конференция молодых ученых «Управление большими системами» (УБС’2019, Тамбов). Тамбов: Издательский центр ФГБОУ ВО «ТГТУ», 2019. С. 175–178.
4. Тимофеев А. В., Юсупов Р. М. Принципы построения интегрированных систем мультиагентной навигации и интеллектуального управления мехатронными роботами // Information Technologies & Knowledge. 2011. Т. 5. № 3.
5. Jur van den Berg, Stephen J. Guy, Ming Lin, Dinesh Manocha. Reciprocal n-body Collision Avoidance // Robotics Research: The 14th International Symposium ISRR, Springer Tracts in Advanced Robotics, v. 70, Springer-Verlag, May 2011, pp. 3–19.
6. Fiorini P., Shiller Z. Motion planning in dynamic environments using Velocity Obstacles. Int. Journal of Robotics Research 17(7), pp. 760–772, 1998.
7. Lake A. T. et al. Reciprocal collision avoidance and navigation for video games. 2012.
8. Schaefer M. Planning and coordination in driving simulation // Acta Polytechnica CTU Proceedings. 2015. Т. 2. № 2. С. 40–44.
9. Mao R., Gao H., Guo L. A Novel Collision-Free Navigation Approach for Multiple Nonholonomic Robots Based on ORCA and Linear MPC //Mathematical Problems in Engineering. 2020. Т. 2020.
10. Толок А. В. Функционально-воксельный метод в компьютерном моделировании / Под ред. акад. РАН С.Н. Васильева. – М.: ФИЗМАТЛИТ, 2016. 112 с. ISBN: 978-5-9221-1680-0.
11. Васильев С. Н., Локтев М. А., Толок А. В., Толок Н. Б., Ульянов С. А. К планированию маршрутов в 3D-среде с многовариантной моделью // Труды СПИИРАН, Вып. 2 (45). ISSN 2078-9181. – СПб, 2016. С. 5–25.
12. Толок А. В., Толок Н. Б. Mathematical Programming Problems Solving by Functional Voxel Method // Automation and Remote Control. 2018. V. 79. № 9. PP. 1703–1712.
13. Локтев М. А. Особенности применения функционально-воксельного моделирования в задачах поиска пути с препятствиями // Информационные технологии в проектировании и производстве. 2016. № 1. С. 45–49.
14. Григорьев С. Н., Толок А. В., Толок Н. Б. Построение градиентного алгоритма локального перебора точек на основе метода функционально-воксельного моделирования // Программирование. 2017. № 5. С. 32–38.
15. Рвачев В. Л. Теория R-функций и некоторые ее приложения. – Киев: Наукова думка, 1982. 552 с.
16. Толок А. В. Графические образы-модели в информационных технологиях // Прикладная информатика. 2009. № 4. С. 31–40.
ТОЛОК Алексей Вячеславович –
доктор технических наук, главный научный сотрудник лаборатории компьютерной графики Института проблем управления им. В. А. Трапезникова РАН
ЛОКТЕВ Михаил Александрович –
кандидат технических наук, старший научный сотрудник лаборатории компьютерной графики Института проблем управления им. В. А. Трапезникова РАН
СЫЧЕВА Анастасия Антоновна –
младший научный сотрудник лаборатории компьютерной графики Института проблем управления им. В. А. Трапезникова РАН
ХАРЛАНОВА Полина Михайловна –
младший научный сотрудник лаборатории Систем логического управления Института проблем управления им. В.А. Трапезникова РАН
СИЗОВА Людмила Николаевна –
ведущий инженер-программист лаборатории компьютерной графики Института проблем управления им. В. А. Трапезникова РАН
Алексей ТОЛОК, Михаил ЛОКТЕВ, Анастасия СЫЧЕВА,
Полина ХАРЛАНОВА, Людмила СИЗОВА
Рассматривается пример описания одного из алгоритмов децентрализованной навигации больших групп агентов ORCA средствами функционально-воксельного метода, а также случай построения области допустимых скоростей для предотвращения столкновений для двух мобильных роботов. На основе графических образ-моделей разработан подход к построению области допустимых скоростей роботов на плоскости.
Введение
Принципы, решающие задачи навигации в многоагентных системах, сопоставимы со взаимодействием социальных общественных групп. Их тоже можно делить на централизованные и децентрализованные [1]. При централизованном подходе действия агентов зачастую рассматриваются с точки зрения выполнения совместной цели общими усилиями. В этом случае агентов собирают в группы, зачастую выбирая лидера, и решают задачу совместным взаимодействием команды. Однако, существует ряд ситуаций, при которых требуется децентрализованная система планирования действий агентов [2], в том числе и система децентрализованной навигации. В таких системах у каждого агента присутствует собственная цель (например, агенты службы доставки). Алгоритм решения такой задачи предполагает учет обстановки по всей сцене и принимает самостоятельное решение относительно поведения остальных агентов. И так происходит с каждым отдельно взятым агентом. Такой алгоритм обязательно применяет оптимизацию решения относительно поставленной цели и множества возникающих ограничений на его пути.
Подобный принцип используется при применении стратегии стайного поведения [3]. В стае достигается более плотное расположение агентов, в результате этого группа занимает меньший объем пространства. Группа по своей форме может быть вытянута вдоль траектории движения или иметь неправильную форму, но члены группы могут вступать в нее или выходить в любой момент, в зависимости от степени совпадения направления движения группы и собственной цели члена группы.
Децентрализованный алгоритм навигации ORCA
Одним из представителей алгоритмов подобного класса является алгоритм ORCA. Он базируется на построении линейных полупространств относительно каждого агента, формирующих на пересечении область возможных решений для применения оптимизационных принципов линейного математического программирования. В работе рассмотрен подход к построению алгоритма ORCA средствами функционально-воксельного моделирования на основе аналитических принципов R-функционального построения области сложной геометрии [4]. На этом этапе открываются новые задачи по эффективной реализации такой модели на программно-техническом уровне.
Алгоритм ORCA впервые был представлен в 2011 году [5] как принцип децентрализованной навигации для больших групп агентов, который обеспечивает достаточное условие для избегания столкновений между агентами с индивидуальными целями. Более того, каждый агент принимает на себя минимум половину «ответственности» за избежание столкновения с другим агентом [1]. Данный принцип базируется на более ранней работе [6], посвященной формированию области столкновений – скоростного препятствия VO (Velocity Obstacles). Скоростным препятствием является область, образованная векторами скоростей и приводящая к столкновению агентов в заданном промежутке времени.
Последующие научные исследования других авторских коллективов использовали алгоритм ORCA при решении различных прикладных задач. Так, в работе [7] рассматривается применение различных алгоритмов навигации для взаимного локального уклонения виртуальных агентов в видеоиграх. Симуляция автомобильного движения на перекрестке на основе алгоритма ORCA рассматривается в работе [8]. Помимо этого, разрабатывались собственные модифицированные алгоритмы. В работе [9] представлен новый безаварийный подход к навигации неголономных роботов на основе ORCA, учитывающий особенности кинематики исследуемых роботов.
Функционально-воксельное моделирование в задачах навигации
Представленные работы основаны на значительном количестве сложных геометрических расчетов на каждом этапе работы алгоритма ORCA. Более того, для большой группы агентов требуется производить взаимный расчет возможных скоростей смещения для каждой пары роботов с последующим вычислением на их основе новой скорости с помощью линейного программирования.
Упрощение математических операций традиционно считается преимуществом функционально-воксельного моделирования, когда часть вычислений заменяется формированием графического образа с заложенной в нем всей необходимой локальной информацией. Метод функционально-воксельного моделирования (ФВМ), описанный в монографии А.В. Толока [10], позволяет организовать компьютерное представление области функции соразмерными воксельными образами на основе разложения функции на локальные геометрические характеристики в каждой точке воксельного пространства.
Данный подход основан на графическом представлении данных об объекте, которое использует аналитический способ описания моделей. При этом функционально-воксельное представление области функции значительно упрощает дальнейшую компьютерную обработку применительно к задачам компьютерного геометрического моделирования с сохранением преимуществ полноты представления геометрии объекта.
Подобные исследования успешно проводились при реализации задач локальной оптимизации пути к цели с обходом препятствий [11]. Также следует отметить успехи в разработке функционально-воксельного моделирования задач математического программирования [12]. На основе предложенного подхода уже были реализованы различные постановки задачи поиска пути [13–14], представленные на рис. 1.
На рис. 1а представлен пример градиентного спуска, как способа определения траектории к цели из любой точки пространства. На рис. 1б продемонстрирован пример так называемой вариативной трассировки, когда на основе анализа функционального пространства определяются характерные элементы рельефа функции (хребты-лощины), по которым и будут проходить возможные маршруты, плавно огибающие препятствия.
Функционально-воксельное представление области столкновения может быть рассчитано предварительно, а в ходе работы алгоритма будут применяться лишь простые вычисления над полученными локальными геометрическими характеристиками модели, что значительно упрощает вычислительный процесс. Такую модель можно построить единожды и далее использовать как графический шаблон при моделировании отношений двух роботов, заданных в пространстве.
Аналитическое представление скоростного препятствия
Рассмотрим конкретный пример взаимного расположения роботов A и B со своими эффективными радиусами RA и RB, равными единице, где PB (–2, 3) и PA (2, –3) (рис. 2). Привяжем положение роботов к системе скоростных координат. Для этого перенесем начало координат в точку PA, тогда изменит свои координаты PB (–4, 6). Начальные скорости обоих роботов определяются векторами vA (vAx=1,5, vAy= 1,0) и vB (vBx=3,0, vBy= –1,5), а разность этих векторов, образующая вектор сближения роботов, определяется вектором v(A-B) (v(A-B)x= ‒ 1,5, v(A-B)y= 2,5), как показано на рис. 3.
Разность координат центров агентов даст новую точку (PA–PB), которая в данном случае будет совпадать с положением агента B. В этой точке построим новую окружность с общим радиусом двух роботов (RA+RB). Прямые Pr1(x, y) и Pr2(x, y) определяют полупространства (RA+RB) для прямых – касательных к окружности с радиусом исходящих из начала координат. Чтобы описать их местоположение, достаточно вычислить углы и
.
Уравнения прямых Pr1(x, y) и Pr2(x, y) примут вид:
Pr1 (x,y)=y–tg(α+β)x, (1)
Pr2 (x,y)=tg(α–β)x–y. (2)
Образуемая между ними область определяет зону возможного столкновения при попадании в нее вектора разности скоростей v(A–B). Однако следует учитывать динамику происходящего процесса. Для этого стоит ввести параметр временного промежутка взаимодействия роботов τ, позволяющий уточнить положение критической зоны с учетом расстояния между двумя роботами. Введение такого параметра позволяет уточнить зону предупреждения столкновения. Введем значение τ = 2,0, как промежуток заведомого (запасного) времени, для которого требуется определить область возможных столкновений. Положение новой окружности, определяющей начало опасной зоны, задается точкой центра (PA–PB)/τ и радиусом (PA+PB)/τ (рис. 4). Полученная окружность будет определять ближайшую к роботу А границу зоны столкновения с роботом В на промежутке времени τ.
Для построения алгоритма определения принадлежности конечной точки вектора разности скоростей v(A–B) области полученной зоны столкновения необходимо эту зону разбить на два участка. Первый участок контролирует попадание вектора v(A–B) в зону , ограниченную прямыми: Pr1, Pr2, Pr3 и Pr4, где Pr3 и Pr4 – перпендикуляры, опущенные на прямые Pr1, Pr2 из центра окружности с радиусом (рис. 4). Уравнения этих прямых описываются так:
, (3)
. (4)
На начальном этапе алгоритма (условие 1) вычисляем значения Pr1(v(A–B)x, v(A–B)y) и Pr2(v(A–B)x,
v(A–B)y) с помощью уравнений (1) и (2). Если оба значения положительны, то точка с координатами (v(A–B)x, v(A–B)y) располагается между прямыми Pr1 и Pr2, а значит, подлежит дальнейшему изучению. В противном случае эта точка не попадает в зону и робот А может двигаться относительно робота В с той же скоростью и в том же направлении.
В случае, если точка (v(A–B)x, v(A–B)y) оказалась между этими прямыми, то следует уточнить ее положение проверкой на положительный знак значения любого из выражений (условие 2): Pr3(v(A–B)x, v(A–B)y)≥0 или Pr4(v(A–B)x, v(A–B)y)≥0. Выполнения второго условия достаточно, чтобы приступить к определению направления нормали к ближайшей границе искомой области ORCAA|B для вычисления вектора корректировки скорости робота А, требуемого для обеспечения выхода из зоны . Обозначим такой вектор корректировки . Направление совпадает с направлением , а длина определяется расстоянием до ближайшей границы зоны . Ближайшая граница в этом случае рассматривается как минимальное расстояние до прямых Pr1 и Pr2:
, (5)
, (6)
, (7)
, (8)
, (9)
, (10)
d(dx,dy)=min(d1 (dx1,dy1),d2 (dx2,dy2 )). (11)
Область ORCAA|B здесь определяется уравнением прямой, параллельной выбранной границе (например, Pr1(x,y)), перенесенной в точку с координатами (vAx+dx,vAy+dy):
ORCAA|B(x,y)=(y–(vAy+dy))–tg(α+β)(x–(vAx+dx)). (12)
Если после выполнения первого условия не выполняется второе, следует продолжить рассматривать другие условия, позволяющие уточнить отношение точки (v(A–B)x, v(A–B)y) к области .
Уравнение Circleτ (x, y) представляет собой уравнение окружности с радиусом (RA+RB)/τ и центром в точке (PA+PB)/τ, а значит, описывается выражением:
. (13)
Часть этой окружности, не входящая в рассмотренную ранее область , продолжает описывать ее границу. Поэтому выражение Circleτ (v(A–B)x, v(A–B)y)≥0 обеспечивает третье условие принадлежности области как проверку принадлежности точки (v(A–B)x, v(A–B)y) области окружности Circleτ (x, y).
При выполнении третьего условия ближайшей точкой на границе для точки (v(A–B)x, v(A–B)y) является точка на окружности с радиусом (RA+RB)/τ. Чтобы определить направление к такой точке как направление нормали, достаточно построить прямую, ортогональную прямой, проходящей через точки (v(A–B)x, v(A–B)y) и (xB/τ, yB/τ), и перенести ее в точку вектора vA, смещенную на координаты (wcosγ,wsinγ), где:
,
.
В результате имеем:
. (14)
Как видно из рассуждений, представленный алгоритм позволяет описать ситуацию взаимной корректировки скорости для робота по отношению к одному из встречных роботов. Полная картина определяется пересечением всех областей ORCA, построенных для каждого из ближайших роботов сцены, влияющих на корректировку окончательного направления и скорости движения. Полученная область возможных решений требует применения средств оптимизации для получения единственно верного вектора скорости. Любая оптимизационная постановка имеет целевую функцию, которая выражается основным направлением к цели. Такая постановка вполне разрешима средствами линейного математического программирования [12].
Для проверки реализации расчета области на конкретно заданном примере была промоделирована область в системе функционально-воксельного моделирования RANOK. Для этого к описанию областей был применен R-функциональный аппарат теоретико-множественных операций над функциями [15], позволивший выделить области с положительным знаком значений:
VOA|B=Pr1∧Pr2∧(Pr3∨Pr4 )∨Circleτ. (15)
На рис. 5 демонстрируется объединение в пространстве скоростей области и области ORCAA|B, наглядно демонстрирующих результат вычислений поставленной задачи.
На рис. 6 представлены графические образ-модели (М-образы), описывающие локальное уравнение в точках области столкновений. М-образы являются одним из ключевых инструментов графического анализа метода функционально-воксельного моделирования [16]. Каждый из этих образов характеризует компоненту нормали, построенную в 4-мерном пространстве. Чтобы описать такое локальное уравнение, необходимо нормальный вектор в каждой точке рассматриваемого пространства представить в четвертом измерении.
Для получения угла наклона области достаточно в точке приложения вектора разности скоростей рассмотреть компоненту двухмерного нормального вектора на оси X (т.е. cosαo2), перенормированную по формуле:
cosα 4x+cosβ 4y+cosγ 4z=cosδ 4, (16)
. (17)
Заключение
Проведенные исследования доказали возможность рассматривать задачу управления группой автономных мобильных роботов (или других агентов) с помощью функционально-воксельного метода. Полученная функционально-воксельная модель выступает в роли шаблона, которая несет полную информацию о локальных геометрических характеристиках в каждой точке пространства. Эта информация позволяет без труда определять необходимое направление области допустимых скоростей . Система управления мобильного робота может использовать данный шаблон для определения направления движения, что позволит отказаться от ряда численных вычислений по сравнению с классическим описанием алгоритма. Применение представленных аналитических подходов делает возможным рассмотрение подобных задач без привязки к размерности пространства.
Литература
1. Дергачев С. А. Экспериментальное исследование реактивного алгоритма навигации для групп агентов – ORCA // Сборник научных трудов 17-й национальной конференции по искусственному интеллекту с международным участием (КИИ-2019), г. Ульяновск. Т. 1. 21–25 октября 2019. С. 102.
2. Яковлев К. С., Баскин Е. С., Андрейчук А. А. Метод автоматического планирования совокупности траекторий для навигации беспилотных транспортных средств // Управление большими системами. Выпуск. – М.: ИПУ РАН, 2015.
3. Харланова П. М. Исследование применения стратегии стайного поведения в ограниченных пространствах // Труды 16-й Всероссийской школы-конференция молодых ученых «Управление большими системами» (УБС’2019, Тамбов). Тамбов: Издательский центр ФГБОУ ВО «ТГТУ», 2019. С. 175–178.
4. Тимофеев А. В., Юсупов Р. М. Принципы построения интегрированных систем мультиагентной навигации и интеллектуального управления мехатронными роботами // Information Technologies & Knowledge. 2011. Т. 5. № 3.
5. Jur van den Berg, Stephen J. Guy, Ming Lin, Dinesh Manocha. Reciprocal n-body Collision Avoidance // Robotics Research: The 14th International Symposium ISRR, Springer Tracts in Advanced Robotics, v. 70, Springer-Verlag, May 2011, pp. 3–19.
6. Fiorini P., Shiller Z. Motion planning in dynamic environments using Velocity Obstacles. Int. Journal of Robotics Research 17(7), pp. 760–772, 1998.
7. Lake A. T. et al. Reciprocal collision avoidance and navigation for video games. 2012.
8. Schaefer M. Planning and coordination in driving simulation // Acta Polytechnica CTU Proceedings. 2015. Т. 2. № 2. С. 40–44.
9. Mao R., Gao H., Guo L. A Novel Collision-Free Navigation Approach for Multiple Nonholonomic Robots Based on ORCA and Linear MPC //Mathematical Problems in Engineering. 2020. Т. 2020.
10. Толок А. В. Функционально-воксельный метод в компьютерном моделировании / Под ред. акад. РАН С.Н. Васильева. – М.: ФИЗМАТЛИТ, 2016. 112 с. ISBN: 978-5-9221-1680-0.
11. Васильев С. Н., Локтев М. А., Толок А. В., Толок Н. Б., Ульянов С. А. К планированию маршрутов в 3D-среде с многовариантной моделью // Труды СПИИРАН, Вып. 2 (45). ISSN 2078-9181. – СПб, 2016. С. 5–25.
12. Толок А. В., Толок Н. Б. Mathematical Programming Problems Solving by Functional Voxel Method // Automation and Remote Control. 2018. V. 79. № 9. PP. 1703–1712.
13. Локтев М. А. Особенности применения функционально-воксельного моделирования в задачах поиска пути с препятствиями // Информационные технологии в проектировании и производстве. 2016. № 1. С. 45–49.
14. Григорьев С. Н., Толок А. В., Толок Н. Б. Построение градиентного алгоритма локального перебора точек на основе метода функционально-воксельного моделирования // Программирование. 2017. № 5. С. 32–38.
15. Рвачев В. Л. Теория R-функций и некоторые ее приложения. – Киев: Наукова думка, 1982. 552 с.
16. Толок А. В. Графические образы-модели в информационных технологиях // Прикладная информатика. 2009. № 4. С. 31–40.
ТОЛОК Алексей Вячеславович –
доктор технических наук, главный научный сотрудник лаборатории компьютерной графики Института проблем управления им. В. А. Трапезникова РАН
ЛОКТЕВ Михаил Александрович –
кандидат технических наук, старший научный сотрудник лаборатории компьютерной графики Института проблем управления им. В. А. Трапезникова РАН
СЫЧЕВА Анастасия Антоновна –
младший научный сотрудник лаборатории компьютерной графики Института проблем управления им. В. А. Трапезникова РАН
ХАРЛАНОВА Полина Михайловна –
младший научный сотрудник лаборатории Систем логического управления Института проблем управления им. В.А. Трапезникова РАН
СИЗОВА Людмила Николаевна –
ведущий инженер-программист лаборатории компьютерной графики Института проблем управления им. В. А. Трапезникова РАН
Отзывы читателей
