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

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

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

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

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

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

Полная масса и грузоподъемность АТС
Полная масса автотранспортных средств состоит из снаряженной массы, массы груза (по грузоподъемности) или пассажиров (по числу мест), их багажа, водителя и другого обслуживающего персонала. Полная масса автопоездов: для прицепного поезда – сумма полных масс тягача и прицепа; для седельного – сумма ...

Навигация

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