Plánování jako logické fungování

Agent m$åe na základ struktury problému vytvo it sloåité plány své þinnosti. Jednoduchý plánující agent je velmi podobný agentovi ešícímu problémy (zmín nému d íve) v tom, åe konstruuje plány k dosaåení svých cíl$, a po vytvo ení plán$ je provede. Další, tzv. þásteþn uspo ádané plánování, je komplikovan jší, prohledává prostor plán$, aby našlo plán zaruþující úsp ch. Zde je zárove navíc flexibilita, umoå ující zvládnout zcela sloåité domény.

Jednoduchý plánující agent

Pokud je stav sv ta p ístupný, m$åe agent pouåít vjemy poskytované okolím (prost edím) k vytvo ení kompletního a korektního modelu okamåitého stavu sv ta. Potom m$åe vzhledem k cíli vyvolat vhodný plánovací algoritmus (Ideal-Planner) k vytvo ení plánu þinností. Plán je vykonáván po krocích, jedna akce v jednom þasovém kroku. Agent pouåívá znalostní bázi.

Algoritmus (vyuåívající bázi znalostí) pro jednoduchého plánujícího agenta:

function Simple-Planning-Agent(percept) returns action

static: KB // znalostní báze, obsahuje popis akcí p // plán (na poþátku åádný plán)

t // þítaþ þasových krok , na poþátku 0

local variables: G	//	cíl
current	//	popis okamåitého stavu

Tell(KB,Make-Percept-Sentence(percept,t)) current Z State-Description(KB,t)

if p = NoPlan then

G Z Ask(KB,Make-Goal-Query(t))

p Z Ideal-Planner(current,G,KB)

if p = NoPlan or p is empty then action Z NoOp else

action Z First(p) p Z Rest(p)

Tell(KB,Make-Action-Sentence(action,t)) t Z t+1

return action

91

Funkce Tell zde vkládá do znalostní báze KB informaci o tom, co se objevilo jako vjem (k þemu po sd lení údaj$ znalostní bázi pak dojde, je záleåitost inference). Make-Percept-Sentence dostane pro daný þasový okamåik t vjem (percept) a vrací representaci vjemu (fakt$ o sv t ); individuální representace fakt$ se nazývají sentence nebo tvrzení—tato (logická) tvrzení jsou vyjád ena v jazyku, kterému znalostní báze rozumí, tj. jazyk representace znalosti.

Funkce Ask se ptá znalostní báze, jaká akce (po sd lení p es Tell, jaká je okamåitá situace) by se pro daný stav m la ud lat. Jde tedy o jakýsi dialog typu poskytnutí informace o skuteþnosti (Tell)—dotaz co za t chto podmínek d lat

(Ask).

Funkce State-Description dostane vjem jako vstup a vrací popis poþáteþního stavu ve formátu vyåadovaném plánovaþem (generátorem plán$).

Funkce Make-Goal-Query je pouåita v dotazu v$þi znalostní bázi na to, co by m lo být dalším cílem agenta.

Ideal-Planner m$åe být jakýkoliv vhodný plánovaþ (viz dále).

Od ešení problém$ k plánování

Plánování a ešení problém$ povaåuje moderní um lá inteligence za odlišné záleåitosti, protoåe representace cíl$, stav$, akcí a sekvencí akcí jsou odlišné.

ešení problém$ zaloåené na vyhledávání:

Representace akcí: akce jsou popsány programy, které generují popisy následných stav$.

Representace stav$: je dán kompletní popis poþáteþního stavu; akce

jsou representovány programem, který generuje kompletní popisy stav$. Proto jsou všechny representace stav$ kompletní. Ve v tšin problém$ je stav jednoduchá datová struktura—permutace þtvereþk$ v hlavolamu s 8 þtvereþky, pozice agenta v problému hledání trasy, nebo pozice šesti osob v problému kanibal$ a misioná $ s lo kou. Representace stav$ se pouåívají pouze pro generovaní následník$, pro heuristickou vyhodnocovací funkci a pro testování cíle.

92

Representace cíl$: jediná informace, kterou má ešící agent o svém cíli, je ve form testu na cíl a heuristické funkci. Oba prost edky mohou být aplikovány na stavy k rozhodnutí, zda jsou stavy vhodné þi pot ebné, ale zárove jsou oba prost edky pouåívány ve form “þerné sk í ky” (agent ešící problém nemá moånost se podívat dovnit nástroje p i výb ru akcí, které mohou být uåiteþné z hlediska dosaåení cíle).

Representace plán$: p i ešení problém$ jsou výsledkem sekvence akcí typu “je z Aradu do Sibiu, dále do Fagarasu a pak do Buchuresti”. B hem konstrukce ešení uvaåují vyhledávací algoritmy pouze nep erušené sekvence akcí vedoucích z poþáteþního stavu (p i obousm rném hledání akce konþící v koneþném stavu).

Jako p íklad lze uvést návrh ešení, ovliv ujících agentovu schopnost vy ešit jednoduchý problém “získej litr mléka, trs banán$ a bezdrátovou vrtaþku s m nitelnou rychlostí otáþek”.

Pro ešení je nutno specifikovat poþáteþní stav: agent je doma bez poåadovaných p edm t$, a soubor operátor$: vše, co agent m$åe d lat. Lze p ípadn pouåít i n jakou heuristiku, nap . poþet p edm t$, které dosud nebyly získány.

Na následujícím obrázku je velmi malá a symbolicky omezená þást prvních dvou úrovní prohledávaného prostoru pro ešení zadaného problému a náznak cesty vedoucí k cíli. Skuteþný faktor v tvení závisí na tom, jak jsou akce specifikovány (b mohou být tisíce nebo miliony), a délka ešení m$åe být v desítkách krok$—existuje p íliš mnoho akcí a stav$.

Heuristická vyhodnocovací funkce m$åe pouze vybrat mezi mnoha stavy k rozhodnutí, který stav je blíåe k cíli; neumí z úvah vylouþit akce. I kdyå se agent dostane do supermarketu, nezbývá mu, neå hádat. Agent p i pokusu o uhodnutí uvaåuje akce (koupit pomeranþe, rybu, brambory, mléko) a jejich ohodnocení evaluaþní funkcí (chybné, chybné, chybné, správné). Agent pak ví, åe koupit mléko je správná þinnost, ale nemá moånost zjistit, co ud lat pak a musí proces pokus$ zahájit znovu. K potíåím agenta tedy p ispívá také fakt, åe musí vådy uvaåovat sekvenci akcí z poþáteþního stavu—musí tedy se nap ed rozhodnout, co ud lat v poþáteþním stavu, kde relevantní výb r mezi þinnostmi je jít na n jaké z mnoha moåných míst. Pokud agent neví, jak získat r$zné poloåky (zakoupení, zap$jþení, pronajatí, vyp stování, vyrobení, ukradení...), pak se nem$åe fakticky rozhodnout, kam jít.

93

		Mluv na papouška
Jdi do obchodu se zvíøaty		Kup psa
Jdi do školy
		Jdi do tøídy

Jdi do supermarketu	Kup rybu
Zaèátek
Jdi spát	Kup mrkev

Èti si kní ku			Kup mléko		...			Konec
Posaï se na idli			Seï nadále
Atd. atd. ...		. . .	Èti kní ku

Z uvedených problém$ plyne, åe agent pot ebuje mnohem flexibiln jší zp$sob ke strukturalizaci svého uvaåování tak, aby mohl zpracovat kteroukoliv þást problému, která je—za p edpokladu okamåité informace—nejpravd podobn jší k vy ešení.

Základní a klíþová idea pro plánování je “otev ení þerné sk í ky”, tj. representací stav$, cíl$ a akcí. Plánovací algoritmy pouåívají popisy ve formálních jazycích, nap . pomocí logiky prvního ádu (viz p íslušnou kapitolu matematické logiky: výrazy, termy, konstanty, prom nné, predikáty, funkce, spojky <, Y, Z, @, kvantifikátory ~, }) nebo její podmnoåiny.

Stavy a cíle jsou representovány soubory výraz$, akce jsou representovány logickým popisem p edpoklad$ a d$sledk$—to umoå uje agentovi p ímé propojení mezi stavy a akcemi:

Ví-li agent, åe cílem je konjunkce zahrnující konjunkt Mít(Mléko) a åe Koupit(x) docílí Mít(x), pak také ví, åe stojí za úvahu plán, v n må je Koupit(Mléko). Nemusí uvaåovat irelevantní akce jako jsou nap .

Koupit(Šlehaþku) nebo JítSpát.

94

Další ideou plánování je skuteþnost, åe plánovaþ má volnost v p idávání akcí k plánu, kdykoliv jsou ty akce zapot ebí—na rozdíl od postupu, kde se pouåívá inkrementální sekvence zaþínající v poþáteþním stavu. Nap . agent se m$åe rozhodnout, åe pouåije Koupit(Mléko), i kdyå ješt se nerozhodl kde, jak se tam dostat, nebo co d lat pak.

Není nutná spojitost mezi po adím plánování a po adím uskuteþ ování. Prvn se stanoví rozhodnutí, která jsou “z ejmá” nebo “d$leåitá”, a pak m$åe plánovaþ redukovat faktor v tvení pro budoucí výb ry a dále redukovat nutnost sledování všech libovolných rozhodnutí.

Representace stav$ jako soubor$ logických výraz$ je podstatná, protoåe umoå uje tuto volnost výb ru: p idání akce Koupit(Mléko) má representaci stavu, kde se akce vykoná, jako Být_v(Supermarketu), coå ve skuteþnosti representuje celou t ídu stav$: s banány a bez banán$, s vrtaþkou a bez vrtaþky, apod. Prohledávací algoritmy, vyåadující kompletní popis stav$, tuto moånost nemají.

Poslední podstatnou ideou pro plánování je skuteþnost, åe v tšina þástí reálného sv ta je nezávislá na v tšin ostatních þástí. Proto je uskuteþnitelné vzít konjunktivní cíl typu “získej litr mléka Y trs banán$ Y vrtaþku...” a ešit ho pomocí strategie “rozd l a panuj” (viz níåe potíåe s hlavolamy).

První dva konjunkty vy eší sub-plán obsahující cestu do supermarketu, další sub- plán (jít do åelezá ství nebo p$jþit si u souseda) vy eší spln ní t etího konjunktu. Sub-plán zahrnující supermarket lze dále rozd lit na sub-plán koup mléka a sub- plán koup banán$. Sjednocením všech sub-plán$ dohromady je ešen celý problém. Funguje to práv z d$vodu velmi malé interakce mezi dv ma sub-plány: cesta do supermarketu nep ekáåí p$jþce od souseda, koup mléka nep ekáåí koupi banán$ (pokud samoz ejm agent nevyþerpá n jaké zdroje k provád ní akcí, nap . po koupi mléka namá na banány).

Strategie rozd l a panuj je úþinná proto, åe je tém vådy snadn jší ešit problém rozd lením na menší podproblémy. M$åe selhat v p ípadech, kdy cena kombinacíešení všech podproblém$ je p íliš vysoká. Tuto vlastnost má mnoho hlavolam$, nap . 8-hlavolam má cílový stav, který je konjunktivním cílem: p esunout

þtvereþek 1 na pozici A ; þtvereþek 2 na pozici B ; ... aå do þtvereþku 8. Z hlediska plánování lze pouåít rozd lení na nezávislé sub-problémy, ale potíå s hlavolamy je práv v obtíånosti dát sub-plány dohromady k dosaåení cíle (1 lze p esunout na A, ale 2 na B m$åe vyåadovat odsunutí 1 z A).

95

Plánování v situaþním kalkulu

Problém plánování je v tomto p ípad p edstavován logickými výrazy (pouåívá se logika prvního ádu), které popisují t i hlavní þásti problému:

Poþáteþní stav: libovolný logický výraz o situaci S0. Pro problém nákupu to m$åe nap . být:

Být_v(Doma,S0 ) Y ¬Mít(Mléko,S0) Y ¬Mít(Banány,S0) Y ¬Mít(Vrtaþka,S0)

Cílový stav: logický dotaz na vhodné situace s, nap .:

} s Být_v(Doma,s) Y Mít(Mléko,s) Y Mít(Banány,s) Y Mít(Vrtaþka,s)

Operátory: soubor popis$ akcí a pomocí logiky prvního ádu, nap .:

~ a,s Mít(Mléko,Result(a,s))	@	[(a = Koupit(Mléko) Y
		Být_v(Supermarket,s)
	Z	(Mít(Mléko,s) Y
		a =/ Vylít(Mléko))]

Pozn.: Situaþní kalkul je zaloåen na myšlence, åe akce m ní stavy: Result(a,s) pojmenovává situaci vzniklou po provedení akce a v situaci s. Pro úþely plánová- ní m$åe být uåiteþné manipulovat se sekvencemi akcí stejn jako s jednotlivými akcemi. Result'(l,s) znamená situaci vzniklou provedením sekvence akcí l poþína- je situací s. Result' je stanoven tím, åe prázdná sekvence akcí nemá vliv na situa- ci, a výsledkem neprázdné sekvence akcí je totéå jako aplikace první akce a pak zbytku akcí z poþáteþní situace.

Problém s dobrými teoretickými ešeními a formálními zápisy je þasto v tom, åe nezaruþují dobrá praktická ešení (k nimå um lá inteligence ovšem sm uje—to byl i d$vod vzniku oboru). D$vodem je nap . exponenciální þasová závislost na délce ešení (v nejhorším p ípad ), nebo existující problémy s logickou inferencí (nap . modus ponens) pro adu reálných problém$, nap . z d$vodu odlišnosti zp$- sobu uvaåování lidí od formáln logického p ístupu (problém typický pro mnoho aplikací expertních systém$). Další potíå pro um lou inteligenci zp$sobuje prob- lém tzv. semi-rozhodnutelnosti, vztahující se k výsledk$m inference v logice prv- ního ádu: lze ukázat, åe výrazy vyplývají z premis, pokud z nich vyplynuly—ale nem$åeme vådy ukázat, åe vyplynou, pokud z nich nevyplynuly (detaily viz v p íslušných kapitolách matematiky).

96

Základní representace pro plánování

Aby plánování agent$ bylo pouåitelné v praktických situacích, um lá inteligence pouåívá dva speciální p ístupy:

(1)Restrikce jazyka pro definici problém$—výsledkem je mén moånýchešení, mezi nimiå je nutno hledat.

(2)Pouåití specialisovaného algoritmu plánovaþ místo obecn zam eného algoritmu dokazování teorém$ pro nalezení ešení problému.

Oba p ístupy jsou spojeny: nový definiþní jazyk vyåaduje nový plánovací algoritmus pro zpracování popisu problému daného jazykem.

V souþasnosti se pro velkou v tšinu plánovaþ$ vyuåívá jazyk zvaný Strips (STanford Research Institute Problem Solver).

Stavy ve Strips jsou representovány konjunkcemi funkþn nezávislými základní- mi literály, tj. predikáty aplikovanými na konstatní symboly, s p ípadnou negací. Nap . poþáteþní stav problému s mlékem apod. m$åe být popsán jako

Být_v(Doma) Y ¬Mít(Mléko) Y ¬Mít(Banány) Y ¬Mít(Vrtaþka) Y ...

Popis stav$ nemusí být úplný—neúplný popis (získaný nap . agentem v ne zcela p ístupném prost edí) odpovídá mnoåin moåných kompletních stav$, pro n å by agent cht l získat úsp šný plán. Mnoho plánovacích systém$ pouåívá konvenci, která v p ípad , åe popis stavu nezmi uje daný positivní literál, povaåuje literál za negativní (v logickém programování je to “negace jako neúsp ch”).

Cíle jsou rovn å popisovány jako konjunkce literál$:

Být_v(Doma) Y Mít(Mléko) Y Mít(Banány) Y Mít(Vrtaþka).

Cíle mohou také obsahovat prom nné. Nap . cíl být v obchod , který prodává mléko m$åe být representován jako

Být_v(x) Y Prodávat(x,Mléko).

97

Prom nné mohou být existenþn kvantifikované. Zde je ale rozdíl mezi cílem pro plánovaþ a dotazem pro dokazovaþ teorém$. Plánovaþ vyåaduje sekvenci akcí, která vede ke spln nému cíli, pokud je provedena. Dokazovaþ vyåaduje údaj o tom, zda dotazovací sekvence je pravdivá za p edpokladu pravdivosti výrok$ ve znalostní bázi.

Representace akcí

Operátory Strips se skládají ze t í þástí:

Popis akce agent vrací prost edí (aby n co ud lal). Plánovaþ pouåívá popis jenom jako název moåné akce.

P edpoklad je konjunkce atom$ (positivních literál$), která íká, co musí být pravdivé p ed aplikací operátoru.

Úþinek (efekt) operátoru je konjunkce literál$ (positivních nebo negativních), která popisuje, jak se situace m ní p i aplikaci operátoru.

P íklad syntaxe pouåité pro vytvo ení operátoru Strips pro p esun z jednoho místa na druhé:

Op(Action: Go(there), Precond: (At(there) Y Path(here, there), Effect: At(there) Y ¬At(here))

Grafická notace pro Go(there). P edpoklad je nad akcí, efekt pod akcí:

At(here), Path(here, there)

Go(there)

Operátor s prom nnými se nazývá operátorové schéma, protoåe neodpovídá jediné proveditelné akci, nýbrå skupin akcí, kde kaådá je r$znou instancí (specifickým výskytem) prom nných. Obvykle lze provád t pouze operátory s úplnou moåností specifikace (plánovací algoritmy musí zajistit, aby kaådá prom nná m la hodnotu v okamåiku þinnosti plánovaþe).

98

P edpoklady musí být konjunkcí positivních literál$.

Efekt musí být konjunkcí positivních a/nebo negativních literál$.

O všech prom nných se p edpokládá, åe jsou universáln kvantifikovatelné a åe nejsou åádné p ídavné kvantifikátory (tyto poåadavky mohou být za urþitých okolností zmírn ny).

Operátor o je aplikovatelný ve stavu s pokud existuje n jaký zp$sob specifikace prom nných v operátoru o tak, åe kaådý p edpoklad o je pravdivý v s (tj. kdyå

Precond(o) / s).

Ve výsledném stavu platí všechny positivní literály v Effect(o) tak, jako platí všechny literály platné v s, krom t ch, které jsou negativními literály v Effect(o). Nap . pokud poþáteþní situace zahrnuje literály

At(Doma), Path(Doma, Supermarket), ...

pak akce Go(Supermarket) je aplikovatelná a výsledná situace obsahuje literály

¬At(Doma), At(Supermarket), Path(Doma, Supermarket), ...

Prostor situace a prostor plánu

Na obrázku stromu v tvení þinností p i poåadavku na obstarání mléka apod. je ilustrován prohledávací prostor situací ve sv t (zde sv t nakupování). Cesta tímto prostorem z poþáteþního do cílového stavu vytvá í plán pro problém nákupu.

Plánovaþ, který daný prostor prohledává z hlediska moåných situací, je plánovaþ situaþního prostoru. Zárove jde o progresívní plánovaþ, protoåe hledá sm rem vp ed z výchozího stavu do cílového. Hlavním problémem je vysoký faktor v tvení a tím velký rozm r prohledávaného prostoru.

Jednou moåností pokusit se sníåit faktor v tvení je hledání zp tným sm rem (z cíle k poþátku)—tzv. regresní plánování. Takový p ístup je moåný, protoåe operátory obsahují dosti informace k regresi z þásteþného popisu výsledného stavu k þásteþnému popisu stavu p ed aplikací operátoru. Obecn není moåné tímto zp$sobem získat kompletní popis stav$, ale to není zapot ebí.

99

Uvedený regresní p ístup je åádoucí, protoåe v typických problémech má cílový stav pouze n kolik konjunkt$, kde kaådý z nich má jenom n kolik vhodných operátor$, zatímco poþáteþní stav obvykle má mnoho aplikovatelných operátor$ (vhodným operátorem rozumíme takový, který je vhodný pro cíl pokud cíl je efektem toho operátoru).

Bohuåel zp tné hledání je komplikováno faktem, åe þasto je nutno dosáhnout konjunkce cíl$, nikoliv jen jednoho. To m$åe snadno vést k nekompletnosti, jejíå odstran ní však zase vede k vysoké neúþinnosti algoritmu.

Alternativou je hledání p es prostor plán$ místo p es prostor situací. Znamená to, åe se zaþne s jednoduchým, nekompletním plánem—tzv. þásteþný plán. Dále jsou zvaåovány cesty k rozší ení plánu, dokud není nalezen kompletní plán ešící problém. Operátory v tomto hledání jsou operátory nad plány: p idání kroku; zavedení takového po adí, které vloåí n jaký krok p ed jiný; specifikace dosud neomezené prom nné; apod. ešením je finální plán a cesta, která vede k dosaåení cíle, je irelevantní.

Operace nad plány jsou ze dvou kategorií: Zdokonalovací operátory p idávají omezení k danému plánu—jednou z moåností pohledu na þásteþný plán je jako na representaci souboru kompletních, pln omezených plán$. Operátory zdokonalo- vání eliminují n které plány z tohoto souboru, ale åádné nep idávají.

Jakýkoliv jiný, neå zdokonalovací operátor, je operátor modifikaþní. N které plánovaþe pracují tak, åe konstruují potenciáln nekorektní plány a pak je “odla ují” pomocí modifikaþních operátor$. V dalším jsou popisovány jen operátory zdokonalovací.

Representace plán$

Pro prohledávání prostoru plán$ je zapot ebí jejich representace. Jako p íklad poslouåí jednoduchý problém: obutí si páru bot. Cílem je konjunkce sloåená z

PraváBotaObuta Y LeváBotaObuta,

poþáteþní stav nemá åádné literály.

100

K dispozici jsou þty i operátory:

Op(Action: PraváBota, Precond: PraváPonoåkaObleþena,

Effect: PraváBotaObuta)

Op(Action: PraváPonoåka, Effect: PraváPonoåkaObleþena)

Op(Action: LeváBota, Precond: LeváPonoåkaObleþena,

Effect: LeváBotaObuta)

Op(Action: LeváPonoåka, Effect: LeváPonoåkaObleþena)

ýásteþný plán pro daný problém má dva kroky: PraváBota a LeváBota. Otázka je, který krok se má ud lat jako první? Mnoho plánovaþ$ pouåívá p ístup zvaný nejmenší závazek, podle n jå se má vybrat k þinnosti jen to, co je práv na starosti, a ostatní v ci nechat na pozd ji. To je pro hledání vhodná metoda, protoåe p i okamåitém výb ru n þeho, co není práv aktuální, m$åe dojít k chyb , která si pozd ji vynutí návrat. Plánovaþ s nejmenším závazkem by mohl po adí obou þinností (PraváBota a LeváBota) nechat nespecifikované.

T etím krokem je PraváPonoåka, a p i p idání k plánu je t eba zajistit, aby tento cíl byl spln n p ed zahájením pln ní cíle PraváBota. Vzhledem k levé bot to ale nehraje roli.

Plánovaþ, který representuje plány, v nichå n které kroky jsou dávány do po adí (p ed a po) vzhledem ke vzájemnému vztahu, p iþemå jiné kroky do po adí dávány nejsou, se nazývá plánovaþ þásteþného po adí.

Alternativou je plánovaþ úplného po adí, v jehoå plánech je jednoduchý seznam krok$. Plán s úplným po adím, který je odvozen z plánu P p idáním omezení na po adí, se nazývá linearisací P.

Plánovaþe musí také brát ohled na vazby prom nných v operátorech. To v problému bot a ponoåek není ukázáno, ale nap . jedním z cíl$ m$åe být

Mít(Mléko), a k dispozici nech" je akce Koupit(poloåka, obchod). Rozumným závazkem k výb ru této akce je poloåku svázat s Mlékem. Zde však není dán dobrý d$vod k vazb obchodu, takåe princip nejmenšího závazku ponechává výb r na pozd ji. Tato strategie pomáhá zbavit se špatných plán$ a vynechat celé v tve stromu. Pokud je kaådá prom nná vázána na konstantu, pak plán se nazývá pln konkretizovaný plán.

101

Plán je formáln definován jako datová struktura skládající se z t chto sloåek:

Soubor krok$ plánu. Kaådý krok je jeden z operátor$ pro daný problém.

Soubor omezení pro uspo ádání krok$. Kaådé omezení, urþující

po adí, má formu Si y Sj, coå znamená “Si je p ed Sj”, neboli krok Si musí n kdy p edcházet krok Sj (ale nikoliv bezprost edn ).

Pozn.: notace A y B y C znamená (A y B) Y (B y C).

Soubor omezení pro vazby prom nných. Kaådé omezení prom nné má formu v = x, kde v je prom nná n jakého kroku a x je bu konstanta nebo jiná prom nná.

Soubor p íþinných propojení. P íþinné propojení Si c S j znamená

“Si dosáhne c pro Sj”. P íþinná propojení slouåí k záznamu úþelu/úþel$ krok$ v plánu: zde je úþelem Si dosáhnout p edpoklad pro Sj.

P ed zahájením jakéhokoliv zlepšování popisuje jednoduše poþáteþní plán nevy ešený problém. Poþáteþní plán se skládá ze dvou krok$ Zaþátek (nebo Start) a Konec (nebo Finish), s omezením na po adí Zaþátek y Konec. Oba tyto kroky mají asociované prázdné akce, takåe kdyå dojde na provád ní plánu, jsou ignorovány. Krok Start nemá åádné p edpoklady a jeho efektem je p idání všech proposic pravdivých v poþáteþním stavu. Krok Konec má jako p edpoklad cílový stav a åádné efekty.

Plánovaþe tedy mohou zaþít s poþáteþním plánem a manipulovat s ním, dokud nedojdou k plánu, jenå je ešením.Problém boty-a-ponoåky je definován d íve uvedenými þty mi operátory a poþáteþním plánem, který lze zapsat takto:

Plan (Steps: { S1: Op(Action: Start),

S2: Op(Action: Finish,

Precond: PraváBotaObuta Y

LeváBotaObuta)},

Orderings: { S1 y S2 },

Bindings: {},

Links: {})

Následující obrázek (a) ukazuje grafickou notaci popisující plány, podobn jako u individuálních operátor$. Další obrázek (b) ilustruje poþáteþní plán pro problém boty-a-ponoåky:

102

	Zaèátek			Zaèátek
Poèáteèní		stav
Koncový		stav	LeváBotaObuta,		PraváBotaObuta
	Konec			Konec
	(a)			(b)

V þásti (a) jsou problémy definovány þásteþnými plány obsahujícími pouze kroky Zaþátek a Konec. Do poþáteþního stavu se vstupuje vlivem efektu kroku Zaþátek, cílový stav je p edpokladem kroku Konec. Omezení na po adí je ukázáno šipkami mezi bloky. V þásti (b) je poþáteþní plán pro problém boty-a-ponoåky.

Následující obrázek ukazuje plán s þásteþným uspo ádáním, který je ešením daného problému, a dále šest linearisací plánu:

Plán èásteèného poøadí:

Plán úplného poøadí:

Start

Start

Start

Start

Start

Start

Start

	LeváPono kaObleèena PraváPono kaObleèena		Pravá	Levá	Pravá	Levá	Levá	Pravá
	Levá	Pravá
			Bota	Bota	Bota	Bota	Pono .	Pono .
	Bota	Bota

Levá	Pravá	Levá	Pravá	Levá	Pravá
Bota	Bota	Bota	Bota	Bota	Bota

LeváBotaObuta, PraváBotaObuta

Konec

Konec

Konec

Konec

Konec

Konec

Konec

Zde je vid t, åe plán þásteþného uspo ádání je silný, protoåe umoå uje plánovaþi ignorovat výb ry, které nemají åádný vliv na korektnost plánu. S nar$stajícím poþtem krok$ roste poþet moåných výb r$ uspo ádání exponenciáln .

103

ešení

ešení je plán, který m$åe agent provést a který zaruþuje dosaåení cíle. Pro kontrolu, zda plán je ešením, by bylo nutno trvat na tom, åe pouze pln specifikované a zcela uspo ádané plány mohou být ešeními. To je však nevyhovující ze t í d$vod$:

(1)Pro problémy typu z posledního obrázku je plánovaþ$m p irozen jší vracet plán s þásteþným uspo ádáním neå libovoln vybírat jednu z mnoha linearisací plánu.

(2)N kte í agenti jsou schopni provád t akce paraleln , takže dává smysl umoånit ešení s paralelními akcemi.

(3)P i vytvá ení plán$, které mohou pozd ji být kombinovány s jinými plány p i ešení rozsáhlejších problém$, se vyplácí uchovávat flexibilitu poskytovanou þásteþným uspo ádáním akcí.

Proto se umoå ují þásteþn uspo ádané plány jako ešení p i pouåití jednoduché definice: ešení je kompletní a konsistentní plán:

Kompletní plán je ten, v n må kaådý p edpoklad kaådého kroku je dosaåen n jakým jiným krokem. Krok dosáhne p edpokladu, pokud p edpoklad je jedním z efekt$ kroku a pokud åádný jiný krok nem$åe zrušit platnost p edpokladu. Formáln ji vzato, krok Si dosáhne p edpokladu c kroku Sj pokud:

1.Si y Sj a c Effects(Si);

2.neexistuje åádný krok Sk takový, åe (¬c) Effects(Sk), p iþemå platí Si y Sk y Sj v n které linearisaci plánu. "

Konsistentní plán je ten, v n må nejsou åádné kontradikce v uspo ádání nebo vázání prom nných. Kontradikce vznikne, kdyå platí

jak Si y Sj tak Sj y Si nebo platí jak v = A a v = B (pro dv r$zné konstanty A a B). Zárove platí, åe jak y tak = jsou transitivní, takåe

nap . plány s S1 y S2, S2 y S3 a S3 y S1 jsou nekonsistentní. "

ýásteþný plán z posledního obrázku je ešením, protoåe všechny p edpoklady jsou dosaåeny. Z uvedených definic je z ejmé, åe libovolná z linearisací ešení je také ešením. Agent m$åe provád t kroky v libovolném po adí s omezeními a vådy má zaruþeno dosaåení cíle.

104

P i þásteþném regresívním plánování plánovaþ prohledává prostor plán$. Zaþíná s poþáteþním plánem, kde jsou representovány kroky zaþátku a konce, a pak iteraþn p idává jednotlivé kroky. Pokud je dosaåeno nekonsistentního plánu, plánovaþ se vrátí a zkouší jinou v tev v prohledávaném prostoru.

Aby bylo hledání sm rováno k poåadovanému cíli, plánovaþ pouze uvaåuje p idání krok$, které slouåí k dosaåení p edpokladu, který doposud nebyl spln n.

Pozn.: Je z ejmé, åe plánovaþ musí udråovat záznam o cest , aby se mohl v p ípad nutnosti vracet.

P íklad vy ešení problému s mlékem, banány a vrtaþkou (cílem je mít všechno doma):

Start

At(Home)

Go(HWS)

At(HWS) Sells(HWS,Drill)

Buy(Drill)

At(HWS)

Go(SM)

At(SM) Sells(SM,Milk)	At(SM) Sells(SM,Ban.)
Buy(Milk)	Buy(Ban.)

At(SM)

Go(Home)

Have(Milk) At(Home) Have(Ban.) Have(Drill)

Finish

(At(home) je doma, Go(HWS) je Jdi_do(äelezá ství), tj. HardWare Shop, At(x) je být v x, SM je SuperMarket, Sells(SM,Milk) je Prodává(Supermarket,Mléko) apod., Buy(Drill) je Kup(Vrtaþku) apod.). Jediná nejednoznaþnost v plánu je moånost zvolit jakékoliv po adí Buy(Milk) a Buy(Bananas), protoåe na tom po adí nezáleåí vzhledem k míst nákupu.

105

Znalostní inåenýrství pro plánování

Metodologii ešení problém$ s plánováním lze vyjád it takto:

1.Definice problému.

2.Definice podmínek, operátor$ a objekt$.

3.Zakódování operátor$ do domény.

4.Zakódování popisu výskytu specifického problému.

5.P edloåení problému plánovaþi a získání plán$.

P íklad pro tzv. problém blok$:

1.Definice problému: doména obsahuje soubor blok$ (kostek) na stole. Kostky mohou být kladeny na sebe, ale pouze jedna urþitá kostka m$åe být umíst na na jinou. Ruka robota m$åe zvednout n jakou kostku a p esunout ji do jiné polohy (na st$l nebo na jinou kostku). V jednom þasovém kroku m$åe být manipulováno s jednou kostkou, nelze manipulovat s kostkou, která má další kostku/kostky na sob . Cílem je vådy vybudovat jeden nebo více sloupk$ z kostek, p iþemå

sloupky jsou popsány pomocí toho, jaké kostky jsou na jiných kostkách—nap . cílem m$åe být vytvo it dva sloupky, jeden s kostkou A na kostce B a druhý s kostkou C na D.

2.Definice podmínek, operátor$ a objekt$: Objekty v této domén jsou kostky a st$l. Representovány jsou konstantami. K indikaci, åe kostka b je na x (x je bu jiná kostka nebo st$l) se pouåije On(b,x). Operátor pro p esun kostky b z pozice na x na y je Move(b,x,y).

Jednou z podmínek p esunu b je, åe na ní není åádná jiná kostka, tedy

vlogice prvního ádu: ¬}x On(x,b) nebo alternativn ~x ¬On(x,b). Vzhledem k representaci plán$ (viz výše) je zapot ebí vytvo it predikát representující fakt, åe åádná kostka není na b a pak zajistit, åe operátory korektn tento predikát zpracují—nap . zde Clear(x) bude znamenat, åe na x není nic.

3.Operátory: operátor Move p esune jednu kostku b z x na y pokud na

ba na y není nic; jakmile je p esun hotový, x je volné (nic na n m není), ale y jiå nadále volné není (je na n m kostka). Formáln jší zápis operátoru Move:

106

Op(Action: Move(b,x,y),

Precond: On(b,x) Y Clear(b) Y Clear(y),

Effect: On(b,y) Y Clear(x) Y ¬On(b,x) Y ¬Clear(y))

Zde ale operátor nezpracovává Clear správn , pokud x nebo y je na stole. Pokud x = Table, výsledkem je Clear(Table), ale st$l nem$åe být zbaven kostek. Pokud y = Table, pak má podmínku Clear(Table), ale st$l nemusí být bez niþeho, aby se na n j dala umístit kostka.

K vy ešení uvedených potíåí se zavede další operátor MoveToTable pro p esun kostky b z x na Table:

Op(Action: MoveToTable(b,x),

Precond: On(b,x) Y Clear(b),

Effect: On(b,Table) Y Clear(x) Y ¬On(b,x))

K tomu je nutno zavést ješt interpretaci Clear(x) ve smyslu “na x je volno a lze tam uloåit kostku”. Clear(Table) pak vådy bude souþástí poþáteþní situace a je korektní, åe Move(b,Table,y) má jako výsledek

Clear(Table).

Jedinou nedokonalostí je nyní fakt, åe nic nem$åe zabránit plánovaþi v pouåití Move(b,x,Table) místo MoveToTable(b,x). V p ípad usku- teþn ní to vede k v tšímu prostoru prohledávání, neå je nutno, ale nevede to k nekorektním odpov dím. Lze to odstranit zavedením dalšího predikátu Block a p idat Block(b) Y Block(y) k podmínkám v Move (zajistit, åe jak b tak y jsou kostky, nikoliv p ipustit, åe by se pro y mohlo jednat taky o st$l zpracovávaný jako kostka, p estoåe má urþité odlišnosti—nap . m$åe na n m být více kostek, na kostce ale nikoliv).

Dalším problémem by mohla být vcelku neopodstatn ná operace Move(B,C,C), která by m la kontradiktorické výsledky. Obecn se tyto problémy ignorují, protoåe nemají åádný vliv na vytvo ené plány (p esun kostky B z C na C je v podstat prázdná operace). Bylo-li by nutno zajistit, aby k tomu nedocházelo, pak by se do podmínek musely zavést nerovnosti: b =/ x =/ y, tj. všechny objekty jsou r$zné.

107

P íklad pro tzv. Shakeyho problém:

P$vodní program v Strips byl navråen k ízení robota jménem Shakey (jméno pochází z faktu, åe jeho motory ho p i pohybu þinily pon kud nestabilním—to shake = kymácet se, t ást se). Robot Shakey byl vyvinut jako souþást robotického projektu ve SRI (Stanford Research Institute) v Kalifornii poþátkem 70. let a potuloval se v institutu po místnostech a chodbách. V tšina Shakeyho þinností byly simulace, ale obþas se skuteþn pohyboval v prostorách institutu s cílem vzít n co nebo p emístit n co. Obrázek ukazuje Shakeyho sv t, který se skládal ze þty místností, podél nichå vedla chodba spojená s místnostmi dve mi. Shakeyho úkolem bylo se pohybovat z místnosti do místnosti, posunovat pohyblivými objekty (krabicemi), vylézt na pevný objekt a slézt dol$ (op t krabice), a zapnout/vypnout sv tlo v místnosti:

Ls4

Místnost 4

Dveøe 4

Ls3

Místnost 3

Dveøe 3

Shakey

Chodba

Ls2

Místnost 2

Dveøe 2

Box3			Ls1
		Box2

Místnost 1		Dveøe 1
Box4	Box1

Pozn. 1: Ls je zapínaþ/vypínaþ osv tlení místnosti (light switch).

Pozn. 2: Shakey nebyl mechanicky dost obratný ke skuteþnému lezení po krabi- cích a ovládání vypínaþe sv tla, ale Strips byl schopen vytvo it plány.

108

Pro Shakeyho lze urþit následující literály a operátory:

1.Jdi ze souþasné pozice na jinou pozici y: Go(y).

Podmínka At(Shakey,x) stanovuje okamåitou pozici a je vhodné, aby x i y bylo v téåe místnosti r: In(x,r) Y In(y,r). Aby bylo moåné napláno- vat cestu z jedné místnosti do druhé, povaåují se tytéå dve e za sou- þást obou místností z hlediska In.

2.Posu objekt b z místa x na místo y: Push(b,x,y).

Zde mohou op t být x i y v téåe místnosti. Zavést je nutno predikát Pushable(b), tj. p emístitelnosti, ale jinak je situace obdobná Go.

3.Vylez na box b: Climb(b).

Je nutno zavést predikát On (kde robot je) a konstantu Floor (podla-

ha), a zajistit, aby podmínka pro Go byla On(Shakey,Floor), tj. aby robot lezl z podlahy na krabici (a resp. zp t), nikoliv nap . skákal z krabice na krabici. Pro Climb(b) musí být podmíka, åe Shakey je At na tomåe míst jako je b, a b musí být tzv. Climbable (tj. b je p edm t, na n jå lze vylézt, tedy vylezitelný).

4.Slez dol$ z boxu b: Down(b).

V principu zrušení efektu vylezení Climb.

5.Zapni sv tlo: TurnOn(ls).

Vzhledem k tomu, åe Shakey na vypínaþ ze zem nedosáhl, musel pro rozsvícení sv tla v místnosti vylézt na krabici b u vypínaþe ls.

6.Vypni sv tlo: TurnOff(ls).

Obdoba Zapni. Jazyk plánování by musel mít k dispozici podmínku pro urþení stavu sv tla, aby se dalo urþit, zda sv tlo je zapnuto nebo vypnuto kv$li schopnosti p epínání z jednoho stavu do druhého.

V jazyce Strips bylo nutno pro kaådý box p idat individuální literál do poþáteþního stavu, zatímco v situaþním kalkulu se napíše axiom, který íká, åe kaådý box lze posunout a na kaådý lze vylézt. Rovn å by bylo zapot ebí zaþlenit kompletní mapu sv ta v poþáteþním stavu—pomocí term$, které objekty jsou v které místnosti, tj. pomocí In. Stejn by se popsalo pomocí At, kde který objekt p esn je.

Jazyk Strips (a jemu obdobné) umoå ují representovat jednoduché domény po- mocí operátor$ Strips, ale návrh mnoåiny správných a pot ebných operátor$ a predikát$ není v$bec snadný.

109

Praktické plánování

V této èásti bude zmínka o existujících plánovaèích, které jsou používány ve

složitých, reálných doménách.

Montáž, integrace a verifikace kosmické lodi

European Space Agency používá plánovaè nazvaný Optimum-AIV na pomoc montáži, integraci a verifikaci kosmických lodí (AIV = Assembly, Integration, and Verification). Systém se používá pro generování plánù a monitorování jejich provádìní. Bìhem monitorování systém upozoròuje uživatele na pøipravované èinnosti a je schopen navrhovat úpravy plánu, když je nìjaká èinnost provedena pozdì, zrušena, nebo se objeví nìco neoèekávaného. Je to zejména schopnost systému zmìnit plán, co jej èiní principiálnì význaèným. Systém sám neprovádí plány; ty jsou provádìny lidmi pomocí standardních konstrukèních a testovacích zaøízení.

V podobnì složitých projektech se obecnì používají plánovací nástroje pocháze- jící z oblasti operaèního plánování, napø. diagramy PERT nebo metoda kritické cesty. Tyto nástroje v zásadì používají jako vstup ruènì navržený kompletní plán rozdìlený na sub-plány v poøadí rozdìleném na èásti a generují pro to optimální rozvrh èinností. Akce jsou považovány za objekty, které vyžadují nìjaký èas a mají omezení vzhledem k poøadí èinností; jejich efekty se neuvažují. Tím se lze vyhnout použití znalostního inženýrství a pro jednorázové problémy to mùže obyèejnì být zcela pøimìøené øešení. Avšak pro vìtšinu praktických aplikací exis- tuje mnoho souvisejících problémù k øešení, takže se obvykle vyplácí popis domény a pak automatické generování plánù.

To je dùležité zejména bìhem provádìní plánù—pokud krok plánu selže, je oby- èejnì nutno plán rychle zmìnit (upravit), aby se projekt znovu uvedl v život. Dia- gramy metody PERT neobsahují pøíèinná propojení a další informaci potøebnou pro to, aby bylo zjevné, jak zmìnit plán, a lidmi provádìné zmìny jsou èasto pøí- liš pomalé.

110

Úspìch systémù umìlé inteligence z reálného svìta vyžaduje integraci do prostøe- dí, v nìmž jsou aktivní. Plánovaè musí být schopen pøístupu do existujících data- bází s informacemi o projektu, nezávisle na formì v níž mohou informace být.

Zároveò representace vstupù a výstupù plánovaèe by mìly být ve formì, která je jak expresívní, tak snadno srozumitelná uživateli. Døíve (velmi struènì) zmínìný jazyk Strips je pro doménu AIV nedostaèující, protože nedokáže vyjádøit ètyøi základní koncepty:

1.Hierarchické plánování: Je zjevné, že vypuštìní kosmické lodi je mnohem složitìjší než nakupování potravin v obchodì. Jednou ze schùdných cest zvládnutí složitosti je specifikace plánù na rùzných úrovních detailù.

Plán na vrcholné úrovni mùže zahrnovat: pøíprava raketového stupnì, pøíprava kosmické kabiny,

naložení kosmické lodi potøebnými vìcmi, vypuštìní.

K tomu mùže být velké množství meziúrovní pøed tím, než se dojde k úrovni zcela konkrétních provádìcích akcí:

vlož matici A do otvoru B a sešroubuj se šroubem C.

Pøidání schopnosti representovat hierarchické plány mùže tvoøit rozdíl mezi uskuteènitelnou a neuskuteènitelnou akcí a mùže zpùsobit snadnìjší porozumìní výslednému plánu. Také pomáhá dovolit uživa- teli, aby poskytl plánovaèi vodítko ve formì èásteènì specifikované- ho, abstraktního plánu, pro nìjž plánovaè doplní detaily.

2.Komplexní podmínky: Operátory Strips jsou v principu proposiè- ní—umožòují promìnné, ale jejich použití je velmi limitované. Neexi- stuje universální kvantifikace, bez níž není možno vyjádøit fakt, že operátor Launch (Vypuštìní) zpùsobí pøemístìní všech objektù lodi na obìžnou dráhu. Podobnì tomu, operátory Strips jsou nepodmínìné: nelze vyjádøit fakt, že pokud všechny systémy jsou vypuštìny, Launch umístí loï na obìžnou dráhu, jinak loï skonèí v oceánu.

111

3.Èas: Jazyk Strips je založen na situaèním kalkulu, proto pøedpo- kládá, že všechny akce se vyskytnou bezprostøednì a že každá akce následuje po nìjaké jiné bez pøerušení. Problémy reálného svìta vyža- dují lepší model èasu—musí representovat fakt, že projekty mají ko- neèné termíny (napø. loï musí být vypuštìna 17. èervna), akce nìjaký èas trvají (testování montáže XYZ trvá 6 hodin) a jednotlivé kroky plá- nu vyžadují èasová okna (napø. stroj pro testování montáže XYZ je k dispozici od 1. kvìtna do 1. èervna vyjma víkendù, ale musí se re- servovat týden dopøedu). Tradièní techniky operaèního plánování mì- ly jako hlavní pøínos uspokojování èasových omezení pro kompletní plán rozdìlený na èásti.

4.Zdroje: Projekt má normálnì rozpoèet, který nelze pøekroèit, takže plán musí být omezený na spotøebu èástky, která je k dispozici. Po- dobnì existují limity na poèet pracovníkù k dispozici a na poèet mon- tážních a testovacích stanic. Omezení zdrojù se mùže týkat vìcí po- tøebných v urèitý èas (napø. lidé) nebo celkového použitelného množ- ství (napø. peníze). Popis akcí proto vyžaduje zahrnutí spotøeby a vy- tváøení zdrojù, stejnì jako plánovací algoritmy musí být schopny zpra- covat úèinnì omezení zdrojù.

Optimum-AIV je založen na plánovací architektuøe z r. 1991, zvané O-Plan, která umožòuje používat jazyka se znaènou možností výrazù pro representaci èasu, zdrojù a hierarchických plánù. Rovnìž pøijímá heuristiky pro vedení vyhle- dávání a zaznamenává dùvody každého výbìru, což usnadòuje pozdìjší úpravy plánu, pokud je zapotøebí. O-Plan byl použit na mnoho problémù, napø. opatøo- vání software v Price Waterhouse, plánování procesu montáže zadní osy u aut zn. Jaguar, a kompletní plánování produkce továrny Hitachi.

Plánování èinnosti pracovištì

Problémy øešené rùznými pracovišti spoèívají v obstarání surovin a dílù a jejich smontováním do koneèných výrobkù. Problém lze rozdìlit na plánovací úlohu (rozhodnutí, které montážní kroky budou uskuteènìny) a rozvrhovou úlohu (roz- hodnutí, kdy a kde bude každý krok uskuteènìn). V mnoha výrobních zaøízeních se plánuje manuálnì a rozvrh se dìlá pomocí automatizovaného nástroje.

112

V Hitachi se O-Plan používá v plánovacím a rozvrhovém systému zvaném

Tosca. Typický problém zahrnuje výrobu 350 rùzných výrobkù, 35 montážních strojù a pøes 2000 rùzných operací. Plánovaè poskytuje rozvrhy na 30 dní pro osmihodinové smìny. Obecnì Tosca sleduje plán rozdìlený na èásti, s nejmen- ším závazkem. Umožòuje také “nízkozávazková” rozhodování: volby, které kladou omezení na plán nebo na nìjaký jeho konkrétní krok. Napø. systém mùže vybrat rozvrh akce pro urèitou tøídu strojù bez konkretizace stroje.

Továrny s menší diversitou výroby èasto sledují pevný plán, ale stále potøebují automatizované rozvrhování. Systém ISIS z r. 1984 byl navržen speciálnì pro rozvrhování a poprvé testován na výrobì èástí turbíny firmy Westinghouse.

Továrna produkuje tísíce rùzných lopatek turbín a pro každý typ existuje jeden èi více plánù zvaných smìrování procesu. Pøi obdržení objednávky je vybrán jeden z plánù a je pro nìj vytvoøen èasový rozvrh. Èas závisí na kritiènosti objednávky: zda jde o urgentní výmìnu lopatky èinného zaøízení, plánovanou údržbovou souèástku se spoustou èasu, avšak s nutností pøesnì splnit datum, nebo prostì objednávka zásob k vytvoøení reservy.

Tradièní metody plánování, jako PERT, jsou schopny najít vyhovující poøadí krokù vzhledem k èasovým omezením, ale ukazuje se, že lidé-plánovaèi použí- vající PERT spotøebují 80-90% svého èasu na komunikaci s pracovníky o tom, co jsou skuteèná omezení. Úspìšný automatický plánovaè potøebuje být schopen representovat a zdùvodnit tato pøídavná omezení. Dùležité faktory zahrnují cenu surovin, které jsou k dispozici, hodnotu vyrobeného, ale zatím neprodaného zboží, pøesné pøedpovìdi budoucích potøeb, a minimální narušení existujících postupù. ISIS používá hierarchické hledání s minimálním závazkem pro nalezení vysoce kvalitních plánù, které uspokojují všechny uvedené požadavky (minimální závazek—viz døíve uvedený popis representace plánù—v podstatì odklad ne právì v daném okamžiku aktuálních záležitostí do jiné fáze).

Plánování kosmických letù

Plánovací a rozvrhové systémy jsou v této oblasti využívány rozsáhle, a to jak pro plánování výprav lodí, tak i pro jejich konstrukci. Dùvodem je pøedevším to, že kosmické lodì jsou mimoøádnì nákladné a také nìkdy obsahují lidi, což v pøí- padì havárie mùže mít extrémnì vysokou cenu škody a pøinést nenahraditelné ztráty. Kromì toho se lety uskuteèòují v prostoru neobsahujícím mnoho dalších agentù, kteøí by mohli narušit oèekávané výsledky.

113

Plánovaèe byly a jsou používány pozemními týmy pro Hubblùv teleskop a nej- ménì pro tøi lodì: Voyager, UOSAT-II a ERS-1. V každém pøípadì je cílem or- ganizace pozorovacího zaøízení, pøenašeèù signálù a kontrola mechanismù pro nastavení a udržování výšky a rychlosti, aby se maximalisovala informace získa- ná z pozorování za pøedpokladu dodržování omezení na èas a energii.

Plánování misí èasto zahrnuje velmi složitá èasová omezení, zejména ty mise, které obsahují periodické události. Napø. ERS-1 (satelit vypuštìný z European Earth Resource Observation) uskuteèní jeden obìh Zemì za 100 minut a do téhož bodu se vrátí každých 72 hodin. Pozorování každého bodu na zemském povrchu mùže být provedeno v libovolném z mnoha èasových okamžikù, navzájem oddì- lených 72 hodinami, ale v jiných èasech nikoliv. Satelity mají omezení zdrojù vý- stupní energie—nemohou pøekroèit pevnì stanovené maximum a musí se zajistit, aby nevyèerpaly pøíliš mnoho energie za èasovou periodu.

Satelity lze považovat za typ pracovištì s plánovaným rozvrhem èinností, kde teleskopy a další zaøízení jsou výrobní stroje a pozorování jsou výrobky. Hubblùv teleskop je dobrým pøíkladem potøeby automatického plánování a rozvrhování. Po svém vypuštìní v dubnu 1990 bylo objeveno, že primární zrcadlo má chybu v nastavení ohniska. Pomocí Bayesových technik pro rekonstrukci obrazu byl pozemský tým schopen chybu kompensovat do stupnì, který umožnil pøedávání nových a dùležitých informací o Plutu, o gravitaèních èoèkách, o supernovì, atd. V r. 1993 astronauti z raketoplánu opravili vìtšinu problémù primárního zrcadla, èímž otevøeli nové možnosti pozorování. Pozemní tým neustále objevuje více možností, které má èi nemá HST k dispozici a bylo by zcela nemožné aktualiso- vat plány pozorování bez automatických nástrojù.

Kterýkoliv astronom mùže pøedložit žádost. Žádosti jsou dìleny na vysokoprio- ritní (70% pozorovacího èasu), nízkoprioritní (podle èasových možností) a zamítnuté. Návrhy pøicházejí v poètu cca 1 za den, což znamená, že je jich více, než je možno uskuteènit. Každý návrh obsahuje specifikaci, který pozorovací nástroj by mìl být namíøen na urèitý nebeský objekt a jaký druh snímku by se mìl udìlat. Nìkterá pozorování lze udìlat kdykoliv, jiná závisejí na faktorech jako postavení planet a zda HST je v zemském stínu. Existují unikátní omezení pro tuto doménu—napø. astronom mùže žádat o periodická pozorování quasaru (velmi vzdálená raná vývojová fáze galaxie) po nìkolik mìsícù nebo let za stejných podmínek stínu Zemì.

114

Plánovací systém HST je rozdìlen na dvì èásti. Dlouhodobý plánovaè SPIKE prvnì dìlá rozvrh pozorování v segmentech po jednom týdnu. Heuristikou je pøiøazování vysokoprioritních návrhù tak, aby mohly být všechny provedeny, dokud zbývá nejménì 20% kapacity. To se dìlá asi rok pøedem. Mnohaletý rozvrh s pøibližnì 5000 pozorováními lze vytvoøit za ménì než hodinu, takže zmìna plánu je snadná. Po naplánování každého segmentu se použije krátkodobý plánovaè SPSS, jenž dìlá detailní plánování pro každý segment a naplòuje èas mezi vysokoprioritními úlohami mnoha nízkoprioritními podle možností. Systém rovnìž vytváøí pøíkazy pro nastavení polohy základny tak, aby se pozorování mohla provést. Kontroluje proveditelnost návrhù a detailních rozvrhù mnohem rychleji, než dokáží lidé-experti.

Budovy, letadla a pivovary

SIPE (System for Interactive Planning and Execution monitoring—systém pro interaktivní plánování a sledování výkonu èinností) byl prvním plánovaèem, který se zabýval problémem zmìny plánu, a také prvním, který použil nìkteré dùležité kroky vùèi expresívním operátorùm. Je podobný systému O-Plan v rozsahu vlastnosti a aplikovatelnosti. Byl použit v nìkterých demonstraèních projektech pro nìkolik domén, vèetnì plánování operací na palubì letadla a plánování výroby pro jeden pivovar v Austrálii. Jiná studie použila SIPE pro plánování konstrukce výškových budov—jedna z nejsložitìjších domén, do které se plánovaè pustil.

SIPE umožòuje deduktivním pravidlùm operovat nad stavy, takže uživatel ne- musí specifikovat všechny relevantní literály jako výsledky pro každý operátor. Tento systém je aplikovatelný na široký rozsah domén, ale jeho obecnost je spojena s velkými náklady. Napø. v doménì konstrukce budov se zjistilo, že

SIPE potøebuje èas úmìrný O(n2.5) pro n-poschoïovou budovu. Z toho plyne vysoký stupeò interakce mezi poschodími, pøièemž ve skuteènosti je ten stupeò mnohem nižší: pøi sledování linie stavby od zemì nahoru a zajištìní toho, aby výtahové šachty byly propojeny je možné získat výkonnost mnohem bližší složitosti O(n).

Uvedené pøíklady poukazují na souèasnou ideu plánovacích systémù. Jsou dost dobré pro modelování složitých domén, ale dosud nebyly zcela prakticky pøijaty mimo omezený poèet pilotních projektù. Je zapotøebí dále zvýšit stupeò flexibili- ty a výkonnosti, aby se tyto systémy staly bìžným nástrojem.

115

Hierarchická dekomposice

Problém s nákupem, popsaný døíve, lze vyøešit použitím vhodných metod tak, že je získáno øešení na pomìrnì vysoké úrovni abstrakce (pro agenta). Napøíklad plán typu:

[Go(Supermarket), Buy(Milk), Buy(Bananas), Go(Home)]

je dobrý popis toho, co dìlat, na vysoké úrovni, ale je velmi daleko od toho, co je zapotøebí agentovi pøedat formou instrukcí do jeho efektorù. Pro agenta je to ne- dostateèné z hlediska toho, co by mìl skuteènì udìlat.

Na druhé stranì by nízko-úrovòový plán typu:

[Forward (1cm), Turn (1deg), Forward (1cm), ...]

obsahoval mnoho tisíc krokù a øešení problému nákupu by bylo nesmírnì dlouhé. Zejména by vznikl problém extrémnì velikého prostoru plánù velké délky a je pravdìpodobné, že by metody hledání nenašly øešení v rozumném èase.

Uvedené dilema se v praktických plánovaèích øeší pomocí myšlenky zavedení hierarchické dekomposice, která vychází z dekomposice abstraktních operáto- rù na skupinu krokù, které vytváøejí plán, který implementuje operátor.

Jako pøíklad lze uvážit problém stavby domu. Abstraktní operátor Build(House)

(postav dùm) lze rozložit na plán, který se skládá za ètyø krokù: Obtain Permit

(získej povolení), Hire Builder (najmi stavitele), Construction (stavba), a Pay Builder (zapla• staviteli).

Kroky ukázaného vysokoúrovòového plánu lze dále rozložit na ještì specifiètìjší plány. Na obrázku je znázornìna dekomposice kroku stavby domu. V dekomposici lze pokraèovat tak dlouho, až je dosažena nejnižší úroveò typu

Hammer(Nail) [Zatlouci(Høebík)]. Plán je kompletní v okamžiku, kdy je každý krok ve formì primitivního operátoru, tj. operátoru, který mùže být pøímo proveden agentem. Hierarchická dekomposice je nejúèinnìjší, pokud lze operátory dekomponovat nìkolika zpùsoby. Napø. operátor Build(Walls), èili

Postav(Zdi), lze rozložit na plán zahrnující døevo, cihly, beton nebo vinyl (zdi lze stavìt z rùzného materiálu a plán by to mìl respektovat).

116

K uskuteènìní nastínìné myšlenky dekomposice je nutno udìlat dvì vìci:

!Do jazyka typu Strips dát rozšíøení, která umožòují neprimitivní operátory.

!Modifikace plánovacích algoritmù tak, aby bylo možné nahradit neprimitivní operátory jejich dekomposicemi.

117

Rozšíøení jazyka

Pro zaèlenìní hierarcické dekomposice je zapotøebí pøi popisu každé problémové

domény upravit dvì vìci:

!Rozdìlení souboru operátorù na primitivní a neprimitivní. V doménì stavby domù je Zatlouci(Høebík) operátor primitivní a Postavit(Dùm) neprimitivní. Obecnì je rozdíl mezi primitivními a neprimitivními operátory relativní a záleží na agentovi, který bude plán vykonávat. Pro dodavatele stavby je operátor typu Namontovat(PodlahováPrkna) primitivní (protože pouze objedná dìlníka k montáži podlahy), pro dìlníka neprimitivní (a pro nìj bude primitivní Zatlouci(Høebík)).

!Pøidání souboru dekomposièních metod. Každá metoda je výraz typu

Decompose(o,p), což znamená, že neprimitivní operátor, který je spojen s o, mùže být rozložen do plánu p. Dekomposice Stavby

(Construction) z pøedchozího obrázku:

Decompose(Construction,

Plan(Steps:{S1: Build(Foundation), S2: Build(Frame),

S3: Build(Roof), S4: Build(Walls),

S5: Build(Interior)}

Orderings: {S1— S2 — S3 — S5, S2 — S4 — S5},

Bindings: {},

Links: {

}))

Dekomposièní metoda je v podstatì procedura nebo makro definující operátor. Musí být zajištìno, aby dekomposice byla korektní implementací operátoru. Platí, že plán p korektnì implementuje operátor o, pokud se jedná o kompletní a konsistentní plán pro daný problém k dosažení úèinkù o za pøedpokladù pro o:

!p musí být konsistentní (tj. neexistuje žádná kontradikce v uspoøádá- ních nebo vazbách promìnných).

!Každý úèinek (efekt) operátoru o musí být prosazen nejménì jedním krokem plánu p (a není popøen nìjakým jiným, pozdìjším krokem plánu p).

!Každá podmínka krokù v p musí být dosažena nìjakým krokem v p nebo být jednou z podmínek operátoru o.

118

Tím je zaruèeno, že je možné nahradit neprimitivní operátor jeho složkami (dekomposicemi) a vše je správnì navázáno na sebe. Je samozøejme vždy nutné zkontrolovat možná ohrožení pocházející z interakcí mezi novì zavedenými kroky s podmínkami a již existujícími kroky s podmínkami—není ale nutno si dìlat starosti s interakcemi mezi kroky obsaženými v samotné dekomposici (ta musí být sama o sobì udìlána zcela korektnì).

Za pøedpokladu, že není pøíliš mnoho interakcí mezi rùznými èástmi plánu, hierarchické plánování umožòuje vybudovat velmi složité plány kumulativnì z jednodušších sub-plánù. Je také umožnìno vygenerovat plány, uložit je, a pak znovu použít v pozdìjších plánovacích problémech.

Následující obrázek ukazuje detailnìjší diagram pøíkladu dekomposice kroku plánu v kontextu rozsáhlejšího plánu:

Analýza hierarchické dekomposice

Hierarchiská dekomposice zde byla ukázána struènì, ve své základní èásti. Je založena na obdobné myšlence jako použití maker nebo procedur v programo- vání—umožnit programátorovi nebo znalostnímu inženýrovi specifikaci problé- mu po èástech majících rozumnou velikost. Èásti mohou pak být hierarchicky kombinovány pro vytváøení velkých plánù, aniž by vznikaly enormní kombinato- rické náklady spojené s konstrukcí z primitivních operátorù.

119

Pøedpokládejme, že existuje zpùsob vzájemného propojení ètyø abstraktních operátorù k postavení domu (viz obrázek z podkapitoly Hierarchická dekompo- sice). Tento zpùsob se nazývá abstraktní øešení—konsistentní a kompletní plán obsahující abstraktní operátory. Nalezení malého abstraktního øešení (pokud exi- stuje), by nemìlo být pøíliš nároèné. Pokraèování tohoto procesu by mìlo vést k dosažení primitivního plánu bez pøílišného navracení se zpìt po cestách hledání.

Zde se ovšem pøedpokládá, že hledání abstraktního øešení—a odmítání jiných abstraktních plánù jako nekonsistentních—je úèelné. Mìly by platit tyto vlast- nosti:

!Je-li plán p abstraktním øešením, pak existuje primitivní øešení, pro nìž je p abstrakcí. Pokud to skuteènì platí, pak jakmile je nalezeno abstraktní øešení, lze odstranit z vyhledávacího stromu všechny ostatní abstraktní plány.Tato vlastnost se nazývá øešení smìrem dolù.

!Je-li abstraktní plán nekonsistentní, pak neexistuje primitivní øešení, pro nìž je ten plán abstrakcí. Pokud to skuteènì platí, pak lze odøíznout veškeré potomky libovolného nekonsistentního abstraktního plánu. Tato vlastnost se nazývá øešení smìrem nahoru, protože to rovnìž znamená, že všechny kompletní abstrakce primitivních øešení jsou abstraktními øešeními.

Tyto dvì vlastnosti lze znázornit graficky:

Každý uzel representuje celý plán (nikoliv pouze jeden krok), každá hrana representuje dekomposièní krok, v nìmž je abstraktní operátor expandován.

120

V koøeni stromu je velmi abstraktní plán, v listech jsou plány s pouze primitivní- mi kroky. Uzly s tuènì znázornìnými obrysy jsou (abstraktními) øešeními. Uzly s teèkovanými obrysy jsou nekonsistentní (tj. nejsou bezesporné). Plány oznaèené

X nemusí být plánovacím algoritmem zkontrolovány. Mohou být (hledáním zleva doprava) odøíznuty.

Pøedpokládejme pro pøíklad jednoduchý model prohledávaného prostoru. Nech• existuje nejménì 1 øešení s n primitivními kroky a dále, že možná ohrožení a omezení lze øešit v zanedbatelném èase—vše, co bude nutno uvažovat, je pouze èas potøebný k výbìru správné množiny krokù. Obrázek ukazuje prostor hledání z hlediska parametrù b, s, a d:

Øešení bude mít n = sd krokù (zde je n = 64). Pøedpokladem je 1/b dekomposic vedoucích k øešení.

121

Nehierarchický plánovaè by vygeneroval plán s n-kroky, pøièemž by pro každý krok vybíral z b možností (pøedpokládejme zde, že poèet dekomposic pro každý neprimitivní krok, b, je tentýž jako poèet aplikovatelných nových operátorù pro podmínku primitivního kroku).

V nejhorším pøípadì je tedy složitost O(bn). Pro hierarchické plánovaèe lze po- užít strategii hledání pouze tìch dekomposic, které vedou k abstraktním øešením

(v ukázaném zjednodušeném modelu na obrázku je právì 1 z každých b dekom- posic øešením—v mnohem realistiètìjších modelech je zapotøebí uvážit, co dìlat, když je poèet øešení nulový nebo je jich více než 1).

Plánovaè musí prohlédnout sb krokù v hloubce d = 1. V hloubce d = 2 je to dalších sb krokù pro každý dekomponovaný krok, ale zde musí dekomponovat jen 1/b z disponibilních krokù pro celkové množství bs2. Celkový poèet uvažovaných plánù je tedy

Rozdíl mezi nehierarchickým a hierarchickým plánovaèem je v nutnosti prohlédnout 3×1030 plánù (nehierarchický) oproti 252 (hierarchický).

Øešení smìrem vzhùru a dolù se jeví jako enormì výkonná—pokud ovšem není žádná ze tøí vlastností pro o (uvedených v podkapitole o rozšíøení jazyka) garanto- vána, pak hierarchický plánovaè nebude lepší než nehierarchický v nejhorším pøí- padì (v prùmìru mùže být lepší).

Jako shrnutí lze øíci, že pùvodní plánovací jazyk umìlé inteligence vycházel z re- presentace stavù a operátorù. Pro jednoduché èi umìle sestavené problémy je ta- kový pøístup použitelný, avšak pro zpracování složitìjších a realistiètìjších do- mén je zapotøebí plánovací jazyk rozšíøit.

122

Existuje celá øada rozšíøení, každé z nich vyžaduje odpovídající zmìny v pláno- vacím algoritmu a vìtšinou dochází k obtížnému kompromisu mezi schopností vyjadøovat výrazy (expresivitou) a výkonností z hlediska nejhoršího pøípadu. V dosud existujících experimentech se ukázalo, že expresívnìjší representace, po- užité uvážlivì a s rozmyslem, mohou vést k nárùstu efektivnosti, pøestože se jedná o pomìrnì složitou úlohu.

Situaèní kalkul a dokazování teorémù jsou z praktického hlediska nepoužitelné, ale vedly ke vzniku srozumitelného paradigmatu (plánování typu Strips).

Jazyk Strips je pøíliš omezený pro komplexní, realistické domény, ale lze jej rozšíøit nìkolika smìry:

!Plánovaèe, založené na rozšíøených versích Strips a na algoritmech používajících èásteèné uspoøádání a nejmenší závazek, se dosud ukázaly jako schopné zpracovat složité domény typu výprava kosmické lodi nebo výroba.

!Hierarchická dekomposice umožòuje zahrnutí neprimitivních operátorù do plánù (je ovšem nutno znát dekomposici na primitivnìjší kroky).

!Hierarchická dekomposice je nejúèinnìjší tehdy, pokud slouží ke zmenšení prohledávaného prostoru. Zmenšování (proøezávání stromu) je garantováno, pokud platí buï øešení smìrem dolù (každé abstraktní øešení mùže být dekomponováno do primitivních øešení) nebo øešení smìrem nahoru (nekonsistentní abstraktní plány nemají žádná primitivní øešení).

Oblast plánování patøí v souèasnosti mezi oblasti umìlé inteligence, kterým je vìnováno význaèné výzkumné úsilí vzhledem k potøebnosti rychlých a

efektivních plánování v množství praktických problémù reálného svìta.

123