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

Предположим, что нас интересует список целей 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)

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]

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