Размышления на тему процедурной анимации
Автор: Игорь Галай
Весьма абстрактные (и малопрактичные:) размышления. Задача состоит в том, что бы научить виртуальных существ самостоятельно выполнять хоть сколько-нибудь сложные двигательные действия. Самостоятельно, в смысле, динамически, без предрассчитаной анимации. Хорошо бы научить их ходить и бегать.
Модель
В виртуальном мире соблюдаются законы физики, симуляцией Лагранжевой механики (или как это там называется). Короче, есть физический движок способный симулировать твердые тела с разнообразными связями. Тогда можно сконструировать существо из нескольких простых тел, связав их джоинтами. Модель гуманоида может выглядеть так:
Кружок – балл-сокет джоинт, прямоугольник – хиндж-джоинт. Легко видеть, что наша модель слегка упрощена. Но как отправная точка – сойдет.
Имеем n сочленений. Каждое сочленение имеет текущие углы сгиба ai.
A := (ai)
Скорости сгиба – wi.
W := (wi)
Пусть Pc – позиция «центральной» части тела, Vc – скорость этой части. Тогда положение существа в пространстве P однозначно определяется:
P := (Pc, A)
Скорость существа V:
V := (Vc, W)
Введем вектор, характеризующий состояние среды в каждый момент времени - S(t).
Работа мышц тела заключается в создании сил, сгибающих или разгибающих соседние части. Можно придумать несколько подходов к моделированию таких сил, внимания на этом заострять не будем. Существо, в каждый момент времени, оценивает свою позицию, скорость, состояние среды, и, исходя из этих данных, прикладывает к каждому сочленению некоторую силу:
fi: (P, V, S) -> R1,2
F := (fi)
Величины F ограничены силой мышц. Причем ограничения для разных направлений координат fi различаются:
F < Bmin, F > Bmax
Прикладывая силы в различных сочленениях, существо движется. Оно использует реакции опор, чтобы перемещаться. Таким образом, приняв начальную скорость за начало отсчета:
V(t) = ∫G(F, V, P, S)dt (интеграл по времени)
Где G – некое отображение соответствующих пространств. Оно имеет весьма сложную структуру, с разрывами. Построением этого отображения, в сущности, и занимается физический движок.
Приняв начальное положение тела за начало отсчета:
P(t) = ∫Vdt
Получили рекурсивного монcтра казуистики:
P(t) = ∫∫G{ F[V(s), P(s), S(s)], V(s), P(s), S(s) } dsdt
Как-либо проанализировать его я затрудняюсь. Тем не менее, мы вполне можем решать это чудо численно, просто запустив цикл симуляции. Каждый вид движения характеризуется отображением F и только им. Естественным образом полагаем, что F задано на компакте, и непрерывно на нем (но имеет резкие скачки в тех местах, где существо начинает применять силы).
Напрягая мускулы
Наверно, гуманоид ходит на двух ногах неспроста. Должно быть, это самый эффективный, с точки зрения энергорасходов, способ передвижения, предусмотренный структурой тела. Для других существ более эффективным может оказаться другой способ. Если задаться целью смоделировать ходьбу гуманоида, логично потребовать от него придти в определенную точку, с минимальными затратами. Но прогулки еще слишком опасны для неокрепшего организма:)
Имеем ровный пол, силу тяжести и небольшие случайные силы, периодически действующие на существо. Все эти данные заключены в векторе состояния среды S(t). Пусть в начальный момент существо касается пола только ступнями. Подумаем над тем как заставить его сохранять равновесие. Существо должно свести свое движение к минимуму, стоя на двух ногах. Логично перейти от минимизации движения к минимизации энергозатрат. Положив:
С(t) := ||∫Fdt|| (интеграл по времени)
Получаем:
C(Δt) -> min
P(t) ∈ P'
Где P' – подпространство, в котором существо может касаться пола только ступнями. В принципе его можно сузить, что бы запретить прыжки.
Будем симулировать небольшой временной промежуток, скажем 10 секунд. В конце получим значение функционала C. То есть симуляция этого промежутка является элементарным тестом. Тест считается пройденным, если удовлетворены условия на P. Наша задача - построить «хорошее» отображение F. В том смысле, что оно удовлетворяет условию на P и дает значение функционала C, в конечный момент, достаточно малым.
Строить F сеточно – абсурд.
Заметим, что fi являются элементами гильбертового пространства непрерывных, на компакте, функций, с интегралом от произведения двух элементов в качестве скалярного произведения. Следовательно, fi являются линейными комбинациями из любого ортогонального базиса (uj) (вообще то, базис должен быть ортонормированным, но наш случай к этому сводится). Отсюда F может быть приближено рядом Фурье:
F = (∑kjuj)
Где (uj) - функциональный базис, (kj) - коэффициенты разложения.
В качестве (uj) может быть взята любая ортогональная система. В принципе, подойдет и любая другая система со всюду плотной линейной оболочкой, но тогда это уже нельзя назвать рядом Фурье. Навскидку для одномерного случая: алгебраический базис - (xn-1). Выбрав некоторый базис, возьмем N членов из него. Попробуем подобрать коэффициенты, минимизюрующие C. Таким образом, мы приблизим проекцию F на линейную оболочку взятых членов Fpr (которая сама по себе является аппроксимацией F). Возможно, нам повезет и F попадет в оболочку, или будет неподалеку. А возможно и нет. Казалось бы логично брать первые члены базиса. Есть вероятность, что они задают общую форму функции, а последующие лишь уточняют рельеф.
Итак, мы выбрали N членов базиса. Как же искать коэффициенты? Искать градиент функционала по ним – сомнительная затея. Можно попробовать методы покоординатного спуска, то есть пробовать небольшие изменения отдельных коэффициентов, прогонять элементарный тест, и оставлять изменения в случае улучшения. Или делать пробные приращения в случайную сторону. Методы спуска страдают от локальных минимумов. Из методов поиска глобального минимума сразу приходят на ум генетические алгоритмы. В ходе эволюции можно случайно заменять элементы базиса. Таким образом, искомое подпространство будет сдвигаться. Методы спуска могут быть использованы для дополнительного уточнения решения.
Рассмотрим теперь нейронные сети, как альтернативу разложению в ряд. Нижеизложенное – из "Горбань А. Н., Обобщенная аппроксимационная теорема и вычислительные возможности нейронных сетей" (дзынь). Пусть имеем линейное подпространство Е пространства непрерывных функций С, замкнутое относительно произвольной нелинейной непрерывной функции f(R). Тогда E совпадает с С.
Отсюда, F может быть построено с помощью нейронной сети прямого распространения, со входом (V, P, S) и выходом – величинами сил fi в сочленениях. Сеть должна допускать произвольное количество сумматоров, с произвольными весами и произвольное количество нелинейных преобразователей (с одной и той же функцией). Если элементы могут быть соединены произвольным образом, то существует подходящая схема без циклов. Можно построить слоистую структуру, но допускающую «сквозные» соединения через множество слоев. Или строго слоистую «классическую» схему, но с возможностью отключать преобразователи. В принципе, абсолютно любая схема может дать некую аппроксимацию.
Подбор коэффициентов сумматоров и структуры сети – задача для алгоритмов поиска. Могут быть применены те, что рассмотренные выше.
Еще немного бессмысленно-общих мыслей
Итак, теоретически, можно натаскать существо на определенный вид движения. Можно, например, заставить его бежать в произвольную точку Ptarg, минимизируя время до прибытия в некоторую ее окрестность:
Δt -> min
||P(Δt) - Ptarg|| < e
Возможны более хитроумные условия. В итоге обучения, получим набор рефлекторных паттернов, легко подменяемых по требованию вышестоящих механизмов. Например, пусть гуманоиду нужно подойти к двери и открыть ее. Сначала включается паттерн "придти в окрестность точки(двери)". Когда дверная ручка попадает в зону досягаемости, включается паттерн "воздействовать ладонью на объект", с целью повернуть ручку. И так далее. Описанная схема уже будет походить на некий базовый «спинномозговой» аппарат.
Хотя, реализация все таки видится мне весьма туманно:)
UPD: наткнулся на топик с обсуждением и реализацией связки нейронная сеть + генетический алгоритм.
#Animation, #approximation, #физика
11 июня 2010