Моделирование некоторых форм адаптивного поведения интеллектуальных роботов

Д.А. Добрынин, В.Э. Карпов

// Информационные технологии и вычислительные системы №2, 2006 с.45-56

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

Введение

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

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

Технологии искусственного интеллекта (ИИ) всегда были тесно связаны с робототехникой. Создание роботов – машин, способных действовать как человек, является общей главной целью этих наук. После впечатляющих успехов, достигнутых во второй половине двадцатого века при успешном внедрении промышленных роботов в процесс автоматизированного производства, в настоящее время можно говорить о переносе центра научных исследований в область создания автономных роботов. Здесь нужно упомянуть космических роботов для изучения поверхности небесных тел Солнечной системы, роботов для подводных исследований. В ходе борьбы с терроризмом возникла острая необходимость в роботах, предназначенных для разминирования подозрительных предметов в местах скопления людей. Нужны «умные» роботы, которые могут без помощи оператора тушить пожары, самостоятельно передвигаться по заранее неизвестной пересеченной местности, выполнять спасательные операции во время стихийных бедствий, технологических аварий и т.п.

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

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

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

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

Разумеется, имеются достаточно строгие и формальные определения робота (например, «ГОСТ 25685-83 Роботы промышленные. Классификация» или «ГОСТ 25686-85 Манипуляторы, автооператоры и промышленные роботы. Термины и определения»), однако касаются они прежде всего промышленных роботов.

В настоящее время различают 3 поколения роботов.

1. Программные. Жестко заданная программа (циклограмма).

2. Адаптивные. Возможность автоматически перепрограммироваться (адаптироваться) в зависимости от обстановки. Изначально задаются лишь основы программы действий.

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

Интеллектуальные роботы

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

Не случайно одним из направлений ИИ до сих пор считается целенаправленное поведение роботов (создание интеллектуальных роботов, способных автономно совершать операции по достижению целей, поставленных человеком) [Поспелов, 1988].

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

Дальнейшее развитие заключается во введении иерархии уровней управления – стратегического, тактического и исполнительного.

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

Если отойти от подобного «перечислительно-функционального» определения ИР, то останется лишь два более или менее конструктивных определения. Первое заключается в том, что интеллектуальный робот – это робот, в состав которого входит интеллектуальная система управления. Тогда достаточно только выбрать определение интеллектуальной системы (ИС). Например, определить ИС как компьютерную систему для решения задач, которые или не могут быть решены человеком в реальное время, или же их решение требует автоматизированной поддержки, или же их решение дает результаты сопоставимые по информативности с решениями человека ([Финн, 2004 a], [Финн, 2004 b]).

Кроме того, среди прочего подразумевается, что задачи, решаемые ИС не предполагают полноты знаний, а сама ИС должна обладать способностями: к упорядочению данных и знаний с выделением существенных параметров; к обучению на основе позитивных и негативных примеров, к адаптации в соответствии с изменением множества фактов и знаний и т.д. ([Финн, 2004 b])

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

Действительно, это определение относится к оценке всего устройства в целом, делая бессмысленными рассуждения об «интеллектуализации» отдельных функций или узлов робота. Устройство, оснащенное лишь «интеллектуальным» зрением (см., например, [Кацухико Нода, 1975]) или «интеллектуальным» двигательным аппаратом ([Барсуков, 2005]), вряд ли может называться полностью интеллектуальным.

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

Архитектура системы

В настоящее время подавляющее большинство работ в области создания моделей поведения, использование методов ИИ для управления различными объектами имеют в основном теоретический, абстрактный характер. Причины тому много, одной из них является кажущаяся трудоемкость и дороговизна проектов, работающих с реальными техническими устройствами. В ходе реализации проекта «Адаптант-2005» (см. [Добрынин и др., 2005], [Добрынин, Карпов, 2005]) был создан универсальный мобильный робот «Амур», являющийся полигоном для отработки и демонстрации различных алгоритмов и методов управления. В настоящей работе речь идет о реализации на базе созданного устройства некоторых простейших формах адаптивного поведения, начиная с моделирования условно-рефлекторного поведения и заканчивая применением эволюционного моделирования и ДСМ-метода для решения конкретных робототехнических задач.

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

Рис.1. Архитектура системы и внешний вид робота

Вычислительные ресурсы робота невелики: тактовая частота микроконтроллера ATMega162 - 7 МГц, флэш-память для хранения программного кода - 16 K, ОЗУ - 512 байт.

Условно-рефлекторное поведение

Рассмотрим далее некоторые вопросы, связанные с моделированием такой простой формы поведения роботов, как условно-рефлекторное.

Автоматная модель

Одной из наиболее эффективных и простых моделей условно-рефлекторного поведения является вероятностный автомат [Цетлин, 1969].

Имеется устройство с N датчиками и M эффекторами (исполнительными механизмами). Таким образом, входной алфавит составляет X=2N сигналов, а выходной - Y=2M (при условии независимой отработки устройством каждого управляющего воздействия). При этом, в отличие от [Цетлин, 1969], рассматривается автомат с детерминированной матрицей переходов по всем 2N сигналам.

Действия автомат совершает в соответствии со стохастической матрицей P размером Q×X×Y, где Q– количество состояний. Т.е., находясь в некотором состоянии q(t) и приняв на входе сигнал x(t), автомат переходит в состояние q(t+1). При этом он совершает действие y, выбираемое из соответствующего вектора вероятностей – строки матрицы P:

y(t+1) = F(x(t), q(t), P(t)),

q(t+1) = Q(x(t),q(t)).

Рис. 2. Стохастическая матрица действий

Реакция автомата на входное воздействие оценивается – автомат наказывается либо поощряется. Смысл реакции на сигнал наказания/поощрения заключается в изменении значений вероятностей выполняемых действий. Теоретически изменение вероятностей при поощрении ( s=0) и наказании ( s= 1) выглядит так:

pij(t+1,s(t)) = pij(t,s(t))+(-1)s(t+1)× g× pij(t,s(t))× [1-pij(t,s(t))]

pik(t+1,s(t)) = pik(t,s(t))-(-1)s(t+1)× g× pik(t,s(t))× pij(t,s(t)) для k¹ j. 0£ g£ 1

Здесь g– параметр, определяющий скорость обучения. Таким образом, с течением времени в ходе «дрессировки» автомат должен сформировать необходимые значения вероятностей действий.

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

Рис.3. Структура управляющего автомата

Однако на практике вполне можно обойтись автоматом «без памяти» – с одним состоянием. На самом деле память реализована матрицей P, но речь идет о том, что автомат не различает понятия «предыдущие моменты времени».

Нейронная сеть

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

Поощрение и наказание

Реализация схемы наказания/поощрения. При дрессировке обычно используется как наказание, так и поощрение. Теоретически при выработке условных рефлексов можно обойтись исключительно наказаниями (отсутствие наказания может и должно рассматриваться как поощрение). Однако отсутствие сигнала поощрения значительно увеличивает время обучения автомата. Основная проблема заключается в том, когда и за что наказывать/поощрять. Между свершением действия и его оценкой проходит какое-то время. Предположим, что действие было оценено как неверное и объекту был послан сигнал наказания. За это время объект мог совершить много других действий, потому, получив сигнал наказания, возникает закономерный вопрос: а за что, собственно, наказали? Для разрешения этой проблемы в проекте был использован т. н. синхронный метод подачи оценочного воздействия. Суть его сводится к тому, что после совершения действия автомат выдает сигнал готовности к приему оценки и ждет в течение некоторого времени. По окончании времени ожидания автомат выдает сигнал неготовности к приему. С точки зрения эффективности организации взаимодействия обучаемого с учителем, это - наиболее простой вариант.

Для поощрения/наказания может использоваться как пульт ручного управления (радиоканал на 4 команды: поощрение, наказание и эмуляция фотодатчиков-глаз), так и управляющая ЭВМ, использующая специальную программу полной эмуляции входных/выходных сигналов робота через интерфейс RS232. «Дрессировка» с помощью ЭВМ, естественно, значительно эффективнее, т.к. при «ручной дрессировке», несмотря на издаваемые роботом звуковые сигналы готовности, промахи совершаются оператором достаточно часто. Это тем более актуально, что для обучения какому-либо рефлексу (типичный пример – «при попадании света в правый глаз робот должен издать звуковой сигнал») требуется порядка 10-12 тактов обучения.

Некоторые замечания к условно-рефлекторному поведению

Поощрение и наказание. Рассмотренная схема обучения с подкреплением (модель «стимул-реакция») обладает рядом требований к балансу между актами поощрения и наказания.

Максимальная скорость обучения достигается при поощрении. Фактически, при имеющихся параметрах достаточно одного акта поощрения для окончания обучения.

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

Рис.4. Реакция элементов вектора на сигналы поощрения-наказания

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

Виды обучения. Рассматриваемая схема выработки роботом требуемого поведения относится к т. н. обучению с учителем. Учитель (обучающее устройство) может формировать не только сигналы поощрения и наказания s={0,1}, но и формировать эталонный вектор управляющих воздействий E= { e1, e2,…, ek}. В этом смысле можно говорить о двух типах обучения (типах обучающего устройства):

·      Б-обучение (± - обучение). Учитель ограничивается сигналами поощрения и наказания;

·      В-обучение. Здесь происходит формирование вектора управляющих воздействий.

Обучение нейронных сетей. Очевидно, что лучшие результаты обучения НС получаются при использовании В-обучения, при котором происходит сравнение выходного вектора НС с эталонным вектором E. Использование же Б-обучения в НС приводит к ухудшению качества обучения. При этом режиме обучения выходной вектор НС сопоставляется с нулевым вектором E, что эквивалентно использованию в обучении исключительно сигнала наказания.

Псевдовзаимодействие роботов

Описанные выше модели, несмотря на свою простоту, позволяют реализовывать и боле сложные поведенческие акты, в которых участвует коллектив роботов. Вопросы, касающиеся моделей коллективного поведения, достаточно хорошо описаны в многочисленной литературе, начиная с классических работ Цетлина, Варшавского и Стефанюка и заканчивая множеством публикаций на многоагентные темы. Здесь мы рассмотрим частный случай взаимодействия двух конкретных технических объектов – мобильных роботов, созданных в рамках проекта «Адаптант».

Рассмотрим следующую задачу. Пусть робот A1 функционирует в некоторой среде S1, а робот A2 - в среде S2. Пусть среды S1 и S2 являются частями некой единой среды S. Отсюда следует естественный интерес к реализации схемы взаимного обмена навыками, полученными роботами с тем, чтобы робот, успешно живущий в S1, мог бы функционировать и в «чужой» среде S2.

Далее предлагается реализация двух экстенсивных моделей типа «1 голова – хорошо, 2 – лучше» (1ГХ2Л). Суть их сводится к тому, что «навыки» роботов A1 и A2, приобретаемые независимо друг от друга с какой то периодичностью считываются центральной управляющей ЭВМ. Далее эти «навыки» подлежат некоторой процедуре объединения, результат которого передается обратно роботам.

Рис.5. Схема 1ГХ2Л

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

Модели типа 1ГХ2Л служат для демонстрации эффективности «параллельного» обучения (то, что знает/умеет один – знают/умеют все остальные члены коллектива). Различаются эти модели формой представления «навыков» у обучаемых объектов.

Модель 1ГХ2Л-A («Автоматы»). В ней рассматриваются роботы, управляемые вероятностными автоматами. Суть модели состоит в процедуре объединения матриц вероятностей действия. Роботы управляются ЭВМ, которая инициирует процесс объединения навыков, подает управляющие и обучающие воздействия на роботов.

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

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

Рис. 6. Объединение матриц вероятностей действия

Модель 1ГХ2Л-НС («Нейронные сети»). Эта модель аналогична модели 1ГХ2Л-A, но вместо матрицы вероятностей (в автоматной модели) используются нейронные сети. Для этой модели осуществляется обмен приобретенными навыками. Теоретическим базисом является процедура композиции нейронных сетей.

Задача индуктивной классификации

Увеличение количества сигналов рецепторов приводит к очевидным сложностям обучения. При R независимых входных сигналах (датчиках) размерность входного алфавита автоматной модели определяется как dim X =2 R . Введение параллелизма (как в случае использование нейронной сети) не спасает ситуацию - время обучения возрастает экспоненциально.

Отсюда неизбежно возникает задача классификации множества входных сигналов (распознавание ситуаций). Вместо стимул-реактивного преобразования «вход-выход» Y = R ( X ) требуется наличие дополнительного устройства – классификатора C:

Рис.7. Преобразователь «вход-выход»

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

Основная задача состоит в создании этого классификатора как результата адаптивного поведения робота.

Ниже будут рассмотрены два механизма получения адаптивного классификатора: использование эволюционного моделирования для получения классификатора в виде распознающего автомата и применение динамического ДСМ-метода для реализации классификатора в виде множества правил.

При этом в качестве задачи был выбран классический тест из регламента фестиваля мобильных роботов – движение по черно-белой полосе. Линия чертится на раскрашенном в шахматном порядке поле и является инверсной. Датчики полосы образованы 4 парами ИК-приемник/излучатель как показано на рис. 8.

Рис. 8 Расположение фотодатчиков определения полосы

Эволюция классифицирующего автомата

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

Обучающие примеры – это множество пар вида

E ={ ei }={( X i , yi )},

где X i - двоичный вектор сигналов рецепторов, yi – требуемая для данной ситуации реакция.

В случае В-обучения требуемой реакцией может служить номер класса ситуации или, в случае изоморфизма «класс-действие» - номер действия.

В случае Б-обучения ситуация несколько усложняется. Входной вектор X должен состоять из двух частей – части, содержащей сигналы рецепторов, и части, описывающей внутреннее состояние системы – состояния эффекторов. Тогда требуемая реакция y может трактоваться «двоичным» образом, т.е. хороша или плоха данная комбинация эффекторов при заданном векторе рецепторов.

Рис.9. Схема включения эволюционного процесса

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

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

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

S(x1,x2,..,xn,y1,y2,...,yn),

где x1,x2,..,xn - входная последовательность, y1,y2,...,yn - выходная последовательность символов. Функция ошибки определяет величину штрафа, получаемого автоматом за неверный выходной сигнал (действие или предсказание). Когда величина накопленных особью штрафов превышает некоторое заданное значение, данная особь «умирает» (аналог естественного отбора). Автомат содержит стохастическую матрицу P, определяющую вероятности действий. Выходная реакция автомата yt определяется стохастическим вектором из P , соответствующим состоянию автомата и входному сигналу.

Рис. 10 Структура особи

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

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

Далее из полученной в результате эволюции популяции автоматов {Ai} выбирается наиболее эффективная особь Aопт. Именно этот автомат загружается в робота в качестве классификатора.

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

При последовательной подаче элементов вектора X очевидно, что для безошибочного распознавания количество состояний автомата | Q | должно удовлетворять следующему требованию:

| Q | ≥ | X | - | I |,

где | X | - длина вектора X, а | I | – длина его «информативной части». Речь идет о том, что требуемые для решения задачи датчики (их номера в векторе) могут занимать далеко не первые позиции, могут быть разгруппированы и т.д.

Рис. 11. Структура вектора датчиков

В этом случае начало информативной части соответствует номеру первого необходимого для решения задачи датчика.

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

На рис.12 представлен один из получившихся в ходе эволюции управляющих автоматов.

Рис.12. Структура управляющего автомата

Пометки переходов интерпретируются следующим образом:

x:f1/p1, f2/p2, f3/p3, f4/p4

где x – значение входного символа, fi – номер действия, pi – вероятность этого действия. Например, пометка

0: 0/0.25, 1/0.25, 2/0.25, 3/0.25

означает, что при входном символе ‘0’ действия 0-3 имеют равные вероятности. Действия автомата (робота) кодируются числами от 0 до 3 – «вперед», «назад», «налево», «направо» соответственно.

Динамический ДСМ

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

Множество обучающих примеров – это множество пар вида

E ={ ei }={( X i ,u i )},

где Xi - вектор сигналов рецепторов, ui – вектор управления (состояние исполнительных механизмов). Элементы векторов сигналов и управления представляются парами двоичных значений:

включено = {01}, выключено = {10}

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

Рис. 13 Структура обучающих примеров и гипотез

Гипотезы представляются в виде множества пар вида:

G ={ gi }= {{ xi , yi }},

где xi – часть вектора сигналов рецепторов, yi – требуемый вектор управления (необходимое действие).

Динамический ДСМ работает в двух режимах:

-      режим обучения, когда происходит заполнение базы фактов (множество обучающих примеров) и генерируются гипотезы, составляющие базу знаний;

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

В режиме обучения для формирования обучающих примеров используется внешний алгоритм – так называемый «учитель». Данный алгоритм получает на вход информацию от рецепторов и вырабатывает управляющие сигналы, необходимые для адекватного поведения робота. Совокупность сигналов рецепторов и выработанных для них управляющих воздействий определяет один обучающий пример. Этот пример проверяется на уникальность и заносится ДСМ системой в базу фактов. После занесения каждого нового примера во множество обучающих примеров производится поиск гипотез. Для данной задачи использовался простой ДСМ метод без запрета на контрпримеры, поскольку нет отрицательных обучающих примеров [Кузнецов, 1991].

Полученное множество гипотез { gi } будет содержать все возможные пересечения (общие части) обучающих примеров. Далее среди них отбираются минимальные гипотезы, то есть такие, которые вкладываются в остальные. Тем самым количество «полезных» гипотез резко сокращается. Полученные минимальные гипотезы проверяются на уникальность и заносятся в базу знаний.

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

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

Если база фактов полна, то характер поведения робота в рабочем режиме под управлением ДСМ системы ничем не должен отличаться от управления «учителем». Проведенные эксперименты с минироботом «Амур» подтверждают этот факт.

На рис. 14 представлен пример простого обучающего алгоритма для движения по темной полосе. Данный алгоритм использует фотодатчики 2 и 3 для отслеживания края полосы.

Рис. 14 Пример обучающего алгоритма для движения по полосе

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

Таблица 1.

_

1

1

_

2

2

_

3

3

_

4

4

F

B

L

R

1

1

0

1

0

1

0

1

0

0

0

1

0

2

1

0

1

0

1

0

0

1

0

0

1

0

3

0

1

1

0

1

0

1

0

0

0

1

0

4

0

1

0

1

1

0

1

0

1

0

0

0

12

1

0

1

0

0

1

0

1

0

0

0

1

13

0

1

1

0

0

1

0

1

0

0

0

1

14

0

1

1

0

1

0

0

1

0

0

1

0

15

0

1

0

1

1

0

0

1

1

0

0

0

16

0

1

1

0

0

1

1

0

0

0

0

1

Таблица 2

_

1

1

_

2

2

_

3

3

_

4

4

F

B

L

R

1

0

0

1

0

1

0

0

0

0

0

1

0

2

0

0

0

1

1

0

0

0

1

0

0

0

3

0

0

0

0

0

1

0

0

0

0

0

1

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

Сравнение результатов обучения

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

Оба метода отрабатывались на одних и тех же обучающих полигонах (см. рис.15).

Рис.15. Один из обучающих полигонов

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

Следует отметить, что внешне поведение роботов, реализующих обучение на основе ЭМ и ДСМ, не слишком отличалось друг от друга.

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

Достаточность обучающих примеров. При наличии представительной выборки обучающих примеров оба метода дают хорошие результаты. Однако в условиях неполноты обучающего множества метод ЭМ дает более устойчивые результаты по сравнению с ДСМ. Это связано прежде всего с характером управления.

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

Эффективность обучения (скорость). Обучение в ЭМ – принципиально длительный процесс. Для устойчивого обучения методом эволюционного моделирования иногда требуются сотни тысяч тактов. В этом отношении ДСМ-метод обладает несомненным преимуществом - для обучения с помощью ДСМ метода достаточно получить несколько разных обучающих примеров. В экспериментах роботу достаточно было проехать один круг на реальном полигоне чтобы сформировались все необходимые гипотезы.

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

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

Требуемые ресурсы. При реализации практических алгоритмов встает проблема ограниченности вычислительных ресурсов автономного робота.

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

Заключение

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

Основной особенностью рассмотренных в работе моделей является их «натурная» реализация, практическое воплощение в робототехническом устройстве. Самое интересное, пожалуй, заключается в том, что ориентация на аппаратную реализацию не только выявила некоторые не столь очевидные особенности реализуемых моделей (вроде проблемы определения момента поощрения-наказания и синхронизации управляющих воздействий), но и определила саму постановку задач, например, возможности использования ДСМ-метода и ЭМ для управления техническим объектом.

Литература

  1. [Цетлин, 1969] Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем. -М.:Наука, 1969.
  2. [Финн, 1991] Финн В.К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ //Итоги науки и техники. Сер. «Информатика». Т. 15. - М.: ВИНИТИ, 1991. - С. 54–101.
  3. [Финн, 2004a] Финн В.К. Искусственный интеллект: Идейная база и основной продукт, 9-я национальная конференция по искусственному интеллекту, Труды конференции, Т.1, М., Физматлит, 2004, с.11-20.
  4. [Финн, 2004b] Финн В.К. Об интеллектуальном анализе данных //Новости искусственного интеллекта №3, 2004
  5. Кузнецов С.О. ДСМ-метод как система автоматизированного обучения // Итоги науки и техники. Сер. «Информатика». Т. 15. - М: ВИНИТИ, 1991. - 17–53.
  6. Карпов В.Э. Эволюционное моделирование. Проблемы формы и содержания // Новости искусственного интеллекта №5, 2003
  7. Добрынин Д.А., Карпов В.Э. Моделирование некоторых простейших форм поведения: от условных рефлексов к индуктивной адаптации //Сб. научных трудов I Международной конференции «Системный анализ и информационные технологии САИТ-2005», М.: КомКнига, Т.1, стр. 188-193
  8. Добрынин Д.А., Карпов В.Э., Мещерякова Т.В., Степанов С.Н. Адаптивный мобильный робот //Мобильные роботы и мехатронные системы: Материалы научной школы-конференции, Москва, 21-25 марта 2005. Часть 1. М.: Изд-во Моск. ун-та, 2005., стр. 137-143
  9. Поспелов Г.С. Искусственный интеллект - основа новой информационной технологии. -М.:Наука, 1988. - 280 с.
  10. Попов Е.П., Письменный Г.В. Основы робототехники: Введение в специальность. М.:Высш.шк., 1990. – 224 с.
  11. Пособие по применению промышленных роботов. Под ред. Кацухико Нода, пер.с япон. -М.:Мир, 1975, -454 с.
  12. Барсуков А.П. Кто есть кто в робототехнике. Справочник. Вып.1., ДМК-Пресс, 2005, -125 с.

Добрынин Дмитрий Анатольевич, к.т.н. научный сотрудник ВИНИТИ РАН, г. Москва

Карпов Валерий Эдуардович, к.т.н., доцент, ведущий научный сотрудник НИИ Информационных технологий, г. Москва