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

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

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