коллектив роботов. Коллективное поведение роботов. Желаемое и действительное
 Скачать 1.49 Mb.
|
|
Модели движения Правила передвижения роевых животных относительно просты. Эти правила позволяют множеству относительно простых элементов формировать "коллективный мозг" способный принимать решения и заставлять двигаться стаю подобно единому организму. При этом зачастую эти правила применимы и к действиям толпы людей [Инстинкт толпы, 2007]. Макромодели. Для описания движения больших масс роевых организмов вполне подходящим оказывается математический аппарат гидродинамики. По сути дела, речь идет о статистических макромоделях. Бродячие муравьи очень быстро реагируют на запахи следов их ближайших соседей. Стоит впереди идущим муравьям приступить к формированию настилов и пешеходных 18 дорожек, как идущие следом мгновенно подхватывают инициативу и выстилают дорожку, по которой бегут остальные. Если плотность муравьев становится слишком высокой, это служит сигналом к формированию множества мостов, дорог и переулков из тел скопившихся муравьев, чтобы другие разбежались по ним в разные стороны, не скучиваясь. Муравьи ведут себя так, чтобы обеспечить рою максимальную скорость передвижения. Движение саранчи. Обычно насекомые охотятся самостоятельно, но иногда молодая саранча сбивается в огромные тучи, насчитывающие миллионы особей. Когда плотность саранчи превышает некоторый пороговый уровень, насекомые внезапно начинают двигаться вместе, выравнивая движение по своему соседу. Движение сверчков. Известны виды сверчков (например, т.н. мормонские сверчки), которые обычно живут обособленно, но иногда они собираются миллионными роями и вытягиваются в многокилометровые полосы (длиной до семи километров). Механизм образования таких протяженных полос достаточно прост. Когда мормонские сверчки не могут найти достаточно пищи, они становятся каннибалами. Каждые 17 секунд сверчки пробуют напасть на других индивидуумов своего рода. Если какой-то сверчок не убегает, он наверняка будет съеден сородичами. Поэтому сверчки и вытягиваются в длинные стаи: тот кто впереди, убегает, чтобы не быть съеденным преследующими его собратьями. Общие механизмы роения. Рой из множества животных можно рассматривать как отдельную единицу. Действительно, стая рыб движется как одно целое. Стая птиц также движется благодаря нескольким лидерам, при этом остальные особи в стае следуют за лидерами. Схожие механизмы действуют и в человеческом социуме: движение общества определяется направлением, задаваемом несколькими лидерами. Толпа людей [Инстинкт толпы, 2007]. Йеном Д. Казиным (Iain D. Couzin, Оксфордский университет) был проведен ряд достаточно простых экспериментов, в которых изучались модели прохождения потока информации через толпу людей. Поведение испытуемых, испытывающих две противоречащие потребности – оставаться с группой или двигаться в индивидуальном направлении – явным образом определялось поведением лидеров. В отсутствии информации о правилах действий других игроков испытуемые совершали действия, характерные для стайного движения – следования за большинством. Итак, основой механизма является подражательное поведение, а движущей силой – действия лидеров. Другим классом моделей являются формальные математические методы, описывающие локальное поведение членов коллективов (стай, роев). Формальные методы. Речь идет о достаточно хорошо известных и проработанных методах и алгоритмах. Говоря о моделях движения объектов, выделяются следующие базовые правила (алгоритмы), которым должны следовать эти объекты: - движение в направлении цели; - движение в направлении центра масс своих соседей; - поддержка минимально допустимого расстояния друг между другом и препятствиями. Хорошо проработаны различного рода алгоритмы обхода препятствий и уклонения от столкновений, алгоритмы, учитывающие такие взаимоисключающие тенденции, как "отталкивание" и "притяжение" особей в стае и т.п., см., например, [Павловский и др., 2002]. Иногда даже считается, что подобные модели поведения стаи (роя, толпы) можно применить не только к движению живых существ. Правилам коллективного движения, подобным движению рыб или саранчи, подчинена работа мозговых клеток; человек принимают решение на основе множества коллективных сигналов и проч. В целом же следует отметить, что подобного рода модели – это лишь реализация неких частных механизмов. Эти модели не претендуют, разумеется, на объяснение природы стайного поведение, предпосылки его появления или некие глубокие обобщения. 19 Тем не менее, на практике эти модели вполне применимы для решения частных технических задач. Иллюстрацией этому может служить, например, робот EPORO фирмы Nissan ([Nissan, 2009]. Робот EPORO. Коллектив роботов имитирует поведенческие модели стаи рыб, избегая препятствий и столкновений друг с другом и способных двигаться целенаправленно. Исследователи утверждают, что это – первая такого рода разработка в мире. Несколько ранее, в 2008 г. той же формой был представлен робот BR23C, отличавшийся "зрением шмеля". EPORO – это развитие той же концепции "заимствования" у природы. Как BR23C, так и EPORO решают задачу движения без столкновений ("инстинктивная навигация": выявление и обход препятствий). Как и рыбы, роботы EPORO имеют специальный сенсор – т.н. "боковую линию", роль которой играет лазерный дальномер. У рыб боковая линия — это чувствительный орган, воспринимающий движение и вибрации окружающей воды и используемый для ориентации. Основная цель этих исследований – создание безопасных автомобилей (сам робот EPORO – это модель: высота — 60 сантиметров, вес — 13 кг.). Разработанные методы должны позволить роботам соответствовать "трём правилам поведения рыб": - изменять направление движения без столкновений с другими; - "путешествовать" бок о бок с остальными, сохраняя определённую дистанцию и скорость; - уметь безопасно сближаться. а) б) Рис.8. а) Робот EPORO. Внизу показаны варианты перегруппировки роботов на манер рыбьей стаи; б) предшественник EPORO – робот BR23C Пример роевого алгоритма. И, наконец, приведем пример типичного роевого алгоритма – т.н. муравьиного алгоритма. Идея алгоритма – моделирование поведения муравьёв, связанного с их способностью быстро находить кратчайший путь от муравейника к источнику пищи и адаптироваться к изменяющимся условиям, находя новый кратчайший путь. Предполагается, что при своём движении муравей метит путь феромоном, и эта информация используется другими муравьями для выбора пути (хотя одно это утверждение уже вызывает массу вопросов). Это элементарное правило поведения и определяет способность муравьёв находить новый путь, если старый оказывается недоступным [МакКоннелл, 2004]. Пусть на муравьиной дороге возникает преграда. В этом случае необходимо определение нового (оптимального) пути. Дойдя до преграды, муравьи с равной вероятностью будут обходить её справа и слева. Те муравьи, которые случайно выберут кратчайший путь, будут быстрее его проходить, и за несколько передвижений он будет более обогащён феромоном. Поскольку движение муравьёв определяется концентрацией 20 феромона, то следующие будут предпочитать именно этот путь, продолжая обогащать его феромоном до тех пор, пока этот путь по какой-либо причине не станет недоступен, см. рис.9. Рис. 9. Реакция на появление препятствия Таким образом, будут искаться необходимые пути, при этом моделирование испарения феромона будет гарантировать, что найденное локальное оптимальное решение не будет единственным. Обобщённый муравьиный алгоритм поиска на графе представим в следующем виде ([Штовба, 2003]): Цикл, пока не выполнены условия выхода: 1. Создание муравьёв (размещение на графе) 2. Поиск решения (переход в следующую точку). Вероятность перехода из вершины i в вершину j зависит от уровня феромона в этой точке. 3. Обновление уровня феромона τ в точке (i,j). Уровень феромона может быть обновлен так: ∑ + − = + ) / ( ) ( ) 1 ( ) 1 ( k ij ij L Q t t τ ρ τ , где ρ – интенсивность испарения, L k (t) – цена текущего решения для k-го муравья, Q – цена оптимального решения, т.е. Q/L k – феромон, откладываемый k -м муравьём, использующим ребро (i,j). 4. Дополнительные действия (например, локальный поиск) КонецЦикла Проект MARS. Пожалуй, одним из первых реальных проектов, реализующих групповое поведение роботов, является MARS (Multiple Autonomous Robots), США, Пенсильванский университет. Начало работ, судя по публикациям, относится к 2000 г. В качестве основы выбрана четырехколесная платформа Clodbuster Рис. 10. Робот проекта MARS 21 Проект был посвящен отработке методов ориентации групп мобильных автономных роботов с использованием правил ближайшего соседства. В основу этих правил положена теория связанных систем. Суть метода заключается в том, что роботы определяют свои действия по действиям, выполняемым соседями. Например, если в такой группе есть ведущий, который движется по запланированной траектории, то все остальные роботы повторяют его движения. Ресурс проекта находится по адресу http://www.cis.upenn.edu/mars/site/platforms.htm (Примечание. Автору не удалось выяснить, что скрывается под термином «Теория связанных систем». Наиболее внятное упоминание об этой теории было найдено в сборнике «Успехи физических наук» за 1935 г. Кроме того, часто название этой теории встречается совместно с т.н. «Теорией биосинхронизма», что совсем повергает автора в уныние.) Замечания к роевым и стайным методам Здесь необходимо сделать два замечания, первое из которых касается терминологии. Стая и коллектив. Следует различать понятия коллективного и стайного управления. Коллективное управление подразумевает, что объекты, входящие в группу, имеют возможность обмениваться друг с другом информацией. В т.ч. – знают о целях и задачах, имеют сведения о составе коллектива и т.д. Стайное управление предполагает, что члены группы не имеют, вообще говоря, информационной связи с другими объектами, могут не знать состава и характеристик прочих членов группы. Условно различие между стаей и коллективом можно изобразить так: Задача подражательного поведения. На самом деле, это весьма непростая задача. Реализация принципа «делай, как остальные» далеко не всегда сводится к правилам «ближайшего соседства». Это, скорее, управление на сложном поведенческом уровне. Дело в том, что для реализации подражания неизбежно возникают следующие задачи: 1. Распознавание «своих», т.е. объектов для подражания. 2. Определение действий «своих», которым следует подражать. Иными словами, робот должен знать, что делает его окружение, т.е. распознать их действия. 3. Выполнение такого же действия. Здесь речь идет даже не столько о реализации действия, сколько о реализации поведенческого акта. Таким образом, принцип «делай, как остальные» превращается в принцип «веди себя так же». Например, идти в том же направлении, что и прочие, отработать защитное поведение, поиск пищи и т.п. Особенно явно это видно у тех же муравьев. Подражательное поведение представляет собой крайне сложные комплексы действий – перенос пищи (в т.ч. – согласованные действия по транспортировке тяжелых грузов), строительство, уход, оборонительные действия и проч. Иными словами, речь идет о том, что подражательность означает запуск больших, сложных поведенческих (не только моторных) программ. И последнее. Типичный пример стайного поведения группы роботов так или иначе сводится к следующему: «Предположим, что каждый робот может выполнять одну из двух работ и при этом может менять одну на другую. Первоначально роботы выбирают себе работу произвольно. Периодически, обмениваясь информацией с ближайшими соседями, роботы принимают решение о продолжении выполнения выбранной ими работы или о ее изменении. Если большинство ближайших соседей выполняют ту же работу, что и данный 22 робот, то робот продолжает ее выполнять, иначе – меняет работу». А далее следуют какие- нибудь выводы, обобщения и проч. Интересно, что автоматные модели 60-х гг. оказываются гораздо глубже, интереснее и разнообразнее. Сравните, например, приведенную постановку с решением задачи о поливе участков [Варшавский и др., 1984]. 3.5. Эволюционные методы Разумеется, ни о какой эволюции роботов как технических устройств речи здесь не идет. В лучшем случае можно говорить о попытках реализации эволюционным путем механизмов внутристайного (внутрироевого) взаимодействия. Однако в этом направлении успехи весьма и весьма скромны, даже если речь идет о сугубо модельной эволюции. Отсутствие адекватных моделей (как методами генетических алгоритмов, так и методами классического эволюционного моделирования) эволюции, приводящей к появлению коллективов можно объяснить, видимо, тем, что для появления стайных образований нужны более сложные модели особей. Кроме того, неясны многие теоретические вопросы, такие, как: - каковы должны быть условия, при которых эволюционный процесс идет не путем усложнения структуры особи, а путем синтезогенеза (понимая под этим объединение разрозненных элементов в систему); - каким образом формируется функция качества для роевого организма, какие составные его части подлежат оценке ("поощрению" и "наказанию"); - каковы механизмы взаимодействия между особями и проч. Подавляющее большинство исследований в области эволюции коллективов роботов (эволюции их поведения) сводятся к тому, что: - реализуется искусственная, модельная среда эволюции, в которой стандартными методами (генетические алгоритмы, эволюционное моделирование и проч.); - моделируется эволюция; - результаты эволюционного процесса (сформированные структуры особей) загружаются в систему управления реальных роботов. Именно так происходит, например, в "эволюции" поведения коллектива роботов в проекте Политехнической школы Лозанны. Искусственная эволюция проходила в симулирующей среде Enki, где моделировались и роботы, и их сенсоры. Затем был использован эволюционный фреймворк роботов Teem. Структура лучших систем управления затем переносилась на реальных роботов. Эволюционированию подлежал 264-битный геном системы управления, который определял, как будет реагировать робот на информацию, поступающую с сенсоров. Таким образом, сейчас результатом эволюции является отдельная особь, а коллектив, по сути, – это просто множество отдельных роботов. Если речь идет о применении генетических алгоритмов, то это набор отдельных хромосом, перенесенный в системы управления, а если используются методы эволюционного моделирования, то, в случае автоматной модели, – автоматный газ в чистом виде. Не хотелось бы называть все это спекуляциями на эволюционные темы, но что-то от этого есть. 4. ЭЛЕМЕНТНАЯ БАЗА Поскольку речь идет о проблемах коллективного поведения роботов, как физических устройств, нельзя обойти вопрос об элементной базе. Универсальные колесные платформы. Это – наиболее распространенный способ реализации члена коллектива роботов. На рис.11 представлены типичные представители этого класса – исследовательский мобильный робот кафедры Теоретической механики и мехатроники МЭИ, робот, выпускаемый фирмой POLOLU и т.н. s-бот. 23 а) б) в) Рис.11. Колесные платформы. а) мобильный робот МЭИ; б) робот POLOLU; в) s-бот Подобного рода устройства обычно достаточно дороги и сложны. Например, упомянутые выше s-боты оснащены процессором Xscale с частотой 400 MHz, 64 MB оперативной памяти и 32 MB флеш-памяти, а также 12 PIC микроконтроллерами для низкоуровневой обработки. Не говоря уже о средствах коммуникации. Специализированные мини-роботы. В рамках открытого проекта SwarmRobot (www.swarmrobot.org) предполагается создание множества минироботов, габариты которых не превышают куба со стороной 3 см. (рис.12, а). Если будут созданы надежные и простые технологии производства таких роботов, то возникнет реальная возможность появления действительно больших коллективов из нескольких сотен членов. Микроробот, летающий на магнитных полях. В канадском Университете Ватерлоо в 2009 г. разработан микроробота MEMS (рис.12, б), который для полета использует магнитное поле Земли. Микроробот весит 0,83 г. Он оснащен крошечными электромагнитами, создающими вокруг него трехмерное параболическое магнитное поле. Микроробот имеет специальные клещи, которые открываются во время нагревания их лазерным лучом и закрываются по мере остывания. Они позволяют переносить микрообъекты из одной точки пространства в другую. Миниатюрные роботы Kilobot предназначены для изучения коллективного поведения (рис.12, в). Отличительной особенностью таких роботов является их дешевизна. Разработчики (Группа исследования самоорганизующихся систем Гарвардского университета) заявляют, что стоимость таких устройств составит всего $14. Вместо колес Kilobot оснащён двумя вибромоторами, позволяющими роботу двигаться вперед и совершать вращение. Скорость перемещения составляет 1 см/сек, а полный оборот вокруг своей оси робот совершает за 8 секунд. а) б) в) Рис.12. а) робот проекта SwarmBot; б) микроробот MEMS; в) робот Kilobot (A – вибродвигатель, B – LiIon-батарея, C – жесткая опорная нога, D – ИК-приемо-передатчик, E – трехцветный (RGB) светодиод). Проект MARV (Miniature Autonomous Robotic Vehicle). Это – один из самых первых проектов по созданию миниатюрных роботов. Проект был реализован в Национальной лаборатории США Сандиа еще в середине 1990-х гг. Объем созданного автономного робота составлял около 1 кубического дюйма, а к 2000 г. его размеры удалось уменьшить более чем 24 в четыре раза. Робот имел процессор с 8 Кбайт памяти, датчик температуры, микрофон, видеокамеру, химический сенсор. В дальнейшем MARV был оборудован системой беспроводной связи, после чего группа микророботов могла объединяться для совместного решения задач под управлением центрального компьютера. Ресурс проекта: http://robotics.sandia.gov/Marv.html Рис.13. Робот MARV Хороший обзор по архитектуре микророботов приведен в [Churaman, 2010]. Там же приведена весьма обширная библиография и ссылки на различные ресурсы. Показательно, что для реализации сложных движений (в т.ч. – прыжков), исследователи глубоко изучают движения насекомых. Рис.14. Шагающий миниробот и фазы движения насекомого |