- MCTS-GEB: поиск по дереву Монте-Карло — хороший конструктор электронных графов (arXiv)
Автор: Голян Хэ, Зак Сингх, Эйко Ёнеки.
Аннотация: Системы перезаписи [6, 10, 12] широко используют насыщение равенством [9], которое представляет собой методологию оптимизации, использующую насыщенный e-граф для одновременного представления всех возможных последовательностей перезаписи, а затем извлекающую оптимальную. Таким образом, можно достичь оптимальных результатов, избегая проблемы упорядочения фаз. Однако мы наблюдаем, что когда e-граф не насыщен, он не может представить все возможные возможности перезаписи, и поэтому проблема упорядочения фаз повторно возникает на этапе построения e-графа. Для решения этой проблемы мы предлагаем MCTS-GEB, общую систему перезаписи, которая применяет обучение с подкреплением (RL) к построению электронных графов. По своей сути, MCTS-GEB использует поиск по дереву Монте-Карло (MCTS) [3] для эффективного планирования оптимального построения электронного графа, и поэтому он может эффективно устранить проблему упорядочения фаз на этапе построения и добиться лучшей производительности в течение разумное время. Оценка в двух разных областях показывает, что MCTS-GEB может превзойти современные системы перезаписи до 49 раз, в то время как оптимизация обычно может занять менее часа, что указывает на то, что MCTS-GEB является многообещающим строительным блоком для будущего поколения. систем перезаписи
2. Поиск по дереву Монте-Карло с приоритетным расширением узла для многоцелевого планирования задач
(архив)
Автор: Кай Пфайффер, Леонардо Эдгар, Куанг-Куонг Фам.
Аннотация: Планирование задач для роботов является сложной вычислительной задачей из-за комбинаторной сложности возможного пространства действий. Этот факт усиливается, если необходимо достичь нескольких подцелей из-за увеличения длины последовательностей действий. В этой работе мы предлагаем многоцелевой алгоритм планирования задач для детерминированных процессов принятия решений, основанный на поиске по дереву Монте-Карло. Мы дополняем алгоритм расширением приоритетных узлов, которое отдает приоритет узлам, которые уже выполнили некоторые подцели. Из-за своей линейной сложности по количеству подцелей наш алгоритм может идентифицировать последовательности действий из 145 элементов для достижения желаемого целевого состояния с 48 подцелями, в то время как дерево поиска ограничено менее чем 6500 узлами. Мы используем сокращение действий на основе критерия кинематической достижимости, чтобы еще больше упростить вычислительную сложность. Мы объединяем наш алгоритм с локализацией объекта и планированием движения и применяем его к демонстрации реального робота с двумя манипуляторами в условиях проверки промышленных подшипников.
