Представление действий

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

 

а		Ь

Рис, 17.1. Проблема планирования в мире блоков — найти последовательность действий, которые по­зволяют достичь следующих целей: блок з должен стоять на блоке Ь. а блок Ь - на блоке С. Такие дей­ствия должны преобразовать начальное состояние (показанное слева) в конечное состояние (справа)

Действия изменяют текущее состояние планируемого мира, вызывая тем самым переход в новое состояние. Но ни одно действие обычно не изменяет все в текущем состоянии; затрагивается только отдельный компонент (компоненты) этого состоя­ния. Поэтому в качественном представлении должна учитываться такая "локализа­ция" результатов действий. Для упрощения рассуждений о подобных локальных ре­зультатах действий состояние удобнее всего представлять в виде списка связей, ко­торые в данный момент являются истинными. Безусловно, при этом следует упоми­нать лишь такие связи, которые касаются данной задачи планирования. Если речь идет о планировании в мире блоков, то подобными связями являются следующие: оп(Block, object) и clear(Object)

В последнем выражении утверждается, что верхняя грань объекта Object откры­та (на ней нет других блоков). При планировании в мире блоков такая связь являет­ся важной, поскольку блок, подлежащий перемещению, должен быть открытым сверху, а другой блок (или место), на который перемещается этот блок, также дол­жен иметь открытую верхнюю поверхность. Открытый сверху объект obiect может представлять собой блок или место на плоскости. Е данном примере а, Ь и с — бло­ки, а 1, 2, 3 и '■■ — места. В таком случае начальное состояние мира (см. рис. 17.1} можно представить с помощью следующего списка связей: [ clear(2), ciear(4), cleart b), Cleart с), on [ a, I), on(b, 3), on f c, a)]

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

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

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

2. Список добавления - список связей, установленных данным действием в те­кущей ситуации; это — условия, которые становятся истинными после выпол­нения этого действия,

3. Список удаления — список связей, разрушаемых в результате данного действия.
Предпосылки будут определяться с помощью следующей процедуры:

can(Action, Cond)

Эта процедура содержит информацию о том, что действие Action может быть вы­полнено только в той ситуации, в которой соблюдается условие Cond. Результаты действия определяются следующими процедурами:

где AddReis — список связей, установленных в результате выполнения действия Action. После выполнения действия Action в некотором состоянии к этому состоя­нию добавляются связи AddRels для получения нового состояния. С другой стороны, DelRels - это список связей, уничтожаемых действием Action. Эти связи удаляют­ся из состояния, к которому применяется действие Action.

В рассматриваемом мире блоков возможно действие только следующего типа: move (Block, From, ты

где Block - это перемещаемый блок, From - текущая позиция блока, а То - его новая позиция. Полное определение этого действия приведено в листинге 17.1.

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

Листинг 17.1. Определение пространства планирования для мира блоков

% Определение действия move (Block, From, To) в у_мре блоков

I can(Action, Condition!:

% действие Action возможно, если условие Condition является истинным

can(move{ Block, From, To), [ Clear! Block), clear! To), on [ Block, From!]):-

is_block(Block), % Перемещаемый блок

objects To), % To - это блок или место

То \== Block, % Блок ие может быть поставлен сам на себя

object(From), % From - это блок или место

From \== То, % Перемещение происходит в новую позицию

Block \==From. % Блок не может быть снят сам с себя

% addst Action, Relationships):

% в результате действия Action устанавливаются связи Relationships

adds(move(X,From,To), [ on(x_rTo), clear(From)]).

I deletest Action, Relationships):

% в результате действия Action уничтожаются связи Relationships

deletes(move(X,From,To), [ on (X, Fro.".:), clear(To)]).

object (X): - % X является одним из объектов, если

placet X) % х - место

; 4 или

is_block(X). 'i x - елок
i Мир блоков

is_block (а). is_blockt b).

is_block(с).

place (1). place (2). place(3). place(4).

% Состояние в мире блоков

i

% с

fe a b

% места 123 4

statel ([ clear(2), clear(4), cleat(b), clearCc), on(a,l), on(b,3), on[c,a) ]).

Определение возможных действий для задачи планирования неявно содержит оп­ределение пространства всех возможных планов, поэтому такое определение называ­ют также пространством планирования.

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

ку, открыть отсек для пленки, вынуть старую пленку, вставить новую пленку, за­крыть отсек для пленки. Состояние, в котором фотокамера готова для получения снимков, определяется следующим образом:

[ slot_closed< battery), slot_closed{ film), in< battery), ok(battery), in! film), film_at_start, film_unused]

Листинг 17.2. Определение пространства планирования для манипулирования фотокамерой

% Пространство планирования для подготовки фотокамеры к работе

% Открыть футляр

can{ open_case_f [camera__in_case]).

adds (open_case, [camera_o"utside_case]).

deletes (open_case, [camera_in_case]).

% Закрыть футляр

сап (close_case, [camera_outside_case, slot_closed(film),

slot closed! battery)]). addM clo~e_case, [earnera_in_case]). deletesf close_case, icamera_outside_case]).

i Открыть отсек для пленки

cant open_slot(X), [camera_outside_case, slot_closed(X)]). adds[ cpen_slc::; X),:slot_open { X)]). deletes! open_slot (X), "!slot_closed (X) ]).

% Закрыть отсек для пленки

cant close_slot(x), [canera_cutside_case, slot_open{ X)]). adds! close_slot£ x), [slot_closed (X) ] }. deletes! close_slot(X), [slot_open(X)]).

I Перемотать одаику

cani rewind, [camera_cutside_case, ln(film), i ilm_at_end]). adds [ rewind, [ f iim_at_start]). deletes! rewind, [ f ilm_at_end]).

% Вынуть аккумулятор или пленку-can (remove! battery), [slot_open С battery), in! battery)]). can! remove! film), [slot_open (film!, in! film), film_at_start]). adda(remove! x}, (slot_empty(X)]). deletes! remove* x), [in( X) ]).

% Бстазкть новый аккумулятор или пленку

can! insert_new< X), [slot_open! X!, slot_empty(X)]).

adds! ir.sert_new; battery), [in (battery), ok (battery) ]).

adds [ insert_new(film), [in(film), f ilm at_start, film_unused]) -

deletes! ir.sert_new(x), [slot_empty{ x) |J.~

% Снять фотографии

can! t»ke_piCtures, [in film), film at_start, fi.lm_unused,

in[ battery), ok< battery), siot_cTosed[ film), slot_closed { battery)]). adds (take__pictures, [ film_at_endj). deletes! take_pictures, [film_at_start, film_urmsed]).

% Состояние, в котором пленка израсходована, а аккумулятор разряжен * (Примечание. Аккумулятор считается разряженным, потому что связь % ok; battery) ке включена в это состояние.)

statel([canera_in_case, slot_clOSed(film), slot_closed(battery), inf film!, film_at_end_r in E battery)]).

386

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

Цель плана определяется в терминах связей, которые должны быть установлены после его выполнения. Для задачи мира блоков (см. рис. 17.1) задачу можно поста­вить как следующий список связей: 1 on! а, Ь), оп(b, с}]

Для задачи с фотокамерой список связей, который гарантирует, что фотокамера готова к съемке, состоит в следующем:

[ in[ film), film at start, film unused, in(battery), ok< battery), _Slot_cTo₃ed< film)7 slot_closed< battery)]

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

Упражнения

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

17.2. Определите пространство планирования для задачи с обезьяной и бананом (см. главу 2), в которой применяются действия "walk" (перейти), "push" (передвинуть), "climb" (залезть) и "grasp" (схватить).

Разработка планов с помощью анализа целей и средств

Рассмотрим начальное состояние задачи планирования (см. рис. 17.1). Предположим, что цель состоит в следующем; on (а, b}. Задача планировщика заключается в том, что он должен найти план {т.е. последовательность действий), который позволяет достичь этой цели. Типичный планировщик формирует свои рассуждения, как описано ниже.

1. Найти действие, которое позволит достичь состояния on (а, Ь). Изучение от­
ношения adds показывает, что такое действие имеет форму

move(a, From, b)

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

2. Теперь создадим возможность выполнения действия move (a, From, Ь). Рас­
смотрим отношение сап, чтобы найти предпосылки этого действия. Они состо­
ят в следующем:

[ clear(a), clearf b), on(a. From)]

В этом начальном состоянии уже имеются связи clear(b) и on (a, From) (где From = 1), но нет связи clear { а). Теперь планировщик сосредоточива­ется на связи clear (а) как новой цели, которая должна быть достигнута.

3. Снова рассмотрим отношение adds, чтобы найти действие, позволяющее дос­
тичь цели clear { а). Это - любое действие в следующей форме:

move (Block, a, To!

Предпосылки этого действия состоят в следующем: [ clear С Block), clear (To), on; Block, a}]

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

Эти предпосылки удовлетворяются в рассматриваемой начальной ситуации, если имеет место:

Block = с -л То = 2

Поэтому в начальном состоянии может быть выполнено действие move (с, а, 2), которое приводит к новому состоянию. Это новое состояние получено из на­чального состояния следующим образом:

• удаление из начального состояния всех связей, которые разрушаются в ре­зультате действия move (с, а, 2);

• добавление в итоговый список всех связей, которые создаются в результате этого действия.

При этом создается такой список:

[ clear[ a), clear { Ь), clear [ с), clea{ А), o n { а, 1), on (b, 3), о п (с-, 2)]

Теперь может быть выполнено действие move (а, 1, Ь), в результате которо­го достигается конечная цель on { а, Ь). Найденный план можно представить в виде следующего списка:

[ move (с, а, 2), move (а, 1, b) ]

Такой стиль формирования рассуждений называется анализом целей и средств. В качестве средств рассматриваются возможные действия, а в качестве целей — дос­тигаемые состояния. Обратите внимание на то, что в приведенном выше примере правильный план был найден немедленно, без какого-либо перебора с возвратами. Таким образом, этот пример показывает, что данный способ формирования рассуж­дений о целях и результатах действий ориентирует процесс планирования в пра­вильном направлении. К сожалению, нельзя утверждать, что при использовании та­кого способа всегда можно избежать перебора с возвратами. Справедливо противопо­ложное утверждение, что комбинаторная сложность и поиск — это типичные атрибуты планирования.

Принцип планирования с применением анализа целей и средств иллюстрируется на рис. 17.2. Он может быть сформулирован, как описано ниже.

Condition Goal Goals

O

PrePlar j^~n Ac lion /"""ч PostPlan----------- /■—\
---------- 4J——— <J ----------- -O

State MnlSialel MidStote2 FinalStale

Рис.. 17.2. Принцип планирования с применением анализа целей и средств

Чтобы найти в состоянии State решения для списка целей Goals, ведущие к со­стоянию FinalState, необходимо применить описанную ниже процедуру.

Если все цели Goals в состоянии State являются истинными, то FinalState = State. В противном случае выполнить следующие действия.

1. Выбрать в списке Goals цель Goal, для которой все еще не найдено решение.

2. Найти действие Action, которое добавляет цель Goal к текущему состоянию.

3. Обеспечить возможность выполнения действия Action, решив задачу создания предпосылок Condition действия Action, что приводит к созданию промежу­точного состояния MidStatel.

4. Применить действие Action к состоянию MidStatel и получить состояние Midstate2 (в состоянии MidState2 цель Goal является истинной).

5. Найти решения для целей в списке Goals в состоянии MidState2, что приведет к конечному состоянию FinalState.

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

Этот принцип может быть реализован в программе на языке Prolog, приведенной в листинге 17.3, в виде следующей процедуры: plan(State, Goals, elan, FinalState)

где State и FinalState начальное и конечное состояния плана, Goals — список достигаемых целей, a Plan — список действий, позволяющих достичь этих целей. Следует отметить, что в этой программе планирования предполагается использовать определение пространства планирования, в котором все действия и цели являются полностью конкретизированными, т.е. не содержат каких-либо переменных. Для пе­ременных требуется более сложная организация программы. Эта тема рассматривает­ся ниже.

Листинг 17.3. Простой планировщик с применением анализа целей и средств

% Простой планировщик с применением анализа целей и средств % plant State, Goals, Plan, FinalState)

plant State, Goals, [], State!; - % План пуст

satisfied! State, Goals). % E состоянии Stale цели Goals истинны

& На основании того, какой способ декомпозиции плана на этапы используется

% в предикате cone, можно считать, что поиск плана Preplan, создающего

'.- предпосылки для действия Action, осуществляется в режиме поиска в ширину,

% Ко длина остальной части плана не ограничена, и достижение целей происходит

% по принципу поиска в глубину

-Ian! State, Goals, Plan, FinalState):-

conc(Preplan, [Action ] PostPlan], Plan), % Выполнить декомпозицию плана

select (State, Goals, Goal), Is Выбрать цель

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

can(Action, Condition),

plant State, Condition, Preplan, MidStatel), \ Создать предпосылки для

% действия Action

apply! MidStatel, Action, MidState2), \ Применить действие Action

plan(Mid5tate2, Goals, PostPlan, FinalState). % Достичь остальных целей

% satisfied! State, Goals}: в состоянии State цели Goals являются истинными

satisfied (State, []).

satisfied (State, (Goal | Goals!):-

member (Goal, State), satisfied(State, Goals).

select(State, Goals, Goal):-
membert Goal, Goals),
not member; Goal, State), % Цель Goal еще не достигнута

% achieves! Action, Goal): цель Goal - это список добавления для действия Action

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

% apply! State, Action, NewState):

% действие Action, выполненное в состоянии State, создает

I новое состояние NewState

apply! State, Action, NewState):-deletes! Action, DelList), delete_ali(State, DelList, Statel),!, adds! Action, AddList), cone! AddList, Statel, NewState),

% delete_all{ LI, L2, Diff):

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

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

delete_all< [ ], _, []).

delete all I [X | LI], L2, Diff):-member! X, L2),!, deiete_ailf Ll, L2, Diff).

delete_all(PJ.¹®: L2, [X ' Diff]):-

Теперь этим планировщиком можно воспользоваться для поиска плана по уста­новке блока а на блок Ь, начиная с начального состояния, показанного на рис. 17.1, следующим образом:

?- Start - [ clear(2), clear{ 4), Clear(Ь), clear) с), оп(а, 1), on (Ь, 3),

oni с, а) ], plan! Start, (on { а, b)],Plan, FinState).

Plan - [ move (с, a, 2), nove { a, 1, to} 1

FinState- [ on! a, b), clear(1), on[ c, 2).clear{ a), clear [ 4), clear{ c),

on f b, 3) ]

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

?- Start = [ camera in case, slot closed! film;, slot closed (battery),

in(film), film at e"nd," in{ battery)],

plan(start, [ ok ("battery)!, FixBattery, _).

FixBattery = [ open_case, open_slot(battery), remove (battery),

?-^SStart^e= [ ^acame7a in case, slot c.lo5ed(film), slot closed ( battery),

in< film), film_at__e-_nd,-in[ battery)],

can [ takejictures, CameraReady), 1 Условие для фотографирования

plant Start, CameraReady, FixCamera, FinState).

CameraReady = [ in (film), fil_M_at_Start, film_unused, in! battery),

ok(battery), slot closed(film), slot closed* battery)]

FixCamera - [ open_case, rewind, o_Pen_slot< film), remove! film),

insert new! film), open slot! battery), remove! battery),

insert>w(battery), close slot (film,,, close slot! battery)]

Finstate = [ slot_closed(battery), slot closed! film), in! battery),

okf battery), in{ film), film_at_start, film_unused, camera_outside_case;

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