Алгоритмы управления мобильными роботами по неполным данным в многоагентных сценариях Семакова Анна Анатольевна

Содержание к диссертации

Введение

Глава 1. Кооперативное отслеживание изолинии неизвестного скалярного поля группой неголономных роботов 31

1.1 Отслеживание изолинии отдельным роботом 32

1.1.1 Постановка задачи и закон управления 32

1.1.2 Предположения, необходимые условия и основной результат 35

1.2 Постановка задачи кооперативного отслеживания изолинии и закон управления 42

1.3 Теорема об отсутствии столкновений между роботами 50

1.4 Теорема об отсутствии кластеризации роботов 52

1.5 Теорема о равномерном распределении роботов 63

1.6 Компьютерное моделирование 71

1.7 Результаты экспериментов с реальными роботами 75

Глава 2. Децентрализованное распределение группы мобильных роботов вдоль эквидистанты неизвестной области 80

2.1 Управление отдельным роботом с помощью угловой скорости 83

2.1.1 Постановка задачи и закон управления 83

2.1.2 Предположения, необходимые условия и основной результат 85

2.2 Постановка задачи многоагентного децентрализованного отслеживания границы области 90

2.3 Закон управления 91

2.4 Отсутствие столкновений между роботами и кластеризации 94

2.5 Теорема о равномерном распределении роботов 97

2.6 Компьютерное моделирование 104

2.7 Результаты экспериментов с реальными роботами 107

Глава 3. Окружение группы движущихся целей неголономным мобильным роботом 110

3.1 Описание системы и постановка задачи 112

3.2 Предположения и необходимые условия 116

3.3 Основные результаты 125

3.4 Частные случаи 132

3.4.1 Окружение группы целей, двигающихся вокруг стационарного объекта 132

3.4.2 Окружение группы целей, двигающихся вдоль неизвестной кривой с сохранением жесткой групповой формации 137

3.5 Результаты компьютерного моделирования 140

Глава 4. Алгоритм близкого окружения группы движущихся целей методом отслеживания динамических границ 145

4.1 Локализация и отслеживание изолинии неизвестного динамического скалярного поля 146

4.1.1 Постановка задачи и закон управления 146

4.1.2 Предположения и необходимые условия 148

4.1.3 Формализация задачи 150

4.1.4 Сходимость алгоритма управления 151

4.1.5 Некоторые характеристики динамического поля 152

4.1.6 Настройка регулятора 156

4.1.7 Доказательства теорем 4.1.2 и 4.1.1. 158

4.1.8 Пример отслеживания динамической изолинии: локализация и окружение мобильной цели по измерениям расстояния до нее 170

4.2 Локализация и близкое окружение группы движущихся целей 172

4.2.1 Формальная постановка задачи, предположения и необходимые условия 172

4.2.2 Сходимость алгоритма управления 176

4.2.3 Настройка регулятора 178

4.3 Компьютерное моделирование 183

Заключение 187

Список сокращений и условных обозначений 189

Список литературы 190

Список рисунков 208

• Постановка задачи кооперативного отслеживания изолинии и закон управления
• Постановка задачи многоагентного децентрализованного отслеживания границы области
• Окружение группы целей, двигающихся вокруг стационарного объекта
• Некоторые характеристики динамического поля

Введение к работе

Актуальность темы. Растущий интерес к простым и универсальным робототехническим платформам c ограниченными (вычислительными, сенсорными, коммуникационными) ресурсами и одновременно — к работе в незнакомых средах, в том числе сложных и динамических, мотивирует привлекательность ресурсосберегающих и локальных методов планирования движения к «глобальной» цели. Однако следствием характерной для них сложности анализа итога применения является дефицит гарантий глобальной сходимости с возможностью отказа, а преодоление этой проблемы требует развития теоретических основ, а также методологии анализа и синтеза локальных алгоритмов. К перспективным направлениям компенсации ограниченных возможностей и компетенций отдельных роботов относится и их кооперация в рамках многоагентного ансамбля, что в свою очередь определяет потребность в специализированных алгоритмах управления для координации роботов ради решения общей задачи, часто — за счет единых для всех агентов алгоритмических рецептов.

С ситуацией такого рода связан ряд сценариев, где элементом сцены является неизвестное скалярное поле, доступны только точечные измерения его значений, и при этом требуется, чтобы роботы (или один робот) обнаружили изолинию с заданным значением поля, переместились к ней и затем двигались вдоль нее. Среди примеров подобных задач — обнаружение и мониторинг границы области критического загрязнения, геологические исследования, локализация и сопровождение точечной цели или протяженной области по измерениям только расстояния до нее. Теории синтеза и анализа управляющих систем, ориентированных на задачи такого типа, посвящены исследования N. Leonard, M. Krstic, M. Arcak, B. Anderson, J. Baillieul, T. Sugie, A. Bertozzi, A. Nehorai, а также (в части алгоритмов координации многих агентов) А.М. Леонтовича, И.И. Пятецкого-Шапиро, П.С. Щербакова, A. Garulli и других известных ученых.

Практические проблемы измерения и оценивания градиента поля мотивировали развитие «неградиентных» подходов (градиент не измеряется и не оценивается). Прототипическим контекстом для них является ситуация либо единичного робота с единственным датчиком значения поля,

либо группы таких роботов в отсутствие коммуникации между ними. Ряд неградиентных алгоритмов практикует переключение между заданными направлениями движения в зависимости от интервала, в который попадает значение поля (A. Bertozzi, A. Joshi, T. Ashley, M. Rendas). Результатом является зигзагообразная траектория и возникающая вследствие взаимно аннулирующих боковых смещений проблема экономии ресурсов. Для таких подходов характерна опора на эвристику без гарантий достижения цели и завершенного обоснования закона управления. Имеющиеся математически обоснованные законы управления либо подразумевают неограниченное управление и подкреплены обоснованием только локальной устойчивости в радиальных гармонических полях (J. Baillieul et.al.), либо используют скользящие режимы (А.С. Матвеев, А.В. Савкин et.al.), применение которых эффективно, однако создает угрозы нежелательных эффектов: так называемого чаттеринга и избыточной активности в канале управления. Несмотря на то, что способы их устранения и подавления хорошо исследованы, значительный интерес представляет возможность решения задачи посредством непрерывных регуляторов.

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

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

работ по данной теме предполагает доступ робота к полным относительным координатам целей. Вместе с тем значительный интерес представляет динамическое окружение на основании измерения только расстояний до целей, когда задача допускает трактовку как отслеживание изолинии искусственного поля, сконструированного из этих расстояний. Однако ранее известные алгоритмы динамического окружения целей по неполным о них данным (M. Deghat, L. Xia, B. Anderson, Y. Hong) имели дело только со случаем угловых данных о целях, простейшей модели робота (интегратор первого порядка с неограниченным управлением) и статичных целей.

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

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

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

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

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

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

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

2. Децентрализованный алгоритм управления линейными скоростями неголономных и не способных к коммуникации роботов с целью их равномерного распределения по эквидистанте неизвестной области; теорема об условиях нелокальной сходимости алгоритма.

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

4. Метод -предельных распределений асимптотического исследования внутригруппового поведения многоагентных систем.

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

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

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

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

Научная новизна. Все результаты, выносимые на защиту, являются новыми и получены автором лично.

¹Наглядные результаты компьютерного моделирования в виде анимации, а также видеозаписи экспериментов с реальными роботами доступны по ссылке

Теоретическая и практическая значимость. Результаты

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

Апробация работы. Основные положения работы докладывались на семинарах кафедры теоретической кибернетики Санкт-Петербургского государственного университета и на следующих международных конференциях: 6-ом международном конгрессе IEEE по ультрасовременным телекоммуникациям и системам управления (Санкт-Петербург, 2014); 10-ой Азиатской конференции по проблемам управления (Малайзия, 2015); 1-ой конференции IFAC по проблемам моделирования, идентификации и управления нелинейными системами (Санкт-Петербург, 2015); 35-ой Китайской конференции по проблемам управления (Китай, 2016).

Часть результатов получена в ходе работ по грантам СПбГУ (проект № 6.38.230.2015), РНФ (проект № 14-29-00142) и Австралийского Совета по науке (the Australian Research Council, project № DP130103898).

Публикации. Основные результаты по теме диссертации изложены в восьми работах [1–]. Из них пять работ [1–5] опубликованы в научных периодических изданиях, индексируемых Scopus и Web of Science, и три работы [6–] — в сборниках трудов ежегодных международных конференций; эти три работы также проиндексированы системой Scopus.

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

В работах [;5;;] диссертанту принадлежит разработка алгоритмов управления, доказательство ключевых результатов и компьютерное моделирование; соавторам принадлежит выбор направления исследований, техническая постановка задач и рекомендации по выбору общих методов.

²Доклад удостоен второго места в конкурсе на лучшую работу конференции.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и одного приложения. Полный объем диссертации составляет 221 страницу, включая 56 рисунков и 6 таблиц. Список литературы содержит 168 наименований.

Постановка задачи кооперативного отслеживания изолинии и закон управления

Следовательно, чтобы цель управления была достижима, необходимо выполнение последнего неравенства. При этом, с одной стороны, в типичном случае ограниченной изолинии перемещающийся по ней со скоростью v(t) v 0 робот зачерчивает всю изолинию, а с другой стороны, профиль его скорости v(t) относится к числу неопределенностей, и для скорости известны лишь верхняя v и нижняя v границы. Поэтому обсуждаемое неравенство естественно распространить, во-первых, на всю изолинию, и во-вторых, на все значения скорости из известного диапазона [v,v]. В результате приходим к следующему условию: \K(V)\V и Vr Є I (do).

Предыдущий анализ касался возможности оставаться на требуемой изолинии. Однако цель управления предполагает регулирование «выходной переменной» d(t) = D[r(t)] к желаемому значению. Разрешимость таких задач традиционно увязывают с наличием у «выхода» некоторой степени управляемости. Например, робот должен иметь возможность перейти от текущей изолинии как к большим, так и к меньшим значениям поля. Поскольку нахождение на изолинии эквивалентно d = О Ф d! = 0, такая управляемость означает возможность произвольно манипулировать знаком 4 d 38

Поэтому последнее неравенство из леммы 1.1.2 гарантирует необходимую управляемость, если в нем знак заменить на . Предполагаем, что эта управляемость имеет место во всей рабочей зоне Ж робота, которую для удобства характеризуем крайними значениями d- d+ поля в ее пределах: Ж = {г : d- D(r) d+}, d- d+. (1.5) Естественно, предполагаем, что требуемая изолиния содержится в этой зоне d- do d+. Суммируя, приходим к следующему условию. Предположение 1.1.1. Существуют константы Ър 0 и А 0 такие, что р = VD b l и \я\ v и —А в области (1.5).

Тогда VD ф 0 и \н\ v и всюду в рабочей зоне Ж. Если рабочая зона ограничена, последние два неравенства эквивалентны предположению 1.1.1. Действительно, тогда эта зона компактна, следовательно, непрерывные функции V-D(r) и (т ) достигают в ней наименьшего и наибольшего значений в некоторых точках Гу)гж Є Ж соответственно, и остается взять Ър := V-D(ry) 0 и А := й—\к{гж)\ v 0. В случае неограниченной рабочей зоны предположение 1.1.1 не только требует выполнения обсуждаемых строгих неравенств, но и оговаривает, что они не вырождаются в нестрогие, даже если точка рабочей зоны, в которой они рассматриваются, убегает на бесконечность.

По тем же соображениям следующее предположение автоматически выполнено в случае ограниченной рабочей зоны и необходимо, только если эта зона Ж неограничена. Предположение 1.1.2. В рабочей зоне (1.5) параметры поля тр и пр ограничены: существуют константы ЪТ 0 и Ъп 0 такие, что \тр\ Ът и \пр\ Ъп для всех г Є Ж.

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

Как обычно, положительным направлением поворота вектора считаем направление против часовой стрелки. По предположению 1.1.1 для любого диска D С Ж при движении вдоль любой кривой j С 1) угол поворота градиента VD однозначно определен конечными точками а и Ъ кривой; этот угол назовем углом поворота градиента при перемещении в диске D от а к Ь. (Здесь использованы три факта: 1) векторное поле г ь- VD(r) не имеет особенностей в диске D, т.е. градиент всюду определен и не обращается в ноль; 2) если кривая непрерывно деформируется так, что ее концы остаются на месте, и в процессе деформации она не проходит через особые точки поля, то угол поворота векторного поля вдоль этой кривой в процессе деформации не меняется; 3) если две кривые с общими концами лежат в диске D, то любую из них можно превратить в другую кривую за счет непрерывной деформации, в процессе которой кривая не покидает этот диск и ее концы остаются на месте.)

Предположение 1.1.3. Диск D радиусом RD := (v + v)u l + 3(v — v)u l с центром в начальном положении робота лежит в области (1.5). Угол поворота градиента при перемещении в пределах этого диска меньше ТТ.

Здесь 7Г выбрано для простоты и определенности, это значение может быть увеличено за счет согласованного увеличения радиуса R-j). Предположение 1.1.3 может быть значительно ослаблено, если движение начинается вблизи желаемой изолинии (и в нужном направлении). Наконец, оно может быть в принципе опущено, если в итоге требуется только локальная сходимость.

Пусть выполнены предположения 1.1.1—1.1.3, робот управляется согласно (1.2), а параметры 7 и /І := 7 регулятора выбраны так, что управления a(t) rfo достигается, и по истечении определенного времени робот постоянно движется вдоль изолинии в отрицательном направлении. При /І — 0 левая часть последнего неравенства в (1.6) стремится к 0. Следовательно, при произвольном 7 0 выполнение (1.6) всегда можно обеспечить выбором достаточно малого /І = Ьр б (т.е. достаточно малого 5 0). Этим фактом можно руководствоваться при экспериментальной настройке регулятора. Если доступны оценки bn,bT,bp,A параметров поля, то (1.6) можно трактовать как явные количественные рекомендации.

По теореме 1.1.1 регулятор (1.2) обеспечивает сходимость к желаемой изолинии независимо от временного профиля линейной скорости v(-) Є [v,v]. Другими словами, настройка регулятора и гарантии сходимости к изолинии опираются только на и и t), при этом имеет место сходимость для всех профилей из промежутка [v,v]. Именно это свойство используем в следующих параграфах для регулирования расстояний между роботами, принимая для этого линейную скорость как управляющую переменную: в результате сходимость к изолинии не разрушается.

Как было отмечено ранее, доказательства результатов параграфа 1.1 опущены. Однако некоторые соображения, связанные с доказательством теоремы 1.1.1, в дальнейшем будут необходимы для доказательства ключевых результатов главы 1. Поэтому приведем их здесь. Соответствующие доказательства могут быть найдены в [137].

Постановка задачи многоагентного децентрализованного отслеживания границы области

Рассмотрим «виртуального» робота vir(p )), который находится в точке р и ориентирован по касательной к 70 в отрицательном направлении. Согласно предположению 1.4.1 вспомогательная зона учета любого vir (р ) не содержит других виртуальных роботов pf ф р 1, а расстояние сицт от pf до радиусов, ограничивающих основную зону учета vir(p )), не равно нулю. По непрерывности эти утверждения распространяются и на реальных роботов в моменты времени t Є (tk — г), tk -\- Т)), где к и г] 0 достаточно большое и малое соответственно. Отсюда следует, что вспомогательная зона учета любого робота т пуста (может, за исключением переднего радиуса), в то время как в основной зоне учета может находиться робот / из другого кластера, в этом случае pm(ri) UJ := min тшроо р шца; Rv} 0. Пусть t Є (tk — т), tk + г)). Если основная зона учета робота j пуста, то р = Rv, и в силу (1.12) Vj — Vi = V(р ) — [V(p ) — bi] V{UJ) — V{]\rj — Ti) , lim (VJ — Vi) V(UJ) — 1 (0), (1.27) к—? +oo, г/— 0 где предел касается только тех t Є (tk — Tj, tk+T]), для которых рассматриваемая ситуация имеет место. Если эта зона не пуста, она может содержать только роботов m из других кластеров. Поэтому р о;, и V(p ) — V(Pi) У(ш) (llrj ri\\)i lim (pi — bj) 0, к— -\-oo,r/— 0 т.е. (1.27) снова выполнено. Следовательно, существуют такие ко и ц 0, что 1 Vj(t) — Vi(t) к, := — I V(ш) — V(0) І 0 V t Є (tk — T]}tk + т])} к ко. Аналогично (1.21), уменьшая ту и увеличивая &о (если необходимо), добьемся, чтобы d к — \\Гп — тЛ\ — cos (р V t Є Uk — і], tk + і]), к ко at 2 Тогда т\-(і. + т?) — 7 (ti. + 7?) # 7 cos ее V& ко, что нарушает iii) в следствии 1.4.1. Полученное противоречие завершает доказательство. И Доказательство теоремы 1.4.1: Утверждение i) обосновывает теорема 1.1.2; утверждение ii) следует из лемм 1.4.1 и 1.4.4; утверждение iii) вытекает из ii). И

Дальнейшая характеристика итогового распределения роботов на изолинии 0 подразумевает сравнение расстояний вдоль этой кривой между соседними парами роботов; например, равномерное распределение означает, что для всех пар это расстояние одно и то же. Вместе с тем измерение расстояния вдоль неизвестной изолинии неизвестного поля является сложной задачей для робота. В этой связи предложенный регулятор использует измерения расстояний не вдоль изолинии, а по прямой. Поскольку аналитическая характеристика итогового распределения требует явной, и желательно — максимально точной, оценки ц расстояния между роботами вдоль кривой при t +оо, и вместе с тем закон управления не использует обратной связи от этого расстояния, такая характеристика оказывается достаточно проблематичной в случае общей кривой 7. (Этот вопрос исследуется далее в параграфе 1.6 с помощью компьютерного моделирования.) Теоретическое же исследование данного параграфа, ограничим ситуацией, когда целевая линия уровня 7 представляет собой окружность. В этом случае (1.9) состоит только из одной компоненты связности: т = 1, и 7? = 7. Следовательно, все роботы принадлежат одной группе G\ и сходятся к окружности 7.

Чтобы обеспечить равномерное распределение вдоль окружности, радиус Rv основной зоны учета не должен быть чрезмерно большим. Для конкретизации этого требования рассмотрим ситуацию, когда роботы находятся на окружности 7 и ориентированы по касательной к ней (см. рисунок 1.19). Пусть d — расстояние от точки д Є 7 до объединения двух лучей, соответствующих радиусам основной зоны учета. Пусть д движется вперед вдоль 7 от точки положения робота. Тогда d будет возрастать до тех пор, пока не будет пройдена определенная критическая точка дсг Є 7. Согласно рисунку 1.19 расстояние по прямой от дсг до робота составляет 2Н SHITT, где К — радиус 7 . Радиус Hv основной зоны учета выбираем так, чтобы она не выходила за пределы критической точки, другими словами, обеспечиваем монотонное возрастание d (вдоль окружности 7) в этой зоне:

Rv 2R sin—. (1.28) Теорема 1.5.1. Пусть выполнены предположения теоремы 1.4.1, требуемая изолиния (1.7) — окружность 7, и для определенности множество {г : D(r) do} лежит внутри 7. Пусть также верно (1.28) и при равномерном распределении роботов вдоль 7 основная зона учета каждого робота не пуста, но при этом первый предшественник не является ближайшим соседом:

Здесь R0 — радиус 70, N — количество роботов, а Rv и Rd заимствованы из рисунка 1.6. Тогда роботы асимптотически приходят к равномерному распределению вдоль 70. А именно, заключение теоремы 1.4.1 справедливо для v := 1, G\ := [ 1 : N], 7i := 70, и после надлежащей нумерации роботов j Є [0 : N — 1] имеют место следующие утверждения: i) при t Т проекции S0(t),... , SN-i(t) роботов на 70 расположены по часовой стрелке; ii) расстояние между соседними роботами стремится к значению, которое соответствует их равномерному распределению где 0 — суммирование по модулю N. Рисунок 1.19 — Критическое расстояние Доказательство i) теоремы 1.5.1: Это утверждение немедленно следует из утверждений ii) и iii) теоремы 1.4.1 вместе с последним утверждением теоремы 1.1.1.

Окружение группы целей, двигающихся вокруг стационарного объекта

Как и в параграфе 1.2, закон управления линейной скоростью подвергаем коррекции с помощью относительно малой тормозящей компоненты (). Окончательно закон управления выглядит следующим образом: Vi(t) = V[Pi] — bi(t). (2.16) По-прежнему для точного определения тормозящей компоненты используем следующие обозначения, проиллюстрированные ранее рисунком 1.12: i\)j\i — полярный угол соседнего робота j в относительной системе координат, связанной с роботом і; г[)е,. — угол ориентации робота j в этой системе координат. Затем выберем три непрерывные функции которые тождественны нулю вне интервала [—(/?-, (/?-] и [0, Rd] соответственно, достигают своих максимальных значений в нуле (см. рисунок 2.4) и достаточно малы: є := єатах{1; Є/з}eq [V(0) — v] N , (2.17) где єа = a(0) 0, єр = /3(0) 0, eq = q(0) 0. Эти функции используем, чтобы конкретизировать влияние робота j на тормозящую компоненту робота і посредством следующего определения веса соседа j относительно робота і:

Соседний робот называется ближайшим, если Wj\{ 0. Цепочка ближайших соседей (ЦБС) — это последовательность, в которой за каждым роботом идет его ближайший сосед.

По лемме 1.2.1 любая ЦБС содержит не более, чем N роботов, причем они попарно различны. Каждый робот і является корневым элементом конечного числа ЦБС и может определить каждую из них, так как расстояние между ближайшими соседями не превосходит Rd и Rd N lRv , где Rv R, а R — радиус зоны видимости робота. Ранг робота і — это максимальная длина ЦБС, для которой робот і является корнем. Заметим, что ранг уменьшается при продвижении вперед по ЦБС.

Тормозящую компоненту ЬІ в (2.16) определяем рекурсивно. Для роботов ранга 1 эта компонента равна нулю. Пусть ЬІ уже определена для роботов, ранг которых не превосходит г. Пусть робот і имеет ранг t + і. Любой его ближайший сосед j обладает рангом, не превышающим г, следовательно, компонента bj уже определена. Положим

Ранее по умолчанию предполагалось, что расстояние РІ от робота до множества НІ = 3« U D\j U R? (см. рисунок 1.6) измеряется по прямой. Тогда вычисление pi является относительно простой задачей. Однако такой метод в общем случае не может обеспечить равномерное распределение роботов вдоль эквидистанты (2.4) в ситуации, когда расстояния между ними понимаются как расстояния вдоль этой кривой, что представляет интерес для многих приложений. Поэтому в данной главе параллельно рассматривается модифицированный закон управления. Его единственное отличие от уже описанного базового закона (2.16) заключается в способе вычисления pi: 1. через интересующую точку г проводится эквидистанта С и измеряется длина L ее дуги между данной точкой и множеством i ; 2. эта длина L принимается за Pi(r), если L R , где R Rv — еще один параметр регулятора; 3. если L R , то объект на позиции г не принимается во внимание. Таким образом, соседи робота і не только находятся в его зоне учета, но и удовлетворяют требованию L R . Вычисление С требует дополнительных сенсорных возможностей: робот должен иметь доступ не только к значению минимального расстояния до области D, но и к значениям расстояний до граничных точек из достаточно большой окрестности своей проекции на область. В силу того, что на больших расстояниях результат такого рода вычислений чувствителен к погрешностям в измерениях, данную альтернативную технику имеет смысл применять только в непосредственной близости к требуемой кривой: \di — do\ ЯІ , где ЯІ do — еще один параметр в законе управления.

Далее рассматриваем роботов, управляемых в соответствии с предложенным алгоритмом и считаем выполненным следующее предположение. Предположение 2.4.1. Каждый робот і удовлетворяет предположениям теоремы 2.1.1 и управляется регулятором (2.5), параметры которого 7 и М удовлетворяют неравенствам (2.13). Утверждение 2.4.1. Роботы постоянно находятся на безопасном расстоянии от области D и сходятся к ее do-эквидистанте (2.4), т.е. выполнено (2.12) и dist [ГІ(І); 8,(do)] — 0 при t — +оо Vi. (2.19) Пусть начальное расстояние между любыми двумя роботами превышает 37ivu l + d , где d из (2.10). Тогда роботы не сталкиваются друг с другом: Vi(t) Ф fj{t) Vi Ф j, t 0. Данный результат справедлив как для основного, так и для модифицированного регулятора скорости и для обоих сценариев С.1) и С.2). Доказательство этого утверждения аналогично доказательству теоремы 1.3.1 и поэтому вынесено в приложение А.

В общем случае целевая эквидистанта 8, (do) может содержать несколько компонент связности, как например, на рисунке 2.5. Тогда из (2.19) следует, что вся группа роботов разбивается на непересекающиеся подгруппы таким образом, что роботы из одной подгруппы сходятся к общей компоненте, отличной от компоненты для роботов другой подгруппы. В этом случае дальнейшие результаты главы 2 следует рассматривать отдельно для каждой компоненты связности и отвечающей ей подгруппы. Поэтому, не умаляя общности, можно наложить следующее условие.

Некоторые характеристики динамического поля

В данной главе рассматривается управление неголономным роботом, который смоделирован как машина Дубинса: робот перемещается по плоскости с постоянной линейной скоростью, угловая скорость его вращения ограничена по модулю и является управляющим параметром. Как следствие, радиус поворота робота ограничен снизу положительной константой и робот способен двигаться только по путям ограниченной кривизны. По плоскости произвольно перемещается группа маневренных непредсказуемых целей, причем в отличие от [126; 127; 132; 134; 135] их скорости необязательно малы. Априорная информация о целях, например, об их кинематике или динамике, о геометрической организации (в случае применимости), пути или направлении следования и т.п., отсутствует. Сенсорная информация сводится к измерению текущего расстояния до каждой из целей, угловые данные недоступны. Кроме того, для робота цели анонимны — он неспособен их различать.

Цель управления состоит в том, чтобы из случайного начального положения вывести робота на заданное среднеквадратичное расстояние от группы и, сохраняя это значение, осуществить дальнейшее сопровождение группы, постоянно двигаясь на заданной «крейсерской» скорости.

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

Вместе с тем в общем случае рассматриваемая задача напрямую не требует обязательного окружения множественных целей: требуется достичь только близости к ним. Такая ситуация имеет место, например, в некоторых задачах наблюдения и разведки, сбора и слияния данных от множественных датчиков, улучшения связи между элементами многоагентной сети и т.д. Использование среднеквадратичного расстояния в формулировке цели управления представляет собой способ достижения компромисса между противоречащими друг другу задачами: нужно оказаться вблизи различных точек плоскости. Альтернативой такой форме компромисса является последовательное посещение малой окрестности каждой цели. В этом случае, однако, роботу необходимо различать цели и идентифицировать их как «уже удостоенные визита» или «ожидающие визита». Это как минимум увеличивает вычислительную нагрузку, а как максимум может оказаться невозможным ввиду анонимности или сходства целей, особенно в условиях их перемещения. Кроме того, по сравнению с последовательным обходом каждой цели, предлагаемый метод пригоден для работы с кинематически неоднородными группами, в которых некоторые цели эпизодически двигаются быстрее преследователя, но так, что средняя скорость группы остается в пределах возможностей робота. С учетом такого сценария (кинематически неоднородной группы целей) в данной главе систематически используются только усредненные характеристики группы.

Вместе с тем имеется ряд задач, когда робот должен в итоге перемещаться по периметру области, содержащей все цели или их «основную массу». В качестве примера можно привести защиту (захват) важных (опасных) подвижных объектов. В этих случаях во избежание нереалистичной постановки задачи следует уточнить понятие «группы», поскольку невозможно, например, обеспечивать окружение неограниченно разбегающихся целей с помощью единичного робота, перемещающегося с ограниченной скоростью. В связи с этим под «группой» будем понимать множество целей, средний разброс положений которых ограничен с течением времени. Как будет показано далее, в этом случае использование среднеквадратичного расстояния обеспечивает обход всей группы, если заданное целевое значение этого расстояния достаточно велико по сравнению с разбросом положений в группе. Когда требуется окружение только лишь «основной» части группы, выбор этого значения позволяет регулировать процент «заведомо окруженных» целей. Более того, в случае преднамеренного или случайного «отвлекающего побега» нескольких целей от основной группы, такой подход способствует концентрации преследователя на основной части, что совершенно не гарантируется при использовании (вместо среднеквадратичного расстояния) расстояния до ближайшей цели или расстояния до центроида группы за вычетом расстояния до самой дальней цели [135].

В данной главе представлены свидетельства того, что предложенный закон управления является в определенном смысле почти исчерпывающим. «Исчерпываемость» при этом понимаем следующим образом: если задача в принципе разрешима с помощью робота с заданными значениями линейной скорости и максимальной скорости вращения его ориентации, то ее можно решить с помощью предложенного закона управления при условии его адекватной настройки, причем рекомендации по настройке должны быть представлены. Для этого сначала выявлены необходимые условия разрешимости задачи: они раскрывают должное соответствие между способностями робота к маневрированию и усредненными параметрами перемещения мобильных целей. Далее показано, что при незначительном и в определенном смысле неизбежном усилении этих необходимых условий предлагаемый регулятор решает поставленную задачу. Это сделано в виде математически строгого доказательства нелокальной сходимости, которое сопровождается рекомендациями по настройке регулятора. Эти рекомендации даны в аналитической форме с точностью до оценки скорости изменения значения явно указанной функции по отношению к изменению одного из аргументов. Данная оценка обычно сводится к элементарному упражнению по математическому анализу, однако ее детали, как правило, сильно зависят от доступной информации о характере движения целей. Поэтому такая оценка детально проиллюстрирована для специальных сценариев, включая сценарий доступной информации, на основании чего также конкретизированы вышеупомянутые рекомендации. Наконец, сходимость и эффективность предложенного регулятора подтверждают представленные в конце главы результаты компьютерного моделирования.