Algorithm for Obtaining a Characteristic Polynom and Transfer Function of Dynamic Model of Drone “Swarm”

A I Nistyuk; Yu V Turygin; V V Khvorenkov; A V Abilov

doi:10.22213/2410-9304-2018-4-122-129

Full Text

Введение Руководитель направления физико-технических исследований Фонда перспективных исследований Игорь Денисов считает, что задачи, стоящие перед оператором дронов, значительно сократятся. Предполагается, что они сведутся к корректной постановке задач группе дронов [1]. По его мнению, один из основных вопросов развития беспилотных летательных аппаратов - это управление группами аппаратов (роевые технологии). «Рой» дронов - это группа нескольких аппаратов, выполняющих общую задачу. Преимущества «роя» очевидны: каждый аппарат выполняет свою подзадачу, большая площадь покрытия, образование информационной сети, изменение состава, структуры, конфигурации «роя» и т. д. «Рой» дронов обладает специфическими возможностями по сравнению с одиночными дронами [2]. «Рой» может управляться оператором или группой операторов, может действовать самостоятельно или в комбинации указанных способов [3]. Одна из самых простейших и распространенных технологий описана Стефаненом Лаззаро [4]. Технология заключается в управлении оператором одним дроном, в то время как остальные дроны стараются сохранить свое положение в «рое» относительно ведущего дрона и остальных дронов. При этом дроны в своем движении колеблются относительно заданной точки в «рое». Одна из главных проблем управления «роем» - это столкновения дронов друг с другом [5], отметил Уильям Ропер, руководитель Strategic Capabilinies Offic, в своем докладе. Движение каждого дрона можно представить как поступательное по заданной траектории и колебательное, возникающее при попытке сохранить положение на траектории относительно других дронов. Целесообразно рассматривать движение системы относительно координатных осей, движущихся со скоростью ведущего дрона. Таким образом, выделяются колебания движения дронов, а «рой» можно рассматривать как колебательную систему. Представленная колебательная система обладает рядом особенностей: переменной структурой, переменным составом, уровнем взаимодействия [6]. В указанной динамической системе нас интересуют частоты собственных колебаний, поскольку наибольшая амплитуда колебаний возможна только при совпадении частоты возмущений с частотой собственных колебаний. С учетом потерь и запаздывания интерес представляют частоты свободных колебаний системы. Алгоритм анализа топологических моделей «роя» дронов Предлагается разработанный алгоритм анализа топологических моделей, с помощью которого можно получить передаточную функцию системы (ПФС) и характеристический полином (ХП). Передаточная функция и характеристический полином получаются в буквенно-численном виде. При этом используется метод присоединения по одной вершине. Алгоритм по сравнению с существующими обладает оптимальным механизмом построения деревьев и прадеревьев частей графа. В конечном итоге сокращаются затраты памяти и времени вычислений. Таким образом, появляется возможность моделировать многокомпонентные «рои» дронов. Исходной информацией при построении ХП системы служит формализованная информация о графе. Информация включает множество варьируемых параметров U, множества ti и Yi. Построим характеристические по заданным множествам ti и Yi . Множества H(gi) одновершинных множеств графа представляются в виде совокупности множеств {SL(gi), M(gi)}. Где M(gi) - множество порядковых номеров вершин, соответствующих слагаемых. Множество слагаемых SL(gi) характеристического полинома одновершинной части gi упорядочено по степеням р. Путем сложения параметрических функций ребер, входящих в множество Yi, получаем характеристический полином одновершинной части. Согласно [7], перемножив по особым правилам ХП H(g1) первой вершины на ХП H(g2) второй вершины, получим частичный ХП для части графа, который состоит уже из двух вершин g1,2. Далее, умножая полученный XП для части g1,2 на XП третьей вершины, получаем полином для части g1,2,3. Таким образом, можно получить ХП всего графа. Для этого необходимо продолжить процесс до N-й вершины графа. При перемножении исключаются некоторые элементы ХП, а именно деревья, содержащие контуры. Основную задачу при получении частичных ХП составляет последовательное исключение таких элементов ХП на каждом i-м этапе перемножения, то есть выявление множества деревьев частичных графов с контурами. Когда разрезаем дуги, граф разделяется на две части. Рассмотрим подробнее, как образуются части графа g1, 2, …, i присоединением одновершинных частей графа gi к части графа g1, …, i-1. Напомним, что вершины {i+1, i+2, …, N} составляют множество внешних вершин нового графа, а вершины {1, 2, …, i} составляют множество внутренних вершин. Поскольку при делении графа дуги разрезаются, то контуры теряются. Для последующего объединения частей графа необходимо хранить ту часть информации, которая дает возможность восстановить контур при операции объединения частей графа. Следовательно, необходима топологическая информация о дугах, которые соединяют внутренние вершины с внешними, и информация о внутренних путях части графа g1, 2, …, i, которые принадлежат соединительным дугам. Эта информация содержится во внешних и внутренних вершинах, которые являются концами соединительных дуг. Назовем множеством внутренних соединительных вершин w1 концы соединительных дуг, лежащих внутри графа. Назовем множеством внешних соединительных вершин w2 концы соединительных дуг, лежащих вне части графа g1, 2, …, i. Пользуясь языком логики, определим множество внутренних соединительных вершин w1 части графа следующим образом если (1) Через множество части g1, 2, …, i-1 можно определить множество части g1, 2, …, i. если (2) Множество определим по формуле если (3) Замкнутые контуры выявляются следующим образом. Для этого специально разработаны множества кортежей части графа KOR2(i). Элементами множества кортежей части графа KOR2(i) являются нулевая вершина и вершины множества Множество кортежей образуются по следующим правилам: 1. Присоединяем i-ю вершину к множеству по выражению (4) тем самым определяя множество головных вершин кортежей. 2. Строим множество кортежей KOR1(i) путем сочетаний кортежей и элементов множества ti, имея множество кортежей части g1, 2, …, i-1 KOR2(i - 1) и вершинных множеств ti части gI . 3. Анализируем на наличие контура каждый полученный кортеж множества KOR1(i). Смотрим, чему равен последний элемент кортежа, соответствующий i-й вершине. Если образованная вершина принадлежит множеству то проверяем элемент на соответствие этой вершине. Если элемент равен i, то считается, что кортеж содержит контур. 4. Заменяем на нуль элемент кортежа, принадлежащий множеству внутренних вершин части g1, 2, …, i. Таким образом, отмечается путь из корня в головную вершину элемента. 5. Заменяем на значение внешней вершины элемент кортежа, принадлежащий множеству внутренних вершин части. Замена производится потому, что для данного кортежа имеется путь из внешней вершины в головную. 6. Оставляем только те элементы в кортеже, которые соответствуют вершинам множества Полученное множество кортежей KOR2(i) содержит информацию о соединительных путях для части графа g1, 2, …, i. Вместе с множеством множество кортежей KOR2(i) участвует в образовании контуров на последующих этапах обработки. Отметим, что множество KOR1(2) строится из вершинных множеств (ВМ) t1 и t2. для образования части g1,2 путем присоединения части g2 к одновершинной части g1. Рассмотрим процесс построения кортежей по приведенным правилам. В качестве примера возьмем часть графа g1,2, представленного на рис. 1. Отметим, что множество головных вершин G1 состоит из вершины 1, 2, множество w1 для части g1,2 состоит из вершины 2. Множество кортежей KOR1 получаем из вершинных множеств t1 = {0, 2} и t2 = {0, 1, 3}. Таким образом, применяя разработанные правила, получаем множество кортежей графа. В табл. 1 показан процесс образования кортежей по вышеизложенным правилам. Рис. 1. Часть графа g1,2 Таблица 1. Таблица кортежей части g1,2 KOR1, исходные кортежи KOR1, множество кортежей после замены элементов KOR2 Номер (0,0) (0,0) (0,1) (0,0) (0,3) (0,3) (2,0) (0,0) (2,1) - (2,3) (3,3) (0) 1 (3) 2 Как видно из таблицы, при просмотре кортежа (2,1) из множества KOR1 выделен контур. Это является основанием отбросить этот кортеж. В результате множество кортежей KOR2 состоит из кортежей (0) и (3), которые соответствуют соединительной вершине 2. Аналогично происходит процесс образования множества кортежей частей графа g1,2,3 и g1,2,3,4, которые показаны на рис. 2 и 3 соответственно. Рис. 2. Часть графа g1,2,3 Рис. 3. Часть графа g1,2,3,4 Присоединяя вершины i = 3 к множеству w1(i - 1) = {2}, получаем множество головных вершин G1 части g1,2,3. Множество головных вершин G1 = {2, 3}. Рассуждая подобным образом, отмечаем, что множество w2(i) = {4, 5, 7}, множество w1(i) = = {3}. На этом этапе множество кортежей KOR1 получаем из множества кортежей предыдущего (табл. 1) этапа KOR2 = {(0), (3)} и вершинных множеств t3 = {0, 2, 4, 5, 6}. Кортежи части g1,2,3 отображены в табл. 2. Очевидно, выделен контур при анализе кортежа (3, 2). В конечном итоге внутренней соединительной вершине 3 соответствует множество кортежей KOR2 и, соответственно, состоит из кортежей (0), (4), (5), (7). Таблица 2. Таблица кортежей части g1,2,3 KOR1, предыдущие кортежи KOR1, множество кортежей после замены элементов KOR2 Номер (0,0) (0,0) (0,2) (0,0) (0,4) (0,4) (0,5) (0,5) (0,7) (0,7) (3,0) (0,0) (3,2) - (3,4) (4,4) (3,5) (5,5) (3,7) (7,7) (0) 1 (4) 2 (5) 3 (7) 4 Подобным образом получаем G1 = {3, 4}, w1 = {3, 4}, w2 = {5, 7} для части g1,2,3,4. Аналогично проводится образования кортежей из вершинных множеств t4 = {0, 3, 5} и предыдущего множества KOR2. В табл. 3 показан процесс образования кортежей. Часть графа g1, 2, 3, 4 имеет две внутренние соединительные вершины. В результате множество кортежей в данном случае состоит из семи двухэлементных кортежей. Далее, чтобы получить частичный характеристический полином, необходимо определить его коэффициенты. Коэффициенты представляем в виде суммы слагаемых произведений числовых весов и различных степеней параметров множества U. Также необходимо определить номер элемента множества кортежей KOR2(i), который соответствует каждому слагаемому частичного характеристического полинома. Следовательно, совокупность множества номеров кортежей MKOR(i) и множества слагаемых SL(g1, 2, …, i) представляет частичный характеристический полином H(g1, 2, …, i). Таблица 3. Таблица кортежей части g1,2,3,4 KOR1, предыдущие кортежи KOR1, множество кортежей после замены элементов KOR2 Номер (0,0) (0,0) (0,3) (0,0) (0,5) (0,5) (4,0) (0,0) (4,3) - (4,5) (5,5) (5,0) (5,0) (5,3) (5,5) (5,5) (5,5) (7,0) (7,0) (7,3) (7,7) (7,5) (7,5) (0,0) 1 (0,5) 2 (5,5) 3 (5,0) 4 (7,0) 5 (7,7) 6 (7,5) 7 Решение этой задачи авторы предлагают следующее. Предполагаем, что найдены множества w1(i - 1) и KOR2(i - 1) для части графа g1, 2, …, i-1. Предполагаем, что указанные кортежи множества KOR2(i - 1) пронумерованы в некотором порядке. Предполагаем, что у частичного характеристического полнома части графа g1, 2, …, i-1 на предыдущем этапе найдено множество слагаемых SL(g1, 2, …, i-1). Предполагаем, что установлено соответствие между кортежами множества KOR2(i - 1) и слагаемыми путем задания для каждого слагаемого номера кортежа, причем множество номеров кортежей MKOR(i - 1) соответствует множеству слагаемых SL(g1, 2, …, i-1). Строим табл. 4 перемножения кортежей при образовании множества KOR2(i) из множеств KOR2(i - 1) и ti для частей графа g1, 2 при перемножении частей графа g1 и g2. Таблица 4. Таблица умножения кортежей TU при перемножении H(g1)Ä H(g2) n m 1 2 3 1 1 1 2 2 1 0 2 Здесь m - порядковый номер из множества n - порядковый номер кортежа KOR2(i - 1). При этом считаем, что элемент таблицы TUnm равен порядковому номеру кортежа множества KOR2(i), который получился в результате сочетания m-го элемента множества ti. и n-го кортежа из множества KOR2(i - 1). Если обнаружен контур в образованном кортеже, то элемент таблицы Tnm принимаем за нуль. Следовательно, сформировалась таблица перемножения для частичного характеристического полинома части g1, 2, …, i. На основе таблицы находим номер кортежа слагаемого частичного характеристического полинома по номерам кортежей элементов характеристического полинома предыдущей части графа g1, 2, …, i-1 и одновершинной части gi, образующих это слагаемое. Аналогичным образом строим табл. 5, 6 перемножения кортежей при образовании множества KOR2(i) из множеств KOR2(i-1) и ti для частей графа g1, 2, 3, и g1, 2, 3, 4 при перемножении частей графа g1, 2 и g3, g1, 2, 3 и g4. Таблица 5. Таблица умножения кортежей TU при перемножении H(g1, 2)ÄH(g3) n m 1 2 3 4 5 1 1 1 2 3 4 2 1 0 2 3 4 Таблица 6. Таблица умножения кортежей TU при перемножении H(g1, 2, 3)ÄH(g4) n m 1 2 3 1 1 1 2 2 1 0 3 3 4 3 3 4 5 6 7 В результате получаем в множестве KOR2(i) порядковый номер кортежа. Находим множества SL(g1, 2, …, i) и множество MKOR(i) путем перемножения частичного характеристического полинома H(g1, 2, …, i-1) на характеристический полином H(gi) ОЧ gi. Получаем коэффициенты частичного характеристического полинома H(g1, 2, …, i) в порядке возрастания степеней переменной р. Сложением произведений коэффициентов частичного характристического полинома H(g1, 2, …, i-1) при степени и коэффициентов характеристического полинома H(gi) при степени получаем коэффициент частичного характеристического полинома H(g1, 2, …, i). При этом должно соблюдаться условие l1 + l2 = K. Перемножением числовых множителей перемножаемых слагаемых из множеств SL(g1, 2, …, i-1) и SL(gi) получаем числовой множитель слагаемого коэффициента частичного характеристического полинома из множества SL(g1, 2, …, i). Их степени складываем, если в перемножаемые элементы входят одинаковые буквенные параметры. По таблице перемножения кортежей TUnm по и номеру m из множества M(gi) номеру кортежа n из множества MKOR(i-1) каждому слагаемому коэффициента ставим в соответствие номер кортежа. И отбрасываем элементы с номерами кортежей, равными нулю. Заменяем одним членом с суммарным числовым весом слагаемые коэффициента характеристического полинома при некоторой степени переменной р. Слагаемые коэффициента характеристического полинома должны быть с одинаковым вхождением буквенных параметров и одинаковой степенью этих параметров. Такая операция называется приведением подобных членов в коэффициенте. На основе вышеприведенных рассуждений разработан укрупненный алгоритм получения характеристического полинома системы, который показан на рис. 4. Также на рис. 5 представлен алгоритм определения таблицы умножения TU для части g1, 2, …, i и множества кортежей KOR2(i). Таким образом, получаем характеристический полином всей системы в виде множества слагаемых SL(g), упорядоченных по степеням комплексной переменной р. Для каждого коэффициента ak суммируем слагаемые и находим выражение характеристического полинома в буквенно-числовом виде (5) Как видно из выражения (5), характеристический полином представлен как функция варьируемых параметров U. В рассматриваемой постановке задачи второй важной характеристикой является передаточная функция системы. Входным узлом системы в этом случае является ведущий дрон, а выходным - анализируемый дрон «роя», кроме ведущего. Для этого в граф системы вводятся дополнительные (структурные) дуги, указывающие входные и выходные узлы системы. Тогда передаточная функция системы находится в виде (6) Взятие алгебраических производных по структурным дугам позволяет получить числитель и знаменатель передаточной функции K(p,U). Рис. 4. Укрупненный алгоритм получения характеристического полинома системы Вывод Представление весов ребер и в виде параметрической функции ребра позволяет расширить возможности методов топологического анализа при автоматизированном проектировании динамических систем с изменяющимися во времени параметрами. Алгоритм дает возможность получать ХП системы как явную функцию различных параметров, а не только тех, которые непосредственно являются коэффициентами дифференциальных уравнений системы. Это намного расширяет простор проектировщику в выборе параметров варьирования. Полученная модель учитывает изменчивость состава, структуры и уровня взаимодействия «роя». При изменении «роя» нет необходимости пересчитывать весь граф, а только изменившуюся часть. Полученную топологическую модель планируется использовать при проектировании поведения «роя» с использованием известных методов, например [8-10]. Особенно эффективно использовать разработанную топологическую модель в технологии построения «роя»с ведущим дроном. Алгоритм отличается от существующих применением более оптимального механизма построения деревьев и прадеревьев частей графа, позволившего сократить затраты времени и памяти, что позволяет моделировать «рои» с большим количеством дронов. Рис. 5. Алгоритм определения таблицы умножения TU для части g1, 2, …, i и множества кортежей KOR2(i)

Galleys

(Русский)

Username
Password
Remember me
	Register

Intelligent Systems in Manufacturing