Глубокое обучение с подкреплением для сборки кубика Рубика

Глубокое обучение с подкреплением для сборки кубика Рубика

Введение

Кубик Рубика — известная трехмерная головоломка. У обычного кубика Рубика шесть граней, на каждой из которых по девять цветных стикеров, и головоломка решена, когда каждая грань имеет единый цвет. Если считать один поворот на четверть (90°) за один ход и два поворота на четверть (поворот лицом) за два хода, то лучшие алгоритмы, изобретенные человеком, могут решить любой экземпляр куба за 26 ходов.

Моя цель — дать компьютеру возможность научиться собирать кубик Рубика, не снабжая его никакими человеческими знаниями, такими как симметрия кубика. Самая сложная часть — Кубик Рубика имеет 43 252 003 274 489 856 000 возможных перестановок. Прежде чем мы обсудим, как подойти к этой проблеме, сначала давайте сформулируем проблему в стиле обучения с подкреплением.

Постановка проблемы

Государственное пространство

Кубик Рубика состоит из 27 кубиков, но центральный никогда не двигается. Мы можем рассматривать перестановку как тензор 3 × 3 × 3, представляющий положение всех этих 27 кубиков. Например, конечное состояние, т. е. решенное состояние, может быть представлено следующим тензором:

tensor([[[ 0.,  1.,  2.],
         [ 3.,  4.,  5.],
         [ 6.,  7.,  8.]],

        [[ 9., 10., 11.],
         [12., 13., 14.],
         [15., 16., 17.]],

        [[18., 19., 20.],
         [21., 22., 23.],
         [24., 25., 26.]]])

Пространство действий

В этом отчете я использую «обозначение Singmaster» для обозначения возможных действий. Во-первых, давайте определим шесть граней кубика Рубика с помощью шести букв: F (спереди), B (сзади), U (вверху), D (внизу), L (слева), R (справа), как показано на следующем рисунке. .

Теперь мы можем использовать эти буквы для обозначения поворота этих граней по часовой стрелке, а когда за буквой следует символ штриха (‘), он обозначает поворот этих граней против часовой стрелки. Например, «F» означает поворот лицевой стороны на 90° по часовой стрелке, а «F’» означает поворот лицевой стороны на -90°.

Очевидно, что для каждого состояния есть 12 возможных действий: {F, F’, B, B’, U, U’, D, D’, L, L’, R, R’}.

Динамика перехода

Из каждого состояния каждое действие приводит к новому детерминированному состоянию. Например, из следующего состояния:

tensor([[[ 6.,  3.,  0.],
         [ 7.,  4.,  1.],
         [ 8.,  5.,  2.]],

        [[ 9., 10., 11.],
         [12., 13., 14.],
         [15., 16., 17.]],

        [[18., 19., 20.],
         [21., 22., 23.],
         [24., 25., 26.]]])

Если мы предпримем действие «F», следующим состоянием должно быть конечное состояние.

Цель и награда

Задача агента — собрать кубик Рубика за как можно меньше шагов. Я установил простой механизм вознаграждения: -1 за каждое действие. Поэтому мы определяем цель агента как максимизацию накопленного вознаграждения.

Классификация проблем

Это проблема конечных марковских процессов принятия решений (MDP) с детерминированной динамикой перехода, о которой мы полностью знаем.

Метод решения

Во-первых, поскольку эта проблема MDP имеет такое огромное пространство состояний, мы не можем использовать метод табличного решения, а подход глубокого обучения.

Как создавать эпизоды

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

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

В отличие от статьи, я решил позволить агенту узнать оптимальные значения состояния вместо значений состояния-действия. После того, как агент узнает оптимальные значения состояния, я бы предложил агенту использовать простую жадную политику. Причина этого дизайна в том, что я хочу, чтобы входные функции для нейронной сети были как можно более простыми.

Как оценить стоимость состояния

Интуитивно, если для сборки куба из состояния A требуется 1 ход, то оно имеет более высокое значение, чем состояние B, в котором для сборки куба требуется 2 хода. Следовательно, если состояние появляется в эпизоде ​​несколько раз, расстояние между его последним появлением и конечным состоянием является более разумной оценкой значения его состояния.

Например, на следующем рисунке state_2 и state_0 — это одни и те же состояния, которые находятся не более чем в 3 шагах от конечного состояния вместо 5 шагов. Все состояния между state_2 и state_0 являются простыми «обходными путями».

Поэтому я использую метод последнего визита Монте-Карло (MC) для оценки оптимального значения состояния.

Реализация и результат

В этом разделе я расскажу о своей реализации с использованием PyTorch в следующем порядке:

1. Подготовка данных
2. Построение нейронной сети
3. Оптимизация модели
4. Политика, основанная на обученной модели
5. Результат эксперимента

Подготовка данных

Государственное представительство

Я использую тензор PyTorch для представления каждой перестановки, то есть состояния куба. Есть два преимущества:

1. Тензор PyTorch может использовать мощность графического процессора для достижения более быстрых вычислений, чем на процессоре.
2. С помощью torch.rot90 можно легко имитировать физический поворот на 90° на каждой грани куба. Я научился этому трюку из реализации NumPy.

Генератор эпизодов

Учитывая длину эпизода l, определим e_l как эпизод, в котором мы случайным образом перемешиваем кубик l раз. Думайте о последовательности состояний как о массиве, индекс каждого состояния является естественным представлением его значения. Нам просто нужно взять отрицательное значение индекса.

Чтобы сделать его более гибким, я добавил коэффициент, чтобы можно было экспериментировать с различными схемами вознаграждения.

estimated_state_value.append(float(-index*c))

Хотя концептуально мы передаем эпизоды обратно агенту, поскольку мы принимаем метод MC последнего посещения, мы собираем значение первого появления состояний в нашем сгенерированном массиве.

Другие приемы работы с GPU

1. Вместо того, чтобы подавать в модель ванильный массив, я использую torch.stack для объединения выборок в тензор более высокой размерности, чтобы использовать параллельные вычисления GPU.
2. Поместите данные на GPU с помощью X.to('cuda').
3. Используйте DataLoader и позвольте PyTorch обработать пакетную обработку.

Построение нейронной сети

Чтобы добавить нелинейности модели, я использую простую функцию ReLu.

NeuralNetwork(
  (flatten): Flatten(start_dim=1, end_dim=-1)
  (linear_relu_stack): Sequential(
    (0): Linear(in_features=27, out_features=512, bias=True)
    (1): ReLU()
    (2): Linear(in_features=512, out_features=512, bias=True)
    (3): ReLU()
    (4): Linear(in_features=512, out_features=1, bias=True)
  )
)

Оптимизация модели

Функция потерь

Это проблема регрессии, потому что агент изучает значение состояния. Поэтому я использую среднеквадратичную ошибку (квадрат нормы L2) в качестве функции потерь.

loss_fn = nn.MSELoss()

Алгоритм оптимизации

Что касается оптимизаторов, я попробовал стохастический градиентный спуск (SGD) и Адама со скоростью обучения 1e-3 и 1e-5.

Политика, основанная на обученной модели

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

Результат

Для эксперимента я создал 17 642 842 эпизода в диапазоне от e_1 до e_19.

Эксперимент 1:

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

Эксперимент 2:

В этом примере я использую SGD и Adam, а PyTorch DataLoader позаботится о пакетной обработке. Однако после 15 эпох обучения функция потерь колеблется между 3 ~ 7. Я пробовал меньшую скорость обучения в более поздние эпохи, но это не помогло.

Учитывая, что функция потерь является среднеквадратичной ошибкой, реальная разница между прогнозом и «истиной» составляет около 1,7–2,5. Это может показаться немного, однако, если куб совершит одну ошибку, он уйдет еще на один шаг от конечного состояния, и ситуация станет намного сложнее.

Отражение

Я думаю, что основная причина, по которой агенту не удается узнать оптимальное значение состояния, заключается в том, что моя модель недостаточно выразительна. Я пробовал с одной парой «Linear-ReLU», двумя парами и тремя парами, и результат почти одинаков. Я предполагаю, что мне нужно использовать слой свертки 3D. Тем не менее, у меня нет достаточно времени, чтобы заставить его работать.

Кроме того, поскольку модель не научилась решать даже головоломку, я не могу начать обобщенную итерацию политики (GPI) с политикой, которая могла бы завершить один эпизод. Поэтому агент может учиться только на случайно сгенерированных эпизодах.

Заключение

Несмотря на то, что кубик Рубика является эпизодической задачей MDP, и у нас есть полное представление о его детерминированной динамике перехода, он по-прежнему очень сложен из-за огромного пространства состояний. Во время проекта я прохожу весь процесс от формулирования проблемы до реализации и экспериментирования. Попутно я изучаю основы PyTorch, с которыми обязательно поиграюсь в будущем. Если бы у меня было больше времени, я бы попробовал слои свертки 3D и использовал графический процессор. В целом, я получил большой опыт и многому научился, реализовав проект на промышленном уровне.