В своем новом обзоре исследователь искусственного интеллекта Янник Килчер (Yannic Kilcher) подробно разбирает научную работу «Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning». В центре внимания находится инновационный алгоритм планирования, который рекурсивно разбивает сложные пространственные задачи на подзадачи с помощью глубокого обучения. Этот подход предлагает альтернативу классическим методам поиска по дереву, значительно оптимизируя вычисления в целеориентированных средах.
🧭 Что такое планирование и почему классический поиск заходит в тупик
<a class="ts" data-seconds="39" href="#t=39" title="Смотреть с 0:39" aria-label="Смотреть с 0:39"><svg viewBox="0 0 24 24" width="14" height="14" fill="currentColor" aria-hidden="true"><path d="M8 5v14l11-7z"/></svg></a>
Традиционное обучение с подкреплением строится на методе проб и ошибок, когда агент совершает действия вслепую, сталкивается со стенами, получает за это штрафы и пробует снова. Планирование же позволяет «думать наперед» и просчитывать последствия шагов в уме, используя внутреннюю модель среды, как это реализовано в знаменитых системах AlphaGo или AlphaZero. Когда перед агентом стоит задача дойти из начальной точки в целевую через лабиринт комнат, процесс планирования неизбежно превращается в построение дерева поиска.
Однако ключевая проблема классического поиска в ширину или глубину заключается в экспоненциальном взрыве сложности. Если путь к цели имеет длину в $D$ шагов, а на каждом этапе доступно 4 направления движения, то дерево разрастется до $4^D$ узлов, что делает полный перебор физически невозможным.
Для решения этой проблемы традиционно применяются эвристики, такие как в алгоритме A*, который отдает приоритет узлам, приближающим агента к цели по евклидову расстоянию ($L_2$-дистанции). Классический алгоритм Monte Carlo Tree Search (MCTS) работает схожим образом: он останавливает глубокий перебор на определенном этапе и оценивает перспективность ветки с помощью эвристической функции ценности.
✂️ Разделяй и властвуй: радикальная идея DC-MCTS
<a class="ts" data-seconds="326" href="#t=326" title="Смотреть с 5:26" aria-label="Смотреть с 5:26"><svg viewBox="0 0 24 24" width="14" height="14" fill="currentColor" aria-hidden="true"><path d="M8 5v14l11-7z"/></svg></a>
Суть предлагаемого метода Divide-and-Conquer Monte Carlo Tree Search заключается в фундаментальном изменении геометрии поиска. Представьте, что у агента есть Оракул, способный гарантировать, что на пути к финишу маршрут обязательно пройдет через определенную промежуточную точку в самом центре лабиринта.
В таком случае задача агента кардинально упрощается. Вместо поиска единого длинного пути протяженностью $D$ шагов, он начинает параллельно искать два независимых полумаршрута длиной $D/2$ каждый: от старта до промежуточной точки и от нее до финальной цели. С математической точки зрения это дает колоссальный выигрыш: вместо построения огромного дерева из $4^D$ узлов, алгоритм строит два дерева размером $4^{D/2}$. Сумма этих двух поддеревьев ничтожно мала по сравнению с исходным массивом вариантов, что означает эффективное разделение сложной задачи на две более простые подзадачи.
Новый алгоритм применяет эту стратегию рекурсивно. Он предлагает среднюю точку, делит задачу пополам, а затем для каждой из половин снова ищет промежуточное состояние, пока подзадачи не сократятся до масштаба одного шага.
Здесь кроется важный концептуальный нюанс, который легко может запутать исследователя: алгоритм DC-MCTS осуществляет поиск не по действиям, а по планам. Сам план представляет собой дерево, но процесс поиска наилучшего плана формирует мета-дерево, где каждый узел — это целая незавершенная траектория или подзадача. Процедура обхода (traverse) раз за разом вызывает функцию выбора (select) для поиска оптимальных промежуточных узлов деления.
🕸️ Подвох алгоритма: размен глубины на ширину
<a class="ts" data-seconds="797" href="#t=797" title="Смотреть с 13:17" aria-label="Смотреть с 13:17"><svg viewBox="0 0 24 24" width="14" height="14" fill="currentColor" aria-hidden="true"><path d="M8 5v14l11-7z"/></svg></a>
Несмотря на кажущуюся элегантность, предложенный метод не является магической таблеткой от всех вычислительных проблем. Главное различие между стандартным Monte Carlo Tree Search и его версией «разделяй и властвуй» кроется в структуре ветвления.
В классическом MCTS агент выбирает следующее конкретное действие, из-за чего дерево имеет фиксированную и небольшую ширину (например, 4 доступных направления), но огромную глубину. В DC-MCTS поиск ведется не по действиям, а по лучшим способам разделения задачи. Каждая свободная клетка на карте гипотетически является кандидатом на роль промежуточного состояния.
Это приводит к тому, что на первом же шаге у алгоритма возникает не 4, а сотни потенциальных вариантов деления, что делает структуру поиска невероятно широкой. Каждое выбранное промежуточное состояние требует аналогичного масштабного ветвления для своих подзадач. Таким образом, алгоритм осуществляет прямой размен: глубина дерева уменьшается, но его ширина увеличивается до колоссальных масштабов. Если развернуть дерево DC-MCTS полностью, оно будет содержать ровно столько же узлов, сколько и дерево классического MCTS.
🧠 Нейросети как оракулы и обучение через призму заднего ума
<a class="ts" data-seconds="1071" href="#t=1071" title="Смотреть с 17:51" aria-label="Смотреть с 17:51"><svg viewBox="0 0 24 24" width="14" height="14" fill="currentColor" aria-hidden="true"><path d="M8 5v14l11-7z"/></svg></a>
Эффективность алгоритма полностью зависит от функции выбора — способности точно определять именно те промежуточные состояния, через которые агент действительно пройдет с высокой вероятностью. Чтобы ограничить чудовищную ширину дерева и не перебирать сотни пустых клеток, авторы работы задействовали глубокое обучение. Нейросетевая модель принимает на вход начальное и целевое состояния и выдает распределение вероятностей по всем клеткам пространства. Клетки с высокой вероятностью подсвечиваются как перспективные «узкие места» маршрута, и дерево поиска DC-MCTS ограничивает свой перебор только этими фаворитами.
Для обучения этого нейросетевого оракула исследователи применили элегантную адаптацию концепции Hindsight Experience Replay (воспроизведение опыта задним числом). На этапе инициализации агент планирует плохо и регулярно совершает ошибки, не доходя до нужной синей клетки, а финишируя в случайной белой точке. Вместо того чтобы засчитать попытку как неудачную, алгоритм использует специфику целеориентированного планирования и «притворяется», что случайно достигнутая клетка и была истинной целью агента в данном эпизоде. Это мгновенно превращает провальный запуск в успешный обучающий пример.
Далее траектория этого успешного (задним числом) маршрута анализируется. Любая точка на пройденном пути признается хорошим кандидатом для промежуточного деления. Более того, авторы делают шаг вперед: если путь занял $M$ шагов, они берут состояние, достигнутое ровно на этапе $M/2$ (в точной середине пути), и используют его как идеальный тренировочный таргет для классификатора. Такой подход запускает процесс самосовершенствования (bootstrap): модель учится лучше делить задачи, планирование становится точнее, траектории — качественнее, что дает еще более чистые данные для обучения.
🕷️ Практические тесты и границы применимости
<a class="ts" data-seconds="1391" href="#t=1391" title="Смотреть с 23:11" aria-label="Смотреть с 23:11"><svg viewBox="0 0 24 24" width="14" height="14" fill="currentColor" aria-hidden="true"><path d="M8 5v14l11-7z"/></svg></a>
В качестве экспериментального подтверждения авторы протестировали алгоритм в сложной трехмерной среде, где виртуальный робот-паук обучался перемещаться с одного блока на другой. Тесты показали, что в этой дисциплине DC-MCTS уверенно превосходит традиционный алгоритм поиска по дереву Монте-Карло.
Тем не менее Янник Килчер призывает сдерживать избыточный оптимизм. По его мнению, данный подход демонстрирует превосходство исключительно в весьма специфическом типе задач.
Ведущий выделяет два жестких критерия применимости DC-MCTS:
- Задача обязательно должна быть целеориентированной (goal-directed), иначе будет невозможно эффективно собирать данные через механизм Hindsight Experience Replay.
- Пространство решений должно обладать выраженными структурными «бутылочными горлышками» (bottleneck states) — точками, мимо которых агент физически не сможет пройти при реализации любого жизнеспособного плана.
Если структура задачи позволяет нейросети с высокой точностью предугадывать такие транзитные узлы, DC-MCTS действительно раскрывает свой потенциал, сокращая глубину поиска и выигрывая у классического MCTS за счет умного ограничения ширины перебора.
