Задача о роботе-пылесосе без датчиков и решение на Haskell

10 мая 2012

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

Есть робот-пылесос и прямоугольная комната размером M на N полей. Робот умеет передвигаться вперед, назад, влево и вправо на одно поле, а также всасывать пыль на текущем поле. Каждое из этих пяти действий расходует одинаковое количество топлива (заряда аккумулятора). В начальный момент времени робот помещается в одно из полей, выбираемое случайным образом. Датчиков, позволяющих определить текущие координаты или наличие пыли в текущем поле, у робота нет. Тем не менее, от робота требуется убрать комнату, израсходовав минимальное количество топлива, зная только M и N.

Как ни странно, эта задача относительно просто решатся, например, с помощью уже знакомого нам алгоритма A*. Для этого вводятся понятия физического и доверительного состояния агента (в данной задаче агент — это пылесос). Физическое состояние — это обычное состояние с множеством грязных и чистых полей, а также текущими координатами пылесоса. Мы использовали бы это состояние для решения задачи, если бы у робота-пылесоса были датчики. Доверительное состояние — это множество физических состояний, в которых на данный момент может находится агент.

В переводе на православный язык Haskell это выглядит следующим образом:

data HooverAction = GoUp | GoDown | GoLeft | GoRight | Suck
  deriving (Eq, Ord, Enum, Bounded, Show)

-- Физическое состояние агента
data PhysicalState = PhysicalState {
    hooverX :: Int, -- координата пылесоса X
    hooverY :: Int, -- координата пылесоса Y
    worldWidth :: Int, -- ширина мира
    worldHeight :: Int, -- высота мира
    wasCleanedUp :: M.Map (Int, Int) Bool -- чистые поля
  } deriving (Eq, Ord, Show)

buildPhysicalState :: Int -> Int -> Int -> Int -> Maybe PhysicalState
buildPhysicalState width height hx hy = -- ...

applyActionPhys :: PhysicalState -> HooverAction -> PhysicalState
applyActionPhys st action = -- ...

isCleanPhys :: PhysicalState -> Bool
isCleanPhys st = -- ...

-- Доверительное состояние агента
data BeliefState = BeliefState {
    -- история действий
    actionsLog :: [HooverAction],
    -- множество физических состояний
    physicalSet :: S.Set PhysicalState
  } deriving (Show)

instance Eq BeliefState where
  x == y = physicalSet x == physicalSet y

instance Ord BeliefState where
  x `compare` y = physicalSet x `compare` physicalSet y

buildBeliefState :: Int -> Int -> Maybe BeliefState
buildBeliefState width height = -- ...

applyActionBelief :: BeliefState -> HooverAction -> BeliefState
applyActionBelief st action = -- ...

isCleanBelief :: BeliefState -> Bool
isCleanBelief st = -- ...

В приведенном листинге опущен код некоторых функций ввиду его тривиальности. Следует также отметить, что история действий (actionsLog) вообще-то не относится к доверительному состоянию, но была включена в него для удобства.

В свете вышесказанного не представляет труда свести задачу к обычному поиску в пространстве состояний. Поскольку робот не умеет отличать грязные поля от чистых, в начальный момент времени будем считать все поля грязными. За начальное состояние примем доверительное состояние, состоящее из M x N физических состояний. Целевым состоянием является такое состояние, в котором у любого физического состояния не осталось грязных полей.

Осталось только найти подходящую эвристическую функцию. Для физического состояния расстояние до цели несложно оценить по количеству еще не убранных полей:

hooverHeuristicPhys :: PhysicalState -> Int
hooverHeuristicPhys st
  | (wasCleanedUp st) M.! (hooverX st, hooverY st) = 2 * dirtyCells
  | otherwise = 2 * dirtyCells - 1
  where
    dirtyCells = M.fold (\x y -> if x then y else y + 1) 0
      (wasCleanedUp st)

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

Но что делать в случае с доверительным состоянием? Для него мы имеем ровно столько эвристик, сколько имеется физических состояний. Ни одна эвристика не является лучше или хуже другой. Так какую же выбрать? И можно ли как-то скомпоновать эвристики в одну, также являющуюся допустимой и монотонной? Оказывается, что можно, и довольно просто:

hooverHeuristic :: BeliefState -> [BeliefState] -> Int
hooverHeuristic st path =
  (length path) +
    (S.fold (\x y -> max (hooverHeuristicPhys x) y) 0 (physicalSet st))

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

Теперь, имея начальное и конечное состояние, а также эвристическую функцию, несложно найти решение, например, для случая M = N = 3:

$ time ./Main
[GoRight,GoRight,GoUp,GoUp,Suck,GoLeft,Suck,GoLeft,Suck,GoDown,
Suck,GoRight,Suck,GoRight,Suck,GoDown,Suck,GoLeft,Suck,GoLeft,Suck]

real  0m8.462s
user  0m8.289s
sys   0m0.148s

На этом можно было бы и закончить повествование, если бы не одна проблема. Оказалось, что для случая M = N = 4 программа работает ну очень долго. Это сподвигло меня поискать более удачную эвристическую функцию, и такая функция действительно нашлась:

-- минимальное количество шагов, необходимое для очистки пола
hooverHeuristicPhys :: PhysicalState -> Int
hooverHeuristicPhys st =
  2 * dirtyCells - 1 -- не учитываем текущее положение пылесоса
  where
    dirtyCells = M.fold (\x y -> if x then y else y + 1) 0
      (wasCleanedUp st)

-- Логическое "И" над двумя физическими состояниями
physicalStateConjunction :: PhysicalState ->
  PhysicalState -> PhysicalState
physicalStateConjunction a b = PhysicalState {
    hooverX = 0, hooverY = 0,
    worldWidth = newWidth, worldHeight = newHeight,
    wasCleanedUp = foldl (\m k -> M.insert k ((wasCleanedUp a M.! k) &&
      (wasCleanedUp b M.! k)) m) M.empty
        [(x, y) | x <- [0..newWidth-1], y <- [0..newHeight-1] ]
  }
  where
    newWidth = min (worldWidth a) (worldWidth b)
    newHeight = min (worldHeight a) (worldHeight b)

hooverHeuristic :: BeliefState -> [BeliefState] -> Int
hooverHeuristic st xs =
  (length xs) +
    hooverHeuristicPhys ( S.fold (\x y -> physicalStateConjunction x y)
      (S.findMin $ physicalSet st) (physicalSet st) )

Здесь мы объединяем физические состояния в одно состояние, каждая клетка которого считается чистой только в том случае, если она была очищена во всех физических состояниях (см функцию physicalStateConjunction). Затем для полученного состояния вычисляется та же hooverHeuristicPhys, что и раньше, за тем исключением, что мы не знаем, на чистой или грязной клетке находится агент в объединенном состоянии. Чтобы не переоценивать расстояние до цели, мы должны предполагать лучшее, то есть, что текущая клетка является грязной.

Теперь мы можем решить задачу для M = N = 4 за разумное время:

$ time ./Main
[GoRight,GoRight,GoRight,GoUp,GoUp,GoUp,Suck,GoLeft,Suck,GoLeft,
Suck,GoLeft,Suck,GoDown,Suck,GoRight,Suck,GoRight,Suck,GoRight,
Suck,GoDown,Suck,GoLeft,Suck,GoLeft,Suck,GoLeft,Suck,GoDown,
Suck,GoRight,Suck,GoRight,Suck,GoRight,Suck]

real  0m16.165s
user  0m15.977s
sys   0m0.136s

На решение задачи для M = N = 5 потребуется около девяти минут, но на данном этапе уже становится ясно, каким будет решение для любых M и N. Сначала роботу следует «упереться» в один из углов, тем самым гарантированно придя в одно физическое состояние, а затем «змейкой» обойти и очистить весь пол.

Если вас заинтересовали описанные здесь приемы, связанные с эвристическими функциями (ослабление задачи, комбинирование эвристик), рекомендую обратить внимание на раздел 4.2 «Эвристические функции» книги «Искусственный интеллект: современный подход» Стюарта Рассела и Питера Норвига. Например, также заслушивает внимания составление базы данных непресекающихся шаблонов, но сей вопрос выходит за рамки заметки. Книгу вы вряд ли найдете в магазинах, но почти наверняка отыщите в интернете.

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

Метки: , , .

Подпишись через RSS, E-Mail, Google+, Facebook, Vk или Twitter!

Понравился пост? Поделись с другими: