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

ПРОЦЕДУРА ГОЛОСОВАНИЯ В ОДНОРОДНЫХ КОЛЛЕКТИВАХ РОБОТОВ

В.Э. Карпов (vkarpov@hse.ru)

МИЭМ НИУ ВШЭ, Москва

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

лидер группа робот алгоритм

Введение

Активные исследования в области создания систем взаимодействующих роботов ведутся уже почти четверть века. Такие направления, как коллективная, роевая, стайная и пр. робототехника, заняли прочные позиции в современной робототехнике и теории многоагентных систем. Однако до сих пор подавляющее число исследований в этой области остается на теоретическом, модельном уровне. Это хорошо видно по многочисленным обзорам, например, таким, как [Zhiguo et al., 2012] и [Yogeswaran & Ponnambalam, 2010]. Представляется, что отсутствие действительных, практически значимых результатов не в последнюю очередь связано со слабой проработкой целого ряда важных задач. Исследования в области групповой робототехники (если под этим понимать обобщенное название коллективной, роевой и т.п. робототехники) носят весьма фрагментарный характер. Более того, характерным настораживающим признаком является явный перенос центра тяжести исследований именно в роевую робототехнику, которая может рассматриваться как более простой, базовый уровень моделей групповой робототехники.

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

Лидерство. Одной из принципиальных особенностей роевой робототехники является локальный характер взаимодействия роботов друг с другом, а также роботов со средой [Zhiguo et al., 2012]. Такое взаимодействие называется неявной коммуникацией (implicit communication) [Yogeswaran & Ponnambalam, 2010]. Речь идет о том, что каждый робот группы непосредственно взаимодействует лишь со своими соседями, находящимися в некоторой ограниченной зоне видимости. Отсюда обычно следует, что в такой системе роботы самостоятельно принимают решения о дальнейших действиях, опираясь на некоторые простые правила локального взаимодействия.

Вместе с тем, однако, подавляющее число примеров решения задач в области роевой робототехники касается согласованного движения роя (очевидная, наглядная и достаточно простая задача, которая в [Zhiguo et al., 2012] выделена как метод "Следование за лидером" - "Leader-Follower method"). При этом считается, что в группе имеется априори заданный лидер, который и задает это движение. Правила локального взаимодействия могут быть самыми разными. От сугубо формальных [Павловский и др., 2010] до весьма экзотических. Например, в [Dewi et al., 2012] правила стайного движения основаны на модели пружин и амортизаторов. "Пружинная" составляющая модели определяет притяжение особей к лидеру (а не друг к другу, что характерно), а "амортизационная" - отталкивание от лидера. В [Карпов, 2012], напротив, описан сугубо технический прием, позволяющий определить лидера для решения задачи согласованного движения. Отметим здесь, что рой при такой организации превращается в стаю - стая характеризуется именно наличием лидера, за которым следуют остальные роботы. Иной подход к определению лидера предложен в [Даринцев, 2006], где описывается динамическое выделение агентов-координаторов (лидеров), основанное на "геометрических" построениях - лидерами групп становятся роботы, ближе всех расположенные к месту проведения неких технологических действий.

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

Распределение задач. Для решения задачи согласованного движения достаточно наличия лидера. Однако для более сложных задач, решаемых группой роботов, требуется дифференциация их функций и, вообще говоря, распределение задач между роботами. Пожалуй, это одно из наиболее проблемных мест роевой робототехники. В уже упомянутых обзорах [Zhiguo et al., 2012] и [Yogeswaran & Ponnambalam, 2010] распределение задач в коллективе роботов рассматривается лишь декларативно. В лучшем случае упоминаются некоторые физические модели, методы распределенного планирования, оптимизации и пр. общие механизмы ([Каляев и др., 2009]). Причиной этому является то, что дифференциация функций и распределение задач не рассматривается роевой робототехникой как актуальная проблема, полагая, что рой должен решать лишь простые, массовые задачи типа согласованного движения. Это, безусловно, снижает значимость роевого подхода и, вообще говоря, идет в разрез с основным декларируемым тезисом роевой робототехники (роевая робототехника, как способ решения сложных задач совокупностью простых технических устройств - роботами).

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

Статический рой. Одной из моделей, описывающих организацию множества локально взаимодействующих агентов или роботов, является так называемый статический рой. Статический рой характеризуется отсутствием заданного управляющего центра и представляет собой некую фиксированную в данный момент времени сеть - совокупность агентов [Карпов, 2013]. Основные свойства статического роя - это активность, локальность взаимодействия и функциональная неоднородность.

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

- агент

- "кандидат", за которого голосует агент

- вес кандидата

- список агентов-соседей

procedure G1()

1. Выбрать среди своих соседей оппонента с максимальным весом :

2. Вычислить значение вероятности изменения мнения

3. С вероятностью изменить мнение:

end procedure

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

Алгоритм G2(). Принятие решения агентом - 2

procedure G2()

1. Выбрать среди своих соседей оппонента с максимальным весом :

2. if then -- Оппонент "сильнее". Меняем свое мнение

3.

else

4. if then -- Силы равны. Меняем свое мнение

-- с вероятностью 0.5

5. p rand() -- Случайное число от 0 до 1

6. if p > 0.5 then

7.

end if

end if

end procedure

Общая схема голосования может выглядеть так:

Алгоритм V(). Голосование

- множество агентов

- агент

- "кандидат", за которого голосует агент

- вес кандидата

- список агентов-соседей

eoj - флаг завершения процедуры голосования

procedure V()

1.

2. for all do -- Инициализация агентов

end for

3. while not eoj do -- Основной цикл голосования

4. for all do -- Цикл по всем агентам

5. G1()

end for

6. «Определение условия завершения процедуры голосования eoj»

end while

end procedure

В этом алгоритме наиболее проблемным является п.6: «Определение условия завершения процедуры голосования eoj». В отсутствие глобальной информации о состоянии сети, агент должен сам принимать решение о том, что голосование закончено. Получаемая от ближайшего окружения информация является явно не достаточной для этого, поэтому возможны два варианта поведения агента:

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

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

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

Далее приведены примеры работы процедуры голосования. На Рис. 3 изображены 3 такта голосования для плотной группы роботов.

Рис. 3. Процедура голосования в плотной группе. Такты 1, 2 и 6

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

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

Рис. 4. Циклическая процедура голосования. Такты 1, 3, 20 и 37

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

Обоснование приведенных алгоритмов подразумевает ответы на два основных вопроса: (1) сходимость алгоритмов к одному решению и (2) оценка количества тактов голосования.

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

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

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

Здесь происходит объединение списков, полученных от всех соседей из некоторой области Z в предыдущий момент времени.

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

Распределение задач. При отсутствии морфологических различий между агентами, распределение ролей в статическом рое определяется исключительно текущей топологией системы. Сам процесс распределения представляет собой известную процедуру распространения волны управления. Инициатором распространения является лидер. Обозначим его роль, как . Непосредственные соседи лидера ("ближний круг") получают от него инициирующий пакет, согласно которому им назначается роль и т.д. Таким образом, роль i-го робота определяется ролями его окружения: