Ez előrefelé kereséssel történő tervkészítés hasonlít a 3. fejezetben bemutatott problémamegoldó megközelítéshez. Ezt progresszív tervkészítésnek nevezzük, mert előrefelé haladva dolgozik.

A feladat kiinduló állapotából indulva végignézzük a lehetséges cselekvéssorozatokat, amíg olyat nem találunk, ami a célállapothoz vezet. A tervkészítési probléma állapottér-keresési problémaként formalizálva a következő:

11.5. ábra - A tervkészítés két megközelítése. (a) Előrefelé (progresszív) állapottér-keresés, a kiinduló állapotból indulva és a probléma cselekvéseit használva halad a cél felé. (b) Visszafelé (regressziós) állapottér-keresés: valószínűségi állapot keresés (lásd 3.6.1. szakasz - Szenzor nélküli problémák részben) a célállapot(ok)ból indulva a cselekvések inverzét alkalmazva keresi visszafelé a kezdeti állapotot.

Emlékezzünk vissza, hogy a függvényszimbólumok hiányában a tervkészítési probléma állapottere véges, ezért teljes gráf keresési algoritmusok, mint például az A* keresés, egyben teljes tervkészítő algoritmusok is.

A tervkészítők kutatásának korai napjaitól (kb. 1961-től) egészen mostanáig (kb. 1998-ig) az a feltételezés élt, hogy az előrefelé kereső algoritmusok nem eléggé hatékonyak a gyakorlati alkalmazásra. Ma már, tekintsünk csak vissza a 11.1. alfejezetre, ezt nem nehéz megindokolni. Először is az előrefelé keresés nem foglalkozik a lényegtelen cselekvések problémájával, mivel minden állapotban minden alkalmazható cselekvést figyelembe vesz. Másodszor pedig ez a megközelítés gyorsan elakad egy jó heurisztika nélkül. Vegyük például a légi csomagszállítási problémát 10 repülőtérrel, egyenként 5-5 repülővel és 20 darab csomaggal. A cél, hogy az A repülőtér összes terhét a B repülőtérre szállítsuk. Van egy egyszerű megoldása a feladatnak: tegyük be mind a 20 csomagot az egyik A-beli repülőgépbe, ezzel repüljünk B-be, és ott rakodjunk ki. A megoldás megkeresése ellenben nagyon nehéz lehet, hiszen az átlagos elágazási faktor óriási: mind az 50 repülő 9 másik reptérre tud repülni, míg mind a 200 csomag kirakható (ha be volt rakva), vagy berakható a reptér bármelyik repülőjébe. Átlagosan mondjuk 1000 lehetséges cselekvés hajtható végre, így a keresési fában a kézenfekvő megoldás mélységéig közel 1000⁴¹ csomópont van. Ebből nyilvánvaló, hogy egy megfelelő heurisztikára lesz szükség, hogy ezt a keresést hatékonnyá tegyük. A hátrafelé keresés áttekintése után néhány lehetséges heurisztikát mutatunk be.

Az állapottérben történő hátrafelé keresést a kétirányú keresés egy részeként a 3. fejezetben röviden már bemutattuk. Ott megjegyeztük, hogy a hátrafelé keresés megvalósítása nagyon nehéz lehet, ha a célállapotokat az explicit megadás helyett megkötésekkel határozzuk meg. Nevezetesen nem mindig nyilvánvaló, hogy hogyan generáljuk le a célállapotok halmazának a lehetséges elődállapotait (predecessors). Látjuk majd, hogy a STRIPS reprezentáció esetén ez meglehetősen egyszerű, mert az állapothalmazokat azokkal a literálokkal írhatjuk le, amelyeknek igaz értékűeknek kell lenni az adott állapotokban.

A hátrafelé keresés fő előnye az, hogy lehetővé teszi számunkra, hogy csak a releváns (relevant) cselekvéseket vegyük figyelembe. Egy cselekvés releváns egy konjunktív cél szempontjából, ha eléri a cél egy konjunktját. Például a 10-repülőteres légi csomagszállítási problémánk esetében a cél az, hogy a 20 csomag a B repülőtéren legyen, vagy pontosabban

Ott(C1, B) ∧ Ott(C2, B) ∧ … ∧ Ott(C20, B)

Vegyük az Ott(C₁, B) literált. Hátrafelé dolgozva, olyan cselekvéseket kereshetünk, melyeknek ez a következménye. Ilyen csak egy van: Kirakodás(C₁, p, B), ahol a p repülőgép meghatározatlan.

Vegyük észre, hogy számos irreleváns cselekvés is van, ami szintén a célállapotra vezet. Például elrepíthetünk egy üres gépet a JFK repülőtérről (John Fitzgerald Kennedy repülőtér New Yorkban) az SFO-ra (San Francisco repülőtere), ami a célállapothoz vezet egy olyan elődállapotból, melyben a repülőgép a JFK-n van, és minden célfeltétel teljesül. Egy hátrafelé keresés, ami megengedi a hatástalan cselekvéseket még teljes, de sokkal kevésbé hatékony. Ha létezik megoldás, akkor azt egy olyan hátrafelé keresés is megtalálja, amely csak releváns cselekvéseket enged meg. A hátrafelé keresés szűkítése a releváns cselekvésekre, gyakran jóval alacsonyabb elágazási tényezőt eredményez, mint az előrefelé keresés. Például a légi szállítási problémánk esetén a kiindulási állapotból előrefelé közel 1000 cselekvés hajtható végre, míg a célból visszafelé indulva mindössze 20.

A visszafelé keresést regressziós (regression) tervkészítésnek is nevezik. A regressziós keresés meghatározó kérdése a következő: melyek azok az állapotok, amelyekből egy adott cselekvés a célhoz vezet? Ezen állapotok leírásának számítását a cél adott állapoton keresztüli regresszálásának (regressing) nevezzük. Hogy lássuk ennek menetét, vegyük a légi szállítási feladatot. Adott a cél az

Ott(C1, B) ∧ Ott(C2, B) ∧ … ∧ Ott(C20, B)

és a releváns cselekvés a Kirakodás(C₁, p, B), ami az első literált adja. A cselekvés csak akkor működik, ha az előfeltételei teljesülnek. Ebből kifolyólag az elődállapotnak tartalmaznia kell a Benne(C₁, p) ∧ Ott(p, B) előfeltételeket. Mindezeken túl az Ott(C₁, B) részcél nem lehet igaz a megelőző állapotban.^[114] Így a megelőző állapot leírása az alábbi:

Benne(C1, p) ∧ Ott(p, B) ∧ Ott(C2, B) ∧ … ∧ Ott(C20, B)

Ennek tetejébe, ha elvárjuk, hogy egy cselekvés kielégítsen egy literált, azt is biztosítanunk kell, hogy nem ront el egy másikat. Az olyan cselekvést, ami megfelel ennek az elvárásnak konzisztensnek (consistent) nevezzük. Például a Berakodás(C₂, p) cselekvés nem lenne konzisztens az aktuális céllal, mert negálja az Ott(C₂, B) literált.

Most, hogy a relevanciát és a konzisztenciát definiáltuk, megadhatunk egy általános módszert a hátrafelé keresés elődállapotának kereséséhez. Adott egy G cél leírása. Legyen az A cselekvés releváns és konzisztens. A megfelelő elődállapot a következő:

A standard keresési algoritmusok bármelyike felhasználható a keresésre. A leállási feltétel, hogy a generált elődállapot leírását a keresés kiindulási állapota kielégítse. Az elsőrendű esetben, ehhez néhány változó behelyettesítésére is szükség lehet az elődállapotának leírásában. Például az előző bekezdés elődállapotának leírását a

Benne(C1, P12) ∧ Ott(P12, B) ∧ Ott(C2, B) ∧ … ∧ Ott(C20, B)

kiindulási állapot a {p/P₁₂} behelyettesítéssel teljesíti. A behelyettesítéseket arra a cselekvésre kell végrehajtani, ami az állapottól a célhoz vezet, így eredményezve a [Kirakodás(C₁, P₁₂, B)] megoldást.

Sem az előre-, sem pedig a hátrafelé keresés nem hatékony egy jó heurisztika nélkül. Emlékezzünk vissza a 4. fejezetből, hogy egy heurisztikus függvény egy állapot célállapottól való távolságát becsli; a STRIPS esetén minden cselekvés költsége 1, így a távolság az alkalmazandó cselekvések száma. Az alapötlet, hogy nézzük a cselekvés következményeit és a célokat, és becsüljük meg, hogy hány lépésre van szükség a célok elérésére. A pontos szám meghatározása NP-teljes probléma, de a legtöbb esetben találhatók kellően pontos becslők, melyek nem nagyon számításigényesek. Szintén képesek lehetünk egy elfogadható (admissable) heurisztika származtatására, azaz olyanra, ami nem becsül túl. Ez az A* kereséssel együtt használható optimális megoldások megkeresésére.

Két megközelítést lehet kipróbálni. Az egyik, hogy a megadott feladatleírásból egy relaxált problémát (relaxed problem) származtatunk, ahogy azt a 4. fejezetben bemutattuk. A relaxált problémára (ami várhatóan könnyen megoldható) adott optimális megoldás költsége elfogadható heurisztikát ad az eredeti problémára. A második megközelítés során feltételezzük, hogy a tiszta „oszd meg és uralkodj” algoritmus működni fog. Ezt nevezzük a részcélfüggetlenség (subgoal independence) feltételezésnek: a részcélok konjunkciójának megoldási költségét, az egymástól függetlenül megoldott részcélok költségeinek összegével becsüljük. A részcélfüggetlenség feltételezés lehet optimista vagy pesszimista. Akkor optimista, hogyha vannak negatív kölcsönhatások a részcélokhoz készített résztervek között (például amikor az egyik részterv egy cselekvése töröl egy célt, melyet egy másik részterv ért el). Akkor pesszimista és egyben elfogadhatatlan is, ha a résztervek redundáns cselekvéseket tartalmaznak (például két cselekvés eggyel helyettesíthető az összefésült tervben).

Vizsgáljuk meg, hogyan származtathatunk relaxált tervkészítési problémákat. Mivel az előfeltételek és a következmények explicit megadásai rendelkezésre állnak, az eljárás ezeket a reprezentációkat módosítja. (Vessük össze ezt a megközelítést a keresési feladatokkal, ahol az állapotátmenet-függvény egy fekete doboz.) A legegyszerűbb ötlet, hogy lazítsuk a problémát úgy, hogy eltávolítjuk az összes előfeltételt a cselekvésekből. Ekkor minden cselekvés mindig alkalmazhatóvá válik, és minden literál elérhető egy lépésben (ha van alkalmazható cselekvés, egyébként a cél elérése lehetetlen). Úgy tűnhet, ez azt jelenti, hogy a célok konjunkciójához vezető lépésszám azonos a kielégítetlen célliterálok számával, de nem egészen; (1) lehet két cselekvés, melyek kölcsönösen törlik a másik által teljesített célliterált, (2) néhány cselekvés több célt is elérhet. Ha kombináljuk a relaxált problémát és a részcél függetlenségi feltételezést, mindkét problémát kiküszöböltnek vehetjük, és az előálló heurisztika pontosan a még kielégítetlen célok száma.

Sokszor pontosabb heurisztika nyerhető, ha legalább a több célt kielégítő cselekvések pozitív kölcsönhatásait figyelembe vesszük. Először tovább relaxáljuk a problémát azáltal, hogy eltávolítjuk a negatív következményeket (lásd 11.6. feladat). Ezután kiszámítjuk, hogy mennyi az a minimális cselekvésszám, melyek pozitív következményeinek uniója kielégíti a célt. Vegyük például a

Cél(A ∧ B ∧ C)

Cselekvés(X, Következmény: A ∧ P)

Cselekvés(Y, Következmény: B ∧ C ∧ Q)

Cselekvés(Z, Következmény: B ∧ P ∧ Q)

A minimális halmaz az {X, Y} cselekvés, ami az {A, B, C} célt kielégíti, így a fedőhalmaz-heurisztika szerinti költség 2. Ez javít a részcél függetlenség feltételezésen, ami 3-as költséget adna. Egyetlen apró probléma van: a fedőhalmaz probléma NP-teljes. Az egyszerű fedőhalmaz-keresési algoritmus garantáltan visszaad egy értéket, ami egy log n-es faktor pontossággal az igazi minimumérték, ahol n a cél literáljainak száma, és a gyakorlatban rendszerint ennél sokkal pontosabb. Sajnos a mohó algoritmus elveszíti a heurisztika elfogadhatóságának garanciáját.

Az is lehetséges, hogy a relaxált problémát a negatív következmények eltávolításával állítjuk elő anélkül, hogy az előfeltételeket elhagynánk. Ez annyit tesz, hogy ha egy cselekvés következménye A ∧ ¬B az eredeti problémában, akkor A a relaxált problémában. Ez annyit tesz, hogy nem kell foglalkoznunk a résztervek közötti negatív kölcsönhatásokkal, mert egyetlen cselekvés sem törölhet egy másik által előállított literált. Az így előálló relaxált feladat megoldásának költsége az üres-törlési-lista (empty-delete-list) heurisztikát adja. A heurisztika meglehetősen pontos, de kiszámítása egy (egyszerű) tervkészítő algoritmus futtatását igényli. A gyakorlatban a relaxált probléma megoldása elég gyors ahhoz, hogy megérje alkalmazni.

Az itt bemutatott heurisztika mind a progresszív (előrefelé), mind pedig a regresszív (hátrafelé) irányba használható. A könyv írásának pillanatában az üres-törlési-lista heurisztikát használó előrefelé keresők a listavezetők. Ez valószínűleg változik, ahogy újabb heurisztikák és keresési technikák jelennek meg. Mivel a tervkészítés exponenciális komplexitású,^[115] nincs olyan algoritmus, amely minden problémára hatékony lesz, de számos gyakorlati feladat oldható meg ezen fejezet heurisztikáival – sokkal több, mint ami néhány éve megoldható volt.