Регрессия целей

Предположим, что нас интересует список целей Goals, являющихся истинными в
некотором состоянии S. Допустим, что состоянием, непосредственно предшествую­
щим S, является SO, а действием, выполненным в состоянии SO, является А. Теперь
попытаемся ответить на вопрос о том, какие цели Goals0 должны быть истинными в
состоянии SO для того, чтобы цели Goals стали истинными в состоянии S, как пока­
зано ниже.
состояние SO: GoalsO------ > состояние S: Goals

А

Цели GoalsO должны иметь свойства, перечисленные ниже.

1, В состоянии SO должно быть возможно действие А, поэтому цели GoalsO
должны формировать предпосылки для А.

2. Для каждой цели G в списке Goals должно быть справедливо одно из следую­
щих утверждений:

• цель G добавлена в результате действия А;

• цель G имеется в списке GoaisO, и выполнение действия А не привело к ее удалению.

Определение списка целей GoalsO исходя из заданного списка Goals и действия А называется возвратом списка Goals в предшествующее состояние (или его регрес­сией) с помощью действия А. Безусловно, нас интересуют только такие действия, в результате которых в список Goals была добавлена некоторая цель G. Отношения между различными множествами целей и условий показаны на рис. 17.3.

Глава 17. Планирование

саг.(A) Goals

 

 

deli AJ

add(A)

Рис. 17.S. Отношения между различными мно­жествами условий при осуществлении регрес­сии целей с помощью действия А Затененная область показывает соответствующие целив списке GoalsO. полученные с результате рег­рессии: GoalsO - сэп< A) и Goals -add (А). Обратите внимание на то, что пере­сечение между списком Gcslsи списком удале-ния действия А должно быть пустым

Механизм регрессии целей может использоваться при планировании, как описано ниже.

Чтобы достичь списка целей Goals из некоторого начального состояния StartState, необходимо выполнить следующие действия.

• Если в состоянии StartState все цели в списке Goals являются истинными, то достаточно применить пустой план.

• В противном случае выбрать цель G из списка Goals и некоторое действие А, в результате которого в этот список добавляется цель G. Затем выполнить регрес­сию целей в списке Goals с помощью действия А, получив список NewGoals, и найти план для достижения целей списка NewGoals из состояния StartState.

Эту стратегию можно улучшить, заметив, что некоторые комбинации целей яв­ляются невозможными. Например, цели он [ a, Ь) и clear (b) не могут быть ис­тинными одновременно. Такое условие можно сформулировать в виде следующего отношения: impossible(Goal, Goals)

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

impossible< on(X, X), \. % Блок не может быть поставлен сам на себя impossible< on! X, Y), Goals):-member{ clear! Y), Goals)

I Блок не может находиться % одновременно в двух местах % Два блока не могут находиться i одновременно в одном и том же месте

member { on (X, YD, Goals), У1

member; on(Xl, Y), Goals], xl \== X.

impossible(clear! X>, Goals);-member (on [ _, X), Goals).

Программа планировщика, основанная на принципах регрессии целей, описанных выше, приведена в листинге 17.5. В этой программе возможные планы рассматрива­ются в режиме поиска в ширину, при котором предпринимается попытка в первую очередь найти самые короткие планы. Реализация этого требования обеспечивается благодаря использованию в процедуре plan следующей цели: cone* Preplan, [Action], Plan)

Часть II. Применение языка Prolog в области искусственного интеллекта

Такой планировщик находит оптимальный трехэтапный план для задачи, пока­занной на рис. 17.1.

Листинг 17.5. Планировщик, основанный на регрессии целей, осуществляет поиск в режиме поиска в ширину

% Планировщик с регрессией целей, работающий в режиме поиска в ширину % plan{ State, Goals, Plan) plant State, Goals, []):-

satisfied [ State, Goals). % Цепи Goals являются истинными

% в состоянии State

plant State, Goals, Plan):-conc(PrePlan, [Action], Plan),

select! State, Goals, Goal), achieves* Action, Goal), can С Action, Condition),

preserves Action, Goals),

regress! Goals, Action, RegressedGoals),

plan! State, RegressedGoals, Preplan).

Выполнить декомпозицию плана, i достигая эффекта поиска в ширину * Выбрать цель

Обеспечить отсутствие переменных! в действии Action

Защитить цели Goals % Выполнить регрессию целей Goals % с помощью действия Action

 

satisfied! State, Goals):-delete all! Goals, State, []].

% Все цели Goals, которые определены % в состоянии State

 

select! State, Goals, Goal):-membert Goal, Goals).

achieves! Action, Goal):-adds! Action, Goals], member(Goal, Goals).

preserves (Action, Goals):-

deletes(Action, Relations),

not (member(Goal, Relations), membert Goal, Goals)).

% Выбрать цель Goal из списка целей Goals % Простой принцип выбора

^; Действие Action не приводит % к уничтожению цели Goals

regress) Goals, Action, RegressedGoals):- % Выполнить регрессию целей Goals

% с помощью действия Action adds) Action, NewRelations), delete_all Goals, NewRelations, RestGoals), can) Action, Condition),

addnew! Condition, RestGoals, RegressedGoals). I Ввести дополнительные

I предпосылки, проверить возможность действий

% addnew! NewGoals, OldGoals, AllGoals):

% OldGoals - это объединение целей NewGoalS и OldGoals;

i цели NewGoals и OldGoals должны Сыть совместимыми

addnew([], l, l).

addnewt [Goal | _ ], Goals, _) impossible) Goal, Goals),!,

fail.

addnew) [x Lib L2, L3>:-

member) X, L2),!, addnew) Ll, Ы, L3).

-

% Цель Goal несовместима с целями Goals l Добавление невозможно

i Игнорировать дубликат

 

addnew! [X I Ll]_f L2, addnew! Ll, L2, L3)

[X

L3])

: -

 

Глава 17. Планирование

% delete_all(LI, L2, Diffj:

Diff - это разность множеств, которые определены в виде списков L1 и L2

delete_all([), _, []).

delete_all([X I LI], L2, Diff):-member[ X, L2),!, delete_all[ Ll, L2, Diff).

delete_allt [X [ Ll], L2, [X I Diff]):-

delete ~-'-~- ' 1, L2, Diff].

Упражнение

17.5. Выполните трассировку процесса планирования, основанного на регрессии це­лей, для достижения цели on (а, Ь) из начального состояния, показанного на рис. 17.1. Предположим, что этот план состоит в следующем: (move(с, а, 2), move(а, 1, Ъ))

Если список целей после выполнения второго действия плана представляет собой [ on (а, Ь}], то каковым является регрес сиров энный (переведенный в пред­шествующее состояние) список целей перед вторым и перед первым действием?

Сочетание планирования по принципу анализа целей и средств с эвристическим поиском по заданному критерию

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

• Отношение select (State, Goals, Goal), в котором принимается решение по выбору последовательности осуществления попыток достижения целей. На­пример, одно из полезных сведений о построении конструкций из блоков со­стоит в том, что в любое время каждый блок должен стоять на надежной опоре и поэтому конструкции необходимо строить в последовательности снизу вверх. Правило эвристического выбора, основанное на знании об этом, должно указы­вать, что "самые верхние" связи on должны формироваться в последнюю оче­редь (т.е. они должны выбираться планировщиком с регрессией целей в пер­вую очередь, поскольку он формирует планы, переходя от конца плана к его началу). Еще одна эвристика должна подсказывать, что выбор тех целей, ко­торые уже являются истинными в начальном состоянии, должен быть отложен до последнего момента.

• Отношение achieves (Action, Goal), в котором принимается решение о том, какое из альтернативных действий должно быть опробовано для достиже­ния заданной цели. (В рассматриваемых планировщиках варианты фактиче-

398 Часть II. Применение языка Prolog в области искусственного интеллекта

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

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

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

Чтобы воспользоваться программами поиска по заданному критерию (см. гла­ву 12), необходимо формализовать соответствующее пространство состояний и эври­стическую функцию; иными словами, необходимо определить перечисленные ниже компоненты.

1. Отношение выбора преемника между узлами в пространстве состояний s(Model, Node2, Cost).

2. Целевые узлы поиска, заданные с помощью отношения goal (Node).

3. Эвристическая функция, представленная в виде отношения h [ Node,

Heuristic-Estimate).

4. Начальный узел поиска.

Одним из способов формирования такого пространства состояний является опре­деление соответствия между множествами целей и узлами в пространстве состояний. При этом в пространстве состояний должна существовать связь между двумя множе­ствами целей, Goals 1 и Goals2, если есть такое действие А, для которого справедли­вы следующие утверждения.

1. Действие А добавляет некоторую цель в множество Goal si.

2. Действие А не уничтожает ни одной цели в множестве Goalsl.

3. Множество Goals2 является результатом регрессии множества Goalsl с по­мощью действия А, как определено отношением regress, приведенным в лис­тинге 17.5:

regress (Goalsl, A, Goals2)

Для упрощения предположим, что все действия имеют одинаковую стоимость, по­этому присвоим стоимость 1 всем связям в пространстве состояний. В таком случае отношение определения преемника з должно выглядеть примерно так:

s(Goalsl, Goals2, 1):-
member! Goal, Goalsl), % Выбрать цель

achieves С Action, Goal), I Соответствующее действие

cant Action, Condition preserves (Action, Goalsl), regress(Goalsl, Action, Goals2).

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

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

Глава 17. Планирование

состояния on (a, b) из начального состояния, показанного на рис. 17.1, является таковой:

[ [ с1еаг( с), clear [ 2), on (с, a), clear (Ь), оп< а, 1)1, % Эти цели являются

% истинными в начальном состоянии

[ clear! a), clear [ b), on (а, 1)], % Цели, истинные после выполнения

% действия movet с, а, 2)

[ on (а, Ь) ] ] % Цели, истинные после выполнения

% действия move! а, 1, Ь)

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

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

Листинг 17.6. Определение пространства состояний для задачи планирования по принципу целей и средств с использованием регрессии целей. Отношения satisfied, achieves, preserves, regress, addnewи delete_all приведены е листинге 17.5

i Определение пространства состояний -." задачи планирования по принципу i целей и средств с использованием регрессии целей:- ор [ 300, y.fy, ->).

s(Goals -> NextAction, NewGoals -> Action, 1):- % Все стоимости равны 1 member(Goal, Goals), achieves[ Action, Goal), cant Action, Condition), preserves! Action, Goals), regress! Goals, Actie NewGoals).

goali Goals -> Action):-

start(State), % Определяемое пользователем начальное состояние

satisfied: State, Goals). ^::- Цели Goals являются истинными в начальном

hi Goals -> Action, H):- % Эвристическая оценка

start(State),

delete_all< Goals, State, Unsatisfied), i Недостигнутые цели

length; Unsatisfied, H). % Количество недостигнутых целей

Теперь определение пространства состояний (см. листинг 17.6) можно использо­вать в программах поиска по заданному критерию (см. главу 12) следующим обра­зом. Необходимо применить для консультации определение задачи планирования в виде отношений adds, deletes и can (которое приведено в листинге 17.1 для мира блоков). Кроме того, программе требуется предоставить отношение impossible, a также отношение start, которое описывает начальное состояние плана. Для состоя­ния, показанного на рис. 17.1, последнее отношение имеет следующий вид;

start ( [ оп(а, 1), оп(Ь, 3), оп(с, a), clear! b), clear [ с), clear (2), clear(4)].

 

 

Часть II. Применение языка Prolog в области искусственного интеллекта

Теперь, чтобы решить задачу, показанную на рис. 17.1, с помощью планировщи­ка, работающего по принципу целей и средств с учетом заданного критерия, необхо­димо вызвать процедуру поиска по заданному критерию следующим образом:?- bestfirstt [ on(a, b), on(b, О] -> stop, Plan).

Здесь дополнительно введено пустое действие stop, поскольку в применяемом представлении за каждым списком целей должно следовать, по требованиям синтак­сиса, какое-либо действие. Но [ on (а, Ь), on (b, с) ] - это конечный список целей плана, за которым фактически не следует действие, поэтому приходится при­менять пустое действие. Ниже приведено решение, которое представляет собой спи­сок, состоящий из списков целей и соединяющих их действий.

Plan = [

[ clear i 2), on i с, a), clear (с), or! Ъ, 3), clear (b), on (a, 1)] ->

move(c, a, 2),

[ clear! с), on (Ь, 3), clear! a), clear{ b), on [ а, 1)1 -> move (b, 3, с),

[ clear! a!, clear! Ъ), on (а, 1), оп(b, с)] -> move! а, 1, Ь),

[ on! a, b), on! b, c) ] -> stop]

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