Эвристики для поиска в пространстве состояний
Итак, из описанного выше следует, что ни прямой, ни обратный поиск не может быть эффективным без хорошей эвристической функции. Как было указано в главе 4, эвристическая функция оценивает расстояние от некоторого состояния до цели; в планировании Strips стоимость каждого действия равна 1, поэтому расстояние измеряется количеством действий. Основная идея состоит в том, что нужно рассматривать результаты действий и цели, которые должны быть достигнуты, а после этого выдвигать предположение, сколько действий потребуется для достижения всех целей. Задача определения точного количества действий является NP-трудной, но чаще всего существует возможность найти приемлемые оценки без слишком большого объема вычислений. Необходимо также иметь возможность вывести допустимую эвристику, которая не приводит к переоценке. Такая эвристика может использоваться в сочетании с поиском А* для нахождения оптимальных решений.
Для составления эвристики могут быть опробованы два подхода. Первый из них состоит в том, чтобы вывести ослабленную задачу из заданной спецификации задачи (см. главу 4). Оптимальная стоимость решения для ослабленной задачи (которую можно надеяться очень легко решить) задает допустимую эвристику для первоначальной задачи. Второй подход состоит в том, что можно воспользоваться предположением о возможности применения алгоритма, действующего исключительно по принципу "разделяй и властвуй". Такое предположение называется предположением о независимости подцелей, согласно которому стоимость решения конъюнкции подцелей аппроксимируется суммой стоимостей решения каждой подцели независимо друг от друга. Предположение о независимости подцелей может быть оптимистическим или пессимистическим. Оно является оптимистическим, если имеются отрицательные взаимодействия субпланов для каждой подцели, например, если действие в одном субплане удаляет цель, достигнутую в другом субплане. С другой стороны, такое предположение является пессимистическим и поэтому недопустимым, если субпланы содержат избыточные действия, например, два таких действия, которые могут быть заменены одним действием в объединенном плане.
Рассмотрим способ вывода ослабленных задач планирования. Поскольку имеются явные представления предусловий и результатов, такой способ может предусматривать модификацию указанных представлений. (Сравните этот подход с задачами поиска, в которых функция определения преемника рассматривалась как "черный ящик".) Простейшая идея состоит в том, что задача может быть ослаблена путем удаления из действий всех предусловий. В таком случае каждое действие всегда будет применимым и любой литерал может быть достигнут за один шаг (если есть какое-либо применимое действие; в противном случае цели достичь невозможно). Из этого почти безусловно следует, что количество шагов, необходимых для решения конъюнкции цели, равно количеству невыполненных целей — почти, но не совсем, поскольку, во-первых, могут существовать два таких действия, каждое из которых удаляет литерал цели, достигнутый другим, и, во-вторых, некоторое действие может достигать нескольких целей. Если же ослабленная задача будет применяться в сочетании с предположением о независимости подцелей, это позволит воспользоваться предположением о том, что указанных проблем не существует, и поэтому результирующая эвристика будет точно соответствовать количеству невыполненных целей.
Во многих случаях существует возможность получить более точную эвристику, рассматривая, по меньшей мере, положительные взаимодействия, вытекающие из наличия действий, достигающих нескольких целей. Прежде всего, можно еще больше ослабить задачу, удаляя отрицательные результаты (см. упр. 11.6). Затем можно подсчитать минимальное количество требуемых действий таким образом, чтобы объединение положительных результатов этих действий позволяло выполнить данную цель. Например, рассмотрим следующее определение:
Goal (А л В л С) Action(X, Effect: А л Р) Action(Y, Effect: В л С л (?) Action{Z, Effect: В л Р л Q)
Минимальное множественное покрытие цели {А, В, С) задается действиями {X, Y], поэтому эвристика множественного покрытия возвращает стоимость 2. Такая оценка лучше по сравнению с предположением о независимости подцелей, которое позволяет получить эвристическое значение 3. Остается непреодоленной лишь одна небольшая неприятная особенность: задача поиска множественного покрытия является NP-трудной. Простой жадный алгоритм поиска множественного покрытия гарантирует возвращение значения, которое находится в пределах коэффициента 1одл от истинного минимального значения, где п— количество литералов в цели, но обычно на практике данный алгоритм действует намного лучше по сравнению с этой оценкой. К сожалению, жадный алгоритм не обеспечивает гарантий достижимости для такой эвристики.
Существует также возможность создавать ослабленные задачи, удаляя отрицательные результаты без удаления предусловий. Таким образом, если некоторое действие в первоначальной задаче имеет результат А л -iB, то в ослабленной задаче будет иметь результат А. Это означает, что не нужно беспокоиться об отрицательных взаимодействиях субпланов, поскольку ни одно действие не способно удалить литералы, достигнутые другим действием. Стоимость решения полученной в конечном итоге ослабленной задачи задает то, что принято называть эвристикой с пустым списком удаления. Эта эвристика является весьма точной, но для ее вычисления требуется действительно выполнить некоторый (простой) алгоритм планирования. Тем не менее на практике поиск в условиях ослабленной задачи часто происходит достаточно быстро для того, чтобы имело смысл применение этой оценки стоимости.
Описанные здесь эвристики могут использоваться либо в прогрессивном, либо в регрессивном направлении. Ко времени написания данной книги первые места в рейтинге эффективности занимали прогрессивные планировщики, в которых применялась эвристика с пустым списком удаления. Такая ситуация вполне может измениться в результате исследования новых эвристик и новых методов поиска. Поскольку задачи планирования являются экспоненциально трудными5, ни один алгоритм не может быть достаточно эффективным для решения всех задач, но с использованием эвристических методов, описанных в этой главе, могут быть решены многие практические задачи, и таких задач стало гораздо больше по сравнению с теми, которые были решаемыми всего лишь несколько лет тому назад.