Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 142

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 142)

Очевидно, что для обеспечения эффективности такого поиска потребуется очень точная эвристика. Мы рассмотрим некоторые возможные эвристики после описания обратного поиска. Обратный поиск в пространстве состояний Обратный поиск в пространстве состояний был кратко описан в составе двунаправленного поиска в главе 3.

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

Действие релевантно конъюнктивной цели„если оно достигает одного из конъюнктов данной цели. Например, целью опи- 524 Частью. Планирование санной выше задачи по воздушной перевозке грузов с ! 0 аэропортами была доставка 20 единиц груза в аэропорт В или, точнее; АС(Сг, В) л АС(Сг, В) д ... л АС(Сте ° В) Теперь рассмотрим конъюнкт АС(С„В). Двигаясь в обратном направлении, можно найти действия, имеющие этот результат. Таковым является только одно действие: (гп1оас((С,, р, В), где самолстр не задан.

Обратите внимание на то, что имеется также много нерелевантных действий, способных привести к целевому состоянию. Например, можно организовать перелет пустого самолета из аэропорта так в аэропорт ВГГ); это действие позволяет достичь целевого состояния из состояния-предшественника, в котором самолет находился в ,тВГГ и все целевые конъюнкты были удовлетворены. Обратный поиск, в котором допускаются нерелевантные действия, по-прежнему булет полным, но гораздо менее эффективным. Если решение сушествует, то должно быть найдено с помошью обратного поиска, допускающего только релевантные действия.

Наличие такого ограничения, в котором допускаются только релевантные действия, означает, что процедура обратного поиска часто имеет гораздо более низкий коэффициент ветвления по сравнению с прямым поиском. Например, в рассматриваемой задаче грузовых воздушных перевозок имеется около )000 действий, ведущих в прямом направлении из начального состояния, но только 20 действий, позволяюших перейти в обратном направлении от цели. Поиск в обратном направлении иногда называют 'в.

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

Мы имеем цель АС(Сы В) д Ае(гю В) д ... д АС(Сы, В) и релевантное действие (гп1оас((С,,р, В), которое позволяет достичь первого конъюнкта. Соответствующее действие будет выполнимо, только если выполнены его предусловия. Поэтому любое состояние-преемник должно включать эти предусловия: 1п(С„р) д АС (р, В) . Более того, подцель АС( Ст, В) не должна быть истинной в состоянии-преемнике4. Поэтому описание состояния-преемника является таковым; Хп(Сы р) л АС(р, В) л АС(Ст, В) д ... л АС(Сте, В) Кроме выполнения того требования, чтобы действия достигали некоторого желаемого литерала, должно также соблюдаться требование, чтобы действия не отменяли какие-либо желаемые литералы. Любое действие, удовлетворяющее этому ограничению, называется 'ак совместимым, Например, действие ьоаст(С,, р) не будет совместимым с текущей целью, поскольку оно отрицает литерал Ас ( с,, В) .

Составив определения понятий релеваятности и совмеслгимислги, мы можем описать обший процесс формирования преемников для обратного поиска. Допустим, 4 Если полцель была истинной в состоянии-преемнике, то данное дейстяяе все равно должно привести к целевому состоянию. С другой стороны, подобные действия являются нерелевантными, поскольку они не могут сделать цель истинной. 525 Глава 1!. Основы планирования что при наличии описания цели о имеется действие д, которое является релевантным и совместимым.

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

Например, описание преемника, приведенное в предыдущем абзаце, будет соответствовать такому начальному состоянию после подстановки (р/Р„); Хп(с~, Р г) х лс(Ргг,в) х Ас(сг, В) л .. х лс(сзс, В) Затем данная подстановка должна быть применена к действиям, ведущим из этого состояния к цели, что приводит к получению решения [ ())з1оас) ( фЄ, В) ) .

Эвристики ддя поиска в пространстве состояний Итак, из описанного выше следует, что ни прямой, ни обратный поиск не может быть эффективным без хорошей эвристической функции. Как было указано в главе 4, эвристическая функция оценивает расстояние от некоторого состояния до цели; в планировании 5(прз стоимость каждого действия равна 1, поэтому расстояние измеряется количеством действий.

Основная идея состоит в том, что нужно рассматривать результаты действий и цели, которые должны быть достигнуты, а после этого выдвигать предположение, сколько действий потребуется для достижения всех целей. Задача определения точного количества действий является ХР-трудной, но чаше всего существует возможность найти приемлемые оценки без слишком большого объема вычислений. Необходимо также иметь возможность вывести допустимую эвристику, которая не приводит к переоценке. Такая эвристика может использоваться в сочетании с поиском А* для нахождения оптимальных решений. Для составления эвристики могут быть опробованы два подхода. Первый из них состоит в том, чтобы вывести ослабленную задачу из заданной спецификации задачи (см, главу 4). Оптимальная стоимость решения для ослабленной задачи (которую можно надеяться очень легко решить) задает допустимую эвристику для первоначальной задачи.

Второй подход состоит в том, что можно воспользоваться предположением о возможности применения алгоритма, действующего исключительно по принципу "разделяй и властвуй". Такое предположение называется предположением о ',ъ. независимости подцелей, согласно которому стоимость решения конъюнкции подцелей аппроксимируется суммой стоимостей решения каждой подцели независимо друг от друга.

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

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

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

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

упр. 11.6). Затем можно подсчитать минимальное количество требуемых действий таким образом, чтобы объединение положительных результатов этих действий позволяло выполнить данную цель. Например, рассмотрим следующее определение: Воа1(А л В л С) Аогдоп(Х, ЕЕЕесе: А а Р) Аосдоп(У, ЕЕЕесе: В л С л д) Аседоп(Я, ЕЕЕесе: В а Р л Д) Минимальное множественное покрытие цели (А,В,С) задается действиями (д, у), поэтому эвристика множественного покрытия возвращает стоимость 2. Такая оценка лучше по сравнению с предположением о независимости подцелей, которое позволяет получить эвристическое значение 3. Остается непреодоленной лишь одна небольшая неприятная особенность: задача поиска множественного покрытия является НР-трудной.

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

Характеристики

Список файлов книги