Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Документ'
Российские музеи-заповедники – это уникальный тип учреждения культуры. Современный музей-заповедник определяется как учреждение культуры, созданное дл...полностью>>
'Документ'
) установленная или запроектированная система кондиционирования (при наличии, либо ранее) 1....полностью>>
'Документ'
Настоящая публичная оферта является предложением ТОО “G-INTERCOM” (далее – Компания) заключить Соглашение о предоставлении услуги определения координа...полностью>>
'Документ'
1.1 Цель — повышение эффективности деятельности по воспитанию законопослушных участников дорожного движения и предупреждению дорожно-транспортного тра...полностью>>

Главная > Документ

Сохрани ссылку в одной из сетей:
Информация о документе
Дата добавления:
Размер:
Доступные форматы для скачивания:

РАЗРАБОТКА МОДЕЛИ АДАПТИВНОГО ПОВЕДЕНИЯ АНИМАТА НА ОСНОВЕ СЕМАНТИЧЕСКОГО ВЕРОЯТНОСТНОГО ВЫВОДА

А. В. ДЕМИН

Институт систем информатики имени А. П. Ершова СО РАН, г. Новосибирск

Е. Е. ВИТЯЕВ

Институт математики СО РАН, г. Новосибирск

E-mail: vityaev@

1. ВВЕДЕНИЕ

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

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

2. ТЕОРИЯ ФУНКЦИОНАЛЬНЫХ СИСТЕМ

Архитектура предложенной нами системы управления основана на теории функциональных систем, разработанной в 1930-1970 гг. известным русским нейрофизиологом П.К. Анохиным [9]. Согласно этой теории единицей деятельности организма является функциональная система, формирующаяся для достижения полезных для организма результатов (например, удовлетворение потребностей). Организация функциональных систем при целенаправленном поведении осу­щест­вляется в соответствии с двумя правилами: последовательностью и иерархией результатов. Последовательность результатов выстраивается по принципу “доминанты”: доминирующая потребность возбуждает доминирующую функциональную систему и строит поведенческий акт, направленный на ее удовлетворение. По отношению к доминирующей функциональной системе все остальные функциональные системы выстраиваются в иерархию по принципу “иерархии результатов”: когда результат деятельности одной функциональной системы входит в качестве компонента в результат деятельности другой.

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

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

3. МОДЕЛЬ АНИМАТА

Приведем схему работы анимата (рис.1), реализующую схему функциональных систем [1–5]. Будем предполагать, что система управления аниматом функционирует в дискретном времени . Пусть анимат имеет некоторый набор сенсоров , характеризующих состояние внешней и внутренней среды, и набор возможных действий . Среди множества сенсоров выделим сенсор , который представляет информацию о совершенном действии. Считаем, что история деятельности анимата хранится в таблице данных , где t-я строка таблицы содержит показания сенсоров в момент времени t: , где – значения сенсоров в момент времени t. На множестве X определим множество предикатов , где сенсорные предикаты, определяющие некоторые условия на показания сенсоров в момент времени t; активирующие предикаты, показывающие, что в момент времени t было совершено действие .

Введем понятие предиката-цели, реализующего условие достижения цели в момент времени t.

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

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

Предположим, что в некоторый момент времени t функциональная система получила запрос на достижение цели . Тогда из множества закономерностей извлекаются все закономерности, условие которых выполнено в текущий момент времени t. Если условие закономерности содержит предикаты-подцели , то функциональная система отправляет запрос на достижение этих подцелей вниз по иерархии функциональных систем. Среди всех отобранных закономерностей выбирается та закономерность, которая с учетом вероятностей выполнения подцелей дает максимальную оценку f вероятности достижения цели. Оценка f закономерности вычисляется следующим образом: , где p – оценка вероятности данной закономерности, – оценка вероятностей достижения подцелей.


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

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

4. ОЦЕНКА РЕЗУЛЬТАТОВ ДЕЙСТВИЙ

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

Предположим, что функциональной системе в момент времени t0 была поставлена задача достичь цель , и после достижения цели в момент времени t1 был получен результат . Тогда оценки результатов действий , начиная с момента времени t0 и до момента времени t1, будут рассчитаны следующим образом: , где r – функция оценки качества полученного результата, , где ||…|| – мера близости между полученным результатом и поставленной целью .

5. ГЕНЕРАЦИЯ ПРАВИЛ

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

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

Данный метод основывается на следующем определении вероятностной закономерности, предложенном в работе [7].

Правило является закономерностью, если оно удовлетворяет следующим условиям

  1. .

Здесь p – оценка условной вероятности правила.

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

Алгоритм семантического вероятностного вывода.

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

  • На k-м (k > 1) шаге генерируется множество уточнений всех правил, созданных на предыдущем шаге. Т.е. для каждого правила , сгенерированного на (k-1)-м шаге, создается множество правил вида таких, что .

  • Проверяется, являются ли полученные правила закономерностями. Правила, не удовлетворяющие условиям закономерности, отсеиваются.

  • Алгоритм останавливается, когда больше невозможно уточнить ни одно правило,

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

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

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

6. ИЗВЛЕЧЕНИЕ ПОДЦЕЛЕЙ

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


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

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

  1. для любого правила такого, что , и для любого такого, что и , выполнено условие ;

  2. существуют правила и такие, что , и .

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

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

7. ОПИСАНИЕ ЭКСПЕРИМЕНТА

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

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

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

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

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

Изначальный набор предикатов анимата состоит из тридцати семи сенсорных предикатов: по четыре предиката на каждый сенсор s, информирующий анимат о состоянии окружающих его клеток: (s = «трава»), (s = «препятствие»), (s = «еда»), (s = «таблетка»), и один предикат, говорящий о наличие таблетки: («есть таблетка» = «да»). А также трех активирующих предикатов: (A = «шаг»), (A = «налево») и (A = «направо»).

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

8. РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТА

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

Для того чтобы оценить эффективность предлагаемой нами системы управления, в экспериментах также проводилось тестовое сравнение с системами, построенными на основании теории обучения с подкреплением (Reinforce­ment Learning), описанной в работах Р. Саттона и Э. Барто [10].

Для сравнения мы выбрали две системы управления, построенные на основе популярного алгоритма обучения с подкреплением Q-Learning. Суть алгоритма заключается в последовательном уточнении оценок суммарной величины награды , которую получит система, если в ситуации st она выполнит действие At, по формуле:

.

Первая из этих двух систем (Q-Lookup Table) основана на использовании таблицы, которая содержит Q-значения для всех возможных ситуаций и действий. Изначально эти значения таблицы заполняются случайным образом. В процессе работы в каждый такт времени система совершает действие и уточняет соответствующие Q-значения.

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

Тестовое сравнение проводилось на поле размером 25 на 25 клеток. Количество таблеток и еды на поле поддерживалось постоянным: по 100 объектов каждого типа. Весь период функционирования анимата был разбит на этапы по 1000 шагов (тактов). Оценивалось, какое количество еды соберет анимат с разными системами управления за каждый этап работы. Очевидно, что после того как система управления полностью обучится и достигнет своего оптимального поведения, анимат начнет собирать примерно одно и то же количество еды за один этап. Таким образом, можно оценить как эффективность каждой системы управления в целом, так и скорость ее обучения.

На рис. 3 представлены результаты тестового сравнения. Для каждой системы управления рассчитывались средние значения по результатам 20-и испытаний. Продолжительность каждого испытания составляла 100,000 шагов, за это время анимат должен был научиться эффективно решать поставленную задачу. Как видно на графике, система управления на основе семантического вероятностного вывода превосходит системы Reinforce­ment Learning как по скорости обучения, так и по качеству работы.

Системы управления на основе Reinforce­ment Learning в данном эксперименте показали плохую обучаемость и нестабильную работу. Основная проблема в работе этих систем была связана с тем, что они не могли за приемлемое время научиться стабильно адекватно реагировать на показания сенсоров о наличие таблеток и зачастую проходили мимо таблеток даже после 100,000 шагов обучения.


Дополнительные эксперименты показали, что система управления на основе нейронных сетей (Q-Neural Net) при увеличении длительности обучения до 300,000 – 500,000 шагов в некоторых случаях способна обучиться правильно реагировать на все показания сенсоров. Однако, по нашему мнению, столь длительный срок обучения является неприемлемым для адаптивной системы.

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

9. ВЫВОДЫ

Таким образом, результаты эксперимента показывают, что в условиях усложнения среды умение формировать и достигать подцели является принципиальным для эффективного достижения конечных целей. Несмотря на то что в данной модели адаптивной системы управления используется достаточно простой способ формирования подцелей, уже эта возможность дает значительные преимущества в обучении. Как видно из эксперимента, использование иерархии функциональных систем и алгоритма выявления подцелей позволяет предлагаемой нами системе управления эффективно обучаться и решать поставленную задачу. Существующие подходы, основанные на нейронных сетях и Reinforce­ment Learning, не могут автоматически выявлять подцели и поэтому значительно проигрывают в усложненных экспериментах.

Литература

  1. Витяев Е.Е. Целеполагание как принцип работы мозга // Модели когнитивных процессов. – Новосибирск, 1997. – Вып. 158: Вычислительные системы. – С. 9-52.

  2. Витяев Е.Е. Вероятностное прогнозирование и предсказание как принцип работы мозга // Измерение и модели когнитивных процессов. – Новосибирск, 1998. – Вып. 162: Вычислительные системы. – С. 14-40.

  3. Витяев Е.Е. Формальная модель работы мозга, основанная на принципе предсказания // Модели когнитивных процессов. – Новосибирск, 1998. – Вып. 164: Вычислительные системы. – С. 3-61.

  4. Михиенко Е.В., Витяев Е.Е. Моделирование работы функциональной системы // VI Всероссийская научно-техническая конференция «Нейроинформатика-2004». Сборник научных трудов. – М.: МИФИ, 2004. – Ч.2. – С. 124-129.

  5. Витяев Е.Е. Объяснение Теории Движений Н.А.Бернштейна // VII Всероссийская научно-техническая конференция «Нейроинформатика-2005». Сборник научных трудов. – М.: МИФИ, 2005. – Ч.1. – С. 234-240.

  6. Витяев Е.Е. Семантический подход к созданию баз знаний. Семантический вероятностный вывод наилучших для предсказания ПРОЛОГ-программ по вероятностной модели данных // Логика и семантическое программирование. – Новосибирск, 1992. – Вып. 146: Вычислительные системы. – С. 19-49.

  7. Витяев Е.Е. Метод обнаружения закономерностей и метод предсказания // Эмпирическое предсказание и распознавание образов. – Новосибирск, 1976. – Вып. 67: Вычислительные системы. – С. 54-68.

  8. Кендал М., Стюарт А. Статистические выводы и связи. – М.: Наука, 1973. – 899 с.

  9. Анохин П.К. Принципиальные вопросы общей теории функциональных систем // Принципы системной организации функций. – М.: Наука, 1973. – С. 5-61.

  10. Sutton R., Barto A. Reinforcement Learning: An Introduction. – Cambridge: MIT Press, 1998.



Похожие документы:

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

    Документ
    ... системы управления адаптацией Разработка программы адаптации Модель адаптации в изменяющихся ... культуре народа содержаться такие модели поведения, следование которым дает ... институциональные и прочие модели, которые являются адаптивными по отношению к ...
  2. Вучебном пособии освежены: технология основных направлений ра­боты практического психолога; методика работы психолога с детьми раз­ного возраста; технологии пс

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

    Документ
    ... за инстинктивным поведением животных и изучил изменчивость и адаптивное значение ряда инстинктов. Позже разработку этого ... английская школы этологии. Тинбергену принадлежит разработка иерархической модели поведения, которая в большей степени учитывала ...
  4. Фатхутдинов Р. А. Ф27 Разработка управленческого решения: Учебник для вузов. 2-е изд., доп

    Учебник
    ... интеллект как тип поведения человека — "умное поведение". Ядро интеллекта ... ЭВМ и графически. Для разработки модели прогнозиро­вания по первому ... системнос­тью, комплексностью, надежностью, адаптивностью, доступностью. Конкурентоспособность менеджера — ...
  5. Академия вэгу е. Ю. Бикметов, В. Д. Голиков, С. В. Егорышев организационное поведение: теория и практика Монография Уфа 2009

    Реферат
    ... неоднородность; разделяемость членами организации; адаптивность; социальность, т.е. создается ... Модели управления персоналом: исследования, разработка, внедрение Текст/Е.П. Померанцева. – М., 2006. 63. Раздорожный, А.А. Организационное поведение ...

Другие похожие документы..