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

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

Страница 4

Рисунок 1.1.15а

Рисунок 1.1.15б

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й – 9, до 4-й – 20, до 5-й – 20, до 6-й – 11.

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

простота реализации;

быстрота работы;

известное заранее время поиска.

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

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

Жадный алгоритм

Существует несколько вариантов работы жадного алгоритма, но, в целом, их принцип сводится к тому, что находится оптимальное решение для каждой локальной задачи, но решение глобальной задачи может в общем случае не являться оптимальным. Для задачи поиска оптимального маршрута это вырождается в то, что следующим всегда выбирается объект, «ближайший» к текущему положению БЛА. Но в данном случае маршрут, который получается в результате, не всегда является оптимальным (Рисунок 1.1.16). [2]

Рисунок 1.1.16 Сравнение оптимального пути (черные стрелки) и пути, полученного с помощью жадного алгоритма (красные стрелки)

Как видно из рисунка 1.1.16, маршрут из начальной точки Н в конечную точку К, полученный с помощью жадного алгоритма, отличается от оптимального.

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

простота реализации;

быстрота работы;

известное заранее время поиска.

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

неоптимальное решение глобальной задачи.

Выбор алгоритма для поставленной задачи

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

Жадный алгоритм не подходит для решения в силу того, что в общем случае не дает оптимального результата.

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

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

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

Обзор существующих методов оптимизации групповых действий

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

Мультиагентные системы

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

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

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

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

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

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

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

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

Расчет численности работающих
На эксплуатационном предприятии состав работающих делится на следующие категории: — производственные рабочие; — эксплуатационный персонал (водители); — вспомогательные рабочие; — инженерно-технические работники; — счетно-конторский персонал; — младший обслуживающий персонал. К производственным рабо ...

Построение статических характеристик регулятора и системы автоматического регулирования
Статическая характеристика регулятора строиться следующим образом: - в координатных осях np - h указывают заданный для расчёта установившийся режим работы 0 как исходный, с координатами , определёнными посредством формул (12), (23) и графика назначаемых индексов подачи топлива, построенного ранее н ...

Расчет плунжера
Расчет плунжера на сжатие в минимальном сечении и удельную нагрузку опорного торца. Напряжение сжатия в минимальном сечении плунжера: МПа где Fп min = м2 – площадь минимального поперечного сечения плунжера ; напряжение сжатия в минимальном поперечном сечении плунжера не превышают допустимых [σ ...

Навигация

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