Методы применения матриц при создании моделей группового преследования

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

В работах [1–4] исследовалось согласованное поведение группы преследователей и целей. Для общих теоретических и практических вопросов в задачах преследования рассматривались работы [5–9]. Наведение преследователя на цель анализировалось в свете информации, представленной в [10–13].

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

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

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

Рассмотрим групповое преследование множества целей: N преследователей догоняют M целей. Сформируем матрицу распределения преследователей по целям:

Каждая ячейка Y_ij содержит информацию о фазовых координатах i-го преследователя и j-й цели. В матрице Y_ij содержится информация о том, каким методом i-й преследователь преследует j-ю цель.

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

В каждой ячейке матрицы Y_ij может рассчитываться прогнозируемое время достижения -м преследователем j-й цели: t_ij.

Результаты работы

В каждой полученной выборке следует найти максимальное значение времен достижений , например из (таблица 1).

Необходимо сформировать матрицы Y_ij, где i= 1…3, j=1…2 в соответствии с возможными выборками A_k,k = 1…6. Затем, после обращения находится максимальное значение t_k=Max{t_ij}. Расчет позволил установить, что наибольшее время достижения демонстрирует преследователь P₁, настигающий цель T₁ из выборки A₂.

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

Получив массив выборок {A_k} с соответственными значениями времен {t_ij}, следует найти минимальное время t_min=Min{t_k}. Так определяется оптимальное время одновременного группового достижения множества целей.

Алгоритмы расчета следующего шага преследователя и оценки времени достижения преследователем цели. На рис. 1 представлен алгоритм функции расчета следующего шага и вектора скорости движения преследователя.

На рис. 2 представлен алгоритм расчета времени и расстояния достижения преследователем цели. Переменная e — это пороговое значение расстояния от преследователя до цели, при достижении которого цель считается достигнутой.

Если цель движется по предопределенной траектории, то алгоритм, представленный на рис. 2, может дать оценку времени t_ij достижения i-м преследователем j-й цели. В этом случае выходным параметром функции может служить количество итераций процесса преследования N_it. Количество итераций N_it — выходной параметр функции расчета времени и расстояния достижения преследователем цели.

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

Формирование библиотеки расчетов управляющих векторов. Матрица распределения Y_ij, где i= 1…N, j=1…M преследователей по целям будет строиться на каждом дискретном промежутке времени. В каждой ячейке матрицы Y_ij будет храниться информация о методе преследования. На ней основывается обращение к библиотеке функций расчета управляющих векторов (рис. 3–11).

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

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

Пример применения матричного моделирования к групповому преследованию. Рассмотрим пример группового преследования (рис. 12).

Здесь все преследователи достигают цели по модифицированному методу параллельного сближения, что соответствует рис. 10. В модели преследования на. рис. 10 кривизна траектории не должна быть больше определенного значения. Поэтому у преследователей P₂ и P₃ увеличивается первоначальный радиус кривизны траектории, что показано на рис. 12.

Сформирована выборка A_k, в которой преследователь P_i догоняет T_j. Далее происходит первичная оценка времени достижения t_ij. Для оценки времени t_ij вычисляются:

• длина прямолинейного участка до цели,
• длина дуги сопрягаемой окружности допустимого радиуса.

Затем выбирается максимальное значение t_k=Max{t_ij}. Увеличение времени t_ij до t_k в данной модели происходит за счет увеличения у преследователя P_i радиуса сопрягаемой окружности со значения r_i до значения r_i +dr_i.

Рис. 13 дополнен анимированным изображением, где показан процесс группового преследования множества целей [21].

По результатам исследования создана и зарегистрирована программа для ЭВМ [22], которая реализует алгоритм группового преследования нескольких целей. Это софтверное решение называется «Модель параллельного сближения на плоскости группы преследователей с одновременным достижением цели».

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

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