Моделирование поведения взаимодействующих агентов в среде с ограничениями Юданов А.А., студент 525 гр. Научный руководитель: к.ф.-м.н.

Задача моделирования
Цель моделирования – классификация режимов работы моделируемой системы
(x1, x2,……….)
(x1, x2,……….)
(x1, x2,……….)
Поведение людей
(Perceptrak)
Видео (IPS)
Распознавание речи
(ViaVoice IBM)
система
компоненты
Сложная система – система, состоящая из компонент, взаимодействием которых нельзя пренебречь
Моделирование - приближение процессов работы системы более простыми процессами.

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

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

Подходы
Нейронные сети
+ Восстанавливают сложные разделительные поверхности
Тяжело обучаемы
Шаблоны
+ Простой процесс добавления/изъятия
Охватывает очень частную закономерность
Конечные автоматы
+ Более общие, чем шаблоны
Охватывают частные закономерности
Скрытые Марковские модели (СММ)
+ Хорошая модель времени
Структурные ограничения зависимостей переменных

Описание модели
Каждому агенту соответствует своя СММ
Состояние агента двухуровневое
скрытое
наблюдаемое
Наблюдаемое состояние зависит только от скрытого
Вероятность смены скрытого состояния каждого агента зависит от предыдущих скрытых состояний всех агентов
Параметры модели
структурные (количество игроков)
свободные (вероятность изменения тактики)

Структура модели
1) Возьмем СММ для каждого агента
• Наборы состояний скрытых и наблюдаемых – дискретны
• Вероятности переходов для скрытых состояний каждого агента записываются в виде k+1 мерной матрицы A
• Вероятности наблюдаемых состояний записываются в 2-х мерной матрице B
2) Добавим вероятностные зависимости для последовательности скрытых состояний
Получаем систему СММ (ССММ)
А
B
tin
bin
Для двух агентов:

Обучение модели: по обучающим выборкам и структурным параметрам модели найти свободные параметры модели
Анализ хода игры: по заданным всем параметрам модели и выборке найти наиболее вероятную последовательность значений скрытых переменных (разметка выборки)
Основные задачи для модели

Схема программной системы
Среда
переводчик
агент
агент
агент
агент
Пред-
обработка
Система
моделирования
Системо-зависимая часть
общая часть
ССММ
Значения
скрытых переменных
Наиболее вероятные
наблюдения
Язык С, система matlab

Эксперименты
Тестовая игра:
- 2 игрока
- 20 возможных событий
- 6581 пар элементов выборки
- 2 значения скрытых переменных
Верхние графики – изменения поведения двух агентов.
Синий и розовый графики – изменения скрытых состояний агентов.
Голубой график – ручная экспертная разметка сигнала.
Нижний красный – разметка с помощью СММ
Код события
шаг
Quake 3

Эксперименты
Код события
шаг
Мера точности:
Нормированная на длину последовательности сумма совпадающих разметок по всем временным шагам
Точность:
ССММ 78-87%
независимые СММ 75%
атака
атака
поиск
Ошибки

Основные результаты
Разработана статистическая модель одного класса многопользовательских игр
Предложены и обоснованы алгоритмы и формулы для работы с моделью
Создана программная система, реализующая модель и алгоритмы работы с моделью; cистема испытана на игре Quake 3
Апробация: результаты работы опубликованы в тезисах конференции «Ломоносов-2010»

Спасибо за внимание!
All your base are belong to us !!