Содержание
В последнее время в робототехнике появилась тенденция к исследованию группового взаимодействия роботов.
Как правило, такие исследования проводятся с группой однотипных роботов, которые должны решить какую-то определенную задачу.
Для решения задачи коллективного управления множеством однотипных объектов применяют роевой интеллект (Swarm Intelligence).
Предполагается, что простые алгоритмы управления каждым отдельным роботом приведут к сложному поведению целой группы роботов.
Управление роботами с помощью нейросетевой архитектуры
Большинство современных разработок в области группового управления роботами осуществляются на примере мобильных роботов.
Роботы имеют похожую архитектуру, а именно:
- Видеокамеры.
- Несколько датчиков дальности.
- Мобильная платформа на колесах.
- Возможно наличие датчиков освещенности.
В свою очередь у роботов есть средства связи, в частности:
- Начиная от простых фотодиодов.
- Заканчивая сложными радиочастотными модулями, например, BlueTooth или ZigBee.
Большинство разработок связано с решением одной узкоспециализированной задачи, например, нахождением кратчайшего пути между двумя точками в лабиринте или борьбе за энергетические ресурсы.
Методы построения алгоритмов управления разнообразны.
Данные методы основываются на алгоритмах искусственного интеллекта:
- Нейронные сети.
- Генетические алгоритмы.
Рассмотрим некоторые разработки в области коллективной робототехники более подробно.
В Федеральном университете Лозанны, Швейцария, проводятся исследования по выработке альтруизма у роботов.
Для этого авторы произвели следующий эксперимент:
- Поместили восемь маленьких мобильных роботов и восемь «источников энергии» на испытательный полигон прямоугольной формы.
- Одна стена полигона была белой, остальные — черные.
- Производительность робота пропорциональна количеству «источников энергии», которые робот доставил к белой стене.
- «Награду» за каждый доставленный источник энергии робот мог оставить себе, а мог равномерно распределить между остальными роботами.
Альтруистическое поведение описывалось на основе правила Гамильтона в публикации [1].
Основные параметры этого правила:
- с (cost) — репродуктивная успешность особи-эгоиста.
- b (benefit) — увеличение успешности выживаемости другой особи, в случае альтруизма первой.
- r (relatedness) — степень родства между особями вычисляется как (1/2)^g.
где
- g — число поколений или минимальное число родственных связей между особями.
- g=2 — для братьев.
- g=3 — для дяди-племянника.
Из правила Гамильтона следует:
- При rb>c средняя приспособленность альтруистов будет выше таковой «эгоистов» и количество копий генов альтруизма должно увеличиваться.
Для решения этой задачи система управления роботом была построена по нейросетевой архитектуре, в результате чего получили:
- Обучение каждой особи происходило при помощи генетического алгоритма (ГА) — весовые коэффициенты нейронной сети представляют собой отдельную особь ГА, «награда», получаемая роботами, служит для оценки приспособленности особи.
- За 500 поколений ГА мобильные роботы выработали законы поведения, позволяющие им решать поставленную задачу.
- Следует отметить, что в работе не описан механизм обмена информацией о выполняемой задаче между отдельными роботами.
- Существует лишь обмен «наградами». [Ошибка! Неизвестный аргумент ключа].
Алгоритм моделирования колонии муравьев
Другое направление в групповой робототехнике основано на моделировании колонии муравьев.
Основная идея этого метода основана на наблюдении за природной колонией насекомых, каждый из которых обладает примитивным поведением (движется по пути, отмеченному феромонами).
При этом целая колония ведет себя как сложный организм.
Для примера рассмотрим алгоритм поиска кратчайшего пути в лабиринте между муравейником и источником пищи представленный на рисунке 1:
где
- Первый муравей находит источник пищи (F), двигаясь по произвольному пути (а), затем возвращается в муравейник (N), оставляя за собой след феромонов.
- Муравьи случайным образом путешествуют по четырем возможным путям, но более короткий путь более посещаем, поскольку на длинных участках пути феромоны «исчезают» быстрей, чем на коротких.
- В результате кратчайший путь содержит максимальное количество феромонов, и именно этот путь выбирает большинство муравьев.
Мобильные роботы, действующие по данному алгоритму предназначены лишь для поиска кратчайшего пути между двумя точками, у ник отсутствует возможность передачи заданий друг другу. [Ошибка! Неизвестный аргумент ключа.].
Существуют алгоритмы роевого интеллекта, а именно:
- Искусственные иммунные системы [4].
- Алгоритм кукушки [5].
- Алгоритм светлячка [6].
Данные подходы являются лишь алгоритмами оптимизации для решения одной поставленной задачи и зачастую узкоспециализированной.
Возникает проблема организации роя мобильных роботов, способных решать разные типы задач, при этом они должны вырабатывать коллективное поведение.
Анализ существующих разработок показал:
- Что на данный момент исследователи коллективного поведения роботов не ставят перед собой задачи практического использования своих наработок.
- Проводимые эксперименты являются скорее полезными для разработки теорий коллективного поведения, чем способом применения групп одинаковых роботов для решения практических задач как в промышленности, так и в других областях человеческой деятельности.
В связи с развитием нанотехнологий и робототехники, общей миниатюризации электроники, мечта писателей- фантастов об использовании нанороботов — мельчайших самостоятельных машин, становится все ближе к осуществлению.
Однако нанороботы будут совершенно неспособны к одиночному функционированию, все планы их использования основаны на функционировании групп таких роботов.
Поскольку многие задачи могут успешно решаться именно с помощью групп одинаковых роботов, такие как:
- Перенос тяжестей группами роботов.
- Имитация групповой деятельности людей.
- Исследование неизвестных/труднодостижимых территорий мобильными отрядами роботов.
- Автоматизированная конвейерная сборка с постоянно изменяющимся технологическим процессом.
Представим себе условия работы отдельных многочисленных групп роботов/нанороботов:
- Небольшие вычислительные мощности отдельного робота и малый радиус коммуникации.
- Большое число одновременно работающих роботов, в тоже время стремящихся к общей цели.
- Большая вероятность потери связи с отдельным роботом/гибели робота (раздавлен, застрял и так далее).
Современные разработки не предназначены для работы одновременного большого числа роботов, в тоже время реализующиеся в них алгоритмы нейронных сетей чувствительны к потере узлов в процессе вычислений, приводящей к необходимости переобучения всей сети.
Таким образом, ведущиеся работы не могут использоваться для перспективных работ по большим группам роботов и нанороботов.
Как нам кажется, следует разработать алгоритмы функционировании больших сетей роботов, предназначенных для решения неких «общих», сформулированных для всего множества роботов, задач.
Исходя из выдвинутых выше условий работы больших колоний роботов, можно сформулировать требования к алгоритмам реализации коллективного поведения:
- Однородность — функциональная неразличимость отдельных роботов в группе.
- Неразрывность — стремление каждого робота сохранять целостность группы роботов.
- Масштабируемость — сохранение приемлемого быстродействия при увеличении числа роботов в группе.
- Устойчивость — способность сохранять способность достигать решения поставленных задач независимо от увеличения/уменьшения числа роботов, причем без существенных потерь во времени.
Описание прогрессивной схемы функционирования алгоритма роя
В рамках данного исследования, важным понятием является понятие «задача».
Задача — некое действие, которое должно стать итогом деятельности всех отдельных особей в группе.
Проводя аналогии с живыми группами существ, можно считать, что задачей группы муравьев может считаться предложение «Найти пропитание».
У группы роботов-исследователей вполне может быть задача «Найти признаки органической жизни».
В дальнейшем, по аналогии с живой природой, условимся называть группу роботов роем, а отдельного робота в рое — особью.
Цель роя — решение задачи с помощью достаточного числа особей.
Работа по данному алгоритму происходит в следующей последовательности:
- Рой осознает задачу, зная алгоритм ее решения.
- Исходя из требования масштабируемости, для роя не должно иметь значении количество особей в нем в данный момент.
- Очевидно, что для любой задачи существует некое минимальное количество особей, достаточное для решения, однако если особей хватает, рой должен достигать своей цели независимо от конкретного числа особей.
- В связи с требованием устойчивости, можно прийти к выводу что задачу, решаемую роем, должна осознавать каждая особь.
- Иначе, «убивая» особей, можно было бы лишить рой цели, и, таким образом нарушить устойчивость.
- Осознание цели роя особью можно описывать выполнением некоторых критериев, которые каждая особь в рое должна уметь проверять.
Например, если цель — найти еду, то каждая особь должна уметь проверять, является ли найденный объект съедобным, и так далее.
Рассмотрим подробнее процесс достижения цели роем с точки зрения программирования.
Если есть поставленная задача, то ее решение можно описать неким алгоритмом, в нашем случае описание алгоритма может иметь два уровня:
- Общий (коллективный) уровень — не оперирует отдельными особями, а лишь целым роем или отдельной группой особей.
Такой алгоритм в общих чертах описывает способ достижения цели. Например, алгоритм крепления детали группой роботов, предполагает, что одна часть роя должна держать деталь, а другая — закрутить винт.
- Частный (индивидуальный) уровень — описывает непосредственно как должны себя вести отдельные особи, чтобы достичь цели роя.
На данном уровне уже непосредственно задается, какие именно особи должны выполнить определенное действие.
Таким образом, существует два алгоритма — один, описывающий поведения всего роя, и второй, описывающий поведение каждой из особей. Так как особи неотличимы и взаимозаменяемы, то алгоритмов второго типа существует множество, однако результат все они дают одинаковый, или почти одинаковый — в той или иной степени решают задачу, поставленную перед роем.
По нашему мнению, для практического применения групп роботов необходимо решить задачу перехода от общего алгоритма действий всего роя к частным алгоритмам, с обязательным соблюдением условия устойчивости.
Это позволит не тратить ресурсы на управление каждой особью в отдельности, а лишь указывать всей группе, что делать.
Если представить себе рой в виде черного ящика, то получим следующую схему согласно рисунка 2:
Именно в переходе от общего алгоритма к частному и заключается сложность решения задачи управления большой группой роботов.
Поскольку группа действует самостоятельно, в ней должен содержаться некий общий алгоритм, позволяющий перевести общую цель в последовательность действий каждого участника группы, без внешнего вмешательства.
Это некий слой абстракции, отделяющий программный код отдельного робота от общего «сознании» всей группы, в котором и хранится цель роя.
Проведем сравнение с живой природой – муравейником:
- Каждый из муравьев стремится выжить, однако алгоритм выживания муравья, является существование в муравейнике и постоянная работа на благо всего муравейника.
- Он может пожертвовать собой ради общей цели, приносит еду не только себе, но и муравьям-охранникам, трутням.
Таким образом, через «программу» одного муравья реализуется общая программа всего выживания муравейника.
Так как один муравей выжить не может, можно сделать вывод, что общий алгоритм выживания хоть и существует в каждом из муравьев, но работать может только тогда, когда он попадает в группу таких же особей.
Попробуем представить себе логическую архитектуру информационной системы, реализующей поведение роя, представленный на рисунке 3:
В разрабатываемой модели учтены следующие условия работы алгоритмов:
- Индивидуальный уровень особи существует физически, в виде реального программного кода, хранимого в памяти отдельной особи и оперирующего напрямую деятельностью этой особи.
- Коллективный уровень является виртуальным — в том же смысле, что и сегодняшние виртуальные ЭВМ.
- Код, выполняемый на виртуальном уровне, хотя и хранится в реальной памяти особи, но выполняется в виртуальной среде, оперирующей понятиями всего роя.
- Отдельным особым объектом является интерпретатор, который представляет собой тот слой абстракции, осуществляющий переход от индивидуальных действий особи к коллективным и обратно.
- Действие интерпретатор сравнимо с работой ПО виртуальной машины, только вместо гостевой ОС выступает коллективный алгоритм.
- Интерпретатор выполняется на каждой из отдельных особей роя, оперируя ее вычислительными возможностями и обеспечивая реализацию программы всего роя.
Исходя из данной модели, можно представить себе, что рой состоит из отдельных особей-роботов, имеющих некоторые базовые навыки, являющиеся реализацией индивидуального уровня.
Из этого получаем следующие действия роботов:
- Способности к передвижению.
- Ориентированию на местности.
- Поднятию тяжестей и так далее.
Главное, что эти базовые навыки никак не зависят от действий других особей, иначе такой навык уже не может являться базовым, а должен стать частью коллективного уровня. Кроме того, каждый из роботов содержит код интерпретатора коллективного уровня.
При объединении роботов в группу, используя средства связи (например радио, свет и т.д.), интерпретатор подгружается в память каждого из роботов и начинает выполнять алгоритм достижения общей цели роя.
Таким образом, решив задачу построения интерпретатора, можно создать управляемый рой/группу роботов, которые, хотя и будут управляться одним человеком, будут самостоятельно распределять подзадачи между собой и действовать как единая группа, аналогично муравьям или пчелам в природе.
Список литературы
- Hamilton WD (1964) Thegenetical evolution of social behavior I+II. J TheorBiol 7: 1-52.
- Waibel M; Floreano, D; Keller, L (2011). «А quantitative test of Hamilton’s rule for the evolution of altruism». PLoSBiology 9 (5): e l 000615.
- Ant Colony Optimization by Marco Dorigo and Thomas Stutzle, MIT Press, 2004.
- de Castro, Leandro N.; Timmis, Jonathan (2002). Artificial Immune Systems: A New Computational Intelligence Approach. Springer, pp. 57-58.
- Х.-S. Yang; S. Deb (December 2009). «Cuckoo search via Levy flights». World Congress on Nature & Biologically Inspired Computing (NaBIC 2009). IEEE Publications, pp. 210-214.
- Yang X.S., (2008). Nature-Inspired Metaheuristic Algorithms. Frome: Luniver Press.
- Принципы построения прогнозной модели электропотребления промышленного предприятия на основе искусственной нейронной сети.
Источник: Проблемы практического применения роевого интеллекта и построение устойчивых управляемых групп роботов / Г.А. Сахопотинов, И.С. Сыркин // Вестник КузГТУ, 2013 год, №2, страницы 70-73.
