Содержание к диссертации
Введение
1 Постановка задачи, управление движением строя автономных агентов в случае управления по скорости 19
1.1 Основные определения 19
1.1.1 Общие понятия и класс допустимых управлений 19
1.1.2 Геометрическая структура строя 23
1.1.3 Виртуальные лидеры 24
1.1.4 Формализация постановки задачи 25
1.2 Правило управления 26
1.2.1 Основные идеи предлагаемого закона управления 26
1.2.2 Правило расчёта положения виртуальных лидеров 27
1.2.3 Итоговое правило управления 29
1.2.4 Формулировка правила управления в матричной форме 30
1.2.5 Процедура расчёта коэффициентов приоритета виртуальных лидеров для агента 32
1.3 Анализ правила управления 34
1.3.1 Формальное обоснование применимости правила управления по скорости 34
2 Дискретизация задачи, разработка среды моделирования 40
2.1 Выбор способа апробации разработанных правил управления мультиагентной системой 40
2.2 Основные принципы разработки среды моделирования
2.2.1 Разработка среды моделирования 42
2.2.2 Процедура внедрения новых алгоритмов в среду моделирования 43
2.2.3 Архитектура классов программы моделирования 44
2.3 Переход к дискретной модели 47
2.3.1 Правило управления в дискретной форме 47
2.3.2 Алгоритм управления 47
2.4 Результаты моделирования 48
2.4.1 Ключевые параметры оценки эффективности алгоритма управления мультиагентной системой 48
2.4.2 Зависимость эффективности управления от параметров управления 49
2.4.3 Взаимодействие различных групп связности 2.4.4 Переключение текущей целевой точки 53
2.4.5 Моделирование внештатных ситуаций 54
3 Модификации правила управления и исследование правила управления при вводе в модель ошибок изменения и шумов 57
3.1 Огибание препятствий 57
3.1.1 Основные определения и модель препятствия 57
3.1.2 Модификация правила управления для огибания препятствий 59
3.1.3 Результаты моделирования для одиночных неподвижных препятствий среднего размера 61
3.1.4 Результаты моделирования для одиночных неподвижных препятствий малого размера 63
3.1.5 Обобщение результатов на случаи огибания нескольких препятствий средних и малых размеров 64
3.1.6 Огибание движущихся препяствий малого и среднего размера
3.2 Избежание коллизий между агентами 68
3.3 Результаты модификации правила управления для избежания коллизий между агентами и огибания препятствий 70
3.4 Ошибки измерения и шумы
3.4.1 Математическая модель ошибок измерений и шумов 71
3.4.2 Моделирование и анализ работы алгоритма в случае введения ошибок измерений и шумов 72
3.4.3 Итоги анализа работоспособности алгоритма при наличии ошибок измерений и шумов 76
3.5 Фиксированная структура строя 77
3.5.1 Количество агентов меньше числа точек целевой геометрической структуры 78
3.5.2 Количество агентов больше числа точек целевой геометрической структуры 81
3.5.3 Переходы между фиксированной и динамической ЦГС 83
4 Управление строем автономных агентов в случае управления по ускорению 86
4.1 Модель динамики агента с учётом ускорения и правило управления по ускорению 86
4.1.1 Ограничения и допустимый класс управлений 86
4.1.2 Адаптация разработанных принципов управления к управлению по ускорению 87
4.1.3 Дискретизация правила управления в случае управления по ускорению и моделирование 88
4.1.4 Анализ результатов моделирования 89
4.1.5 Лидер в прямом преследовании 91
4.2 Сравнение двух реализаций управления по ускорению
4.2.1 Методика проведения исследования при помощи моделирования 94
4.2.2 Результаты анализа немодифицированного управления по ускорению 95
4.2.3 Результаты анализа модифицированного управления по ускорению и сравнение с немодифицированным 98
4.3 Модификация базового алгоритма управления по ускорению для огибания препятствий и избежания коллизий 99
4.3.1 Огибание препятствий разного размера 99
4.3.2 Избежание коллизий между агентами при управлении по ускорению 103
4.3.3 Огибание движущихся препятствий малого и среднего размера при управлении по ускорению 103
4.4 Анализ немодифицированного управления по ускорению в условиях наличия шумов и ошибок измерения 105
4.4.1 Исследование помехоустойчивости управления по ускорению при помощи компьютерного моделирования 105
4.4.2 Сравнительный анализ помехоустойчивости управления по скорости и по ускорению 109
Заключение 112
Список рисунков
- Правило расчёта положения виртуальных лидеров
- Архитектура классов программы моделирования
- Обобщение результатов на случаи огибания нескольких препятствий средних и малых размеров
- Методика проведения исследования при помощи моделирования
Правило расчёта положения виртуальных лидеров
Движение группы агентов при применении данного подхода может осуществляться при помощи движущегося по заранее заданной траектории агента-лидера, относительно которого выравнивается все агенты за счёт жёсткости соответствующего графа и движения каждого агента в направлении минимизации ошибки по заданным расстояниям до своих соседей. Также движения строем можно достичь, если все агенты после формирования строя будут двигаться по одинаковой заданной траектории с одинаковой скоростью. Данный подход оказывается крайне не гибким в своём применении, так как вопросы планирования траектории или управления агентом-лидером остаются за рамками решения при применении данного подхода, а выход агента из строя грозит нарушением свойства жёсткости графа.
Второй подход к управлению движением строя был получен модификацией управления, ведущего агентов к консенсусу (достижение консенсуса — приведение к единому значению некоторого параметра состояния, которым обладает каждый агент, при помощи усреднения). Задачи по поиску консенсуса составляют целый отдельный класс задач по управлению мультиагентными системами (с довольно исчерпывающим обзором задач, решаемых при помощи данного подхода, можно ознакомиться в работе [19]). Одна из задач по поиску консенсуса заключается в сборе всех агентов в единой точке, она получила название «задача рандеву» (от англ. rendezvous problem). В таких задачах рассматриваются безразмерные агенты. Управление, обеспечивающее сбор агентов в одной точке при условии того, что каждый агент из группы знает координаты всех остальных агентов, имеет следующий вид: Pi(t) = У (Pj(t) — Pi(t)). Если же добавить к данному правилу управления вектор сдвига Ьц (Xij\ (в двухмерном случае вектор Ьц = отражает относительное расположение агентов г УИ и j по обеим осям неподвижной мировой системы координат), то вместо сбора в одной точке можно получить определённую геометрическую структуру. Каждый агент будет в итоге сдвинут относительно точки «рандеву» на вектор 6j = bij. Правило управление в данном случае выглядит следующим образом: pi(t) = У (pj(t) — Pi(t) + bij) = У (Pj(t) — Pi(t)) + bi. зфі зфі
Форма данной геометрической структуры задаётся кососимметричными матрицами, характеризующими относительное расположение агентов г и j вдоль разных осей координат (в двухмерном случае это матрицы X = (xij), Y = (yij)). Движение группы агентов с сохранением соответствия строя заданной геометрической структуре при использовании данного подхода к управлению происходит аналогичным образом, как и в подходе, основанном на теории жёсткости.
Отличительной особенностью обоих вышеописанных подходов является то, что в этих подходах никак не решается вопрос об ориентации строя в пространстве при движении: нет возможности задать целевую ориентацию геометрической структуры строя в пространстве относительно направления движения. Сложившаяся при первичном формировании строя, соответствующего заданной геометрической структуре, ориентация в пространстве зависима от начального расположения агентов и будет сохраняться в ходе движения вне зависимости от направления движения.
Третья группа подходов, используемых для решения задач управления строем, оперирует понятиями виртуальных формаций и/или виртуальных лидеров (в зависимости от того, что подразумевается под этими терминами). Основная идея таких подходов — следование каждого агента за некоторой точкой, изменяющей свою координату во времени по определённому закону. В некоторых подходах эта точка именуется виртуальным лидером. Её текущие координаты рассчитываются вне мультиагентной системы при помощи внешнего вычислительного ресурса и передаются агенту как входной параметр в каждый момент времени. Иногда прибегают к термину «виртуальная формация». В таких постановках для каждого агента задаётся виртуальная формация (набор точек, задающий целевую геометрическую форму строя). Каждому агенту фиксированно присваивается точка виртуальной формации с определённым номером, затем задаётся траектория движения виртуальной формации и её скорость. Агент выполняет сдвиг виртуальной формации в соответствии с заданной скоростью и траекторией таким образом, чтобы «своя» точка виртуальной формации была впереди него вдоль заданного направления. Он преследует данную точку виртуальной формации с фиксированным номером. Это обеспечивает движение мультиагентной системы с сохранением геометрической структуры строя. Одним из главных затруднений, с которым сталкиваются на практике перечисленные подходы, является применимость разработанных на их основе алгоритмов на практике с учетом следующих внештатных ситуаций: выход из строя одного или нескольких агентов с последующей потерей связи, особенно агента-лидера; приобретение связи с агентом, который по мере движения к цели оказался в зоне слышимости других агентов; неполадки связи с координационным центром (в подходах, где предполагается передача значимой для управления информации агентам в каждый момент времени).
В каждом из подходов предпринимались попытки сгладить указанные недостатки, но чаще всего при помощи наложения дополнительных ограничений (предположение возможности установления связи между любыми агентами [25], сохранение фиксации места каждого агента в строю после введения различных возможных геометрических структур строя для разного количества агентов [26]). Во многих существующих подходах агенты фактически не являются взаимозаменяемыми, так как место в геометрической структуре строя зачастую зафиксировано за агентом с конкретным номером. Подходы, где в каждый момент времени агентам передаются координаты виртуальных лидеров или виртуальных формаций и направление их движения, фактически не соответствуют принципам децентрализованного управления, так как в таких подходах предполагается наличие центра управления, в котором происходит планирование заданий и из которого к каждому агенту по каналу связи непрерывно поступает информация, необходимая агенту для управления своим передвижением (например, работы [23,27]).
Целью данной работы является разработка эффективного правила управления группой агентов, моделирующих мобильных роботов, которое бы обеспечивало движение группы агентов с соблюдением определённого строя (определённых взаимных расстояний относительно друг друга).
Архитектура классов программы моделирования
Общая блок-схема мультиагентной системы будет состоять из аналогичных блок-схем самоуправления (в соответствии с количеством агентов) и иметь единые управляющие параметры и общую ошибку строя , вычисленную на основании всех (см. схему на рис. 1.4). В терминах теории управления объектом управления являются сами агенты, состояние объекта —это координаты агентов (матрица ). Управляющее воздействие вырабатывается управляющим устройством мультиагентной системы (распределённым по всем агентам) на основании обратной связи о текущем значении матрицы состояний системы (результаты измерений), а также на основании управляющих параметров и координат целевой точки. Динамику системы управления описывает система (1.2). При этом для выработки управления агент использует по сути отклонение между своим текущим положением и положением виртуального лидера (т.е. отклонение текущего строя от «идеальной» ЦГС, которой всегда соответствуют виртуальные лидеры по построению).
Целесообразно чтобы в случае прямого преследования лидера агент преследовал исключительно данного лидера, который во избежание коллизий, в свою очередь, не был преследуем другими агентами из группы связности. : {u, , ()}
Рассмотрим агента и виртуального лидера к Этому лидеру в законе управления соответствует коэффициент ij. Предлагается выбирать его в зависимости от расстояния между всеми агентами из группы связности и -м лидером, чтобы иметь возможность избежать таких ситуаций, когда ближайший к не находящемуся в прямом преследовании виртуальному лидеру агент не движется к нему по причине того, что его «притягивает» в противоположном направлении большое число более отдаленных виртуальных лидеров, не находящихся в прямом преследовании, а также такие ситуации, когда агент движется к лидеру, в -окрестности которого уже находится его сосед.
Коэффициенты приоритета виртуальных лидеров для агента — , где является номером агента, а является номером виртуального лидера — определяют матрицу С К х . Коэффициенты приоритета предлагается выбирать следующим образом:
Коэффициент единица получает первый из лидеров, не находящихся в прямом преследовании, к которому агент является ближайшим из всех агентов (в этом случае все остальные виртуальные лидеры игнорируются данным агентом) или прочие лидеры, не находящиеся в прямом преследовании, для которых агент не является ближайшим агентом.
Базовое правило (1.3) дополняется следующими эвристиками, которые позволяют достичь некоторых улучшений в распределении лидеров между агентами: если — ближайший агент к лидеру , , то должен быть равен 1, а коэффициенты этого же лидера для других агентов ( , = ) должны быть равны нулю для того, чтобы точке занималась ближайшим к ней агентом. При чём, если , — не находящийся в прямом преследовании лидер, то при вычислении ближайшего к нему агента следует исключить из рассмотрения агентов, которые уже прямо преследуют других лидеров; если несколько лидеров находятся на одинаковом расстоянии от агента, то агент должен брать в расчет только одного из них и проигнорировать остальных (соответствующие коэффициенты Cij = 0);
Очевидно, что вычисление С подобным образом зависит от порядка вычислений, содержит условные переходы, и потому наиболее легко может быть описано в форме алгоритма.
Проведём формальное обоснование применимости предложенного подхода для проведения последующего сравнения с результатами моделирования. Формальное обоснование будем вести для ситуации, когда количество агентов в группе связности (обозначаемое к) постоянно.
Для упрощения выкладок, не ограничивая общности, проведём обоснование в R2 и опустим, где возможно, индексы к и г. Напомним некоторые определения, введённые в разделе 1.1, с учётом данных упрощений. Du — фиксированный параметр управления, характеризующий сдвиг виртуальных лидеров относительно агентов. В R2 Du = (Dx, Dy)T. U—j-й виртуальный лидер из числа рассчитанных агентами лидеров. Индекс к опущен, индекс г также можно опустить, так как наборы виртуальных лидеров, рассчитанные агентами г и г" из одной группы связности, идентичны (в отсутствие помех и ошибок измерений).
Аст— центр масс агентов группы связности. В R2 Аст = (АХ,АУ). Таким же способом может обозначаться и радиус-вектор точки (АХ,АУ): Аст = г(Аст).
Теорема. Пусть Dx = 0, 0 Dy Vrnaxt и для каждого агента АІ из группы связности Np (\NP\ = к) в некоторый момент t нашёлся единственный виртуальный лидер Ьл находящийся в прямом преследовании (\\LM(t ) — Pi(t )\\ Vmaxt), и имеет место взаимно однозначное соответствие {Аг} =1 о {LJ} =1, т. е. агенту с номером і соответствует «свой» виртуальный лидер с номером ji, и обратно каждому виртуальному лидеру соответствует единственный агент. Тогда при предложенном правиле управления: 1. найдётся такой момент t t , if оо, начиная с которого будет выполнено условие достижения группой целевой точки: \\1 — Аст\\ Vrnaxt, і і ; (1.4) 2. при і t для каждого агента г выполнено условие соблюдения строя: \\ЬЛ — Pill Vmaxt ; Є = У \\pi — ЬЛ + RpDu\\ = 0 , АіЄМр где є — ошибка соблюдения строя. Миссия будет выполнена, так как целевая точка достигнута и движение происходило с сохранением соответствия строя заданной ЦГС с приемлемой точностью. Доказательство. Сначала докажем первое утверждение теоремы. Для этого докажем вспомогательное утверждение: если в момент времени t выполнено условие \\pi(t) — Ьл(t) VmaxAt (лидер находится в прямом преследовании агентом), то в момент времени t-\-8t (8t — малое приращение) также верно, что \\pi(t-\-8t)—LM(t-\-8t) VmaxAt. Это вспомогательное утверждение эквивалентно утверждению, что после момента, когда каждый агент нашёл «своего» лидера, расстояние между ними при последующем движении не будет расти, что обеспечит преемственность данного лидера для агента (коэффициент приоритета данного лидера будет равен 1, а коэффициенты всех прочих лидеров будут равны 0 для данного агента). Движение группы агентов к целевой точке перейдёт в установившийся режим, при котором каждый агент преследует одного лидера и обеспечено соответствия строя заданной ЦГС с необходимой точностью. Перейдём к доказательству вспомогательного утверждения.
Рассмотрим векторную функцию /() = Pi(t) — L (t) при t ) f, /(t) Є К2 отражает отклонение агента от «своего» лидера. Для неё /() = Pi(t) — L3i(t). Поскольку в момент t лидер Vі находится в прямом преследовании агентом АІ, то С = 0 для всех j ф ji, поэтому правило управления имеет вид: Pi = LP — "pi. = 0, следовательно при t = t=t Так как pi(t) = 0 (скорость агента р\ постоянна на каждом из временных промежутков длиной At), а значит LM(t) = jhif) \ Piif) =Pi(t), то f(t) t + 8t также верно следующее неравенство: \\Pi(t + 8t) — Vі {t + 8Ї)\ VJnaxAt.
То есть после момента t расстояние между каждым агентом и лидером, находящимся в прямом преследовании данным агентом, не будет превышать V naxAt, что обеспечит преемственность прямого преследования данного лидера для агента. Таким образом, доказано, что после выполнения в момент t = t неравенства pi(t ) — L3i(t )\\ VmaxAt, это неравенство будет сохраняться и при t t , т. е. ЦГС строя будет соблюдаться с необходимой точностью.
Вспомогательное утверждение доказано. Введём функцию F(t) = Т — Acm(t)—это вектор от целевой точки Т до центра масс группы Аст. Тогда F(t) = — Аст в силу неподвижности целевой точки Т . Лидер-«фаворит» — U1 по условию является для агента АІ единственным лидером, находящимся в прямом преследовании. По правилу выбора коэффициентов Су (описанных системой (1.3)) U1 будет единственным лидером, коэффициент приоритета которого равен 1 (с = 1), прочие лидеры будут проигнорированы (с = 0 при j ф ji). По причине преемственности прямого преследования лидеров при t , с учетом значений с г (I = 1,... ,к) и нормировочных коэффициентов, уравнение движения агента АІ при t t принимает вид: р\ = Ul — pi.
Обобщение результатов на случаи огибания нескольких препятствий средних и малых размеров
В алгоритме используется локальная информация о расположении ближайших соседей, а также информация о собственном расположении. На практике измеренная при помощи сенсоров или переданная при помощи радиосвязи информация может содержать ошибки и шумы [38]. Разберём более подробно возможные вероятные причины их возникновения: ошибка при измерении агентом собственных координат, а также координат агентов, находящихся в прямой видимости, вследствие погрешности измерений используемых приборов и датчиков; помехи при передаче информации о своих координатах или координатах своих соседей другим агентам; за время, требуемое на обработку поступающей информации или её передачу, реальное значение параметра, о котором собирается или передаётся информация, может измениться.
Алгоритм, не устойчивый к вводу в модель шумов и ошибок, слабо применим на практике, поэтому большую значимость имеет исследование работоспособности правил управления в таких условиях. Для упрощения изложения далее используется термин «ошибки измерения и шумы», означающий несовпадение реальных координат агента с координатами этого агента, используемыми для расчётов (без детализации о причинах данного несовпадения). Одними из наиболее важных вопросов, таким образом, становятся вопросы, связанные с применимостью правила управления в условиях наличия ошибок измерения и шумов, а также с определением допустимых границ применимости.
Для исследования устойчивости разработанного алгоритма при моделировании было введено случайное отклонение измеренных агентом координат соседей, а также собственных координат, от фактических. Далее измеренные или вычисленные агентом параметры даются с указанием в верхнем индексе. Пусть истинное положение в момент времени — это (j = 1,..., k), а его измеренное агентом положение — () = () + (). Здесь — случайный вектор, компоненты которого являются случайными величинами с равномерным распределением на отрезке [-,]. При этом измерение собственного положения для І также содержит ошибки: \{) = іі) + ц{). Фактическое расположение агентов составляет следующую матрицу:
Помимо этого ошибки измерений и шумы будут оказывать влияние на вычисление коэффициентов приоритетов ij. Например, лидер, в действительности находящийся в прямом преследовании некоторым агентом, может быть признан «свободным» другим агентом, который присвоит соответствующему лидеру коэффициент 1 вместо 0.
Разработанное правило управление основано на использовании усреднения информации, получаемой в ходе измерений (к такой информации относится i, так как прочие входные параметры управления — ,U, —заданы до начала выполнения миссии). В правиле управления используется центр масс, являющийся усреднением векторов, составляющих i, и потому имеются предпосылки к смягчению эффекта от воздействия ошибок измерений и шумов.
Исследуем работоспособность управления по скорости при наличии ошибок измерения в условиях отсутствия препятствий. Зафиксируем число агентов = 8 и их начальное положение (пусть они будут располагаться на осях координат мировой системы координат с фиксированным интервалом между собой), зададим u = (0, 0.05)т, max = 0.05 и проанализируем работу алгоритма при управлении по скорости при разных значениях (см. графики на рис. 3.5, 3.6). Будем рассматривать значения из интервала [0.01 = 0.2maxA,0.25 = 5maxA] с шагом 0.02. Точки на графиках, соответствующие ситуации = 0 отражают значения параметров в отсутствие ошибок измерения и шумов. График с рис. 3.5 показывает характер роста количества шагов, требуемых для достижения целевой точки, при росте В. На рисунке также приведена формула многочлена, интерполирующего множество точек, полученных на основании измерения показателей в ходе моделирования. График показывает, что скорость роста количества шагов с увеличением В выше линейного роста, но тем не менее она не экспоненциального характера. При В Є (0, 2VmaxAt] количество шагов возрастает не более, чем на 30% от базового количества шагов (без ошибок измерения и шумов). Средняя скорость движения группы связности вдоль направления к целевой точке падает с ростом В, что объясняется менее эффективной погоней за виртуальными лидерами вследствие введённых в модель ошибок, что влечёт отклонение от траектории движения к целевой точке по кратчайшему пути.
График с рис. 3.6 показывает характер роста медианы ошибки строя при росте В. Медиана считается для набора значений {e At = 0),..., e At = і At),... , e At = q At)}, где q — шаг, на котором целевая точка была достигнута. Причём ошибка строя измеряется по фор / и гі о п II ТІ D rt 1 А муле &t = max mm \\Lik — К/зЬ и — Pi\\, где Lik = а$гк + — }_ P, то есть для измерения ошибки строя используются фактические координаты агентов и система виртуальных лидеров, рассчитанная относительно фактических координат центра масс группы связности. На рисунке также приведена формула многочлена, интерполирующего множество точек, полученных на основании измерения ошибки строя в ходе моделирования. График показывает, что рост ошибки строя происходит медленнее, чем линейно по отношению к росту В, что является хорошей характеристикой алгоритма. Медиана ошибки строя остаётся в пределах допустимого отклонения (т.е. в пределах [0, Vmaxt]) при В 3Vmaxt.
По графикам видно, что на точность поддержания заданной структуры строя и скорость В В достижения текущей целевой точки напрямую влияет соотношение . При t в ошибка измерений вносит лишь некоторые колебания текущей структуры строя в пределах допустимой ошибки строя. При 1 ошибка строя начинает превышать Vmaxt, и движение к цели происходит медленнее, так как нарушается преемственность приоритетов лидеров и агенты заняты непрерывным формированием строя из-за перестроений вследствие постоянной смены наиболее приоритетного лидера.
Моделирование также позволило выявить повышение ошибки строя вблизи целевой точки (см. рис. 3.7). Всплеск ошибки перед достижением целевой точки почти не заметен при в в С 1, повышается вместе с ростом и становится особенно заметным (много В Vmaxt Vmaxt 1. кратно превышающим допустимую погрешность) при т Для объяснения этого всплеска рассмотрим двух агентов і и г" в двух ситуациях (t = t\) и (t = іг). Первая ситуация: агенты на расстоянии D(t\) Vmaxt от Т , A cm(ti) и A"m(t2) — координаты центра масс группы связности, рассчитанные каждым из агентов соответсвен-но. Вторая ситуация: агенты на расстоянии D(o) = Vmayit от Т , координаты центра масс (іг) и A cm(t2) соответсвенно. При этом пусть в обеих ситуациях из-за ошибки измере Рисунок 3.7: Динамика ошибки строя по шагам в ходе движения агентов к целевой точке при разных граничных значениях величины ошибки измерений и шумов ний расстояние между А ст и А"т составляет одинаковое расстояние. Очевидно, что угол между A cm(ti)T и A"m(ti)T будет меньше, чем угол между A cm(t2)T и A"m(t2)T . Чем ближе агенты к целевой точке, тем больше разнится ориентация систем виртуальных лидеров, построенных разными агентами, из-за ошибки измерений, характер изменения которой инвариантен к расстоянию до целевой точки. Значительные расхождения в ориентации систем лидеров каждого из агентов вблизи целевой точки вызывают всплеск ошибки строя. При этом данный всплеск наблюдается и при управлении по скорости, и при управлении по ускорению.
При В 2VmaxAt динамика ошибки строя чётко различается до момента первичного формирования строя и после него: на первом этапе агенты первично формируют строй (убывание ошибки строя), на втором больше продвигаются к целевой точке сохраняя строй (колебания ошибки строя около некоторого значения, не превышающего значительно допустимых границ ошибки, повышение ошибки строя непосредственно перед достижением целевой точки). Для исследования второго этапа, представляющего наибольший интерес по результатам моделирования была построена таблица 3.6, на которой приводится доля шагов, начиная с начала движения, от общего числа шагов, которая потребовалась, чтобы ошибка строя впервые вошла в установленные допустимые пределы погрешности. В последней колонке таблицы приводится медиана ошибки строя после наступления данного момента. Характер
Методика проведения исследования при помощи моделирования
Введём в правило управления компонент в" аналогичным образом, как для препятствий (считаем другого агента препятствием малого размера). Тогда правило управления с учётом огибания препятствия и коллизий: расстояние агенты предпринимают симметричные усилия по избежанию коллизии, что дополнительно снижает риск столкновения по сравнению с огибанием неподвижного препятствия. Моделирование подтверждает, что приведённое правило управления позволяет избегать столкновение между агентами одновременно с огибанием препятствий (прежде в процессе колебательных движений при огибании препятствий агенты часто сталкивались).
Пусть движение препятствий происходит таким же образом, как в случае управления по скорости (подробнее см. подраздел 3.1.6).
Расположим препятствие таким образом, чтобы траектория его движения пересекалась с траекторией движения строя к целевой точке. Фиксируем параметры управления и при помощи компьютерного моделирования исследуем при каком соотношении между Vmax и T4bs не происходит столкновения агентов с движущимся препятствием (см. таблицу 3.3). Пусть Vmax = 0.05, атах = 0.5V nax, ГА = 0.03, R\ = 0.3, R2 = 0.05, Du = (0,0.05)т, к = 7, Т1 = (1.5, 4.0), Т2 = (—2.5,-2.5), h\ = (1.0,2.7), hi = (1.0,1.0), k0\ s имеет рекомендованное значение. Начальное положение агентов задано фиксировано. В ходе моделирования могут непредсказуемо добавляться очередные агенты. Кроме того оператором могут добавляться очередные целевые точки для намеренного создания ситуации вероятного столкновения с препятствием.
В ходе моделирования выяснилось, что столкновения с движущимся препятствием при правиле управления, заданном системой 4.6, происходят и при довольно низкой скорости пре 1 пятствия (при моделировании использовался диапазон Vobs Є I—Vmax; VmaxI). Более глубокий 5 анализ показал, что причина в том, что прибавляемый к вектору ускорения отталкивающий компонент не достаточен для наращивания ускорения в необходимом направлении в достаточной мере для своевременного изменения вектора скорости. Если препятствие огибается небольшим манёвром, то это не критично, в отличие от столкновений «в лобовую». Так как мы не учитываем ограничений на скорость изменения ускорения, то предлагается вместо добавления отталкивающего компонента напрямую задать вектор ускорения равным отталкивающему компоненту (с учётом нормировки) при приближении к препятствию на расстояние меньше порогового:
Промежуточным вариантом также могло бы быть добавление двух коэффициентов приоритета: один для компонента ускорения, отвечающего за движения за виртуальными лидерами, и второй для компонента, отвечающего за уклонения от столкновения. При приближении к препятствию на критичное расстояние, первый из коэффициентов приближался бы к 0.
Проведём повторное моделирование при условиях, описанных выше, но применяя правило (4.7). Таблица 4.3 содержит основные результаты моделирования: успешное огибание движущихся препятствий при рекомендованной параметризации возможно при V0 s Сбірах. Указанный порог возможно поднять, если оптимизировать параметры алгоритма управления с данной целью. частые столкновения с препятствиями среднего размера и редкие столкновения с препятствием малого размера частые столкновения с препятствиями малого и среднего размера
Исследуем немодифицированное правило управления по ускорению на устойчивость к помехам и ошибкам измерения. Внедрение помех и ошибок измерения в модель выполнена идентичным образом, как в случае с управлением по скорости (см. раздел 3.4). То есть,
Для выявления устойчивости правила управления по ускорению к помехам и ошибкам измерения по аналогии со случаем управления по скорости было проведено компьютерное моделирование. При этом ключевые параметры среды моделирования были оставлены такими же, как и в случае аналогичного исследования при управлении по скорости. Это было сделано для возможности последующего сравнения надёжности управления по скорости и по ускорению в случае неточных знаний агентов об окружающей среде.
Зафиксируем число агентов = 8 и их начальное положение (пусть они будут располагаться на осях координат мировой системы координат с фиксированным интервалом между собой), зададим u = (0,0.05)т, max = 0.05 и проанализируем работу алгоритма при управлении по ускорению при разных значениях (см. графики на рис. 4.8, 4.9). Бу 105 дем рассматривать значения из интервала [0.01 = 0.2 ах A, 0.25 = 5maxA] с шагом 0.02. Точки на графиках, соответствующие ситуации = 0, отражают ситуацию отсутствия ошибок измерения и шумов.
График с рис. 4.8 показывает характер роста количества шагов, требуемых для достижения целевой точки, при росте . На рисунке также приведена формула многочлена, интерполирующего множество точек, полученных на основании измерения показателей в ходе моделирования. Хотя график показывает скорость роста количества шагов в зависимости от выше, чем линейная, рост тем не менее не носит экспоненциального характера. При Є [O maxA] количество шагов возрастает не более, чем на 30% от базового количества шагов (без ошибок измерения и шумов). Средняя скорость движения группы связности вдоль направления к целевой точке падает с ростом , и это объясняется отклонениями от оптимальной траектории и менее эффективной погоней за виртуальными лидерами вследствие введённых в модель ошибок.