К вопросу об управлении мобильным роботом в условиях общей постановки задачи - Статья

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

Вопросы управления роботами в слабоформализованных условиях, в том числе при нечеткой, общей постановке задачи, рассматриваются в рамках так называемой интеллектуальной робототехники. Само понятие интеллектуального робота (ИР) является сегодня не вполне определенным. Большинство определений ИР относится к функционально-перечислительной категории, т.е. сводящихся к перечислению интеллектуальных свойств, которыми должен обладать робот («зрение», «слух», «планирование» и т.д., вплоть до указания конкретных механизмов искусственного интеллекта (ИИ)) [1].

Кроме указанного, останется лишь два более или менее конструктивных определения ИР. Первое определение заключается в том, что ИР - это робот, в состав которого входит интеллектуальная система управления. При этом достаточно выбрать определение интеллектуальной системы (ИС). Например, определить ИС как компьютерную систему для решения задач, которые или не могут быть решены человеком в реальное время, или же их решение требует автоматизированной поддержки, или же их решение дает результаты сопоставимые по информативности с решениями человека ([2],[3]).

Вторым, менее формальным определением ИР, является способность системы решать задачи, сформулированные в общем виде. Это определение является, не смотря на свою «слабость», достаточно конструктивным по крайней мере для того, чтобы определить степень интеллектуальности робота. Действительно, такое определение относится к оценке всего устройства в целом. При этом рассуждения об интеллектуальности отдельных функций или узлов робота становятся бессмысленными. Устройство, оснащенное лишь интеллектуальным зрением [4] или интеллектуальным двигательным аппаратом [5], вряд ли может называться интеллектуальным.

Положим, что ИР должно быть достаточно лишь общей постановки задачи. Рассмотрим, возможна ли подобная общая постановка на примере задачи движения по линии (классический тест из регламента соревнований мобильных роботов). Датчики полосы образованы 4 парами ИК-приемник/излучатель как показано на рис. 1.

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

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

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

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

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

В настоящее время большинство работ в области создания моделей поведения и использования методов ИИ для управления различными объектами имеют в основном теоретический, абстрактный характер. Причин тому много, одной из них является кажущаяся трудоемкость и дороговизна проектов, работающих с реальными техническими устройствами. В ходе реализации проекта «Адаптант» [3, 4] был создан универсальный мобильный миниробот «Амур», являющийся полигоном для отработки и демонстрации различных алгоритмов и методов управления.

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

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

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

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

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

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

Однако интерес представляет обучение, при котором учитель (обучающее устройство) формирует только сигналы поощрения и наказания, оценивая поведение системы в целом. Это - так называемое, Б-обучение (±-обучение). Но даже в случае Б-обучения предполагалось, что эта оценка основывается на полном априорном знании требуемой реакции. То есть учитель должен знать, какое действие должен совершить робот в том или ином классе ситуаций и затем осуществить оценку этого действия. Иными словами, явно или неявно предполагалось наличие некого сильного критерия обучения.

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

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

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

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

Действия автомат совершает в соответствии со стохастической матрицей P размером Q?X?Y, где Q - число состояний; X, Y - размерность входного и выходного алфавитов. Таким образом, находясь в некотором состоянии 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)).

Рис. 3. Стохастическая матрица действий мобильный робот моделирование рефлекторный

Реакция автомата на входное воздействие оценивается - автомат наказывается либо поощряется. Смысл реакции на сигнал наказания/поощрения заключается в изменении значений вероятностей выполняемых действий. Изменение вероятностей при поощрении (s = 0) и наказании (s = 1) выглядит так: pij(t 1, s(t)) = pij(t, s(t)) (-1)s(t 1)gpij(t, s(t))[1 - pij(t, s(t))], (1) pik(t 1, s(t)) = pik(t, s(t)) - (-1)s(t 1)gpik(t, s(t))pij(t, s(t)), k ? j, 0?g?1, где g - параметр, определяющий скорость обучения. В этой связи с течением времени в ходе «дрессировки» автомат должен сформировать необходимые значения вероятностей действий.

Робот, управляемый вероятностным автоматом, считывает состояние датчиков и совершает очередное действие. Далее происходит проверка выполнения «слабого критерия» - видит ли он линию (например, хотя бы одним датчиком). Если робот после совершения движения по-прежнему находится на линии, то робот поощряется (вероятность этого действия для предыдущего состояния увеличивается), иначе - наказывается (вероятность уменьшается).

Эта весьма простая схема показывает достаточно устойчивые положительные результаты.

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

Рис.4. Начальное положение робота на полигоне

На рис. 4, а показана ситуация наличия неудобного для обучения участка - развилки. В этом случае предпочтительнее начальная ориентация, указанная на рис. 4, б.

В дальнейшем по окончании обучения робот показывает стабильную работу и в реальных «загрязненных» условиях. Эти модельные «загрязненные» условия представлены на рис. 5.

Рис. 5. Один из обучающих «реальных» полигонов

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

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

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

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

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

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

а) б) в)

Рис.6. Реакция элементов вектора на сигналы поощрения-наказания. а) - исходный вектор; б) распределение вероятностей при поощрении за действие 2; б) распределение вероятностей при наказании за действие 3;

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

Управление на основе эволюционного моделирования

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

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

Рис.7. Модифицированный преобразователь «вход-выход»

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

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

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

Как известно [12], одной из основных задач эволюционного моделирования является задача предсказания последовательности символов. Предположим, что в результате процесса эволюции был создан предсказатель P, определяющий значение входного вектора X в момент времени t 1 на основе своей предыстории и значения управляющего вектора: Xt 1 = P(Ut, Xt, Xt - 1, …, Xt - n), (2) где Xt - значение вектора входных сигналов (сигналов датчиков) в момент времени t;

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

Введем показатель качества - общий критерий управления роботом - в виде функции f: X® {0,1}, (3) определяющей положение робота относительно полосы. Например, следующим образом:

(4)

Таким образом, мы приходим к задаче определения такого управления U, что f(X)=1, а именно: Ut: f(Xt 1) = f(P(Uit, Xt, Xt - 1, …, Xt - n))=1 (5)

Основным здесь является именно предсказание Xt 1 на основе предыдущих наблюдений и управления Ut в момент времени t и выбор на основе этого предсказания подходящего управления.

Если оператор предсказания P выводится эволюционным путем, то определение управления Ut может быть осуществлено на основе перебора возможных вариантов Uit и выбора среди них подходящего. Иными словами, для каждого Uit можно, согласно (5) определить f(Xt 1).

Формирование предсказателя P осуществляется путем эволюции популяции распознающих (классифицирующих) автоматов. Среда, в которой происходит эволюция, образована множеством элементарных признаков (обучающих примеров): S = {ji }, ji=(, f(X)) (6) где X - вектор входных сигналов, U - вектор управления, f(X) - значение оценочной функции (4).

Полученное множество обучающих примеров формирует среду, в которой запускается эволюционный процесс. Эволюции подлежат конечные вероятностные автоматы, задачей которых является классификация обучающей выборки (6) [6]. Фактически цель эволюции заключается в создании классифицирующего автомата, разбивающего множество ji на 2 класса: «хорошие» («положительные») и «плохие» («отрицательные») ситуации, в которых робот видит или не видит линию соответственно.

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

S(x1, x2, …, xn, y1, y2, ..., yn), где x1, x2, …, xn - входная последовательность;

y1, y2, ..., yn - выходная последовательность символов.

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

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

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

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

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

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

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

Рис. 9. Процесс эволюции. а) - Индивидуальные показатели качества особей; б) - усредненный показатель качества популяции; в) - средний возраст особей популяции.

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

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

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

Пометки переходов интерпретируются следующим образом: x: f1/p1, f2/p2, где x - значение входного символа;

fi - выходной сигнал (действие);

pi - вероятность этого действия.

Например, пометка 3: 0/0,5, 1/0,5 означает, что при входном символе «3» действия 0 и 1 имеют равные вероятности. Выходной алфавит автомата - это символы 0 и 1, определяющие классы «плохих» (робот не на линии) и «хороших» (робот на линии) ситуаций, т.е. значения функции (4).

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

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

Для всех возможных вариантов управления Ui произвести следующий цикл: Сформировать входную последовательность eti={()}.

Подать сигнал на вход автомата и оценить реакцию fi: fi = A(eti).

Если f i =1, то в качестве управления выбрать Ui и выйти из цикла.

Завершить цикл.

Отработать управление Ui .

Перейти к этапу 1.

Подобная организация стратегии управления показывает значительно лучшие результаты, нежели условно-рефлекторная схема, в которой движение робота по полосе менее устойчиво. Кроме того, индуктивное управление является более гладким - устройство практически не подвержено рысканиям. Все это связано с глубиной анализа ситуации. Если в условно-рефлекторной схеме речь идет об анализе исключительно текущей позиции (глубина памяти равна 1), то в индуктивной схеме робот может осуществлять коррекцию движения плавно, используя ретроспективные знания (предысторию, определяемую глубиной памяти) [7].

На рис. 10 изображена схема включения индуктивного классификатора в систему управления роботом.

Рис.10. Схема включения эволюционной компоненты в систему управления

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

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

E={ei}={(Xi, yi)}, где Xi - двоичный вектор сигналов рецепторов;

yi - требуемая для данной ситуации реакция.

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

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

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

1. Барсуков А.П. Кто есть кто в робототехнике. Справочник. Вып.1. ДМК-Пресс, 2005. 125 с.

2. Девянин Е.А. Интеллектуальные мобильные роботы // Политехнические чтения. Вып. 2. Кибернетика - ожидание и результаты. М.: Знание, 2002. С.102-103.

3. Добрынин Д.А., Карпов В.Э. Моделирование некоторых простейших форм поведения: от условных рефлексов к индуктивной адаптации // Сб. научн. тр. I Международной конференции «Системный анализ и информационные технологии САИТ-2005». М.: КОМКНИГА, 2005. Т.1. С. 188-193

4. Добрынин Д.А., Карпов В.Э., Мещерякова Т.В. и др. Адаптивный мобильный робот // Мобильные роботы и мехатронные системы: Мат-лы научн. школы-конф., Москва, 21-25 марта 2005. Ч. 1. М.: Изд-во Моск. ун-та, 2005. С. 137-143

5. Добрынин Д.А., Карпов В.Э. Моделирование некоторых форм адаптивного поведения интеллектуальных роботов // Информационные технологии и вычислительные системы. № 2. 2006. С. 45-56

6. Карпов В.Э. Эволюционное моделирование. Проблемы формы и содержания // Новости искусственного интеллекта. № 5. 2003.

7. Карпов В.Э. Об одной задаче управления мобильным роботом // Десятая национальная конференция по искусственному интеллекту с международным участием КИИ-2006 (25-28 сентября 2006 г., Обнинск): Тр. конф. В 3-т. Т.2. М: Физматлит, 2006. С. 719-727.

8. Пособие по применению промышленных роботов / Под ред. Кацухико Нода, пер.с япон. М.: Мир, 1975. 454 с.

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

10. Финн В.К. Искусственный интеллект: Идейная база и основной продукт, 9-я национ. конф. по искусственному интеллекту. Тр. конф. Т.1. М.: Физматлит, 2004. С.11-20.

11. Финн В.К. Об интеллектуальном анализе данных // Новости искусственного интеллекта. № 3. 2004.

12. Фогель Л., Оуэнс А., Уолш М. Искусственный интеллект и эволюционное моделирование. М.: Мир, 1969. 230 с.

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

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