Записки программиста

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Метки: Haskell, Искусственный интеллект, Функциональное программирование.