Лекция из учебного курса Стэнфордского университета (Stanford Online) AA228V посвящена продвинутым методам валидации систем, критичных к безопасности, с фокусом на поиск сценариев отказов (фальсификацию). Преподаватель подробно разбирает, как интеграция оценок вероятности в оптимизационные алгоритмы позволяет находить реалистичные критические ситуации, а также объясняет преимущества планирования на основе поиска по дереву перед глобальной оптимизацией. Переход от поиска по всему пространству параметров к итеративному построению траекторий открывает новые возможности для тестирования сложных автономных систем и робототехники.
📉 Интеграция вероятности в поиск отказов 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 (дискретный мир-сетка с препятствием), где агент периодически проскальзывает при движении. При стандартной минимизации робастности популяция траекторий напрямую движется к препятствию кратчайшим, но нереалистичным путем. В то же время функция с учетом правдоподобия находит сценарий, где агент долгое время следует штатному маршруту и срывается в аварию лишь в самый последний момент, что представляет гораздо большую угрозу в реальной эксплуатации.
🛠️ Инструменты оптимизации: локальный спуск против популяционных методов 10:35
После формализации целевой функции встает вопрос выбора алгоритма оптимизации. Для реализации этих процессов в программной среде используются готовые библиотеки на языке Julia, такие как Optim.jl или специализированный пакет JuMP. Оптимизатор работает как «черный ящик»: он принимает на вход целевую функцию и варьирует параметры (начальное состояние и шумы), выдавая на выходе наихудшую траекторию.
Существует два принципиально разных класса методов оптимизации:
- Методы локального спуска (Local descent methods): начинают поиск с базового начального приближения (например, нулевых шумов, когда система ведет себя идеально) и постепенно модифицируют параметры в сторону уменьшения функции. Главный риск — зависимость от начальной точки и высокая вероятность застревания в локальном минимуме вместо глобального.
- Популяционные методы (Population methods): одновременно поддерживают и итеративно развивают целое облако (популяцию) различных траекторий. Это позволяет охватить широкие области пространства параметров, избегать локальных тупиков и находить сразу несколько качественно разных режимов отказа (например, падение маятника как влево, так и вправо).
Внутри методов локального спуска выделяют алгоритмы первого и второго порядков, требующие вычисления градиентов (Gradient Descent, Adam, L-BFGS). Они обладают колоссальной мощностью и способны оптимизировать модели с миллионами параметров, но жестко требуют знания внутренней математики всей цепочки симуляции. Если система представлена в виде закрытого программного комплекса (Black-box model), взятие градиента становится невозможным.
В таких сценариях применяются методы нулевого порядка, или прямые методы (Hooke-Jeeves, Nelder-Mead). Для их работы достаточно лишь запускать симуляцию и получать итоговое значение функции для конкретных входных данных. Они прекрасно подходят для тестирования сложных промышленных симуляторов, внутреннее устройство которых скрыто от инженера.
🪵 Фальсификация через планирование: почему важно «сохраняться» 21:00
Новым концептуальным витком в валидации систем является фальсификация через планирование (falsification through planning). Преподаватель иллюстрирует ценность этого подхода бытовой аналогией: во время совместной удаленной работы на кухне компьютер ее мужа внезапно завис, уничтожив результаты за последние три часа из-за отсутствия промежуточных сохранений. Сама же лектор имеет привычку нажимать комбинацию клавиш Ctrl+S каждые пять секунд. Смысл периодического сохранения заключается в возможности вернуться в стабильную точку, если процесс пошел в неверном направлении, вместо того чтобы перестраивать все с нуля. Планирование в инженерии работает аналогично: гораздо проще строить опасную траекторию пошагово, чем пытаться оптимизировать ее целиком.
Прямая глобальная оптимизация траектории неизбежно сталкивается с проблемой проклятия размерности. Для простейшего перевернутого маятника при глубине симуляции всего в 21 шаг размерность пространства поиска составляет:
$$2 \text{ (начальное состояние)} + 2 \times 21 \text{ (возмущения)} = 44 \text{ измерения}$$
Для комплексных систем реального мира эта цифра легко доходит до сотен и тысяч измерений, что делает сквозную оптимизацию за один проход вычислительно неэффективной. Алгоритмы планирования успешно решают эту проблему, пошагово и итеративно достраивая дерево возможных путей развития событий.
🌳 Универсальный фреймворк поиска по дереву и алгоритм RRT 25:15
Структура данных в алгоритмах планирования представляет собой дерево, где каждый узел (node) жестко задает конкретное физическое состояние системы, а каждое ребро (edge) — это переход под воздействием определенного возмущения. Учебное пособие, на базе которого построен курс, предлагает единый универсальный фреймворк, сводящий любой алгоритм поиска по дереву всего к двум базовым шагам:
- Шаг выбора (Select): определение узла, который уже находится в дереве и заслуживает дальнейшего развития.
- Шаг расширения (Extend): генерация нового возмущения из этого узла для перехода в следующее состояние и добавления его в дерево.
Классическим примером реализации данного фреймворка являются быстро исследующие случайные деревья (RRT — Rapidly-exploring Random Trees), также называемые эвристическим поиском. В своей базовой (ванильной) версии алгоритм RRT работает по следующей схеме:
- В пространстве состояний случайным образом выбирается целевая точка (goal state).
- Для всех существующих узлов дерева рассчитывается расстояние (эвристика) до этой цели.
- Выбирается узел, находящийся ближе всего к случайной цели (минимальное значение эвристической функции).
- Из выбранного узла применяется случайное возмущение, порождающее новое состояние, которое прикрепляется к дереву.
Повторение этого процесса позволяет дереву эффективно заполнять свободное пространство траекторий. Однако случайный перебор возмущений из номинального распределения системы чаще всего уводит дерево в штатные, безопасные режимы работы, так как автоматика спроектирована возвращать систему в стабильное состояние. Для направленного поиска аварий стандартный RRT требует глубокой модернизации.
💡 Модификации RRT и альтернативные целевые функции 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) для непрерывных сред 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 отчетливо демонстрирует, как алгоритм, сохраняя широкую карту разведки, со временем формирует выраженные плотные и темные ветви траекторий, бьющие точно в самые уязвимые места валидируемой системы.
