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

Пример задачи планирования приведен на рис. 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), iilm_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 GoalGoals

O

PrePlar j^~nAc 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 fb, 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;

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