Mathematical support for controlling the position of non-stationary objects of information and telecommunication system

Full Text

Введение

Планирование траектории автономного мобильного объекта (АМО) – это поиск оптимальной траектории перемещения объекта от начальной до конечной точки при определенных ограничениях, которые могут соответствовать как маневренности, так и целям миссии [1]. Однако ряд целей и ограничений может вступать в противоречие, из-за чего отсутствует универсально оптимальный путь. Следовательно, методы планирования маршрутов должны обеспечивать компромисс между различными требованиями для достижения наилучших возможных решений.

В последние годы в задаче планирования маршрутов АМО начали активно применяться методы природной оптимизации, обладающие высокой способностью к нахождению эффективных решений [2]. Среди алгоритмов, вдохновлённых природными механизмами, оптимизация роя объектов (PSO) считается одним из наиболее эффективных подходов, способных находить оптимальные решения с высокой скоростью сходимости. Хотя такой метод прост в реализации, он приводит к общей целевой функции, оптимизация которой не гарантирует достижения оптимума по каждой из составляющих целей. В таких случаях требуется иной подход – многокритериальная оптимизация.

В этой области были предложены различные методы для планирования маршрутов, основанные на многокритериальном подходе, включая многокритериальный алгоритм светлячков (MOFA), многокритериальный вариант PSO (MOPSO) и алгоритм недоминируемой сортировки второго поколения (NSGA-II). Преимущество таких методов заключается в получении множества решений, образующих фронт Парето – совокупность лучших компромиссных результатов. Тем не менее, современные многокритериальные алгоритмы, как правило, не учитывают кинематические ограничения АМО. Поскольку учёт этих ограничений критичен для построения реалистичных траекторий, их необходимо интегрировать в алгоритм.

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

 

Математическое обеспечение и накладываемые ограничения

 

Объект рассматривается как материальная точка, перемещающаяся в трёхмерном пространстве. Согласно работе [3], его движение описывается следующими кинематическими уравнениями:

 

(1)

 

где  — координаты положения АМО;

       — линейная скорость;

      и  — углы подъема и поворота.

Из-за физических ограничений на движение АМО его скорость и углы перемещения ограничены следующими условиями:

 

(2)

 

где  и  обозначают минимальную и максимальную линейные скорости;

         и  — максимальные допустимые изменения углов поворота и подъема. Учет этих ограничений необходим для формирования реалистичных маршрутов, пригодных для фактического выполнения перемещения АМО.

 

 Целевые функции для планирования перемещений

 

Траектория оценивается с помощью набора целевых функций, формализующих требования к её характеристикам. Функции разработаны на основе существующих исследований [4], однако были модифицированы и нормированы в диапазоне [0, 1] для соответствия требованиям многокритериальной оптимизации.

 

Длина маршрута

 

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

 

 

Рис. 1. Параметры траектории перемещения

 

Евклидово расстояние между двумя соседними точками обозначается как . Затраты по длине пути определяются следующим выражением:

 

(3)

 

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

 

Обход препятствий

 

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

 

Рис. 2. Иллюстрация обхода препятствий

 

Расстояние от препятствия до отрезка пути между точками  и  обозначается как . Пусть  – размер АМО, а  – необходимое безопасное расстояние. Целевая функция, отвечающая за предотвращение столкновений, формулируется следующим образом:

 

(4)

 

где  – общее число препятствий в зоне перемещения, а  вычисляется по формуле

 

((5)

 

Из уравнения (5) следует: если участок маршрута находится вне опасной зоны (рис. 2), то он не влечёт дополнительных затрат. Если же путь пересекает опасную зону, стоимость обратно пропорциональна расстоянию до центра препятствия. При прямом столкновении к функции добавляется бесконечная стоимость, указывающая на недопустимость траектории.

 

Поддержание высоты

 

Для энергоэффективной работы предпочтительно, чтобы АМО двигался на стабильной высоте. Обозначим  и  – максимальную и минимальную допустимые высоты перемещения, а  – текущую высоту в точке маршрута. Предпочтительная высота рассчитывается как . Целевая функция, отражающая отклонения от желаемой высоты, задаётся следующим образом:

 

(6)

где:

.

(7)

 

Плавность перемещения

 

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

 

(8)

 

Учитывая, что  отражает степень отклонения направления движения, функция , отвечающая за плавность, вычисляется по формуле

 

(9)

 

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

 

Подход к многокритериальной оптимизации

 

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

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

 

Эффективность Парето

 

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

 

(10)

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

Определение 1. Решение  не является доминируемым, если не существует такого решения , что  для , но при этом существует хотя бы один , для которого .

Определение 2. Пусть  – допустимая область решений, следовательно,  будет являться оптимальным решением по Парето в том случае, если оно недоминируемое относительно других элементов из множества .

Определение 3. Множество Парето-оптимальных решений  можно определить как совокупность всех решений , являющихся оптимальными по Парето.

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

 

Многокритериальная оптимизация роя

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

Пусть  и  – положение и скорость объекта  на итерации . Обозначим  как индивидуально лучшее положение объекта, а  – глобально лучшее положение роя. Тогда перемещение объекта описывается следующими уравнениями:

 

(11)

 

где  — инерционный вес;

       и  — коэффициенты когнитивной и социальной составляющих;

       и  — случайные значения из равномерного распределения на [0, 1].

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

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

 

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

 

Нижняя и верхняя границы гиперсетки по измерению  задаются как:

 

,	(12)
,	(13)

 

где  — размер ячейки, вычисляемый по числу делений .

Обозначим  — позицию выбранного лидера для объекта . Тогда обновление положения объекта записывается так:

 

(14)

 

 

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

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

 

Навигационные переменные для представления положения объектов

 

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

 

.

(15)

 

Однако использование декартовых координат, как в (15), не позволяет учесть маневренные характеристики АМО. Это затрудняет получение недоминируемых решений и мешает соблюдению кинематических ограничений, предъявляемых к допустимым траекториям.

Согласно существующим подходам, применимым в робототехнике, в частности – методами, используемыми для управления манипуляторами, мы моделируем траекторию АМО как цепь, состоящую из  сегментов. Каждый сегмент описывается набором параметров, аналогичных параметрам Денавита-Хартенберга [5], включая:

– угол подъема ;

– угол поворота ;

– длину сегмента .

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

Для реализации этой идеи в каждой точке  задается локальная система координат, связанная с ориентацией АМО (рис. 4):

– ось  направлена вперёд по линии  и ;

– ось  – влево относительно направления движения;

– ось  – вертикально вверх, перпендикулярно плоскости  и .

 

 

Рис. 4. Переменные для представления объектов

 

В этой системе используются три навигационные переменные:

–  – расстояние между последовательными путевыми точками , ;

–  – угол подъема между отрезками  и проекцией точки  на плоскость ;

–  – угол поворота между тем же отрезком и его проекцией.

Эти параметры  называются навигационными переменными. Совокупность этих переменных для маршрута  формирует вектор  в навигационном пространстве:

 

(16)

В отличие от (15), представление траектории с использованием навигационных переменных позволяет учитывать маневренность АМО и направленно ограничивать пространство поиска [6]. Ограничения на углы  и , определённые в (2), могут быть включены напрямую через допустимые диапазоны этих переменных.

Для оценки пригодности объектов необходимо преобразовать навигационные параметры  обратно в декартовое представление , что достигается с помощью последовательных матриц преобразования. Перемещение АМО от точки  к  включает три операции:

– поворот на угол  вокруг оси ;

– поворот на угол  вокруг оси ;

– смещение на расстояние  вдоль оси .

Матрица преобразования между двумя путевыми точками определяется как:

 

(17)

 

где  и  – матрицы поворота вокруг осей  и , а  – матрица смещения вдоль оси .

 

Механизм адаптивной трансформации

 

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

Для случайно выбранного объекта ​ на итерации , трансформация выполняется по следующему правилу:

 

(18)

 

где  — случайно выбранный индекс компоненты;

      — случайная величина с нормальным распределением;

       — коэффициент усиления трансформации.

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

 

(19)

 

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

 

Реализация и анализ эффективности

 

Для оценки эффективности предложенного алгоритма МОНП были проведены численные эксперименты.

 

Настройка сценария

 

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

Настройки параметров алгоритма МОНП во всех экспериментах сохранялись неизменными и задавались следующим образом:

– количество узлов в траектории: ;

– инерционный вес:  с коэффициентом затухания 0,98;

– когнитивные и социальные коэффициенты: ;

– деление гиперсетки: ;

– коэффициент масштабирования: ;

– коэффициент трансформации: ;

– пределы углов поворота и подъема: .

 

Результаты планирования траектории

 

На рис. 5-8 представлены траектории, построенные с использованием МОНП для двух сценариев. Второй сценарий отличается повышенным уровнем сложности рельефа.

 

 

Рис. 5. Трехмерный вид перемещений по алгоритму МОНП для сценария 1

 

 

Рис. 6. Трехмерный вид перемещений по алгоритму МОНП для сценария 2

 

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

 

 

Рис. 7. Боковая проекция для сценария 1

 

 

Рис. 8. Боковая проекция для сценария 2

 

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

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

Полученные нормированные значения целевых функций для различных сценариев приведены в табл. 1.

 

Таблица 1

Результаты значений целевых функций

Сценарий	Показатель	Результаты
1		0,013	0,016	0,038
		0,026	0,025	0
		0,289	0,086	0,07
		0,036	0,036	0,06
2		0,213	0,052	0,144
		0,015	0,006	0
		0,088	0,16	0,086
		0,094	0,074	0,148

 

Предлагаемый алгоритм МОНП имеет возможность формировать множество недоминируемых решений, что делает данный метод универсальным инструментом.

Заключение

 В данной работе предложен новый подход к планированию перемещений АМО – алгоритм МОНП, сочетающий принципы многокритериальной оптимизации с учётом кинематических ограничений.

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

_________________________

© Черноиваненко И.А., 2025

About the authors

Igor’ A. Chernoivanenko

Voronezh State Technical University

Author for correspondence.
Email: chernoivanenko2000@mail.ru

graduate student

Russian Federation, 84 20-letiya Oktyabrya str., Voronezh 394006, Russia

References

Supplementary files