Моделирование некоторых простейших форм поведения: от условных рефлексов к индуктивной адаптации

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

Моделирование некоторых простейших форм поведения: от условных рефлексов к индуктивной адаптации

Добрынин Дмитрий Анатольевич,

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

Карпов Валерий Эдуардович,

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

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

адаптивный робот поведение рефлекторный

Введение

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

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

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

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

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

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

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

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

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

Действия автомат совершает в соответствии со стохастической матрицей 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) выглядит так:

p_ij(t+1,s(t)) = p_ij(t,s(t))+(-1)^s(t+1)gp_ij(t,s(t))[1-p_ij(t,s(t))]

p_ik(t+1,s(t)) = p_ik(t,s(t))-(-1)^s(t+1)gp_ik(t,s(t))p_ij(t,s(t)) для kj. 0g1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис.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 парами ИК-приемник/излучатель.

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

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

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

E={e_i}={(X_i,yⁱ)},

где X_i - двоичный вектор сигналов рецепторов, yⁱ - требуемая для данной ситуации реакция.

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

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

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

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

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

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

|Q| ? |X| - |I|,

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

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

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

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

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

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

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

E={e_i}={(X_i,uⁱ)},

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

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

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

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

G={g_i}= {{x_i,yⁱ}},

где x_i - часть вектора сигналов рецепторов, yⁱ - требуемый вектор управления (необходимое действие). Гипотезы существуют двух видов: положительные гипотезы определяют, при каком входном воздействии выполнять действия, приводящие к положительному результату; отрицательные гипотезы определяют, какие действия не нужно делать при данном входном воздействии.

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

F = (Photo1=ON) AND ((MotorLeft=ON) OR (MotorRight=ON)),

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

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

Принятие решения для нового состояния

- если вкладывается (+) гипотеза, то изменяем управление в соответствии с ней

иначе это (t) пример, задать случайный вектор управления с учетом (-) гипотез

Считывание датчиков, запоминание предыдущего состояния

Ждем изменения состояния или тайм-аута

Применение оценочной функции:

если удовлетворяет функции или приводит к ее удовлетворению, то это (+) пример

иначе - это (-) пример

Получение гипотез с помощью ДСМ, фальсификация гипотез

Переход к п.1.

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

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

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

В данном случае использовался метод с запретом на контрпримеры - полученная положительная гипотеза не должна вкладываться в отрицательные примеры, и наоборот - отрицательная гипотеза не должна вкладываться в положительные примеры [3].

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

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

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

Заключение

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

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

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

Литература

1. Цетлин М.Л. Исследования по теории автоматов и моделированию биологических систем. -М.:Наука, 1969.

2. Финн В.К. Правдоподобные рассуждения в интеллектуальных системах типа ДСМ // Итоги науки и техники. Сер. «Информатика». Т. 15.-- М.: ВИНИТИ, 1991.-- С. 54-101.

3. Кузнецов С.О. ДСМ-метод как система автоматизированного обучения // Итоги науки и техники. Сер. «Информатика». Т. 15.-- М: ВИНИТИ, 1991.-- 17-53.

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