Аналитический обзор существующих методов и подходов к планированию групповых действий

Информация » Разработка алгоритмов поиска оптимального маршрута для БЛА при наблюдении им подвижных наземных объектов » Аналитический обзор существующих методов и подходов к планированию групповых действий

Страница 6

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

Данный метод описан в работе [4]. В данной работе предлагается сначала провести кластеризацию всех объектов по методу k-средних. Этот метод заключается в том, что все объекты разбиваются на количество кластеров k, равное количеству БЛА следующим образом:

случайным образом на поле решения задачи выбрасывается k точек, которые являются центрами кластеров (центроидами);

каждый объект заносится в кластер того центроида, к которому он находится ближе всего;

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

шаги 2 и 3 повторяются до тех пор, пока центроиды не перестанут передвигаться.

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

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

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

Последним шагом данного метода является применение алгоритма поиска «Tabu search», суть которого сводится к тому, что в случае, если алгоритм находит решение, которое потенциально является оптимальным, он «запрещает» его, и «разрешает» движение в сторону максимизации времени полета БЛА. Таким образом, алгоритм препятствует «застреванию» поиска в локальных минимумах.

Сильные стороны:

применение множества способов препятствования попаданию в локальные минимумы.

Слабые стороны:

исключение взаимодействия между БЛА;

применяется сразу несколько методов поиска и оптимизации, что существенно увеличивает время расчета;

метод применим только для неподвижных объектов.

Страницы: 1 2 3 4 5 6 

Похожие статьи:

Подготовка технических средств навигации
Таблица №1.7.1 -Точностные характеристики технических средств навигации Прибор, система тип, марка СКП выработки нав.пар. Измеря емый параметр Условия 1 2 3 4 5 Магнитный компас «КМО-Т» ±1,0° ±1,5о Пеленг Днем, ночью Радиопеленгатор «Рыбка » ±2,0° Радиопе-ленг Днем, ночью Гирокомпас «Вега» ±0,70 Пе ...

Расчет креплений грузов, не предусмотренных техническими условиями
Исходные данные: груз - железобетонное изделие длина груза L - 9320 мм. ширина груза В - 2455 мм. высота груза Н - 2110 мм. Количество мест заданного груза n - 1 Масса одного места груза т. а - 1110 Выбор типа подвижного состава для перевозки заданного груза Для перевозки заданного груза использует ...

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

Навигация

Copyright © 2019 - All Rights Reserved - www.localtransport.ru