Введение
Глава 1. Алгоритм самораспределения сенсоров для покрытия области
на плоскости
1.1. Краткий обзор предшествующих результатов . . . . . . . . . .
1.2. Постановка задачи
1.3. Основные предположения
1.4. Базовый алгоритм решения задачи
1.4.1. Общая схема алгоритма
1.4.2. Описание алгоритма
1.5. Предложенная модификация базового алгоритма
1.5.1. Общая схема
1.5.2. Первая половина шага (целые моменты)
1.5.3. Вторая половина шага (дробные моменты) . . . . . . . . . . . . . 17
Глава 2. Анализ предложенного алгоритма . . . . . . . . . . . . . . . . . . 23
2.1. Сходимость предложенного правила достижения конценсуса . . . . . . . 23
2.2. Экспериментальное сравнение двух алгоритмов достижения конценсуса 26
2.3. Сравнение базового и модифицированного алгоритмов покрытия области
методом компьютерного моделирования
Заключение
Список литературы
Приложение А. Иллюстрации к работе
Приложение Б. Полное описание алгоритма
Б.1. Пояснение
Б.2. Целые моменты
Б.3. Дробные моменты
Важным этапом в развитии экономики стало формирование разделения труда и образование мануфактур. Практика доказала эффективность разделения производства на специальные виды деятельности, поручаемые отдельным коллективам, специализирующимся в этой области, дальнейшего дробления всего цикла работ на части, поручаемые отдельным работникам, и итогового объединения результатов в конечный продукт.
Аналогично многие современные технологии формируются, опираясь на принципы эффективной организации, распределения и использования ресурсов. В качестве прорывного аналога разделения труда и организации мануфактурного производства можно рассматривать современную парадигму интеллектуальных децентрализованных мультиагентных систем, которая применима к широкому классу задач управления и наблюдения. К ее основным принципам относится достижение определенной «глобальной» цели за счет композиции децентрализованных суверенных действий и решений членов команды (агентов). Как и в мануфактурном производстве, отдельный агент может не знать, откуда к нему поступают материалы (агенты не обладают полной информацией о глобальной проблеме), а весь цикл производства продукции оказывается согласован между участниками (взаимодействия между агентами синхронизированы). Чем лучше организован процесс распределения обязанностей, передачи готовых результатов в конвейерной цепочке создания продукции, тем более продуктивно работает мануфактура. Решение с мультиагентной системой должно также основываться на максимально эффективном взаимодействии агентов.
В совокупности все алгоритмы с участием мультиагентной системы можно разделить на два класса:
1. Координация по распределению задач между агентами и последующая композиция решений происходит под контролем некоторого общего координационного ≪центра≫
2. Поведение каждого агента подчиняется общему правилу, распределение задач
происходит в процессе взаимодействия агентов между собой, а координирующий
«центр» отсутствует.
У каждого подхода имеются свои плюсы и минусы. Наличие центра упрощает процесс решения задачи, так как следить за протекающими процессами в системе проще из <одной точки», нежели оценивать поведение каждого агента по отдельности. Децентрализация в свою очередь дает ослабление таких эффектов как потеря данных, задержки в передаче сообщений в сети, скорость принятия решения и т. д. Эти проблемы переносятся на локальный уровень. Однако, более сложным для исследования оказывается вопрос о синхронизации действий и достижении конечной цели. Подход мультиагентных систем хорош еще и тем, что позволяет не сосредотачивать все вычислительные ресурсы в одной области, а по возможности распределить нагрузку равномерно по всей сети. Тем самым, один мощный по производительности ресурс можно заменить несколькими более слабыми.
При решении реальных задач встречается проблема «контроля» некоторой области. Под ≪контролем≫ области можно понимать отслеживание движения определенных объектов в некоторой области. Например определение области разлившегося в море нефтяного пятна, отслеживание траектории движения охраняемых животных в заповедной зоне. Еще одной интерпретацией может служить задача перемещения одного или нескольких объектов области из одной точки в другую за сравнительно небольшой промежуток времени. Иллюстрацией может служить задача разбора образовавшихся завалов при стихийном бедствии или вариант организации получения и сдачи на хранения вещей для временно образованной складской зоны.
Для достижения ≪контроля≫ области во всех случаях необходимо и достаточно.
чтобы любая точках из области лежала в операционной зоне хотя бы одного из агентов. В данной работе будем рассматривать случай, когда границы области не меняются со временем, но заранее их точное положение неизвестно. В силу ограниченности коммуникационных возможностей и других ресурсов, построение алгоритма будет де-централизованным. Для конкретности рассмотрен случай, когда задача заключается в мониторинге обрасти. В этой связи речь пойдет о сети сенсоров, а операционная зона каждого из них именуется зоной мониторинга. Вместе с тем результаты работы равноприменимы и в иных ситуациях, например, когда сеть образована актуаторами и операционная зона - это зона, в пределах которой данный актуатор может совершать определенные действия.
Рассмотрена задача мониторинга априори неизвестной области плоскости сетью
роботизированных мобильных сенсоров. С целью повышения скорости сходимости разработана модификация алгоритма решения этой задачи, предложенного ранее в [9].
Методом компьютерного моделирования произведен сравнительный анализ базового
и модифицированного алгоритмов; эксперименты продемонстрировали достижение поставленной цели ускорения алгоритма. Сходимость предложенного в работе алгоритма
согласования ключевых параметров агентов обоснована теоретически и подтверждена
результатами компьютерного моделирования.
Среди возможных направлений дальнейших исследований отметим задачу покрытия трехмерных областей, а также исследование проблемы робастности алгоритма к
1. потерям данных в каналах связи между сенсорами;
2. погрешностям измерений и вычислений;
3. потере части сенсоров.
