# Стэнфордский курс AA228V: фальсификация систем через планирование и MCTS Источник: https://www.youtube.com/watch?v=162ToWqAMnc Канал: Stanford Online Опубликовано: 07.04.2025 --- Лекция из учебного курса Стэнфордского университета (Stanford Online) AA228V посвящена продвинутым методам валидации систем, критичных к безопасности, с фокусом на поиск сценариев отказов (фальсификацию). Преподаватель подробно разбирает, как интеграция оценок вероятности в оптимизационные алгоритмы позволяет находить реалистичные критические ситуации, а также объясняет преимущества планирования на основе поиска по дереву перед глобальной оптимизацией. Переход от поиска по всему пространству параметров к итеративному построению траекторий открывает новые возможности для тестирования сложных автономных систем и робототехники. ## 📉 Интеграция вероятности в поиск отказов [[JUMP:0:05]] В рамках системной валидации ключевой задачей является фальсификация — целенаправленный поиск траекторий и условий, приводящих к сбою. Математически эта задача формулируется как минимизация целевой функции, отражающей «близость к отказу», где переменными выступают начальное состояние системы и последовательность внешних возмущений. В качестве такой функции стандартно применяется метрика робастности (или сглаженная робастность для градиентных методов). Однако максимизация или минимизация исключительно робастности имеет серьезный недостаток: алгоритм может находить крайне маловероятные траектории. Например, в симуляции с перевернутым маятником система способна спровоцировать падение, последовательно генерируя редкие, практически невозможные в реальности шумы окружающей среды. Такой сценарий признается искусственным и малополезным для инженеров. Решением этой проблемы является явное включение фактора правдоподобия (likelihood) в целевую функцию. Чтобы оценить общую вероятность траектории $\tau$, необходимо перемножить плотность вероятности начального состояния и плотности вероятностей всех случайно выбранных возмущений на каждом шаге. Формула выглядит следующим образом: $$P(\tau) = P(s_0) \times \prod_{t=1}^{T} P(d_t | s_t, a_t, o_t)$$ Здесь полное возмущение $d_t$ может складываться из шума агента, среды и сенсоров. На практике прямое перемножение множества малых величин ведет к потере численной стабильности компьютера. Для предотвращения этой ошибки вычисления переводятся в логарифмическую форму (Log PDF), что позволяет заменить операцию умножения на сложение. Новая целевая функция разделяется на два базовых случая: * **Траектория привела к отказу** ($\tau \notin S$): функция возвращает отрицательное логарифмическое правдоподобие траектории. Алгоритм пытается минимизировать это значение, тем самым максимизируя вероятность данного сбоя. * **Траектория осталась успешной**: функция игнорирует вероятность и возвращает стандартную метрику робастности. Это заставляет алгоритм целенаправленно двигать систему ближе к опасной зоне. Эффективность данного подхода наглядно демонстрируется в симуляционной среде Grid World (дискретный мир-сетка с препятствием), где агент периодически проскальзывает при движении. При стандартной минимизации робастности популяция траекторий напрямую движется к препятствию кратчайшим, но нереалистичным путем. В то же время функция с учетом правдоподобия находит сценарий, где агент долгое время следует штатному маршруту и срывается в аварию лишь в самый последний момент, что представляет гораздо большую угрозу в реальной эксплуатации. ## 🛠️ Инструменты оптимизации: локальный спуск против популяционных методов [[JUMP:10:35]] После формализации целевой функции встает вопрос выбора алгоритма оптимизации. Для реализации этих процессов в программной среде используются готовые библиотеки на языке Julia, такие как `Optim.jl` или специализированный пакет `JuMP`. Оптимизатор работает как «черный ящик»: он принимает на вход целевую функцию и варьирует параметры (начальное состояние и шумы), выдавая на выходе наихудшую траекторию. Существует два принципиально разных класса методов оптимизации: 1. **Методы локального спуска (Local descent methods)**: начинают поиск с базового начального приближения (например, нулевых шумов, когда система ведет себя идеально) и постепенно модифицируют параметры в сторону уменьшения функции. Главный риск — зависимость от начальной точки и высокая вероятность застревания в локальном минимуме вместо глобального. 2. **Популяционные методы (Population methods)**: одновременно поддерживают и итеративно развивают целое облако (популяцию) различных траекторий. Это позволяет охватить широкие области пространства параметров, избегать локальных тупиков и находить сразу несколько качественно разных режимов отказа (например, падение маятника как влево, так и вправо). Внутри методов локального спуска выделяют алгоритмы первого и второго порядков, требующие вычисления градиентов (Gradient Descent, Adam, L-BFGS). Они обладают колоссальной мощностью и способны оптимизировать модели с миллионами параметров, но жестко требуют знания внутренней математики всей цепочки симуляции. Если система представлена в виде закрытого программного комплекса (Black-box model), взятие градиента становится невозможным. В таких сценариях применяются методы нулевого порядка, или прямые методы (Hooke-Jeeves, Nelder-Mead). Для их работы достаточно лишь запускать симуляцию и получать итоговое значение функции для конкретных входных данных. Они прекрасно подходят для тестирования сложных промышленных симуляторов, внутреннее устройство которых скрыто от инженера. ## 🪵 Фальсификация через планирование: почему важно «сохраняться» [[JUMP:21:00]] Новым концептуальным витком в валидации систем является фальсификация через планирование (falsification through planning). Преподаватель иллюстрирует ценность этого подхода бытовой аналогией: во время совместной удаленной работы на кухне компьютер ее мужа внезапно завис, уничтожив результаты за последние три часа из-за отсутствия промежуточных сохранений. Сама же лектор имеет привычку нажимать комбинацию клавиш `Ctrl+S` каждые пять секунд. Смысл периодического сохранения заключается в возможности вернуться в стабильную точку, если процесс пошел в неверном направлении, вместо того чтобы перестраивать все с нуля. Планирование в инженерии работает аналогично: гораздо проще строить опасную траекторию пошагово, чем пытаться оптимизировать ее целиком. Прямая глобальная оптимизация траектории неизбежно сталкивается с проблемой проклятия размерности. Для простейшего перевернутого маятника при глубине симуляции всего в 21 шаг размерность пространства поиска составляет: $$2 \text{ (начальное состояние)} + 2 \times 21 \text{ (возмущения)} = 44 \text{ измерения}$$ Для комплексных систем реального мира эта цифра легко доходит до сотен и тысяч измерений, что делает сквозную оптимизацию за один проход вычислительно неэффективной. Алгоритмы планирования успешно решают эту проблему, пошагово и итеративно достраивая дерево возможных путей развития событий. ## 🌳 Универсальный фреймворк поиска по дереву и алгоритм RRT [[JUMP:25:15]] Структура данных в алгоритмах планирования представляет собой дерево, где каждый узел (node) жестко задает конкретное физическое состояние системы, а каждое ребро (edge) — это переход под воздействием определенного возмущения. Учебное пособие, на базе которого построен курс, предлагает единый универсальный фреймворк, сводящий любой алгоритм поиска по дереву всего к двум базовым шагам: 1. **Шаг выбора (Select)**: определение узла, который уже находится в дереве и заслуживает дальнейшего развития. 2. **Шаг расширения (Extend)**: генерация нового возмущения из этого узла для перехода в следующее состояние и добавления его в дерево. Классическим примером реализации данного фреймворка являются быстро исследующие случайные деревья (RRT — Rapidly-exploring Random Trees), также называемые эвристическим поиском. В своей базовой (ванильной) версии алгоритм RRT работает по следующей схеме: * В пространстве состояний случайным образом выбирается целевая точка (goal state). * Для всех существующих узлов дерева рассчитывается расстояние (эвристика) до этой цели. * Выбирается узел, находящийся ближе всего к случайной цели (минимальное значение эвристической функции). * Из выбранного узла применяется случайное возмущение, порождающее новое состояние, которое прикрепляется к дереву. Повторение этого процесса позволяет дереву эффективно заполнять свободное пространство траекторий. Однако случайный перебор возмущений из номинального распределения системы чаще всего уводит дерево в штатные, безопасные режимы работы, так как автоматика спроектирована возвращать систему в стабильное состояние. Для направленного поиска аварий стандартный RRT требует глубокой модернизации. ## 💡 Модификации RRT и альтернативные целевые функции [[JUMP:39:04]] Чтобы заставить RRT эффективно искать критические сбои, в оба шага фреймворка вносятся изменения: * **Модификация шага Select**: вместо случайного выбора целевой точки по всему пространству, цели генерируются исключительно внутри известной зоны отказа (например, внутри геометрических границ препятствия). * **Модификация шага Extend**: вместо генерации одного случайного шума алгоритм временно сэмплирует множество потенциальных возмущений и оставляет то, которое сильнее всего продвигает систему к заданной зоне сбоя. Для оценки качества покрытия пространства и своевременной остановки алгоритма применяются строгие геометрические метрики, такие как дисперсия и звездное расхождение (star discrepancy). Стабилизация (выход на плато) этих показателей во времени служит сигналом к успешному завершению поиска. При поиске траекторий с конкретными свойствами функция оценки узла в шаге `Select` заменяется на полноценную двухкомпонентную стоимость: $$Cost = Current\ Cost + Estimated\ Cost\text{-}to\text{-}go$$ Поскольку истинная «стоимость оставшегося пути» (Cost-to-go) до момента решения задачи неизвестна, ее оценивают с помощью эвристической функции $h$. В зависимости от инженерной задачи формулируются различные типы стоимости: * **Кратчайший путь к отказу**: текущая стоимость — это физическая длина траектории от корня до узла; оставшаяся стоимость — евклидово расстояние до цели по прямой. * **Наиболее вероятный отказ**: текущая стоимость — это накопленное отрицательное логарифмическое правдоподобие шумов; оставшаяся стоимость оценивается через эвристические прокси (например, расстояние до препятствия, поскольку более короткие траектории обычно требуют меньшего числа аномальных шумов и статистически более вероятны). При этом к логарифму правдоподобия обязательно добавляется смещающая константа $C$, гарантирующая строго положительные значения стоимости, что критически важно для предотвращения зацикливания алгоритма. Если используемая эвристика является допустимой (admissible — то есть гарантированно никогда не переоценивает реальную стоимость достижения цели), а пространства состояний и шумов дискретны, то данный алгоритм планирования математически трансформируется в классический поиск $A^*$ (A-star). Это дает строгую гарантию нахождения абсолютно наихудшего или максимально вероятного сценария аварии. ## 🎰 Поиск по дереву Монте-Карло (MCTS) для непрерывных сред [[JUMP:59:09]] Поиск по дереву Монте-Карло (MCTS) представляет собой еще более мощный метод планирования, который на явном математическом уровне балансирует между исследованием новых зон (exploration) и эксплуатацией уже найденных перспективных путей (exploitation). Каждый узел дерева MCTS хранит две переменные: оценку стоимости $Q$ (которую в контексте поиска отказов стремятся минимизировать) и счетчик посещений данного узла $n$. Поскольку реальные физические системы функционируют в непрерывном пространстве, стандартный дискретный MCTS неприменим — дерево рискует бесконечно плодить уникальные дочерние узлы в одной точке, не продвигаясь вглубь. Для обхода этого ограничения используется метод прогрессивного расширения (progressive widening). На шаге `Select` при нахождении в узле проверяется строгое условие: $$\text{Количество детей} \le k \cdot n^\alpha$$ Параметры $k$ и $\alpha$ являются настраиваемыми гиперпараметрами (типичные базовые значения: $k = 2$, $\alpha = 0.5$). Если неравенство выполняется, алгоритм принудительно останавливает спуск по дереву и переходит к шагу `Extend`, создавая нового «ребенка» посредством генерации свежего возмущения. Если же детей у узла уже достаточно, алгоритм спускается глубже к тому дочернему узлу, который минимизирует нижнюю доверительную границу (LCB — Lower Confidence Bound): $$LCB = Q_{child} - c \cdot \sqrt{\frac{\ln n_{parent}}{n_{child}}}$$ Компонент $Q_{child}$ отвечает за эксплуатацию (выбор путей, где ранее уже были зафиксированы опасные низкие робастности), а радикальное выражение с коэффициентом исследования $c$ выдает крупный «бонус исследования» тем узлам, которые посещались редко, стимулируя проверку альтернативных маршрутов. После выбора узла и добавления нового состояния ($n=1$), его стартовая стоимость $Q$ оценивается через серию быстрых случайных симуляций до самого конца (rollouts). Полученная оценка робастности транслируется обратно вверх по всей цепочке предков до самого корня дерева (обратное распространение — backpropagation). На каждом уровне счетчики посещений $n$ увеличиваются на единицу, а значения $Q$ пересчитываются через скользящее среднее. Визуализация итогового дерева MCTS отчетливо демонстрирует, как алгоритм, сохраняя широкую карту разведки, со временем формирует выраженные плотные и темные ветви траекторий, бьющие точно в самые уязвимые места валидируемой системы.