Семинар Отдела динамических систем
14 мая 1999 г., 15⁰⁰

Специализированные системы визуализации для некоторых классов дифференциальных игр

Пыхтеев О.А.

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

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

Для восстановления поверхности был выбран метод триангуляции. Суть специализированного алгоритма заключается в следующем. На фронтах выделяются точки, в которых линии резко изгибаются. Этими точками фронты разбиваются на несколько компонент так, что в пределах одной компоненты нет резких изгибов. Затем находится соответствие между компонентами на соседних фронтах. Между соответствующими компонентами производится триангуляция. Алгоритм позволяет выделять места, где нарушается гладкость и непрерывность графика функции цены. Закраска треугольников производится методом Гуро. Система включает в себя средства для изменения ракурса, "материала" поверхности, положения источника света. Имеется возможность плавного изменения цвета поверхности в зависимости от значения функции. На рис. 1 показано изображение графика функции цены для дифференциальной игры "шофер-убийца". В горизонтальной плоскости даны фронты, просчитанные по алгоритму, разработанному В.С.Пацко и В.Л.Туровой.

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

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

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

Рис. 1: График функции цены для игры "шофер-убийца"