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

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

Страница 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

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

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

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

Подбор технологического оборудования для аккумуляторного участка
Подбор технологического оборудования аккумуляторного участка проводим согласно рекомендаций [1] и по каталогам технологического оборудования для ТО и ТР автомобилей [11]. Таблица-2.15 Технологическое оборудование для аккумуляторного участка Поз Наименование Кол-во Примечание 1 Стеллаж для ожидающих ...

Навигация

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