Обратный поиск в пространстве состояний
Обратный поиск в пространстве состояний был кратко описан в составе двунаправленного поиска в главе 3. В этой главе было отмечено, что задача организации обратного поиска может оказаться сложной, если целевые состояния описаны с помощью множества ограничений, а не перечислены явно. В частности, не всегда очевидно, как должно составляться описание возможных преемников множества целевых состояний. А в этой главе будет показано, что представление Strips позволяет решить такую задачу очень легко, поскольку множества состояний могут быть описаны с помощью литералов, которые должны быть истинными в этих состояниях.
Основным преимуществом обратного поиска является то, что он позволяет рассматривать только релевантные действия. Действие релевантно конъюнктивной цели, если оно достигает одного из конъюнктов данной цели. Например, целью описанной выше задачи по воздушной перевозке грузов с 10 аэропортами была доставка 20 единиц груза в аэропорт В или, точнее:
At(Clt В) Л At(C2, В) л ... Л At(C2o, В)
Теперь рассмотрим конъюнкт At(ClfB). Двигаясь в обратном направлении, можно найти действия, имеющие этот результат. Таковым является только одно действие: Unload (Clf р, В), где самолетр не задан.
Обратите внимание на то, что имеется также много нерелевантных действий, способных привести к целевому состоянию. Например, можно организовать перелет пустого самолета из аэропорта JFK в аэропорт SFO; это действие позволяет достичь целевого состояния из состояния-предшественника, в котором самолет находился в JFKw все целевые конъюнкты были удовлетворены. Обратный поиск, в котором допускаются нерелевантные действия, по-прежнему будет полным, но гораздо менее эффективным. Если решение существует, то должно быть найдено с помощью обратного поиска, допускающего только релевантные действия. Наличие такого ограничения, в котором допускаются только релевантные действия, означает, что процедура обратного поиска часто имеет гораздо более низкий коэффициент ветвления по сравнению с прямым поиском. Например, в рассматриваемой задаче грузовых воздушных перевозок имеется около 1000 действий, ведущих в прямом направлении из начального состояния, но только 20 действий, позволяющих перейти в обратном направлении от цели.
Поиск в обратном направлении иногда называют регрессивным планированием. Основной вопрос регрессивного планирования состоит в следующем: есть ли такие состояния, из которых применение некоторого действия приводит к цели? Вычисление описаний таких состояний называется регрессией цели через действие. Для того чтобы определить, как можно найти ответ на указанный выше вопрос, рассмотрим пример с воздушными грузовыми перевозками. Мы имеем цель
Afc(Ci, В) Л At(C2l В) Л ... Л At(C20, В)
и релевантное действие Unload(Clf р, В), которое позволяет достичь первого конъюнкта. Соответствующее действие будет выполнимо, только если выполнены его предусловия. Поэтому любое состояние-преемник должно включать эти предусловия: ln{Cltp) л At{p,B). Более того, подцель At (С±, В) не должна быть истинной в состоянии-преемнике4. Поэтому описание состояния-преемника является таковым:
Inid, р) Л At{p, В) Л At{C2l В) Л ... Л At(C20, В)
Кроме выполнения того требования, чтобы действия достигали некоторого желаемого литерала, должно также соблюдаться требование, чтобы действия не отменяли какие-либо желаемые литералы. Любое действие, удовлетворяющее этому ограничению, называется совместимым. Например, действие Load{C2f р) не будет совместимым с текущей целью, поскольку оно отрицает литерал At (С2, В).
Составив определения понятий релевантности и совместимости, мы можем описать общий процесс формирования преемников для обратного поиска. Допустим,
что при наличии описания цели G имеется действие А, которое является релевантным и совместимым. Соответствующий преемник может быть определен, как описано ниже.
• Любые положительные результаты действия А, которые появляются в цели G, удаляются.
• Добавляется каждый литерал предусловия А, если он еще не присутствует в определении действия.
Для осуществления обратного поиска могут использоваться любые из стандартных алгоритмов поиска. Завершение работы происходит после выработки такого описания преемника, которое соответствует начальному состоянию задачи планирования. В случае использования логики первого порядка для обеспечения соответствия с начальным состоянием может потребоваться подстановка переменных в описание преемника. Например, описание преемника, приведенное в предыдущем абзаце, будет соответствовать такому начальному состоянию после подстановки {р/ Р12}:
In(d, Р12) Л At(Pi2,B) л At(C2, В) л ... л At(C20, В)
Затем данная подстановка должна быть применена к действиям, ведущим из этого состояния к цели, что приводит к получению решения [ Unload{Clf Р12, В) ].