# Янник Килчер разобрал новый алгоритм Divide-and-Conquer MCTS для целевого планирования

Источник: https://www.youtube.com/watch?v=tjbEVY5XIk0
Канал: Yannic Kilcher
Опубликовано: 08.05.2020

---

В своем новом обзоре исследователь искусственного интеллекта Янник Килчер (Yannic Kilcher) подробно разбирает научную работу «Divide-and-Conquer Monte Carlo Tree Search For Goal-Directed Planning». В центре внимания находится инновационный алгоритм планирования, который рекурсивно разбивает сложные пространственные задачи на подзадачи с помощью глубокого обучения. Этот подход предлагает альтернативу классическим методам поиска по дереву, значительно оптимизируя вычисления в целеориентированных средах.

## 🧭 Что такое планирование и почему классический поиск заходит в тупик
`[[JUMP:0:39]]`

Традиционное обучение с подкреплением строится на методе проб и ошибок, когда агент совершает действия вслепую, сталкивается со стенами, получает за это штрафы и пробует снова. Планирование же позволяет «думать наперед» и просчитывать последствия шагов в уме, используя внутреннюю модель среды, как это реализовано в знаменитых системах AlphaGo или AlphaZero. Когда перед агентом стоит задача дойти из начальной точки в целевую через лабиринт комнат, процесс планирования неизбежно превращается в построение дерева поиска.

Однако ключевая проблема классического поиска в ширину или глубину заключается в экспоненциальном взрыве сложности. Если путь к цели имеет длину в $D$ шагов, а на каждом этапе доступно 4 направления движения, то дерево разрастется до $4^D$ узлов, что делает полный перебор физически невозможным. 

Для решения этой проблемы традиционно применяются эвристики, такие как в алгоритме A*, который отдает приоритет узлам, приближающим агента к цели по евклидову расстоянию ($L_2$-дистанции). Классический алгоритм Monte Carlo Tree Search (MCTS) работает схожим образом: он останавливает глубокий перебор на определенном этапе и оценивает перспективность ветки с помощью эвристической функции ценности.

## ✂️ Разделяй и властвуй: радикальная идея DC-MCTS
`[[JUMP:05:26]]`

Суть предлагаемого метода Divide-and-Conquer Monte Carlo Tree Search заключается в фундаментальном изменении геометрии поиска. Представьте, что у агента есть Оракул, способный гарантировать, что на пути к финишу маршрут обязательно пройдет через определенную промежуточную точку в самом центре лабиринта.

В таком случае задача агента кардинально упрощается. Вместо поиска единого длинного пути протяженностью $D$ шагов, он начинает параллельно искать два независимых полумаршрута длиной $D/2$ каждый: от старта до промежуточной точки и от нее до финальной цели. С математической точки зрения это дает колоссальный выигрыш: вместо построения огромного дерева из $4^D$ узлов, алгоритм строит два дерева размером $4^{D/2}$. Сумма этих двух поддеревьев ничтожно мала по сравнению с исходным массивом вариантов, что означает эффективное разделение сложной задачи на две более простые подзадачи.

Новый алгоритм применяет эту стратегию рекурсивно. Он предлагает среднюю точку, делит задачу пополам, а затем для каждой из половин снова ищет промежуточное состояние, пока подзадачи не сократятся до масштаба одного шага. 

Здесь кроется важный концептуальный нюанс, который легко может запутать исследователя: алгоритм DC-MCTS осуществляет поиск не по действиям, а по планам. Сам план представляет собой дерево, но процесс поиска наилучшего плана формирует мета-дерево, где каждый узел — это целая незавершенная траектория или подзадача. Процедура обхода (traverse) раз за разом вызывает функцию выбора (select) для поиска оптимальных промежуточных узлов деления.

## 🕸️ Подвох алгоритма: размен глубины на ширину
`[[JUMP:13:17]]`

Несмотря на кажущуюся элегантность, предложенный метод не является магической таблеткой от всех вычислительных проблем. Главное различие между стандартным Monte Carlo Tree Search и его версией «разделяй и властвуй» кроется в структуре ветвления.

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

Это приводит к тому, что на первом же шаге у алгоритма возникает не 4, а сотни потенциальных вариантов деления, что делает структуру поиска невероятно широкой. Каждое выбранное промежуточное состояние требует аналогичного масштабного ветвления для своих подзадач. Таким образом, алгоритм осуществляет прямой размен: глубина дерева уменьшается, но его ширина увеличивается до колоссальных масштабов. Если развернуть дерево DC-MCTS полностью, оно будет содержать ровно столько же узлов, сколько и дерево классического MCTS.

## 🧠 Нейросети как оракулы и обучение через призму заднего ума
`[[JUMP:17:51]]`

Эффективность алгоритма полностью зависит от функции выбора — способности точно определять именно те промежуточные состояния, через которые агент действительно пройдет с высокой вероятностью. Чтобы ограничить чудовищную ширину дерева и не перебирать сотни пустых клеток, авторы работы задействовали глубокое обучение. Нейросетевая модель принимает на вход начальное и целевое состояния и выдает распределение вероятностей по всем клеткам пространства. Клетки с высокой вероятностью подсвечиваются как перспективные «узкие места» маршрута, и дерево поиска DC-MCTS ограничивает свой перебор только этими фаворитами.

Для обучения этого нейросетевого оракула исследователи применили элегантную адаптацию концепции Hindsight Experience Replay (воспроизведение опыта задним числом). На этапе инициализации агент планирует плохо и регулярно совершает ошибки, не доходя до нужной синей клетки, а финишируя в случайной белой точке. Вместо того чтобы засчитать попытку как неудачную, алгоритм использует специфику целеориентированного планирования и «притворяется», что случайно достигнутая клетка и была истинной целью агента в данном эпизоде. Это мгновенно превращает провальный запуск в успешный обучающий пример.

Далее траектория этого успешного (задним числом) маршрута анализируется. Любая точка на пройденном пути признается хорошим кандидатом для промежуточного деления. Более того, авторы делают шаг вперед: если путь занял $M$ шагов, они берут состояние, достигнутое ровно на этапе $M/2$ (в точной середине пути), и используют его как идеальный тренировочный таргет для классификатора. Такой подход запускает процесс самосовершенствования (bootstrap): модель учится лучше делить задачи, планирование становится точнее, траектории — качественнее, что дает еще более чистые данные для обучения.

## 🕷️ Практические тесты и границы применимости
`[[JUMP:23:11]]`

В качестве экспериментального подтверждения авторы протестировали алгоритм в сложной трехмерной среде, где виртуальный робот-паук обучался перемещаться с одного блока на другой. Тесты показали, что в этой дисциплине DC-MCTS уверенно превосходит традиционный алгоритм поиска по дереву Монте-Карло.

Тем не менее Янник Килчер призывает сдерживать избыточный оптимизм. По его мнению, данный подход демонстрирует превосходство исключительно в весьма специфическом типе задач. 

Ведущий выделяет два жестких критерия применимости DC-MCTS:

* Задача обязательно должна быть целеориентированной (goal-directed), иначе будет невозможно эффективно собирать данные через механизм Hindsight Experience Replay.
* Пространство решений должно обладать выраженными структурными «бутылочными горлышками» (bottleneck states) — точками, мимо которых агент физически не сможет пройти при реализации любого жизнеспособного плана.

Если структура задачи позволяет нейросети с высокой точностью предугадывать такие транзитные узлы, DC-MCTS действительно раскрывает свой потенциал, сокращая глубину поиска и выигрывая у классического MCTS за счет умного ограничения ширины перебора.