Модель формирования адаптивного поведения автономных агентов

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

Научно-исследовательский институт системных исследований РАН, Москва

Модель формирования адаптивного поведения автономных агентов

Редько В.Г., д.ф.-м.н.

е-mail: vgredko@gmail.com,

Бесхлебнова Г.А., к.т.н.

е-mail: gab19@list.ru

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

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

ОПИСАНИЕ МОДЕЛИ

В модели предполагается, что популяция, состоящая из n агентов, эволюционирует в двумерной клеточной среде (мире). В любой клетке мира может находиться только один агент. У каждого агента есть свое направление «вперед». В некоторых клетках, число которых фиксировано, имеется пища агентов, причем величина порции пищи в каждой из этих клеток тоже фиксирована. Агент обладает ресурсом R(t). Ресурс агента увеличивается при съедании им пищи и уменьшается при выполнении им действий. Если ресурс агента R(t) в результате его действий становится меньше определенного порога R_min, то данный агент умирает. Агенты функционируют в дискретном времени, t = 0,1,…

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

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

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

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

Размер двумерного мира равен N_xN_y клеток (координаты клеток равны x = 1,…,N_x; y = 1,…,N_y). Клеточный мир замкнут: если агент, находящийся в клетке с координатой x = N_x , движется вправо, т.е. пересекает «границу мира», то он перемещается в клетку с координатой x = 1, аналогично происходит движение агента при пересечении других границ мира.

компьютерный модель агент автономный

Выбор действий агента обеспечивается имеющейся у него системой управления. Система управления агента представляет собой набор правил вида:

S_k(t) A_k(t), (1)

где S_k(t) - текущая ситуация, A_k(t) - действие, соответствующее этому правилу, k - номер правила. Каждое правило имеет свой вес W_k , веса правил модифицируются при обучении агента. Здесь S_k(t) есть вектор, компоненты которого принимают значения либо 0, либо 1. Значения 1 и 0 соответствуют наличию или отсутствию порции пищи или другого агента в определенной клетке в «поле зрения» агента. Поле зрения включает в себя четыре клетки: ту клетку, в которой агент находится, клетку впереди агента и клетки справа и слева от агента.

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

Обозначим через A^* намечаемое к выполнению действие. Это действие может быть выбрано либо в соответствии с имеющимися у агента правилами, либо случайным образом. Выбор действия агентом осуществляется следующим образом. Определяется текущая ситуация S(t) и формируется множество выделенных правил {R_S}, в это множество включаются те правила агента, для которых все компоненты вектора S_k(t) совпадают с компонентами вектора S(t), т.е. S_k(t) = S(t). Из правил, входящих в {R_S}, выбирается правило, для которого вес правила W_k максимален, и с вероятностью 1-е намечается для выполнения действие A^* = A_k(t), входящее в это правило, а с вероятностью е для выполнения намечается случайное действие A^*. Если правил, для которых S_k(t) = S(t), у данного агента нет, т.е. множество {R_S} в рассматриваемой ситуации оказывается пустым, то для выполнения намечается случайное действие A^*. Если при случайном выборе действия у рассматриваемого агента правило S(t) A^* отсутствует, то это новое правило добавляется к имеющимся, вес его полагается равным 0. В результате для выполнения намечается действие A^* и формируется новое правило (если у агента не было правила, соответствующего текущей ситуации S(t) и намеченному действию A^*). Далее намеченное действие A^* выполняется.

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

При обучении веса правил W_k модифицировались методом обучения с подкреплением [2]. Сигналами поощрения или наказания служили изменения ресурса агента. Изменение весов W_k при обучении происходило следующим образом. Менялся вес того правила, которое использовал агент в предыдущий такт времени t-1; этот вес изменялся в соответствии с изменением ресурса агента при переходе к такту t и весом правила, применяемого в такт t. Пусть вес правила, примененного в такт t1, равен W(t1), вес правила, применяемого в такт t, равен W(t), ресурс агента в эти такты времени равен R(t-1) и R(t), соответственно. Тогда изменение веса W(t-1) равно [2]:

ДW(t1) = б [R(t) R(t1) + гW(t) W(t1)], (2)

где б - параметр скорости обучения, г - дисконтный фактор; 0< б <<1, 0 < г < 1, 1г << 1. В результате обучения увеличивались веса правил, применение которых приводило к росту ресурса агента.

Процесс эволюции популяции агентов предполагает, что при делении агента ресурс родителя делится пополам между родителем и потомком. Логические правила потомка отличались от правил родителя малыми мутациями.

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

Моделирование проводилось в рамках полной описанной модели и в рамках упрощенной версии. В последнем случае изучалось обучение одного агента.

В случае полной версии модели рассматривалась популяция, состоящая из n =50 агентов, помещенная в мир из 100 клеток (N_x = N_y = 10), в котором в половине клеток была случайно распределена пища. В этом случае агент определял наличие/отсутствие пищи в 4-х клетках поля зрения и наличие/отсутствие другого агента в 3-х клетках поля зрения (впереди, справа, слева), т.е. каждая ситуация S(t) характеризовалась бинарным вектором, имеющим семь компонент. Следовательно, всего было 128 возможных ситуаций и 7 возможных действий; итого, имелось 896 возможных правил. Было продемонстрировано, что в полной модели в процессе эволюции и обучения агентов формировалось естественное их поведение: агенты преимущественно питались и часто отнимали ресурс друг у друга, изредка они выполняли и другие действия.

Пример расчета по полной модели иллюстрируется на рис.1, 2. Приведем параметры расчета. Порция пищи расположена в 50 клетках, прирост ресурса агента при съедании пищи был равен 1 (считаем ресурс безразмерным). Расход ресурса на каждое из действий, кроме удара, был равен 0.01, расход на удар составлял 0.02, при ударе ударяющий агент отнимал у ударяемого ресурс, равный 0.05. Параметры обучения с подкреплением были следующими: б = 0.1, г = 0.9. Применялся метод отжига: при t = 0 полагалось е = 1, со временем величина е по экспоненте уменьшалась до нуля, характерное время уменьшения е составляло 1000 тактов времени. Интенсивность мутаций была равна 0. Исходный ресурс агента (при t = 0) составлял R = 1. Минимальный ресурса агента R_min (при R < R_min агент умирал) был равен 0: R_min = 0.

Рис. 1 Зависимость среднего по популяции ресурса агента <R> от номера такта времени t

Рис. 2 Зависимость числа агентов Ne, выполняющих действие «питание», от номера такта времени t

На рис.1 представлена зависимость среднего по популяции ресурса агента <R> от номера такта времени t. Видно, что сначала (t < 2000) скорость роста <R> мала, так как логические правила еще не сформированы, и веса имеющихся правил еще не настроены. При t > 5000 скорость роста <R> практически постоянна; стохастичность на этом участке обусловлена случайным перемещением агентов по клеткам мира, а также случайным размещением новых порций пищи в ячейках мира при съедании части пищи агентами.

Видно, что при больших значениях t примерно 30% агентов (из общего числа агентов популяции, равного 50) выполняет каждый такт это действие. Наблюдаются сильные стохастические колебания числа Ne во времени. Примерно такая же зависимость от времени наблюдается и для числа агентов, выполняющих действие «нанесение удара»; число таких агентов при больших t равно примерно 15-20. При больших t число агентов, выполняющих действие «деление», мало и составляет около 1, а число агентов, выполняющих каждое из остальных действий (движение вперед, повороты направо/налево, отдых), равно примерно 3-5.

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

В упрощенных версиях модели анализировалась возможность формирования цепочек действий одним самообучающимся агентом. Рассматривалось два варианта формирования цепочек. В первом варианте агент мог выполнять только 4 действия: питаться, двигаться вперед и поворачиваться направо либо налево. Считалось, что имелась только одна расположенная в определенной клетке порция пищи. Агенту необходимо было сформировать заданную цепочку из одного, двух или трех действий. Например, трехзвенная цепочка включала следующие действия: 1) «поворот направо», 2) «перемещение вперед», 3) «питание»; при этом порция пищи исходно располагалась в клетке справа от той клетки, в которую исходно помещался агент. Основные параметры расчета были такими же, как и для полной модели. Метод отжига в этом варианте не использовался. Величина е, регулирующая случайный выбор действия агентом, была постоянной и составляла е = 0.2. Расчеты показали, что простые одно-, двух-, трехзвенные цепочки действий достаточно легко формировались в процессе самообучения агента.

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

Рис. 3 Зависимость ресурса R самообучающегося агента от номера такта времени t

Результаты моделирования для второго варианта оказались интересными, остановимся на них подробней. Так как агент был один, то каждая ситуация S(t) определялась только наличием/отсутствием пищи в 4-х клетках поля зрения и характеризовалась бинарным вектором, имеющим 4 компоненты. Всего было 16 возможных ситуаций и 5 возможных действий; итого, имелось 80 возможных правил. Интересно, во всех расчетах общее число правил, сформированных каждым агентом, было равно 80, То есть, в начале расчета, когда вероятность случайного выбора действия была высока, агент путем случайного поиска формировал все возможные правила. Однако веса этих правил менялись в процессе обучения, и к концу расчета, как изложено ниже, преимущественно использовались только 16 правил из 80 возможных.

В конце расчета были выделены логические правила, имеющие достаточно большой вес (превышающий 1). Оказалось, что для типичного расчета число таких выделенных правил с большими весами было равно 16, каждое из правил соответствовало одной из возможных ситуаций и выполняемому в этой ситуации действию. Именно эти правила применялись агентом. Этот набор правил можно рассматривать как обобщающие эвристики, формируемые агентом в процессе самообучения. Эти эвристики сводятся к следующему: 1) если порция пищи расположена в той же клетке, в которой находится агент, то нужно выполнить действие «питание» (таких правил было 8); 2) если порции пищи нет в той клетке, в которой находится агент, и есть пища в клетке впереди или справа/слева от агента, то нужно выполнить действие «перемещение вперед» или «поворот направо/налево», соответственно; если вообще не было пищи в поле зрения агента, то агент предпочитал действие «перемещение вперед». Перемещение вперед имело предпочтение перед поворотами, это можно объяснить тем, что при наличии порции пищи впереди, эта порция съедалась после двухзвенной цепочки действий, а при использовании поворотов порция могла съедаться только после трехзвенной цепочки действий. Интересно, что когда агент попадал в ситуацию «буриданова осла», т.е. видел пищу в двух клетках, справа и слева, то в одних расчетах он предпочитал поворачиваться направо, а в других - налево. Отметим, что действие «отдых» игнорировалось во всех ситуациях. В некоторых расчетах было небольшое число и других правил с весами, большими 1, тем не менее, свойства применяемых правил только изредка незначительно отличались от вышеописанных. Представленная на рис.3 зависимость R(t) соответствовала 16 выделенным правилам с большими весами: для каждой из возможных 16 ситуаций было свое правило, характер этих правил изложен выше. Следовательно, в процессе обучения агент самостоятельно формировал вполне естественные правила, определяющие «разумную» стратегию поведения.

НАПРАВЛЕНИЯ ДАЛЬНЕЙШЕЙ РАБОТЫ

Итак, построена и исследована компьютерная модель эволюционирующей популяции автономных самообучающихся агентов в двумерной клеточной среде. Система управления агентов основана на логических правилах вида «Если имеет место ситуация S(t), то следует выполнить действие A(t)». Особое внимание уделено процессам формирования новых правил, что важно в случае большого числа ситуаций, а также тогда, когда есть ситуации, неизвестные заранее.

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

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

Также отметим, что анализируемые методы формирования адаптивного поведения автономных агентов составляют определенный этап работ по проекту «Мозг анимата», направленному на изучение адаптивного поведения модельного организма (анимата) с несколькими естественными потребностями [9,10].

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

Литература

1. Редько В.Г. Перспективы моделирования когнитивной эволюции// Третья международная конференция по когнитивной науке: Тезисы докладов. - М.: Художественно-издательский центр, 2008. - Т.2. - С.576-577.

2. Sutton R.S., Barto A.G. Reinforcement Learning: an Introduction. - Cambridge MA: MIT Press, 1998.

3. Holland J.H., Holyoak K.J., Nisbett R.E., Thagard P. Induction: Processes of Inference, Learning, and Discovery. - Cambridge MA: MIT Press, 1986.

4. Редько В.Г., Прохоров Д.В. Нейросетевые адаптивные критики// Научная сессия МИФИ-2004. VI Всероссийская научно-техническая конференция «Нейроинформатика-2004». Сборник научных трудов. - М.: МИФИ, 2004. - Т.2. - С.77-84.

5. Витяев Е.Е. Извлечение знаний из данных. Компьютерное познание. Модели когнитивных процессов. - Новосибирск: НГУ, 2006.

6. Финн В.К. О машинно-ориентированной формализации правдоподобных рассуждений в стиле Ф. Бэкона - Д.С. Милля// Семиотика и информатика. - М.: ВИНИТИ, 1983. - № 20. - С.35-101.

7. Бонгард М.М., Лосев И.С., Смирнов М.С. Проект модели организации поведения «Животное»// Моделирование обучения и поведения. - М.: Наука, 1975. - С.152-171.

8. Непомнящих В.А., Попов Е.Е., Редько В.Г. Бионическая модель адаптивного поискового поведения// Известия РАН. Теория и системы управления. - 2008. - № 1. - С.85-93.

9. Анохин К.В., Бурцев М.С., Зарайская И.Ю., Лукашев А.О., Редько В.Г. Проект «Мозг анимата»: разработка модели адаптивного поведения на основе теории функциональных систем// Труды VIII-й Национальной конференции по искусственному интеллекту с международным участием. - М.: Физматлит, 2002. - Т.2. - С.781-789.

10. Red'ko V.G., Anokhin K.V. et al. Project “Animat Brain”: Designing the Animat Control System on the Basis of the Functional Systems Theory// Anticipatory Behavior in Adaptive Learning Systems: From Brains to Individual and Social Behavior. LNAI 4520/ Ed.by M.V Butz, O. Sigaud et al.- Berlin, Heidelberg: Springer Verlag, 2007. - P.94-107.

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