УДК 681.51

ОБ ОДНОЙ ЗАДАЧЕ УПРАВЛЕНИЯ МОБИЛЬНЫМ РОБОТОМ

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

В.Э. Карпов [1]

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

Введение

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

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

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

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

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

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

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

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

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

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

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

Одной из наиболее эффективных и простых моделей условно-рефлекторного поведения является вероятностный автомат [Цетлин, 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. Начальное положение робота на полигоне

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

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

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

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

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

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

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

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

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

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

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

Как известно [Фогель, 1969], одной из основных задач эволюционного моделирования является задача предсказания последовательности символов. Предположим, что в результате процесса эволюции был создан предсказатель P, определяющий значение входного вектора X в момент времени t+1 на основе своей предыстории и значения управляющего вектора:

Xt+1 = P(Ut, Xt, Xt-1,…Xt-n) (1)

Здесь Xt – значение вектора входных сигналов (сигналов датчиков) в момент времени t, а Ut – это значение вектора управления робота, определяющего действие (или комплекс действий) робота в тот же момент времени.

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

f: X® {0,1} (2)

определяющей положение робота относительно полосы. Например, следующим образом:

(3)

Таким образом, мы приходим к задаче определения такого управления U, что f(X)=1, т.е.:

Ut: f(Xt+1) = f(P(Uit, Xt,Xt-1,…))=1  (4)

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

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

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

S = {ji }, ji=(<X, U>, f(X)) (5)

где X – вектор входных сигналов, U – вектор управления, f(X) – значение оценочной функции.

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

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

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

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

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

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

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

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

Рис. 5. Процесс эволюции

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

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

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

x:f1/p1, f2/p2

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

3: 0/0.5, 1/05

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

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

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

1.        Считать состояние датчиков в текущий момент времени Xt;

2.        Для все возможных вариантов управления Ui  цикл:

·   Сформировать входную последовательность eti={(<Xt, Ui>)}

·   Подать на вход автомата и оценить реакцию fi
fi = A(eti)

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

3.        КонецЦикла

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

5.        Перейти к П.1.

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

Заключение

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

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

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

Список литературы

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

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

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

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

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

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

 

[1] 113054, Москва, ул.Бахрушина, 18, стр.3, НИИ Информационных технологий, karpov_ve@mail.ru