12.2. Hierarchikus feladatháló tervkészítés

Az egyik legelterjedtebb módszer a komplexitás kezelésére a hierarchikus dekompozíció (hierarchical decomposition). Az összetett szoftvereket szubrutinok vagy objektum osztályok hierarchiájából építik fel, a hadseregek különböző egységek hierarchiái, a kormányok és cégek igazgatóságokból, osztályokból és alosztályokból állnak. A hierarchikus struktúra fő előnye, hogy a hierarchia minden szintjén egy számítási feladat, egy hadművelet vagy egy adminisztratív feladat az eggyel alatta lévő szint néhány cselekvésére épül, így e cselekvések megfelelő elrendezése a magasabb szinten lévő feladat megoldásához kis számítási költséggel jár. Másrészről a nem hierarchikus módszerek a feladatot nagyszámú, független cselekvésre bontják fel, ami nagy léptékű feladatok esetén egyáltalán nem praktikus. A legjobb esetben – amikor a magas szintű megoldásokhoz mindig kielégítő alacsony szintű megvalósítás tartozik – a hierarchikus megoldások az exponenciális idejű tervkészítő algoritmusokkal szemben lineáris időre vezetnek.

Ez az alfejezet a hierarchikus feladathálókon vagy HFH-kon (hierarchical task networksHTN) alapuló tervkészítési módszert mutatja be. A megközelítésünk ötvözi a részben rendezett tervkészítés (11.3. alfejezet) alapötleteit, illetve a „HFH-tervkészítés” területét. A HFH-tervkészítésben a kiinduló problémát, amely a feladatot írja le, a végrehajtandó feladat egy nagyon magas szintű leírásának tekintjük, például: építsünk egy házat. A terveket cselekvésdekompozíciókkal (action decompositions) finomítjuk. Minden cselekvésdekompozíció a magas szintű cselekvést alacsonyabb szintű cselekvések részben rendezett halmazára bontja. A cselekvésdekompozíció ezért a cselekvések megvalósítására vonatkozó ismereteket testesíti meg. Például egy ház felépítése az engedélyek megszerzésére, a kivitelező megbízására, az építkezés elvégzésére és a kivitelező kifizetésére redukálható. (A 12.5. ábra egy ilyen dekompozícióra mutat példát.) A folyamat addig folytatódik, amíg csak az egyszerű cselekvések (primitive actions) maradnak a tervben. Az egyszerű cselekvések tipikusan azok a cselekvések, amelyeket az ágens automatikusan végre tud hajtani. Egy általános kivitelezőre a „kertépítés” egy egyszerű cselekvés lehet, mert egyszerűen csak egy kertépítő bevonását jelenti. Egy kertépítő számára azonban az olyan cselekvések tekinthetők egyszerűnek, mint az „ültessen rododendront ide”.

A „tiszta” HFH-tervkészítésben a terveket csak egymást követő cselekvésdekompozíciókkal állítjuk elő. A HFH ezért a tervkészítést a cselekvésleírások konkretizálásának tekinti, szemben az üres cselekvésből kiinduló cselekvésleírás elkészítésének folyamatával (ami az állapottér-keresésre és a részben rendezett tervkészítésre is igaz). Végezetül kiderül, hogy minden STRIPS cselekvésleírás egy cselekvésdekompozícióra írható át (lásd 12.6. feladat), és a részben rendezett tervkészítés a tiszta HFH-tervkészítés egy speciális esetének tekinthető. Bizonyos feladatokra azonban – különösen „szokatlan” konjunktív célokra — a tiszta HFH-nézőpont eléggé természetellenes, így egy hibrid megközelítést részesítünk előnyben, ahol a cselekvésdekompozíciókat mint a részben rendezett tervkészítés tervfinomításait használjuk fel, a nyitott előfeltételek teljesítése és az ütközés feloldásra szolgáló rendezési megkötések hozzáadása mellett. (Annak, hogy a HFH-tervkészítést a részben rendezett tervkészítés kiterjesztésének tekintjük, további előnye, hogy egy teljesen új jelölésrendszer bevezetése helyett ugyanaz használható.) Kezdésként a cselekvések dekomponálását mutatjuk be részletesebben, majd elmagyarázzuk, hogy a részben rendezett tervkészítést hogyan kell módosítani a dekompozíciók kezeléséhez. Végezetül a teljesség, a komplexitás és a használhatóság kérdéseit tárgyaljuk.

12.2.1. A cselekvésdekompozíciók reprezentációja

A cselekvésdekompozíciós módszerek általános leírásait egy tervkönyvtárban (plan libary) tároljuk, ahonnan kinyerhetők és a készülő terv igényeinek megfelelően felhasználhatók. Minden módszer egy Dekomponál(a, d) formájú kifejezés, amelynek jelentése, hogy egy a cselekvés dekomponálható a d tervbe, mely egy – a 11.3. alfejezetben leírtaknak megfelelő – részben rendezett tervként van megadva.

A házépítés egy szép, konkrét példa, ezért ezt használjuk fel a cselekvésdekompozíció bemutatására. A 12.5. ábra a HázatÉpít cselekvés egy lehetséges dekompozícióját mutatja négy alacsonyabb szintű cselekvésre. A 12.6. ábra néhány cselekvés leírását tartalmazza erre a feladatkörre, valamint a házépítés dekompozícióját, ahogyan az a tervkönyvtárban megjelenne. A könyvtárban más lehetséges dekompozíciók is szerepelhetnek.

A dekompozíció Indít cselekvése szolgáltatja a terv cselekvéseinek összes olyan előfeltételét, melyet más cselekvés nem állít elő. Ezeket külső előfeltételeknek (external preconditions) nevezzük. Példánkban a dekompozíció külső előfeltételei a Telek és a Pénz. Hasonlóképp a Befejez előfeltételei a külső következmények (external effects). Ezek a terv cselekvéseinek összes olyan következményét jelentik, melyeket más cselekvések nem negálnak. Példánkban a HázatÉpít külső következményei a Ház és a ¬Pénz. Néhány HFH-tervkészítő szintén különbséget tesz az elsődleges következmények (primary effects), mint a Ház, és a másodlagos következmények (secondary effects), mint a ¬Pénz között. Mivel mindkét típusú következmény felhasználása ütközésekhez vezethet más cselekvésekkel, csak az elsődleges következményeket használhatjuk a célok elérésére, ami nagymértékben csökkenti a keresési teret.[119]

12.5. ábra - A HázatÉpít cselekvés egy lehetséges dekompozíciója
A HázatÉpít cselekvés egy lehetséges dekompozíciója

A dekompozíciónak a cselekvés egy korrekt megvalósításának kell lennie. A d terv egy a cselekvést korrekten valósít meg, ha d egy teljes és konzisztens részben rendezett terv arra a problémára, ahol a előfeltételeiből a következményeit kell elérnünk. Ha a dekompozíció egy helyesen működő részben rendezett tervkészítő futásának eredménye, akkor nyilvánvalóan korrekt.

Bármely magas szintű cselekvéshez a tervkönyvtár számos dekompozíciót tartalmazhat, például a HázatÉpít-nek lehet egy másik dekompozíciója, amely a folyamatot úgy írja le, hogy a házat az ágens saját kezűleg építi kövekből és malterből. Minden dekompozíciónak egy korrekt tervnek kell lennie, de a magas szintű cselekvésleírásban szereplőkön túl további előfeltételeket és következményeket is tartalmazhat. Például a HázatÉpít 12.5. ábrán látható dekompozíciója a Telek mellett a Pénz-t is megköveteli, és következménye a ¬Pénz. Másrészről a saját kezű építés nem igényel pénzt, de szükséges hozzá egy felhasználásra váró és Malter készlet, valamint eredménye lehet egy FájósHát.

Mivel egy magas szintű cselekvésnek, mint amilyen a HázatÉpít, számos lehetséges dekompozíciója lehet, elkerülhetetlen, hogy a STRIPS cselekvésleírása elrejtse ezen dekompozíciók néhány előfeltételét vagy következményét. A magas szintű cselekvés előfeltételeit a dekompozícióiban szereplő külső előfeltételek metszete, míg a következményit a dekompozíciók külső következményeinek metszete adja. Másképpen, a magas szintű előfeltételek és következmények garantáltan részhalmazai minden egyszerű implementáció valós előfeltételeinek és következményeinek.

12.6. ábra - A házépítési probléma cselekvéseinek leírása és a HázatÉpít cselekvés részletes dekompozíciója. A leírások a pénzzel kapcsolatban egy egyszerűsített, az építőkkel kapcsolatban egy optimista nézetet alkalmaznak.
A házépítési probléma cselekvéseinek leírása és a HázatÉpít cselekvés részletes dekompozíciója. A leírások a pénzzel kapcsolatban egy egyszerűsített, az építőkkel kapcsolatban egy optimista nézetet alkalmaznak.

Az információ elrejtésének két másik formáját is meg kell említenünk. Először, a magas szintű leírás teljes mértékben figyelmen kívül hagyja a dekompozíciók összes belső következményét (internal effects). Például a HázatÉpít általunk javasolt dekompozíciójának ideiglenes belső következménye az Engedély és a Szerződés.[120] Másodszor, a magas szintű leírás nem specifikálja a cselekvésen belüli időintervallumot, ami alatt a magas szintű előfeltételeknek és következményeknek teljesülniük kell. Például a Telek előfeltételnek csak addig kell teljesülnie (a közelítő modellünkben), amíg az EngedélytSzerez nem hajtódik végre, és a Ház csak a KivitelezőtKifizet végrehajtása után igaz.

Az információ elrejtésének ez a módja szükségszerű, ha a hierachikus tervezés célja a komplexitás csökkentése. Szükséges, hogy a magas szintű cselekvésekről anélkül dönthessünk, hogy a számtalan implementációs részlet miatt aggódnánk. Ennek azonban ára van. Konfliktusok léphetnek fel, például egy magas szintű cselekvés belső feltételei, valamint egy másik magas szintű cselekvés belső cselekvései között, miközben a magas szintű leírások alapján nincs mód ezek detektálására. Ennek a problémának komoly hatásai vannak a HFH-tervkészítő algoritmusokra. Dióhéjban, míg a tervkészítő algoritmus az atomi cselekvéseket, mint pontszerű eseményeket kezelheti, a magas szintű cselekvéseknek időbeli kiterjedése van, ami alatt minden mehet tovább.

12.2.2. A tervkészítő módosítása a dekompozíciók kezeléséhez

Most megmutatjuk, hogyan módosítható a részben rendezett tervkészítő, hogy egy HFH-tervkészítőt is tartalmazzon. Ehhez a részben rendezett tervkészítő állapotátmenet-függvényét (lásd 11.3.1. szakasz - Példa a részben rendezett tervkészítésre részben) módosítsuk úgy, hogy lehetővé tegye a T aktuális részleges terven a dekompozíciós módszerek alkalmazását. Az új következő terveket úgy alakítjuk ki, hogy először kiválasztunk néhány nem-atomi a’ cselekvést a T-ből, majd a tervkönyvtár minden Dekomponál(a, d) metódusára, amelyben a θ behelyettesítéssel az a és a’ egyenlővé válik, az a-t behelyettesítjük a d’ = SUBST (θ, d)-vel.

A 12.7. ábrán egy példa látható. Az ábra tetején egy ház megszerzésére vezető T terv található. Az a’ = HázatÉpít magas szintű cselekvést választottuk a dekompozícióra. A 12.5. ábráról a d dekompozíciót választottuk, és a HázatÉpít cselekvést ezzel helyettesítettük. A dekompozíciós lépés által létrehozott Pénz nyitott feltétel teljesítésére a KölcsöntVeszFel járulékos lépést vezettük be. Egy cselekvés helyettesítése annak dekompozíciójával egy kicsit hasonlít a szervátültetéses műtétekhez. Az új résztervet ki kell bontanunk a csomagolásából (az Indít és Befejez lépések közül), be kell illesztenünk és mindent megfelelően le kell zárnunk. Ezt többféleképpen is megtehetjük. Hogy pontosabbak legyünk, minden lehetséges d’ dekompozícióhoz az alábbiakat kell megtennünk:

  1. Először is az a’ cselekvést el kell távolítani a T tervből. Ezután a d’ minden s lépésére ki kell választanunk egy cselekvést, amely kitölti az s szerepét, és hozzá kell adnunk a tervhez. Ez lehet az s egy új példányosítása vagy egy meglévő s’ lépés a T-ből, ami s-sel azonos. A Borkészítés cselekvésdekompozíciója például megkövetelheti a TelketVesz cselekvést, de várhatóan használhatjuk ugyanazt a TelketVesz cselekvést, mely már szerepel a tervben. Ezt részfeladat-megosztásnak (subtask sharing) nevezzük.

A 12.7. ábrán nincsenek megosztási lehetőségek, ezért új cselekvéspéldányokat hoztunk létre. Ha egy cselekvést kiválasztottunk, d’ minden belső előfeltételét átmásoljuk. Például az EngedélytSzerez cselekvés, az építkezés elé rendelt, és létezik egy okozati kapcsolat ezen lépések között, mely szerint az Engedély előfeltétele az Építkezés-nek. Ez lezárja az a’ helyettesítését a példányosításával.

12.7. ábra - Egy magas szintű cselekvés dekompozíciója egy létező tervben. A HázatÉpít cselekvést a 12.5. ábra dekompozíciójával helyettesítjük. A Telek külső előfeltételt a már létező TelketVesz-ből kiinduló okozati kapcsolat biztosítja. A Pénz külső előfeltétel nyitott marad a dekompozíciós lépés után, ezért a KölcsöntVeszFel cselekvést szúrjuk be.
Egy magas szintű cselekvés dekompozíciója egy létező tervben. A HázatÉpít cselekvést a 12.5. ábra dekompozíciójával helyettesítjük. A Telek külső előfeltételt a már létező TelketVesz-ből kiinduló okozati kapcsolat biztosítja. A Pénz külső előfeltétel nyitott marad a dekompozíciós lépés után, ezért a KölcsöntVeszFel cselekvést szúrjuk be.

  1. A következő lépés, hogy az eredeti tervben szereplő a’ sorrendezési megkötéseit megfelelően átvezessük a d’ lépéseihez. Először vegyük T B a’ alakú sorrendezési megkötéseit. Hogyan kellene B-t rendezni a d’ lépéseinek megfelelően? A legkézenfekvőbb megoldás, hogy B az összes d-ben szereplő lépés előtt jöjjön, amit úgy érhetünk el, hogy d’ minden Indít s alakú megkötését a B s megkötéssel helyettesítjük. Másrészről ez a megközelítés túlzottan szigorú lehet! Például a TelketVesz a HázatÉpít előtt kell következzen, de nincsen szükség arra, hogy a TelketVesz a KivitelezőtVeszFel előtt jöjjön a kiterjesztett tervben. Egy túlzottan szigorú rendezés felállítása lehetetlenné teheti néhány megoldás megtalálását. Ezért minden rendezési megkötésre a legjobb megoldás, hogy rögzítsük a megkötés okát. Ha ezután egy magas szintű cselekvést kibontunk, az új rendezési megkötések a lehető leglazábbra vehetők az eredeti megkötés okával összhangban. Ugyanezek a megfontolások alkalmazhatók, amikor az a C alakú megkötéseket helyettesítjük.

  1. Az utolsó lépés, hogy az okozati kapcsolatokat átvezessük. Ha a az eredeti terv egy okozati kapcsolata volt, helyettesítsük azt egy okozati kapcsolathalmazzal, amely B-ből d’ összes olyan lépéséhez vezet, amelynek előfeltétele a d dekompozíció Indít lépése által előállított p (például d’ összes lépése, melyekre p egy külső előfeltétel). A példában a okozati kapcsolatot a kapcsolattal helyettesítjük. (A dekompozícióban szereplő KivitelezőtKifizet, Pénz előfeltétele nyitott feltétellé válik, mert az eredeti tervben nincs olyan cselekvés, ami a Pénz-t biztosítja a HázatÉpít-hez.) Hasonlóképpen a terv összes okozati kapcsolatát helyettesítsük d’ bármely, a d dekompozíció Vége lépéséhez p-t szolgáltató lépésből C-be mutató okozati kapcsolathalmazzal (például dp-t külső következményként tartalmazó lépéséből). Példánkban a kapcsolatot a kapcsolattal helyettesítjük.

Ez lezárja a részben rendezett tervkészítőknél alkalmazott, a dekompozíciók elkészítéséhez szükséges kiterjesztéseket.[121]

A részben rendezett tervkészítő algoritmushoz további módosítások szükségesek, mert a magas szintű cselekvések elrejtik az információt a végső elemi megvalósításukról. Nevezetesen az eredeti részben rendezett tervkészítő algoritmus hibával lép vissza, ha az aktuális terv feloldhatatlan ütközést tartalmaz, vagyis ha egy cselekvés ütközik egy okozati kapcsolattal, de nem helyezhető sem elé, sem pedig mögé. (Erre a 11.9. ábra mutat példát.) Másrészről, a magas szintű cselekvések esetén a feloldhatatlan ütközések néha feloldhatók az ütköző cselekvések dekompozíciójával és lépéseik összerendezésével. Erre a 12.8. ábra mutat be egy példát. Így előfordulhat olyan eset, ahol dekompozícióval egy teljes és konzisztens alapterv nyerhető, még akkor is, hogyha nem létezik teljes és konzisztensen magas szintű terv. Ez a lehetőség azt jelenti, hogy egy teljes HFH-tervkészítőnek végig kell tekintenie az eredeti részben rendezett tervkészítőhöz található számos metszési lehetőséget. Egyébként használhatjuk bármely metszési eljárást, remélve, hogy nem hagyunk figyelmen kívül lehetséges megoldást.

12.8. ábra - Az O. Henrik történetből kiragadott Mágusok ajándéka probléma egy inkonzisztens absztrakt tervet mutat, ami azonban dekomponálható egy konzisztens megoldásra. Az (a) ábra a problémát mutatja be: egy szegény házaspárnak csak két értékes tulajdona van. A férfinek egy aranyórája, a nőnek pedig a gyönyörű hosszú haja. Mindketten azt tervezik, hogy ajándékot vásárolnak a másiknak, hogy az boldog legyen. A férfi úgy dönt, hogy az óráját egy ezüstfésűre cseréli be, míg a nő eladja a haját, hogy aranyláncot vegyen az órához. (Feltételezzük, hogy a „Fésűt ad” cselekvés előfeltétele a Haj, mivel ha a feleségnek nincs hosszú haja, a cselekvés nem éri el a kívánt hatást, hogy boldoggá tegye; és hasonlóképpen a „Láncot ad” cselekvésre.) A (b) ábrán szereplő részleges terv inkonzisztens, mert a „Fésűt ad” és „Láncot ad” absztrakt lépések nem sorrendezhetők konfliktus nélkül. (c) Dekomponáljuk a „Fésűt ad” lépést egy „beilleszt terv” metódussal. A dekompozíció első lépésében a férj megszerzi a fésűt, és odaadja feleségének, miközben az órát egy későbbi időpontban adja oda fizetségül. A második lépésben az órát átadja, és a kötelezettséget teljesíti. Egy hasonló módszer dekomponálja a „Láncot ad” lépést. Amíg mindkét odaadó lépést a szállítási lépés elé sorrendezzük, ez a dekompozíció megoldja a feladatot. (Vegyük észre, hogy ez azon múlik, hogy a lánc használata az órához vagy a fésű használata a hajhoz boldogságot okoz még akkor is, ha a tulajdonjogot már elvesztették.)
Az O. Henrik történetből kiragadott Mágusok ajándéka probléma egy inkonzisztens absztrakt tervet mutat, ami azonban dekomponálható egy konzisztens megoldásra. Az (a) ábra a problémát mutatja be: egy szegény házaspárnak csak két értékes tulajdona van. A férfinek egy aranyórája, a nőnek pedig a gyönyörű hosszú haja. Mindketten azt tervezik, hogy ajándékot vásárolnak a másiknak, hogy az boldog legyen. A férfi úgy dönt, hogy az óráját egy ezüstfésűre cseréli be, míg a nő eladja a haját, hogy aranyláncot vegyen az órához. (Feltételezzük, hogy a „Fésűt ad” cselekvés előfeltétele a Haj, mivel ha a feleségnek nincs hosszú haja, a cselekvés nem éri el a kívánt hatást, hogy boldoggá tegye; és hasonlóképpen a „Láncot ad” cselekvésre.) A (b) ábrán szereplő részleges terv inkonzisztens, mert a „Fésűt ad” és „Láncot ad” absztrakt lépések nem sorrendezhetők konfliktus nélkül. (c) Dekomponáljuk a „Fésűt ad” lépést egy „beilleszt terv” metódussal. A dekompozíció első lépésében a férj megszerzi a fésűt, és odaadja feleségének, miközben az órát egy későbbi időpontban adja oda fizetségül. A második lépésben az órát átadja, és a kötelezettséget teljesíti. Egy hasonló módszer dekomponálja a „Láncot ad” lépést. Amíg mindkét odaadó lépést a szállítási lépés elé sorrendezzük, ez a dekompozíció megoldja a feladatot. (Vegyük észre, hogy ez azon múlik, hogy a lánc használata az órához vagy a fésű használata a hajhoz boldogságot okoz még akkor is, ha a tulajdonjogot már elvesztették.)

12.2.3. Elemzés

Kezdjük a rossz hírrel: a tiszta HFH-tervkészítés (ahol az egyetlen megengedett tervfinomítás a dekompozíció), a véges állapottér ellenére is, eldönthetetlen! Ez nagyon elszomorítónak tűnhet, mivel a HFH-tervkészítés lényege, hogy növeljük a hatékonyságot. Ez a nehézség azért lép fel, mert a cselekvésdekompozíciók rekurzívak (recursive) (például a sétálás implementálható egy lépés megtételével és utána egy sétálással), így a HFH-tervek tetszőlegesen hosszúra nyúlhatnak. Nevezetesen a legrövidebb HFH-megoldás is tetszőlegesen hosszú lehet, így nincs arra lehetőség, hogy a keresést egy megadott idő után leállítsuk. Ennek ellenére azonban legalább három okunk van a bizakodásra:

  1. Kizárhatjuk a rekurziót, amit csak nagyon kevés tervkészítési feladat igényel meg. Ebben az esetben az összes HFH-terv véges vagy megszámlálható hosszúságú.

  2. Korlátozhatjuk azon megoldások hosszát, amelyekre kíváncsiak vagyunk. Mivel az állapottér véges, az olyan terv, amelynek több lépése van, mint az állapottér állapotainak száma, mindenképpen tartalmaz ciklust, ami ugyanabba az állapotba többször lép be. Az ilyen HFH-megoldások kizárásával nagyon picit vesztünk, de uraljuk a keresést.

  3. Létrehozhatunk egy hibrid megközelítést, ami a részben rendezett és a HFH-tervkészítőket kombinálja. A részben rendezett tervkészítés önmagában elegendő, hogy eldöntsük, létezik-e terv, így a hibrid feladat is nyilvánvalóan eldönthető.

A harmadik megoldással egy kicsit óvatosan kell bánnunk. A részben rendezett tervkészítő különböző módokon tud elemi cselekvéseket összehuzalozni, így olyan megoldásokkal találhatjuk magunkat szembe, amelyek nagyon nehezen érhetők, és amelyeknek nincs meg a HFH-tervek szép hierarchikus rendezése. Egy megfelelő kompromisszum, hogy a hibrid keresést úgy szabályozzuk, hogy a cselekvésdekompozíciókat előnyben részesítjük az új cselekvések hozzáadása előtt, de nem olyan mértékben, hogy tetszőlegesen hosszú HFH-tervek jöjjenek létre, mielőtt egy elemi cselekvést hozzáadnánk. A megvalósítás egyik lehetséges módja egy költségfüggvény alkalmazása, amely engedményt ad a dekompozíció által bevezetett cselekvésekre. Minél nagyobb az engedmény, a keresés annál inkább a tiszta HFH-tervkészítésre hasonlít, és a megoldás annál inkább hierarchikus. A hierarchikus tervek rendszerint sokkal könnyebben végrehajthatók a valós helyzetekben, és könnyebben javíthatók, ha valami elromlik.

A HFH-tervek egy másik fontos tulajdonsága a részfeladat-megosztás lehetősége. Emlékezzünk vissza, hogy a részfeladat-megosztás azt jelenti, hogy ugyanazt a cselekvést használjuk fel a tervdekompozícióban szereplő két különböző lépéshez. Ha megtiltjuk az alfeladat megosztását, akkor a d’ dekompozíció minden példányosítása csak egyetlen módon hajtható végre, nem pedig sokféleképp, így jelentősen szűkítjük a keresési teret. Rendszerint ez a szűkítés időt spórol, és a legrosszabb esetben is az optimálisnál csak kicsivel hosszadalmasabb megoldásra vezet. Néhány esetben azonban több problémát is okozhat. Vegyük például az „élvezzük a mézesheteket, és neveljünk fel egy családot” célt. A tervkönyvtár a „házasodj és menj Hawaiira” tervvel állhat elő az első részcélra és a „házasodj és legyenek gyermekeid” tervvel a másodikra. A részfeladat megosztás nélkül a terv két különálló házasodás cselekvést tartalmaz, ami nagymértékben kerülendő.

Egy érdekes példa a részfeladat-megosztás költségeire és előnyeire a fordítók optimalizálásánál fordul elő. Vegyük a tan(x) – sin(x) kifejezés fordításának problémáját. A legtöbb fordító ezt két külön szubrutin triviális összeolvasztásával éri el: a tan lépések a sin lépések előtt következnek. Vegyük azonban a sin és tan alábbi Taylor soros közelítéseit:

Egy részfeladat-megosztást tartalmazó HFH-tervkészítő sokkal hatékonyabb megoldásokat készíthet, mert a sin kiszámításának számos lépésére választhatja a tan meglévő lépéseit. A legtöbb fordító nem alkalmazza ezt a fajta procedúrák közötti megosztást, mert az összes lehetséges megosztott terv figyelembevétele túl sok időt venne igénybe. Ehelyett a legtöbb fordító minden résztervet függetlenül készít el, majd esetleg módosítja az eredményt egy optimalizáló használatával.

A cselekvésdekompozíció által bevezetett járulékos bonyolítások tudatában miért hisszük mégis, hogy a HFH-tervkészítés hatékony lehet? A komplexitás valós forrásai a gyakorlatban nehezen analizálhatók, ezért vegyünk egy idealizált esetet. Tegyük fel például, hogy egy n cselekvésből álló tervet akarunk létrehozni. Egy nemhierarchikus előrefelé haladó állapottér-tervező költsége, minden állapotban b megengedett cselekvéssel, O(bn). A HFH-tervkészítő esetén feltételezzünk egy nagyon általános dekompozíciós formát: minden nem elemi cselekvésnek, d lehetséges dekompozíciója van, mindegyik a következő alacsonyabb szinten k cselekvésből áll. Tudni szeretnénk, hogy ebben a struktúrában hány különböző dekompozíciós fa létezik. Ha a kiindulási szinten n cselekvés van, akkor a gyökér alatti szintek száma logkn, így a belső dekompozíciós csomópontok száma 1 + k + k2 + … klog k n–1 = (n – 1)/(k – 1). Minden belső csomópontnak d lehetséges dekompozíciója van, így összesen d(n–1)/(k–1) lehetséges dekompozíciós fa alkotható. Ezt a képletet megvizsgálva láthatjuk, hogy d alacsonyan tartása nagy k mellett óriási megtakarításokat eredményezhet. Ha b és d összemérhető, akkor gyakorlatilag a nemhierarchikus költség k-adik gyökét vesszük. Másrészről azonban egy kisszámú, de hosszú dekompozíciót tartalmazó tervkönyvtár megalkotása, bár lehetővé teszi bármely probléma megoldását, nem mindig lehetséges. Másképp mondva, a hosszú makrók, amelyek problémák széles körén alkalmazhatók, kiemelten értékesek.

Egy másik és talán jobb ok arra, hogy a HFH-tervkészítő hatékonyságában higgyünk, az, hogy a gyakorlatban működik. A nagyméretű alkalmazásokhoz használt tervkészítők majdnem mindegyike HFH-tervkészítő, mert a HFH-tervkészítés lehetőséget ad az emberi szakértő számára, hogy a komplex feladatok végrehajtásához szükséges elengedhetetlen tudást átadhassák, hogy a nagy tervek kicsi számítási ráfordítással elkészíthetők legyenek. Például a HFH-tervkészítést az ütemezéssel ötvöző O-PLAN-t (Bell és Tate, 1985) arra használták, hogy a Hitachi számára készítsen gyártási terveket. Egy tipikus gyártási sor probléma 350 különböző terméket, 35 összeszerelő gépet és több mint 2000 különböző műveletet tartalmaz. A tervkészítő egy 30 napos ütemezést készít, naponta három 8 órás műszakkal és több millió lépéssel.

A HFH-tervkészítés kulcsa így egy tervkönyvtár megalkotása, amely a komplex magas szintű cselekvések megvalósításához tartalmazza az ismert módszereket. A könyvtár megalkotásának egyik módja, hogy a problémamegoldások tapasztalataiból tanuljunk módszereket. Egy terv elkészítésének gyötrelmes tapasztalatai után az ágens elmentheti a tervet a könyvtárba mint egy a feladat (task) által definiált magas szintű cselekvés megvalósítási módját. Ily módon az ágens egyre kifinomultabbá válik, ahogy a régi módszerekre alapozva új módszerek épülnek. Ennek a tanulási folyamatnak egyik fontos szempontja, hogy az elkészített módszereket általánosítani tudja, a tervből csak a kulcslépéseket megtartva, azaz a probléma példányainak specifikus részleteit elhagyva (például az építő nevének és címének elhagyása a tervekről). Az ilyen általánosításra alkalmas módszereket a 19. fejezetben mutatjuk be. Számunkra elképzelhetetlen, hogy hasonló mechanizmusok nélkül az emberek olyan kompetensek lehetnek, mint amilyenek.



[119] Ez néhány nem várt terv előállítását is megakadályozhatja. Például egy csődeljárás előtt álló személy minden ingó vagyonát eltüntetheti (a ¬Pénz elérésével) egy ház megvásárlásával vagy megépítésével. Ez a terv hasznos, mert az aktuális törvény kizárja az elsődleges lakóhely hitelezők általi lefoglalását (legalábbis az USA-ban – a szerk.).

[120] Az Építkezés negálja az Engedély-t, egyébként ugyanazon engedély több ház megépítéséhez is használható lenne. Sajnos az Építkezés nem zárja le a Szerződés-t, mert előbb a KivitelezőtKifizet-et kell végrehajtanunk.

[121] Vannak további apró módosítások a magas szintű cselekvések konfliktusfeloldásának kezelésére. Az érdeklődő olvasó ezeknek a fejezet végén hivatkozott irodalmakban nézhet utána.