Системы управления роботами типа "Рой"

Размещено на http://www.allbest.ru/

1

СОДЕРЖАНИЕ

Введение

Системы управления

Групповое взаимодействие роботов

Критерий эффективности

Парадокс критерия эффективности

Задача группового управления роботами

Стратегии управления группами роботов

Алгоритмы коллективного распределения целей в группах роботов

Алгоритмы коллективного улучшения плана

Алгоритм 1

1. Анализ возможности улучшения плана методом попарного обмена целями между роботами.

2. Улучшение плана путем попарного обмена целями.

3. Организация роботами группы цепочек замен целей

4. Определение цепочки возможных замен целей у роботов группы

Алгоритм 2

Алгоритм 3

Алгоритм 4

Алгоритм 5

Определение численности роботов с учетом их отказов

Вывод

Список литературы

Введение

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

Цель работы: Изучение алгоритмов коллективного управления роботами для их использования при разработке системы управления.

Системы управления

1. Центральное управление последовательное (ЦУПос). В этом случае центр управления связан с каждым элементом группы непосредственно, и шагом работы СУ является движение одного элемента группы. Очередность выбора элементов для шага может быть различной.

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

3. Один ведущий. При этом ведомыми реализуется режим «движение за лидером» или «конвой». Следует особо отметить, что ведущий элемент группы не обязательно является постоянным.

4. Распределенное автономное управление (РАУ). Этот тип управления соответствует линии «муравьиного интеллекта» П. Брукса. В этом случае производится априорная настройка процедур решения у каждого элемента группы. Обмена информации между элементами группы нет.

5. ·Распределенное управление с обменом информацией (РУСОИ). При этом производится обмен информацией между элементами всей группы или отдельных ее подмножеств. Управление организуется без иерархического подчинения (гетерархия), и информация касается в основном характеристик среды. При этом обмен информацией может осуществляться, если элементы группы достаточно близко находятся друг от друга, либо находятся в пределах видимости друг друга, а также возможно планирование мест встречи для обмена информацией.

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

Например, режим ЦУПар + РУСОИ позволяет при общем централизованном управлении организовывать группы элементов, решающих конкретную подзадачу [2].

Групповое взаимодействие роботов

Проблема группового взаимодействия является очень важной в современной робототехнике, большой интерес для рассмотрения она представляет в такой перспективной области современной робототехники, каковой является микроробототехника. Основные исследования в области управления группами роботов ведутся во многих индустриально развитых странах мира, прежде всего в интересах обороны. Наиболее интенсивный характер этих работ применительно к направлению военной робототехники наблюдается в США. Анализ результатов исследований показывает, что в настоящее время практически нет какого-либо общего подхода к проблеме группового управления роботами. Каждая исследовательская группа пытается разработать свой способ решения стоящей перед ней частной задачи, который, как правило, не может быть применен при решении других задач подобного типа. Таким образом, актуальной становится проблема разработки методов и алгоритмов распределенного (децентрализованного) управления коллективным взаимодействием роботов при их групповом применении в условиях заранее неизвестных динамически изменяющихся ситуаций. Решение данной проблемы позволит, во-первых, значительно расширить области применения роботов, во-вторых, вплотную приблизиться к решению проблемы массового применения микророботов в составе больших групп, насчитывающих тысячи и десятки тысяч микророботов. Первые научные исследования в области применения групп роботов, взаимодействующих между собой для достижения цели, проводились в 80-х годах ХХ века, решался ряд узкоспециализированных задач. Первые попытки систематизации исследований в области коллективного управления роботами при их групповом взаимодействии и построения теоретической и методологической базы для их дальнейшего развития совершены в начале 2000-х годов. Эволюция систем группового управления идет в направлении увеличения децентрализации с сохранением за центром только обеспечения общесистемных не поддающихся декомпозиции функций групп. Современная тенденция к минитюаризации делает более перспективным их групповое применение. [1].

Критерий эффективности

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

· критерий эффективности первого рода - степень достижения цели системы.

· критерий эффективности второго рода - оценка эффективности в некотором заданном пути достижения цели.

Парадокс критерия эффективности

В зависимости от критерия возможен различный характер поведения этой эффективности в зависимости от числа элементов РМС. Сказанное иллюстрирует таблица 1, где приведены различные критерии эффективности для задачи контурного обхода РМС некоторой области. Исследования показывают, что в общем случае эффективность (рассматриваемая как время выполнения задачи) изменяется следующим образом: при небольшом количестве элементов группы, время выполнения задачи уменьшается с ростом их числа. Далее, оно слабо колеблется у некоторой постоянной величины. А затем, оно увеличивается (роботы начинают мешать друг другу).

Таблица 1.

Тип оценки эффективности	Формула	Характер функции критерия
Время обхода	где L - длина контура, n - число МР, V - скорость МР	Монотонное уменьшение с ростом n.
Мультипликативная схема «время на стоимость эксплуатации»	где c - стоимость эксплуатации одного МР во время операции обхода	Постоянная
Аддитивная весовая схема		Есть оптимальное решение
Аддитивная схема с учетом затрат на обмен сообщениями	где - период обмена сообщениями типа «каждый с каждым», m - цена обмена единичным сообщением	Есть оптимальное решение

Задача группового управления роботами

Задача группового управления роботами может быть сформулирована следующим образом. Пусть некоторая группа , состоящая из N роботов , функционирует в некоторой среде Е . Состояние каждого робота , ( в момент времени t описывается вектор-функцией . Состояние группы роботов задается вектором . Состояние среды вокруг j-го робота - в момент времени t описывается вектором

Тогда состояние среды, в которой функционируют роботы рассматриваемой группы, при условии, что среда стационарна, в момент времени t описывается вектором

.

Роботы и среда, взаимодействуя друг с другом, образуют систему "группа роботов - среда", под состоянием которой в момент времени понимается состояние, описываемое парой . Множество различных состояний системы "группа роботов - среда" описывается точками -мерного пространства состояний . Под начальным и конечным (целевым) состояниями системы "группа роботов - среда" понимаются

,

Состояние системы "группа роботов-среда" в текущий момент времени называется текущим. Каждый робот может выполнять действия, описываемые вектором, причем множество действий, которые может выполнять робот , - . Множество действий, которые может выполнять группа роботов, есть объединение множеств действий отдельных роботов группы: . Действия, выполняемые группой роботов в момент времени t, могут быть описаны с помощью вектор-функции . Изменения состояния системы «группа роботов - среда» описываются системой дифференциальных уравнений вида

При этом на ситуации, а также на действия роботов группы могут накладываться некоторые ограничения:

,

где - множество допустимых в момент времени t состояний системы «группа роботов - среда»;

- множество допустимых в момент времени t действий группы роботов.

С учетом введенных выше обозначений задача группового управления роботами заключается в определении на интервале таких оптимальных действий для каждого робота , которые переводят систему "группа роботов - среда" из начального состояния в конечное (целевое) и при которых удовлетворяются система связей (2), ограничения (3), а также обеспечивается экстремум функционала

задающего цель функционирования группы роботов и оценивающего качество процесса управления.

Для задач группового управления роботами, функционирующими в условиях динамических, недетерминированных сред, недостаточно существования оптимального управления. Необходимо еще, чтобы это управление было найдено в течение времени, за которое состояние системы "группа роботов - среда" существенным образов не изменится. На решение задач группового управления роботами, функционирующими в условиях динамической, недетерминированной среды, а также в условиях противодействия, направлены рассматриваемые методы и алгоритмы [1].

Стратегии управления группами роботов

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

1. Централизованное управление

a) Единоначальное управление (наличие в группе командира или центрального устройства управления (ЦУУ), на которые возлагается задачи планирования и управления группой).

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

b) Иерархическое управление (так же наличие ЦУУ или командира, которые управляют небольшим количеством подчиненных, в подчинении каждого из них состоит своя группа объектов). По сравнению с единоначальным управлением, существенно снижается сложность задачи, решаемой отдельным командиром или ЦУУ, однако усложнение структуры управления может приводить к сильным задержкам или сбоям в передаче команд от верхнего к нижнему уровню

2. Децентрализованное управление

a) Коллективное управление (в системе нет командира или ЦУУ, все единицы равноценны и каждый член группы самостоятельно принимает решение, пытаясь внести максимально возможный вклад в достижение групповой цели, при это члены группы обмениваются информацией о выбранных действиях друг с другом). За счет того, что каждый элемент решает задачу оптимизации только для себя, а не пытается оптимизировать действия всей группы, она существенно упрощается, поэтому решение может осуществляться быстро, в реальном времени. Но это сильно усложняет алгоритмизацию и предъявляет к элементам большой «интеллектуальный уровень», т.к. от них требуется четко понимать групповую задачу и уметь выбирать такие действия, которые приводят к наилучшему ее решению с точки зрения всей группы.

b) Стайное управление (в системе нет командира или ЦУУ, все единицы равноценны и каждый член группы самостоятельно принимает решение, пытаясь внести максимально возможный вклад в достижение групповой цели, при этом обмена информации между членами группы нет, и каждый объект «подстраивает» свои действия на основании косвенной информации)

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

Размещено на http://www.allbest.ru/

1

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

При условии, что ситуация изменяется медленно, например при составлении карты местности, более приемлемым будет использование иерархической стратегии, когда с центрального узла поступают команды (задания) для отдельных групп роботов, каждая из которых имеет своего локального командира, который осуществляет управление внутри группы. В случае, если ситуация изменяется очень быстро, как в случае боевых действий, то решение о групповых действиях необходимо принимать очень быстро, зачастую не обращая внимания на качество решений, в этом случае подходит одна из стратегий децентрализованного управления: коллективная или стайная. Практическая реализация рассмотренных выше стратегий группового управления приводит к соответствующим принципам организации систем группового управления (СГУ) роботами. В общем случае СГУ состоит из подсистемы планирования групповых действий (ППГД), локальных бортовых систем управления (БСУ j, ) отдельных роботов группы, отвечающих за реализацию групповых действий и бортовых исполнительных устройств (БИУ j, ) отдельных роботов. Ключевую роль в данном случае играет организация ППГД. В работе рассмотрены различные способы организации этих подсистем, в частности - централизованные, распределенные (децентрализованные) и смешанные, например, иерархические централизованные и иерархические распределенные.

Как показал анализ существующих систем группового управления, централизованная организация ППГД имеет ряд существенных недостатков, основными из которых являются, во-первых, низкая живучесть системы, так как выход из строя центрального устройства управления (ЦУУ) или канала связи с роботами приводят к выходу из строя всей системы группового управления, а во-вторых, большие объемы информации, которой ЦУУ обменивается с роботами.

Распределенная ППГД обладает рядом преимуществ по сравнению с ППГД с централизованной организацией. Во-первых, локальные бортовые подсистемы планирования действий роботов решают более простые задачи. Во-вторых, существенно снижаются требования к каналам связи. В-третьих, подсистема планирования групповых действий является надежной и робастной, потому что может динамически приспосабливаться к изменениям ситуации и потере отдельных роботов группы, а также способна противостоять прерываниям связи и сбоям. Смешанные или комбинированные системы группового управления основаны на комбинации принципов централизованного и децентрализованного управления и обычно используются для управления большими группами роботов. [2]

Алгоритмы коллективного распределения целей в группах роботов

Задача коллективного распределения целей

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

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

при ограничении, которое заключается в том, что в текущий момент времени, каждый робот может выбирать только одну цель. Возможны и другие ограничения, например, на количество роботов, необходимых для выполнения l-й цели в текущий момент времен, при различных соотношениях числа роботов в группе и количества целей, поставленных перед группой. Задачу распределения целей в группах роботов можно свести решению соответствующей задачи линейного программирования, либо к решению другими методами. Однако, время решения в таком случае чаще всего оказыватся недопустимо большим. Поэтому обычно рассматривается и используется решение задачи распределения целей с помощью итерационной процедуры оптимизации коллективных действий. Методы, реализующие такую процедуру, можно отнести к многошаговым методам управления. Такие методы делятся на точные и приближенные. Точные методы направлены на отыскание глобального экстремума функционала (4),а приближенные - на отыскание его локального экстремума. Обычно, приближенные методы оказываются более простыми и используются при ограниченном времени на решение задачи управления, и зачастую они так же называются ускоренными методами. Многие из ускоренных методов можно использовать для получения в реальном времени если не оптимальный, то близкий к оптимальному результат. В условиях динамической недетерминированной среды нет смысла реализовывать действия роботов, обеспечивающие экстремум функционала (глобальный или локальный) на всем промежутке времени , так как ситуация может измениться таким образом, что полученное решение в дальнейшем станет далеко не оптимальным. И исходя из этого, распределение целей, обеспечивающее экстремум функционала (4) реализуется лишь в ближайшем будущем, т.е. на интервале времени , где _ текущий момент времени.

Алгоритмы коллективного улучшения плана

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

Алгоритм 1

Рассмотрим простейший алгоритм для сформулированной задачи (4), (5), когда M=N, , т.е. когда число целей группы равно числу роботов в группе. Для достижения цели достаточно одного робота. При этом робот может выбирать любую цель, но достижение каждой из них данным роботом дает разное значение оценки эффективности (4). Тогда задачу распределения (4), (5) можно сформулировать следующим образом. Требуется распределить цели между роботами группы таким образом, чтобы обеспечить максимум функционала

При ограничениях

,

,

Где

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

Решение задачи (7)-(10) при с использованием алгоритма коллективного улучшения плана разбивается на 2 этапа.

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

Первый способ - случайный выбор. Первый случайный выбор делает робот с номером j=1, то есть робот . Номер выбранной цели сообщается другим роботам и она исключается из списка доступных целей. Затем случайный выбор делает робот с номером , сообщая ее номер всем остальным. Процедура случайного выбора продолжается до тех пор, пока все цели не будут распределены между роботами. Полученное таким образом распределение называется опорным планом.

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

При использовании этих способов, вероятность того, что полученный первоначальный опорный план будет оптимальным, очень мала. При этом для получения оптимального плана, являющегося решением (4)-(10), может потребоваться значительное число итераций улучшения плана. Но если при формировании опорного плана стремиться к максимизации функционала (6), то количество итераций сократится. Такой подход используется при использовании третьего способа.

При его использовании, выбор цели так же начинает робот с номером j=1, т.е робот . Но он выбирает такую цель, для которой элемент массива имеет максимальное значение, т.е

После этого, робот передает номер выбранной им цели и значение всем остальным роботам. Робот аналогичным образом определяет номер своей цели

групповой управление робот цель

т.е выбор делается из еще не выбранных целей. Номер выбранной им цели и значение передается остальным роботам. Выбор целей аналогичный (11) и (12) продолжается до тех пор, пока выбор не сделает робот . Таким образом, формируется первоначальный план. Если для робота две или более цели имеют одинаковые максимальные значения оценок эффективности, то робот должен выбрать одну из них, следуя ранее заложенным правилам.

В последующих циклах итерационной процедуры оптимизации коллективных действий выполняются меры по улучшению первоначального плана, которые заключаются в следующих действиях:

1. Анализ возможности улучшения плана методом попарного обмена целями между роботами

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

Хотя число вариантов «обмена» равно , каждый робот вычисляет только N-1 значений Если все значения , то должен выполнятся переход к п.3, если , то к п.2.

2. Улучшение плана путем попарного обмена целями

Так как все роботы в группе имеют значения , то каждый из них среди всех значений (13) определяет максимальное (по абсолютной величине) и передает всем остальным роботам это значение и значение индекса k, указывающего на номер робота, с которым обмен целями предпочтительнее. После чего роботы определяют из всех максимальных значений наибольшее (по абсолютной величине) например . Обмен целями между роботами происходит следующим образом, робот выбирает цель с номером предложенную роботом , а робот выбирает цель с номером , предложенную роботом . Далее выбирается из оставшихся значений второе, максимальное по абсолютной величине, например, , но при это должно выполняться , т.е. роботы уже обменявшиеся целями в выполнении этого шага в текущем итерационном цикле не участвуют. Роботы и меняются целями как и в предыдущем случае. На этих же условиях производится выбор следующего значения . В результате получается новый улучшенный опорный план. Сумма всех значений , выбранных на 2.

Показывает на выигрыш функционала (6) в результате целей. В (14), S - число всех попарных замен на 2.

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

3.  Организация роботами группы цепочек замен целей

Смысл заключается в попытке каждого робота улучшить свой выбор цели путем организации цепочек замен. Для этого каждый робот определяет, не приведет ли замена его цели к увеличению (6). Такая замена может быть целесообразной, если оценка эффективност цели-претендента больше чем сумма оценок эффективности ранее выбранной цели данным роботом и цели - претендента для выбравшего ее другого робота.

Чтобы определить возможность замены цели выполняются такие вычисления. Сначала робот вычисляет значения

Если , то замены целей не приведут к желаемому результату, и полученно в результате выполнения 1 и 2 распределение целей является оптимальным. В противном случае, если есть значения , то выполняется 4. Для того чтобы выполнить эти вычислений при использовании централизованной системы управления нужно N*(N-1) вычислений по формуле (15), в тоже время при использовании децентрализованного управления каждый робот выполняет N-1 вычислений по (15), к тому же, вычисления могут производиться всеми роботами группы одновременно.

4. Определение цепочки возможных замен целей у роботов группы

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

где в первой скобке сумма выигрышей функционала, даваемых каждой заменой, а во второй - сумма оценок эффективности целей до их замены. Величина (16) указывает на выигрыш функционала (6) и целесообразность замен. После замен целей, 4 повторяется. Есля для первой цепочки замен , т.е выигрыш функционала не получен, то замены не выполняются и ищется вторая цепочка замен. Для этого ищется робот со вторым максимальным по абсолютной величине значением , и построение цепочки начинается с него. В результате выполнения этого пункта, при так же получается улучшенный опорный план. Таким образом, план является оптимальным, если все , т.е признаком оптимального плана является условие

, ,

Это означает, что ни при каких заменах приращение целевого функционала не обеспечивается, т.е. достигнут его максимум.

Алгоритм 2

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

Алгоритм 3

В данном случае, M - число целей, на которые может быть разложена общая групповая цель, удовлетворяет условию M>N при ограничениях, что каждый робот в текущий момент времени может выбрать только одну цель. Для достижения каждой цели достаточно одного робота, но любая из целей может быть не выбрана ни одним из роботов. При этом . В таких условиях, (7)-(10) можно записать как

При ограничениях

(20) означает, что какая- либо цель может быть не выбранна, из-за того, что M>N.

После формирования опорного плана, все множество целей оказывается разбитым на 2 подмножества: - выбранных (вошедших в основной план) и не выбранных , при этом .

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

 для всех ,

где - оценка эффективности цели , выбранной роботом и входящей в опорный план; - оценка эффективности цели , т.е. не входящей в опорный план, для робота . Количество значений для каждого робота равно . Условие

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

Пункт 2 заключается в выполнении процедуры замены целей, приводящей к увеличению значения функционала. Каждый из роботов группы, среди всех вычисленных им значений , удовлетворяющих (23), определяет максимальное по абсолютной величине , и сообщает его остальным роботам группы, а также номер цели , которую он выбрал, для внесения в улучшенный план. Среди всех известных ему значений , каждый робот определяет максимальное, а т.к. у всех роботов одна и та же информация, то выбор будет одинаковым. Робот, для которого все члены группы определили значение , имеет первоочередное право на замену цели. Он выбирает новую цель и включает ее в опорный план, а «старая» цель включается в подмножество невыбранных целевых задач, т.е. . После чего ищется следующее максимальное по абсолютной величине отрицательное значение , при условии, что его индексы не были равны ни одному из индексов предыдущих максимальных в даной итерации. Шаги 1 и 2 повторяются, пока ни для одного робота группы не будет определено не одного значения , удовлетворяющего (23).

Пункты 3 и 4 аналогичны пунктам 1 и 2 в алгоритме 1. Если во время вычислениия формулы (13), не получено значений, удовлетворяющих , то выполняется пункт 5. В противном случае, выполняется пункт 4, идентичный пункту 2 данного алгоритма. После выполнения 4, роботы группы возвращаются к выполнению 1, на котором они проверяют, не даст ли увеличение функционала замена цели, выбранная на 4, на другую, не вошедшую в опорный план. Чтобы это сделать, вычисляются значения по формуле (22), и если среди них имеются удовлетворяющие ее условию, то информация передается всем остальным роботам группы и выполнятся шаг 2. Потом шаг 1 и если это необходимо, то шаг 2 выполняют остальные роботы группы. Если при какой-либо итерации на шаге 1 не получено не одного значения (22), удовлетворяющего условию (23), то выполняется шаг 3.

Шаги 5 и 6 аналогичны шагам 3 и 4 алгоритма 1. На шаге 5, опорный план проверяется на оптимальность. Если все значения, вычисляемые по (15) удовлетворяют условию (17), то предполагается, что решение найдено. Если же нет, то выполняется шаг 6, который идентичен шагу 4 алгоритма 1. В следующем цикле повторяются шаги 1-4. Шаги 1-2 вначале делают роботы, произведшие замены целей на шаге 6, а затем остальными роботами. Повторение шагов 1-6 идет до тех пор, пока не будет получен оптимальный план.

Алгоритм 4

В данном случае, целей M, на которые можно разложить групповую цель, меньше числа роботов в группе M<N. При этом, каждый робот в момент времени может выбрать только одну цель и для того чтобы ее достичь, достаточно одного робота. Пусть , т.е. число целей для всех роботов одинаково, но меньше числа роботов в группе. Тогда задача (6)-(10), может быть представлена как

при ограничениях

Формулы (25) и (26) показывают, что один или несколько роботов группы не выберут цель из-за того, что M<N, но каждая цель будет выбрана каким-либо роботом. В этом случае, при решении (24)-(27), формируется опорный план, любым из предыдущих способов. При его составлении, все множество роботов делится на два подмножества -

- выбравших цель и - ее не выбравших. После этого, выполняется первый цикл процедуры оптимизации коллективных действий. Полученный в результате опорный план, в последующих циклах улучшается, аналогично процедуре используемой при решении (18)-(21). Отличия наблюдаются только в 1 и 2 шагах.

Шаг 1 заключается в проверке возможности увеличения функционала (24) за счет перераспределеия целей путем передачи роботами своих целей, роботам из подмножества . Чтобы это сделать, роботы , основываясь на полученной от роботов информации о выбранных ими целях, вычисляют значения

,

где - оценка эффективности цели, выбранной роботом для робота .

Если для какой-либо пары и выполняется условие

,

то выполняется шаг 2, в противном случае, переходим к шагу 3

Шаг 2 является улучшением опорного плана, путем передачи роботам роботам (j,k) своих целей, если выполняется условие (29). Этот шаг начинают все роботы, для которых значение (28) является наибольшим по абсолютной величине, например и , при этом

т.е., роботы, выполнившие шаг 2 в данном итерационном цикле, до его окончания не участвуют. Роботы, передавшие свои цели, переходят в подмножество , а отдавшие в подмножество . Выполнение 2 шага, продолжается, пока не останется ни одной пары роботов, для которых выполняется (29) и (30). После чего выполняется шаг 1.

Шаги 3 и 4, решения (24)-(27), аналогичны шагам 1 и 2, решения (6)-(9) и являются проверкой возможности улучшения опорного плана (шаг 3), т.е. в возможности увеличения значения функционала (24) путем попарного обмена целями между роботами группы . В данном случае, обмен осуществляется между роботами, для которых значения , вычисленные по (13), являются отрицательными(шаг 4). При этом, выполнившие обмен целями роботы на этом шаге (шаг 4), в текущем итерационном цикле до его окончания не участвуют. Если же на шаге 3, ни для одной пары роботов в текущем итерационном цикле не существует значений , то выполняется шаг 5.

Шаг 5 аналогичен решению (6)-(9) и на нем проверяется каждым роботом возможности улучшения опорного плана путем выбора какой - либо другой цели, но если рядом имеются роботы, для которых значения, вычисленные по (15), не удовлетворяет условию оптимальности плана (17), то улучшения происходит на шаге , которое заключается в осуществлении цепочки замен целей, в соответствии с алгоритмами, приведенными при описании шага 4 задачи (6)-(9).

Алгоритмы 3 и 4, для решения (18)-(21) и (24)-(27), можно использовать и в случае, когда для достижения целей, они должны быть выбраны несколькими роботами.

Алгоритм 5

Данный алгоритм рассматривает случай, когда несколько роботов выбирают одну цель для ее достижения. Причем для достижения разных целей, число используемых роботов может оказаться разным. При этом, число целей М, на которое разбивается групповая цель, также может быть не равна числу роботов в группе. В таком случае, задачу (6)-(9), можно сформулировать следуюущим образом:

при ограничениях

,

,

,

где - необходимое число роботов, которые должны выбрать l -ю цель. Условия (31) и (32) соответствуют случаю, когда , и каждую цель выберет необходимое число роботов . После того, как какую - либо цель выберет достаточное число роботов , назовем ее покрытой.

Решение (31) - (34), может быть выполнено аналогично решению (6) - (9). Но существует отличие, которое заключается в том, что второй способ формирования опорного плана не может быть использован, т.к. одну цель должны выбрать несколько роботов группы. Следовательно лучше использовать третий способ, который предполагает выбор каждым роботом непокрытой цели, имеющей для него максимальное значение оценки эффективности.

Для этого, перед началом распределения, роботам задается или формируется на ими самими на основе анализа групповой целевой задачи одномерный массив , элементами которого являются числа роботов, необходимые для покрытия каждой цели. Решение (31) - (34) многоэтапное решение и оно является многократным решением задачи (24) - (27).

На первом этапе выполнения алгоритма 5, только М роботов группы выбирают цели.Так как. M<N, то решается задача (24) - (27), которая рассмотрена в алгоритме 4.

После того, как М роботов выбрали цели , учитывая ограничения (32), и учитывая что каждый робот может выбрать только 1 цель и сообщили о своем выборе остальным элементам группы, все роботы на единицу уменьшают значениие элемента . При этом, если , то цель считается обеспеченной и дальше не рассматривается.

Затем задача (24) - (27) решается роботами, которые не выбрали цель на предыдущем этапе, рассматривая только непокрытые цели. Из-за чего, перед вторым этапом, роботам необходимо проверять все элементы массива на равенство нулю [2].

Определение численности роботов с учетом их отказов

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

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

Пусть количество роботов в группе из-за отказов уменьшается по закону

где - количество роботов в i-й группе при t=0, т.е. в момент начала выполнения группой поставленой задачи; - постоянная, характеризующая скорость выхода из строя в i-й группе. Соотношение (35) соответствует ситуации, когда число роботов, выходящих из строя в единицу времени, прямо пропорционально общему числу роботов данной группы в каждый момент времени. Оно достаточно честно описывает многие реальные процессы.

Если для рассматриваемой задачи формула (35) выполняется, то роботы должны быть распределены так, чтобы выполнялось условие

где - число роботов, необходимое для полного покрытия i - й цели;

- время, требуемое для достижения i - й цели;

- время решения задачи целераспределения.

[] - подразумевается операция взятия целой части с избытком

Пусть роботы начинают движени к целям по окончании решения задачи целераспределения. Тогда с учетом (35), условие (36) принимает вид

Выражаем из (37) , из чего следует что для задачи покрытия целей необходимо перед решением задачи целераспределения пересчитать значения по формуле . Все остальные алгоритмы решения задачи распределения целей не меняются.

При расчете количества роботов в коллективе необходимо учитывать следующее:

1) Эффект «старения» (и выхода из строя) роботов приводит прежде всего к увеличению общего число роботов в группе, перед которым стоит m целей. Минимальное число роботов в этом случае определяется условием

Если время достижения всех целей и время периода, через которое роботы выходят из строя одинаковы, и

,

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

2) Пусть заданы характеристики и численность групп роботов: , время решения и число . Тогда условие покрытия j -й группой i - й цели

позволяет оценить время способности j - й группы решить i - ю задачу с помощью выражения

Откуда следует, что начальная численность j - й группы роботов не должна быть меньше величины . Если условие выполняется, то уравнение (39) определяет продолжительность интервала времени, в течение которого j - я группа роботов способна достичь i- й цели, с численностью, гарантирующей ее покрытие [4].

Вывод

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

Список литературы

1. Капустян С. Г. Методы и алгоритмы коллективного управления роботами при их групповом применении. - Ростов-на-Дону, 2008. - 310 с.

2. Каляев И.А. Модели и алгоритмы коллективного управления в группах роботов. - Москва, Физматлит 2009. 278 с.

3. Бакиров А.К., Кирильченко А.А. Проблемы управления распределенными мобильными системами . ИМП им. Келдышева РАН М., 2000

4. Каляев И.А. Распределенные системы планирования действий коллективов роботов. - М., Янус-К 2002. 291 с.

Размещено на Allbest.ru