УДК 681.51

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

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

Д.А. Добрынин1

В работе рассматриваются вопросы моделирования адаптивного поведения мобильного робота с помощью динамического ДСМ-метода. Миниробот создан в рамках проекта «Адаптант». 

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

Камнем преткновения при создании робототехнических систем стала проблема адаптации роботов к изменениям окружающей их среды. Оказалось, что даже при выполнении простейших действий – перемещений объектов с помощью манипуляторов, движении по местности колесных роботов и т. п. возникают большие трудности [Девянин, 2002]. Например, человек легко берет предмет произвольной формы и может перенести его с одного места на другое. Выполнение этой операции промышленным роботом–манипулятором на сегодняшний день представляет значительные трудности. Если манипулятор «не знает» заранее формы предмета, то такая простая операция во многих случаях просто не выполнима. Жесткие алгоритмы, которые использовались в системах управления роботов, оказались непригодны для решения задач в изменяющейся среде.

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

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

 Одним из мощных методов интеллектуального анализа данных является ДСМ-метод. Этот метод автоматического порождения гипотез получил свое название в честь известного британского философа и экономиста Джона Стюарта Милля. В 1843г. вышла его книга “A System of Logic Ratiocinative and Inductive”, в которой были изложены некоторые принципы индуктивной логики. Новый подход к индуктивной логике был сформулирован профессором В.К. Финном в начале 80-х гг [Финн, 1991].

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

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

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

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

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

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

E={ei}={(Xi,ui)},

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

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

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

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

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

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

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

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

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

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

В режиме обучения для формирования обучающих примеров может быть использовано два подхода:

- внешний алгоритм – так называемый «учитель»;

- решающее правило общего вида.

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

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

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

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

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

Решающее правило для конкретного набора значений входных датчиков определяет – целевое свойство (хорошо или плохо).

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

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

Эксперименты проводились на минироботе «Амур», созданном в Творческой научно-технической лаборатории Политехнического музея [Добрынин и др., 2005].

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

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

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

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

[Поспелов, 1988] Поспелов Г.С. Искусственный интеллект - основа новой информационной технологии. -М.:Наука, 1988.

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



1 125190, Москва, ул. Усиевича, д. 20, ВИНИТИ РАН, dobr@viniti.ru