ОПТИМАЛЬНОЕ ПЛАНИРОВАНИЕ ОПЕРАЦИЙ РОЯ ПОДВИЖНЫХ ОБЪЕКТОВ В УСЛОВИЯХ НЕОПРЕДЕЛЁННОСТИ

Оптимальное планирование операций роя подвижных объектов

в условиях неопределённости

Я.А. Мостовой1, В.А. Бердников1 1 Самарский национальный исследовательский университет имени академика С.П. Королёва, 443086, Россия, г. Самара, Московское шоссе, д. 34

Аннотация

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

Цитирование: Мостовой, Я.А. Оптимальное планирование операций роя подвижных объектов в условиях неопределённости / Я.А. Мостовой, В.А. Бердников // Компьютерная оптика. - 2020. - Т. 44, № 3. - С. 466-475. - DOI: 10.18287/2412-6179-CO-599.

Citation: Mostovoy YA, Berdnikov VA. Optimal planning of networks of mobile objects under uncertainty. Computer Optics 2020; 44(3): 466-475. DOI: 10.18287/2412-6179-CO-599.

Введение

Одним из самых быстро развивающихся направлений робототехники на сегодняшний день является групповая робототехника подвижных объектов (или робототехника роя) [1-6]. Рой роботов, как система относительно простых взаимосвязанных объектов, выполняющих общую задачу, по сравнению с обычным одиночным роботом, пусть и имеющим более сложную платформу, имеет ряд преимуществ, наиболее значимые из которых:

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

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

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

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

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

Рассматриваемая задача распределённого размещения объектов роя в зоне обслуживания сначала случайным образом, а затем в некоторой фронтальной беспропусковой структуре требует представления зоны обслуживания в виде квадратной матрицы со случайным заполнением квадратных же ячеек, как модели случайной операционной среды в прямой геометрической интерпретации [7-10].

В этой квадратной матрице с числом строк Ь случайная часть ячеек чёрная, содержащая объекты роя, а остальные ячейки - белые, не содержащие объектов. В рассматриваемой задаче чёрная ячейка может быть представлена как прямая геометрическая интерпретация зоны работы целевой аппаратуры робота, и размер квадратной ячейки задаётся вписанной в неё окружностью с радиусом действия аппаратуры или зоной передачи сигналов взаимодействия объектов роя между собой (радиус вписанной в ячейку окружности - не менее чем половина дальности возможного взаимодействия).

При росте концентрации «чёрных» ячеек (вероятности появления объекта в ячейке) некоторые из них случайным образом начинают соприкасаться рёбрами, что можно интерпретировать как возникновение тесного взаимодействия, и сливаться. Соприкасающиеся рёбрами (не вершинами!) чёрные ячейки образуют случайные «проводящие» кластеры, которые образуются и растут вместе с ростом концентрации чёрных ячеек [7, 11].

В этом случае перколяционный путь через матрицу - модель зоны обслуживания будет путём сквозного беспропускного фронтального покрытия зоны обслуживания работой целевой аппаратуры или передачи сигнала от одного робота другому при сетевом управлении роем.

В классической теории перколяции [7, 9-12] ищется концентрация чёрных ячеек рпр - порог стохастической перколяции, при которой образуется сквозной проводящий случайный маршрут по «чёрным» ячейкам через всю матрицу в заданном направлении - стохастический перколяционный кластер.

При этом доказано, что концентрация порога стохастической перколяции для квадратных матриц находится в окрестности рпр = 0,59 для матриц конечного размера.

Стохастический перколяционный кластер имеет рыхлую структуру, множество «мёртвых ветвей» и явно избыточен с точки зрения решения поставленных практических задач, а классическая теория стохастической перколяции не может быть использована для этой цели. Поэтому в [13-18] авторами предложен и развивается аппарат искусственной управляемой или программируемой перколяции.

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

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

Центральный вопрос этой задачи - какова должна быть оптимальная с точки зрения минимизации общих затрат концентрация объектов роя на первой фазе.

В [9 -11, 18, 19] рассмотрена большая сеть нано-спутников. В [12, 17, 20] рассматривается сеть неподвижных объектов, состояние которых может меняться от незащищённого (белая ячейка) к защищён-ному (чёрная ячейка). В обоих случаях применение двухфазных операций позволило на второй фазе построить сквозной перколяционный путь, снизив концентрацию объектов, и минимизировать общие затраты. При этом источник заполняющих межкластерные интервалы объектов не рассматривался и в обоих случаях можно говорить о статической картине двухфазных операций.

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

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

Для подвижных и управляемых объектов роя в данном случае после снятия неопределённости о месте и времени проведения операции выполнение второй фазы происходит одновременно по всем межкластерным интервалам планируемого пути программируемой перколяции и занимает поэтому минимальное время, которое можно оценить как T ^К, где T ф) -средний путь «установки объекта роя» в межкластерную дыру, измеряемый в числе ячеек матрицы и на определённой в статье рабочей оптимальной концентрации p = 0,2 (T(p) < 3), C - скорость перемещения объекта роя.

С другой стороны, построение управляемого пер-коляционного пути сразу после появления определённости о месте и времени операции в одну фазу без проведения предварительной подготовки займёт гораздо больше времени. Это время может быть оценено величиной порядка L /C, где L - размер зоны обслуживания в числе ячеек матрицы. Можно полагать, что достижимое в ближайшее время число объектов роя подвижных объектов [21] будет определяться значением L > 20.

За эту оперативность двухфазных операций приходится платить избыточностью объектов роя относительно минимально необходимого их количества, которая может быть оценена, как показывают результаты статистического моделирования, величиной 0^. Эта избыточность обеспечивает надёжность проводимой операции роя и возможность оперативной замены её цели.

Таким образом, двухфазные операции управления роем подвижных объектов обеспечивают: - сокращение времени реализации перколяции зоны

обслуживания на второй фазе за счёт подготовки

этого процесса на первой фазе операции,

- минимизацию общей стоимости операции за счет оптимизации количества объектов в рое - концентрации объектов роя.

Статистическое моделирование на конечных квадратных матрицах является основным методом исследования теории перколяции. Это моделирование позволяет обнаружить и исследовать три статистических феномена теории. Первый статистический феномен - наличие порога стохастической перколяции, как «пробоя» матрицы при определённой концентрации pпр проводящим перколяционным кластером, подробно описан в [7, 13].

Второй статистический феномен, описанный и рассмотренный авторами в [13-18, 20], - наличие значения концентрации, при котором среднее число образовавшихся кластеров имеет максимум. Обнаруженная в результате численного статистического моделирования характерная зависимость среднего числа образующихся кластеров от концентрации с максимальным значением при концентрации в районе 0,26 физически объяснима: при дальнейшем росте концентрации кластеры растут и начинают активно объединяться, при этом их количество падает.

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

Также в ходе численного статистического и аналитического моделирования в [7, 13-18] были установлены зависимость от концентрации объектов средней длины пути (извилистости пути) программируемого перколяционного пробоя с максимумом в районе pпр = 0,59 и зависимость от концентрации среднего числа добавленных в межкластерные интервалы объектов с минимумом в районе pпр = 0,59. Это можно считать третьим статистическим феноменом, который также и проявляется на концентрации pпр.

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

В результате использования при планировании операций роя в условиях неопределённости второго статистического феномена суммарная концентрация объектов роя при реализации такой программируемой перколяции становится в три раза меньше порога стохастической перколяции. Соответственно, в три раза меньше становится потребное для проведения операции число объектов роя.

Для исследования второго статистического феномена нами проведено обширное статистическое моделирование на нескольких тысячах матриц со случайным заполнением различного размера и при различной концентрации чёрных ячеек. При этом образующиеся кластеры распознавались алгоритмом Хо-шена-Копельмана [22, 23] и подсчитывалось среднее количество образовавшихся кластеров для каждой концентрации объектов роя. Результаты приведены на рис. 1. Если данные результаты нормировать по площади матрицы - количеству ячеек в ней, то среднее нормированное количество кластеров для матриц большого размера не зависит от размеров матрицы, что также отмечено на рис. 1 [7, 14-18, 20].

Функции МСр)

Рис. 1. Внешний вид функций М$(р) членов ряда и функции суммы членов ряда Мэ(р) - среднего количества кластеров

в зависимости от концентрации р: график 1 - М(р), график 2 - Мв=1(р), график 3 - Мв=2(р), график 4 - Мв=з(р), график 5 - Мэ=4(р), график б -Мэ=5(р), график 7 - Мв=б(р)

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

Аналитически была получена основанная на подсчёте образующихся случайным образом фигур кластеров - «зверей» [11] - зависимость среднего количество кластеров объектов от концентрации (для N ^ да), нормированная по числу ячеек в матрице:

N »тах5

m (p ) = £ £ gstNps (1 - p )

где N - количество ячеек в перколяционной матрице, p - концентрация объектов на матрице, 5 - количество ячеек, из которых состоит кластер, t - необходимое количество пустых (белых) ячеек вокруг отдельно существующего кластера, gstN - количество различных «фигур» кластеров, которые можно получить из 5 ячеек и с t пустыми соседними ячейками.

Графики изменения по концентрации р каждого члена ряда МДр) для 5 < 6 приведены на рис. 2. Из рисунка видно, что значения МДр) с ростом 5 убывают для каждого из значений р, что делает ряд сходящимся [20]. Это убывание членов ряда по 5 для каждого

значения p примерно соответствует закону степенной регрессии, что позволяет оценить сумму всех членов данного ряда. На рис. 2 приведён график изменения по концентрации p среднего количества кластеров, построенный по выражению 1. Он практически совпадает во всех точках с аналогичным графиком на рис. 2, построенным на базе статистических исследований по матрице со случайным заполнением. Таким образом, статистический феномен максимума среднего количества кластеров [13-16], обнаруженный как результат статистического моделирования, подтверждается данным аналитическим выражением 1.

Также был проведён обширный математический эксперимент [7, 13-18] по исследованию двухфазной операции на различных перколяционных матрицах конечного размера. Данный эксперимент проводился следующим образом: на множестве матриц проводился сначала случайный «засев» объектов роя с различными концентрациями. Далее выделялись все образовавшиеся кластеры, и через попутные кластеры (т.е. кластеры, через которые проходит планируемый путь) строились оптимальные программируемые пер-коляционные пути.

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

Фунщии М(р) " "" 3000^

Концентрация, р

Рис. 2. Среднее количество кластеров как функция вероятности нахождения объекта в ячейке -концентрации, полученное в результате статистического моделирования на матрицах различного размера; график 1 - нормированная функция среднего количества кластеров, график 2 - функция среднего количества кластеров для матриц 150*150, график 3 - функция среднего количества кластеров для матриц 100*100, график 4 - функция среднего количества кластеров для матриц 50*50

На рис. 3 в качестве иллюстрации представлены результаты работы алгоритма «Молния-Дейкстра» для матриц размера 30 х 30 для концентраций p = 0,25 (рис. 3а) и p = 0,4 (рис. 36).

На полученном на рис. 3 примере одного из путей программируемой перколяции есть два типа ячеек:

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

□ □ ■

□ □ □ □ ■

□ □ □ □ ■ ■ ■

□ □ □ □ □ □ ■ ■ □ □ □ □ □ □ □ ■ □ □ □ □ □ □ □ □ ■ □ ■ □ □ ■ □

□ □ I ■ I

□ □ □ □ □ □ □ □ ■ □ □ □ □ ■ □ □ □ □ ■ □ ■ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □

□ □ □

□ ■ □ □ I

□ □ ■ □ I

□ □ I ■ □ I

□ □ ■ ■ ■ ■ ]

□ ■ □ □ □ □ □ □ □ ■ ■ ■ ■ ] □ ■ ■ ■

□ □ □ □ ■ □ □ □ □ □ □ ■ ■ □ □ ■ □ □ □ ■ □ □ □ □ ■

□ □ 1 □ □

■ ■ □ □ ■

I □□□□□□I

■ ■ □ □ □ I

I □ □ □ □ ■ ■ □□□□□□□

■ ■ □□□□! □□□□□□□

■ ■ □ □ □ ■

□ ■ ■

□ ■ ] □ □ □ □ □ [ ■ ■ ■

□ □ [ ■ ■ □□□□□□

□ ■ : □ □ □ □

■ □ □ □

□ ■ □ □ □ I

□ □ □ □ □ I

□ □ □ □ ■ □

I □ ■ ■ ■ ■

I □ □ □ [ ■

■ □ □ □ ■ □ ■ □ □ □ □ □ □ □ □ □ □ ■

□ □ □

□ ■ ■ ■

□ □ I ■ ■

□ □ □ □ □

□ □ [ ■ ■ □ □ □ □ □ □

■ □ □ I □ □ □ I I □ I

I □ □ □ ■ I □ □

□ □ □

□□□□□□I □ □

□ □ □ □ I

I □ □

I □ □ □ I ■

□ ■ □ □ ■ □ □ □ □ □ □ □ □

□ □ I

□ □ I

□ ■■]:■■ ■ □ I

□□□□□□□

□ □ □ □ □ □ □ □ □ □ □ □ □ □ □ □ ■ □ ■ □ □ ■ □ ■ □

I □ □ □ □

I ■ ■ □ □

I □ □ □ ■

■ ■ ■ ■

□ □ □ □ ■ □

■ □ □ ■ I

□ □ ■ □ I □ □ i

■ □ □ □ □ ■ □ □ □ □

I С ■ □ ■ ■

I □ □ □ □

□ □ □ □ □ □ ■ ■ ■

□ □ □ ■ □ □ □

■ ■ ■ ■ ■ ■

□ □ □ □ □ ■ ■ ■ □ □ □ □ ■ □ □ ■ ■ ■ □ ■ ■ ■ ■ □

□ □ □

[ ■ I ■ ■ ■ ■ ■

□ [ ■ ■ ■ ■ ■ [ ■■ ■

■ □ ■

□ □ □ □

I С ■ □ □

I □ □ □ □ □ □ □ □

□ □ □ □ □ □ ■ □ □ □ ■ □

□ 1 □

■ ■ □ ■

■ □ □

I □ □

□ □ I

□ □ ■ [

■ □ □ □ I □ III

■ ■ I

■ □ □ I

I □ □

■ ■ □ ■ ■ □ □ ■

□ □ □

■ ■ I

■ ■ □ I

□ □ □ I

■ □ □ I

II □ I

I □ □ □ I ■ ■

□ С ■ □□□□□□□□

■ □I I

□ I □ ■

□ □ I

□□■□□□□□□□□□I

□ □ I

□ □ □

■ ■ □ [ ■ ■ ■

□□□□□□□□□□I

■ □I

□ □ I

□ □ □ □ □

II □ ■ ■ ■

□ □ □ □ □ ■ ■ □ □ □ □ ■ ■ ■ □ □ □ □ □ ■

Рис. 3. Увеличение извилистости (длины) пути с ростом концентрации p концентрация p=0,25 (а), концентрация p=0,4 (б)

■ □I

■ □I

□ □ I

□ □ I

■ ■I

■ □ □

□ ■ □ ■

■ ■ ■ ■

□ □ □ □ □ □

□ □ 1 □ ■ □

I □ □ □ I □ □ □

I □ ■ ■ ■ ■

I ■ □

I ■ □ ■ ■ □

I □ □ □

I □ 1 □ ■ ■

I □ □ □

I □ ■ □

I □ □ ■

□ □ □

□ □ ■

□ □ □ □ ■ □ ■ □ ■ ■ □

□ ■ □ □ ■ ■

□ ■ □ □ ■ □ □ ■ □ □ □ □ ■ ■ ■ □ □

□ 1 □ □ ■

□ 1 □ ■ ■ ■

□ ■ □ ■ ■ □ ■ □ ■ ■ □ ■ □ □ ■ □ □ □ □ ■ ■ □ ■ ■ □ □ □ □ □ ■

□ 1 □ □ ■ ■

□ □ □ ■ ■ □ □ □ ■ □ □ ■ ■ ■ □ ■ ■ ■ □ □ ■ □ ■ ■ ■ ■ ■ □ □ ■ □ ■ □ □ □ ■ □ □ ■ ■ ■ □ □ □ □

I С ■ ■ I ■ I ■ ■ I ■

■ □ ■ □

Статистическая обработка ансамбля полученных путей позволила определить среднюю длину кратчайшего пути программируемой перколяции, среднее количество объектов роя, добавляемых в межкластерные интервалы (см. рис. 5), как функции концентрации объектов роя от р. Независимость полученных результатов рис. 4, 5 от размера матрицы обеспечивается их нормированием по длине матрицы L.

Также была определена средняя длина «пути установки» T(p) (рис. 6) в зависимости от концентрации p объектов роя - минимальное в среднем расстояние, на которое надо переместить нужный нам для установки на перколяционный путь ближайший внешний по отношению к перколяционному пути объект роя.

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

Обозначим K(p) - среднюю длину пути искусственного программируемого перколяционного пути, измеренную в количестве ячеек, от концентрации объектов роя - вероятности наличия объекта роя в ячейке. Очевидно, что данная средняя длина является суммой двух функций, зависящих от концентрации, Бф) и Яф) - соответственно среднего количества чёрных ячеек, лежащих на попутных кластерах и среднего количества добавленных ячеек (красных).

K (p ) = B (p )+ R (p ).

Нами найдено, что нижеприведённые выражения (3) и (4) для В(р) и R(р) хорошо аппроксимируют полученные результаты статистического исследования (рис. 4, 5). Структура выражений (3) и (4) вытекает из рассмотрения процесса случайных отклонений пути программируемой перколяции от заданного направления из-за прохождения через попутные случайно расположенные кластеры. В структуре выражений (3) и (4) просматривается функция, связанная с функцией распределения Релея, которой можно аппроксимировать зависимость от концентрации числа кластеров (см. рис. 2) [20, 24].

B (p ) = p"Q (p)L

■Q(p)\\

при p < (3)

B(p) = L, при p >

где Q (p ) =

М(р) - среднее количество кластеров, Ь - длина матрицы, через которую идет перколяция, С - согласующий коэффициент, являющийся функцией от р и равный 0,97 для р < 0,25; 1,09 для 0,25 < р < 0,4; 0,85 для 0,4 < р < 0,59 и 0,75 для 0,4 < р < л/4. Если использовать среднеинтегральное С1 = 0,9, то полученная аппроксимация будет несколько хуже, но в целом проще (см. рис. 4).

Функции М(р)

Рис. 4. График 1 - статистическое среднее количество попутных чёрных ячеек В(р) в пути программируемой перколяции; график 2 - среднее количество попутных чёрных ячеек по выражению (3) с несколькими описанными

пороговыми значениями согласующего параметра С1; график 3 - среднее количество попутных чёрных ячеек для одного среднеинтегрального значения коэффициента С1

Для Я(р) аппроксимирующая функция равна:

к (р) = р^ро, (р)(1 -р)Ь е 2(Прр(р))2 ,

(с>1 (р ))2

где ^ (р) - средняя «ширина» кластера, равная 1,483(1 -р) , ч 1

M (р)(гшах( р)

Гшах (р )=Щр),

Яро,(р) - параметр масштаба, равный: ъРо1 (р) =

= I , 1 Л , В(р) =Ь,

V, (р)=2 (1 - р )^ро, (р )

м (р )И (р )6С2

где р /М(р) - среднее число черных ячеек в кластере, 2

И (р) =

Ш(х) - "-функция Ламберта [25], С2 - согласующий коэффициент, являющийся функцией от р и равный

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

Рис. 5. График 1 - статистическое среднее количество

добавленных ячеек Щр), нормированное по размеру матрицы Ь, в перколяционный путь; график 2 - среднее количество добавленных ячеек по выражению (4) с несколькими описанными пороговыми значениями согласующего параметра С2; график 3 - среднее

количество добавленных ячеек для одного среднеинтегрального значения коэффициента С2

Результаты расчётов, проведённых по данным выражениям, приведены на рис. 4 и 5 для сравнения с аналогичными результатами статистического моделирования. Их расхождения малы и допустимы.

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

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

Таким образом, у каждого члена роя может быть сформирована бинарная матрица роя, как модель зоны обслуживания, где 1 означает, что в данной точке пространства - ячейке матрицы установлен член роя, 0 - в ячейке член роя отсутствует.

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

Управляющая система более высокого уровня иерархии (ею может быть как специально назначенный член роя, так и внешний по отношению к рою объект) не управляет перемещением объектов роя, а лишь передаёт рою целеуказание в достаточно общем виде - координаты начального и конечного членов роя (А и В соответственно), между которыми необходимо проложить сквозной перколяционный путь для решения целевой или связной задачи.

Каждый член роя строит у себя в памяти бортовой ЦВМ перколяционный путь, используя упомянутые алгоритмы, и оценивает своё положение относительно этого пути. При этом ближайшие к межкластерным интервалам запланированного перколяционного пути объекты роя самостоятельно и автономно перемещаются в эти межкластерные интервалы.

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

После выбора оптимальной концентрации объектов роя, исходя из покрытия зоны обслуживания и выполнения первой фазы операции, при появлении определённости о месте проведения второй её фазы для конкретной реализации второй фазы могут быть использованы те же самые алгоритмы (Молния-Дейкстра, Хошена-Копельмана и т.п.), что и при статистическом моделировании.

Обозначим стоимость каждого из распределенных случайным образом объектов а, а стоимость одного объекта, устанавливаемого в определённое место большой сети, - ZR(p). При этом ZR(p) > а с учётом стоимости его установки в межкластерный интервал.

Тогда суммарная стоимость двухфазной операции Р будет:

Р = арЬ2 +ZR(р)R(р)Ь .

Здесь первое слагаемое - стоимость стохастической основы большой сети роботов, а рЬ2 - среднее количество членов роя в стохастической основе.

Второе слагаемое - стоимость добавленных объектов для формирования кратчайшего искусственного перколяционного пути через стохастически образованные попутные кластеры объектов. При этом R(p) -среднее количество этих добавленных объектов, определённых по результатам вышеприведённых исследований и статистического моделирования, нормированное по размеру матрицы Ь (см. рис. 5).

Значения а и ZR (р) зависят от множества факторов, характерных для конкретной конструкции объекта роя. В этих условиях нам совсем не обязательно получать конкретные значения стоимости двухфазной операции. Для оптимального планирования достаточно определить значение концентрации объектов роя, при которой выражение для суммарной стоимости операции будет иметь минимум.

Затраты на один дополняющий перколяционный путь объект роя с установкой его в межкластерный интервал планируемого программируемого перколя-ционного пути ZR (р) будем определять как стоимость одного объекта а, увеличенную пропорционально длине среднего «пути установки» Т (р), от места первоначального расположения в ближайшей окрестности пути перколяции до места «дырки» в планируемом пути программируемой перколяции (см. рис. 6). Значения Т(р) получены в результате статистического моделирования по большому числу матриц, не зависят от размера матрицы и не нормируются по нему.

Затраты на перемещение и установку одного дополняющего перколяционный путь объекта также прямо пропорциональны числу межкластерных «дырок» Б (р)Ь, в которые надо установить дополняющие объекты (см. рис. 7), и обратно пропорциональны отношению количества объектов роя в ближайшей окрестности планируемого перколяционного пути, готовых встать в межкластерные интервалы О (р) к общему потребному количеству добавляемых «красных» объектов R (р) Ь на планируемом перколяционном пути. Чем больше это отношение, тем меньше затраты на выбор и перемещение дополняющих объектов.

ZR (р) = Е аБ (р)Т(р)*(р)Ь2

Здесь Е - некоторый, пока не определённый коэффициент пропорциональности, зависящий от конструкции объектов роя.

График Т(р) весьма близок к полученному в [17] графику зависимости среднего размера «дырок» вдоль пути программируемой перколяции (см. рис. 6, график 2). Действительно, и в том, и в другом случае речь идёт о среднем размере межкластерного интервала. Однако для межкластерных интервалов на программируемом перколяционном пути следует учитывать, что они получены в результате выбора кратчайшего пути алгоритмом Дейкстры.

В свою очередь, количество располагаемых для перемещения объектов G(p) определяется длиной пути управляемой перколяции K(p) (см. рис. 5), вдоль которого они размещены, умноженной на погонную «толщину слоя «ближайших» к планируемому перко-ляционному пути объектов и на концентрацию p объектов роя.

Функция 7

Рис. 6. График 1 - средняя длина «пути установки» Т(р) от концентрации; график 2 - средний размер межкластерного интервала от концентрации

Функция 7

Рис. 7. График среднего количества интервалов между

кластерами пути программируемой перколяции D(p)

от концентрации, нормированный по размеру матрицы

В качестве толщины слоя рассмотрим тот же определённый статистическим моделированием «средний путь установки» T(p), зависящий от концентрации p. При этом, умножая площадь зоны вокруг пути перколяции на значение концентрации p, мы получим количество объектов роя, распложенных в таком слое вокруг перколяционного пути:

G(p) — K(p)T(p)Lp .

Тогда окончательно затраты на один дополняющий перколяционный путь объект роя

zr (p )—F .

у & pK (p)

С учётом этого уравнение суммарных затрат примет вид:

Р = apL2 +F aD(p)Я2 (p)L2 pK (p)

В полученной формуле есть неопределённые величины, зависящие от конструкции объектов роя (F, a). Рассмотрим относительную стоимость двухфазной операции, приведённой к стоимости однофазной операции с чисто стохастической перколяцией объектов роя, для чего разделим левую и правую часть полученного уравнения на Рп = apпр L2, учитывая, что для концентрации порога перколяции p^ > 0,59 значение Яф^) ^ 0.

Тогда:

РОТН — "

■ —1,7

p + F

я 2 (p )

где F - коэффициент пропорциональности, K(p) - зависимость длины среднего нормированного пути управляемой перколяции от концентрации (см. рис. 5), D(p) - среднее нормированное количество интервалов между кластерами кратчайшего пути (см. рис. 7), R(p) - среднее нормированное количество добавленных объектов (см. рис. 4).

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

Зависимость относительной стоимости двухфазной операции от концентрации приведена на рис. 8 для различных значений F, поскольку нас интересует, учитывая сказанное, не абсолютное значение стоимости двухфазной операции, а положение минимума функции стоимости в зависимости от концентрации p объектов роя в зоне обслуживания.

Анализ полученных зависимостей показывает, что при значении коэффициента пропорциональности F = 0,1 оптимальное значение концентрации - вероятности наличия объекта в ячейке стохастической основы составляет 0,2. Это значение концентрации меньше значения концентрации для максимального числа кластеров стохастической основы и почти в три раза меньше порога стохастической пер-коляции. В случае, если F не равно 0,1, значение оптимальной концентрации стохастической основы увеличивается до 0,25.

Также отметим, что рассматривать концентрацию объектов роя роботов в зоне обслуживания ниже 0,05 нецелесообразно. В таком рое будет не более чем 0,05L2 объектов, но количество добавленных объектов для организации программируемого перколяци-онного пути в случае малых концентраций будет стремиться к L (см. рис. 4).

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

Рис. 8. Зависимость относительных затрат на проведение двухфазной операции от концентрации для коэффициентов пропорциональности F = 0,1 (график 3), F = 0,15 (график 2) и F = 0,2 (график 1)

Заключение

- уменьшение времени реализации перколяции зоны обслуживания на второй фазе за счёт подготовки этого процесса на первой фазе операции,

- минимизацию общей стоимости операции за счёт оптимизации количества объектов в рое -концентрации объектов роя.

Литература

Концентрация, p

International Journal of Modern Physics C. - 1998. -Vol. 9, No 1. - P. 43-61.

Сведения об авторах

Мостовой Яков Анатольевич, 1940 года рождения, в 1963 году окончил Куйбышевский авиационный институт по специальности «Летательные аппараты», доктор технических наук, много лет проработал в РКЦ ЦСКБ - Прогресс, последняя должность - главный конструктор, Лауреат Государственной премии СССР, в настоящее время профессор Самарского университета. Область научных интересов: компьютерное управление сложными техническими системами. E-mail: _jakob.mostovoi@yandex.ru .

Бердников Валерий Андреевич, 1994 года рождения, в 2016 году окончил Самарский национальный исследовательский университет имени академика С.П. Королева по специальности 10.05.03 «Информационная безопасность автоматизированных систем», аспирант Самарского университета. Область научных интересов: математическое моделирование, теория перколяции, теория вероятности, роевая робототехника, искусственный интеллект. E-mail: teridax63@yandex.ru .

ГРНТИ: 27.43.51

Поступила в редакцию 15 июля 2019 г. Окончательный вариант - 16 апреля 2020 г.

Optimal planning of networks of mobile objects under uncertainty

Y.A. Mostovoy 1, V.A. Berdnikov1 1 Samara National Research University, 443086, Samara, Russia, Moskovskoye Shosse 34

Abstract

When solving a given common task, a swarm of moving objects coordinates the state of its individual members. When planning swarm operations, there is a need to take into account the possibility of its operational regrouping, since at the time of planning the exact purpose of the swarm operation may be either not yet defined, or secret, or determined by a number of random circumstances. At the same time, the swarm resources are insufficient for one-time coverage of all possible targets in a given service area. Therefore, the execution of the operation of the swarm begins to resolve the aforementioned uncertainties. In this case, the operation time can be significantly reduced. This problem is solved by methods of the percolation theory. A concept of programmable percolation of the service area, which is implemented in two phases, is introduced. The value of the concentration of objects in a basic stochastic swarm is obtained numerically -- using the results of statistical modeling of two-phase operations -- and analytically, providing a minimum total cost of the two-phase operation. The synergy of information interaction between the swarm objects when implementing a programmable percolation path is analyzed.

Citation: Mostovoy YA, Berdnikov VA. Optimal planning of networks of mobile objects under uncertainty. Computer Optics 2020; 44(3): 466-475. DOI: 10.18287/2412-6179-CO-599.

References

[1] Kalyaev IA, Gayduk AR, Kapustyan SG. Models and algorithms of team management in robot teams [In Russian]. Moscow: "Fizmatlit" Publisher; 2009.

[2] Kalyaev IA, Gaiduk AR. Social principles of management in the entity groups. Mechatronics, Automation, Control 2004; 12: 27-38.

[3] Grosan C, Abraham A, Chis M. Swarm intelligence in data mining. In Book: Abraham A, Grosan C, Ramos V, eds. Swarm intelligence in data mining. Berlin, Heidelberg: Springer-Verlag; 2006: 1-20. DOI: 10.1007/978-3-540-34956-3_1.

[4] Beni G. From swarm intelligence to swarm robotics. In Book: §ahin E, Spears WM, eds. Swarm Robotics. SAB 2004 International Workshop. Berlin, Heidelberg: Springer-Verlag; 2005: 1-9.

[5] Bonabeau E, Meyer Ch. Swarm intelligence: a whole new way to think about business. Harv Bus Rev 2001; 79(5): 106-114.

[6] Sahin E. Swarm robotics: From sources of inspiration to domains of application. In Book: §ahin E, Spears WM, eds. Swarm Robotics. SAB 2004 International Workshop. Berlin, Heidelberg: Springer-Verlag; 2005: 10-20.

[7] Moskalev PV, Shitov VV. Mathematical modeling of porous structures [In Russian]. Moscow: "Fizmatlit" Publisher; 2007.

[8] Alexandrowicz Z. Critically branched chains and percolation clusters. Phys Lett A 1980; 80(4): 284-286.

[9] Stauffer D. Scaling theory of percolation clusters. Phys Rep 1979; 54: 1-74.

[10] Stauffer D, Aharony A. Introduction to percolation theory. London: Taylor Francis; 1992.

[11] Tarasevich YY. Percolation: theory, applications, algorithms. Moscow: "URSS" Publisher; 2002.

[12] Galam S, Mauger A. Universal formulas for percolation thresholds. Phys Rev E 1996; 53(3): 2177-2181.

[13] Mostovoy JA. Statistical phenomena for scale distributed clusters of nanosatellites [In Russian]. Vestnik of Samara University 2011; 26: 80-89.

[14] Mostovoy YA. Two-phase operations in scale networks of nanosatellites. Computer Optics 2013; 37(1): 120-130.

[15] Mostovoy YaA. Controlled percolation and optimal two-phase operations in scale networks of nanosatellites [In Russian]. Vestnik of Samara University. Aerospace and Mechanical Engineering 2014; 1(43): 253-266.

[16] Mostovoi YA. Simulation of optimal two-phase operations in random operating environments. Optoelectronics, Instrumentation and Data Processing 2015; 51(3): 241-246.

[17] Mostovoy YA, Berdnikov VA. Large scale networks security strategy. CEUR Workshop Proceedings 2017; 1901: 187-193.

[18] Mostovoy YA, Berdnikov VA. Statistical modeling of a scale network of nanosatellites. J Phys: Conf Ser 2018; 1096(1): 012184.

[19] Mostovoy YA, Berdnikov VA. Planning of a large network of nanosatellites with coverage of the inter-orbit interval of the orbit route. Proceedings of the conference "VI all-Russian scientific and technical conference with international participation". Actual problems of rocket and space technology ("VI Kozlov readings")" 2019; 2: 157169.

[20] Mostovoy YA, Berdnikov VA. Analytical and numerical modeling of the process for cluster emergence of objects in a random environment. J Phys: Conf Ser 2018; 1096(1): 012185.

[21] The U.S. military&s ultimate weapon is almost here: The &Swarm&. Source: (https://nationalinterest.org/blog/the-buzz/the-us-militarys-ultimate-weapon-almost-here-the-swarm-18173).

[22] Babalievski F. Cluster counting: Hoshen-Kopelman algorithm versus spanning three approach. Int J Mod Phys C 1998; 9(1): 43-61.

[23] Hoshen J, Kopelman R. Percolation and cluster distribution. I. Cluster multiple labeling technique and critical concentration algorithm. Phys Rev B 1976; 14: 3438-3445.

[24] Wadzinski RN. The reference probability distributions [In Russian]. Saint-Petersburg: "Nauka" Publisher; 2001.

[25] Euler L. De serie Lambertina Plurimisque eius insignibus proprietatibus. Acta Acad Scient Petropol 1783; 2: 29-51. Reprinted In Book: Euler L. Opera Omnia, Series Prima. Vol 6 Commentationes Algebraicae. Leipzig, Germany: Teubner; 1921: 350-369.

[26] Bezruchko BP, Koronovskii AA, Trubetskov DI, Khramov AE. The way to synergetics. Excursion in ten lectures [In Russian]. Moscow: "KomKniga" Publisher; 2005.

Authors& information

Yakov Anatolyevich Mostovoy, born in 1940, in 1963 he graduated from Kuibyshev Aviation Institute with a degree in Aircraft, doctor of Technical Sciences, worked for many years in the RCC TsSKB - Progress, last position -Chief Designer, Laureate of the State prize of the USSR, currently Professor of the Samara University. Research interests: computer control of complex technical systems. E-mail: _jakob.mostovoi@yandex.ru .

Valery Andreevich Berdnikov, born in 1994, graduated from Samara National Research University in 2016, specialty 10.05.03 "Information Security of Automated Systems", post-graduate student of Samara University. Research interests: mathematical modeling, percolation theory, probability theory, swarm robotics, artificial intelligence. E-mail: teridax63@yandex.ru .

Received July 15, 2019. The final version - April 16, 2020.