11.3. Részben rendezett tervkészítés

Az előre- és hátrafelé keresés a teljesen rendezett terv keresés speciális fajtái. Ezek a cselekvéseknek csak szigorúan lineáris sorozatait tárják fel, melyek közvetlenül kapcsolódnak a kiinduláshoz vagy a célhoz. Ez annyit tesz, hogy nem használhatják ki a problémadekompozíció lehetőségeit. Ahelyett hogy a részproblémákon külön dolgoznának, mindig arról kell dönteniük, hogy hogyan sorrendezzék a részproblémák cselekvéseinek összességét. Előnyösebb lenne egy olyan megközelítés, ami több részcélon dolgozik függetlenül, ezeket több résztervvel megoldja, majd összerakja a részterveket.

Egy ilyen megközelítésnek megvan az az előnye is, hogy rugalmas a terv összeállításának sorrendjében. A tervkészítő így nem kényszerül arra, hogy a lépéseken időrendi sorrendben dolgozzon, hanem először inkább a „nyilvánvaló” vagy „fontos” döntéseken dolgozhat. Például egy Berkeleyben lévő tervkészítő ágens, amely Monte Carlóba igyekszik, először egy San Francisco–Párizs járatot vizsgál meg, majd amikor ismeri a pontos indulási és érkezési dátumokat, foglalkozhat a reptérre kijutás, illetve az onnan továbbjutás problémájával.

Azt az általános stratégiát, mely szerint egy választást késleltetünk egy keresés során, legkisebb megkötés (least commitment) stratégiának nevezzük. A legkisebb megkötésnek nincs formális definíciója, és nyilvánvaló, hogy valamennyi megkötés szükséges, különben a keresés nem haladna. Az informális definíció ellenére a legkisebb megkötés nagyon hasznos megközelítés annak meghatározására, hogy a döntéseket mikor kell meghozni egy keresési problémában. Az első példánk jóval egyszerűbb, mint egy nyaralás megtervezése. Vegyük a cipőfelvétel egyszerű esetét. Ezt formálisan a következő tervkészítési problémával írhatjuk le:

Cél(JobbCipőFenn BalCipőFenn)

Kiindulás()

Cselekvés(JobbCipő, Előfeltétel: JobbZokniFenn, Következmény: JobbCipőFenn)

Cselekvés(JobbZokni, Következmény: JobbZokniFenn)

Cselekvés(BalCipő, Előfeltétel: BalZokniFenn, Következmény: BalCipőFenn)

Cselekvés(BalZokni, Következmény: BalZokniFenn)

A tervkészítőnek két cselekvéssorozattal kell előállnia, a JobbZokni-t a JobbCipő követi, hogy a cél első konjunktját elérjük és a BalZokni-t a BalCipő követi a második konjunkthoz. A két cselekvéssorozat kombinálható, hogy teljes tervet nyerjünk. Így a tervkészítő a két részsorozatot egymástól függetlenül kezelheti anélkül, hogy felállítana bármi megkötést arra, hogy az egyik sorozat egy cselekvése a másikéhoz képest előbb vagy később következik. Bármely olyan tervkészítő algoritmust, ami két cselekvést be tud illeszteni egy tervbe anélkül, hogy meghatározná azok sorrendjét, részben rendezett tervkészítőnek nevezünk (partial-order planner). A 11.6. ábra a cipő és zokni felvételére készített részben rendezett tervet szemlélteti. Vegyük észre, hogy a megoldást a cselekvések gráfja ábrázolja, nem egy szekvencia. Érdemes megfigyelni az Indít és a Befejez „technikai” cselekvéseket, melyek a terv kezdetét, illetve végét jelölik. Ezeket cselekvésnek nevezni egyszerűsíti a dolgokat, mert így a terv minden lépése egy cselekvés. A részben rendezett megoldás hat teljesen rendezett megoldásnak felel meg, melyek mindegyike a részben rendezett megoldásnak egy sorba rendezése (linearization).

11.6. ábra - Egy részben rendezett terv a zokni és a cipő felvételéhez, és a hat lehetséges sorba rendezés a teljesen rendezett tervhez
Egy részben rendezett terv a zokni és a cipő felvételéhez, és a hat lehetséges sorba rendezés a teljesen rendezett tervhez

A részben rendezett tervkészítés megvalósítható, mint egy keresés a részben rendezett tervek terében. (Ezentúl ezeket egyszerűen csak „terv”-nek nevezzük.) Egy üres tervvel indulunk. Ezután a terv finomításának módjait keressük egészen addig, míg elő nem állunk a teljes tervvel, ami megoldása a problémának. A cselekvések ebben a keresésben nem a való világ cselekvései, hanem terveken végrehajtott műveletek: egy lépés hozzáadása a tervhez, a cselekvésekhez egy sorrend rendelése, ami egy cselekvést egy másik elé helyez és így tovább.

A továbbiakban definiálni fogjuk az RRT algoritmust a részben rendezett tervkészítéshez. Hagyományosan az RRT-t mint egy önálló programot szokás bemutatni, ehelyett mi a részben rendezett tervkészítést, mint a keresési probléma egy példányát fogjuk megfogalmazni. Ez lehetővé teszi, hogy az alkalmazható tervfinomító lépésekre koncentráljunk ahelyett, hogy azt vizsgálnánk, hogyan térképezi fel a keresési teret az algoritmus. Valójában, ha a keresési feladatot megfogalmaztuk a nem informált vagy heurisztikus keresési módszerek széles választéka áll rendelkezésre.

Emlékezzünk vissza, hogy a keresésünk állapotai (többnyire még befejezetlen) tervek lesznek. Hogy elkerüljük a valós cselekvésekkel való keveredést, itt tervekről és nem állapotokról fogunk beszélni. Minden terv a következő négy komponensből áll, ahol az első kettő a terv lépéseit definiálja, míg az utolsó kettő naplózásra szolgál, hogy abból meghatározzuk, hogyan bővíthetők a tervek:

  • Cselekvések (actions) halmaza, amelyek a terv lépéseit adják. Ezeket a tervkészítési probléma cselekvéshalmazából vesszük. Egy „üres” terv csak az Indít és a Befejez cselekvéseket tartalmazza. Az Indít-nak nincsenek előfeltételei, míg a következményrésze a tervkészítési feladat kiindulási állapotának literáljait tartalmazza. A Befejez cselekvésnek nincsen következmény része, míg előfeltételei megegyeznek a célállapot literáljaival.

  • Rendezési kényszerek (ordering constraints). Minden rendezési kényszer AB alakú, amit „B előtt A”-nak olvasunk, és azt jelenti, hogy az A-t valamikor a B előtt kell végrehajtani, de nem feltétlenül közvetlen előtte. A rendezési kényszerek egy megfelelő részben rendezést kell leírjanak. Bármilyen ciklus (mint az AB és a BA) ellentmondást jelent, ezért olyan rendezési kényszer nem adható a tervhez, amely ciklust hozna létre.

  • Okozati kapcsolatok (causal links). Az A és B cselekvések közötti okozati kapcsolatot -vel jelöljük és úgy olvassuk, hogy „A teljesíti p-t B-hez”. Például a okozati kapcsolat jelentése, hogy a JobbZokniFenn egy következménye a JobbZokni cselekvésnek és előfeltétele a JobbCipő-nek. Tartalmazza azt a megkötést is, hogy a JobbZokniFenn-nek igaznak kell maradnia a JobbZokni cselekvéstől a JobbCipő cselekvésig. Más szavakkal, a terv nem mindig bővíthető egy új C cselekvéssel, ami ütközik egy okozati kapcsolattal. Egy C cselekvés ütközik az -vel, ha C következménye a ¬p, és ha C az A után és B előtt jöhet (a rendezési kényszereknek megfelelően). Néhány szerző az okozati kapcsolatokat védett tartományoknak (protection intervals) nevezi, mert az megvédi p-t a negálástól az AB intervallumban.

  • Nyitott előfeltételek (open preconditions). Egy előfeltétel nyitott, ha nem teljesül a terv egy akciójának hatására. A tervkészítők feladata, hogy a nyitott előfeltételek halmazát üres halmazra csökkentse, ellentmondások bevezetése nélkül.

Például a 11.6. ábrán bemutatott teljes terv a következő komponenseket tartalmazza (nem tüntettük fel a rendezési kényszereket, amelyek minden cselekvést az Indít után és a Befejez elé helyeznek):

Cselekvések:{JobbZokni, JobbCipő, BalZokni, BalCipő, Indít, Befejez}

Rendezések: {JobbZokniJobbCipő, BalZokniBalCipő}

Nyitott előfeltételek: {}

Fontos

Konzisztens tervnek (consistent plan) nevezzük azt a tervet, amelyben nincsenek ciklusok a rendezési megkötésekben és nincsenek ellentmondások az okozati kapcsolatokkal. Egy konzisztens terv, mely nyitott előfeltételektől mentes, a megoldás (solution). Rövid gondolkodással belátható: egy részben rendezett megoldás minden sorba rendezése egy teljesen rendezett megoldás, melynek végrehajtása az induló állapotból egy célállapotra vezet. Ez annyit tesz, hogy a „terv végrehajtását” a teljesen rendezett tervekről kiterjeszthetjük a részben rendezett tervekre. Egy részben rendezett terv végrehajtása során ismétlődően mindig választunk egy következő cselekvést, a lehetséges következő cselekvések bármelyikét. A 12. fejezetben látni fogjuk, hogy az ágens számára a terv végrehajtásának rugalmassága nagyon hasznos lehet, ha a környezet nem az elvártaknak megfelelően működik. A rugalmas sorrendezés egyszerűsíti a kisebb tervek összekombinálását nagyobbakká, mert minden részterv átrendezheti a cselekvéseinek sorrendjét, hogy elkerülje a más tervekkel való ütközést.

Most már készen állunk arra, hogy formalizáljuk azt a keresési problémát, amit az RRT megold. Egy olyan formalizálással kezdünk, ami az ítéletlogikai tervkészítési problémákra alkalmas, az elsőrendű logikai megoldással járó komplikációkat későbbre hagyjuk. Mint rendszerint, a definíció tartalmazza a kiinduló állapotot, a cselekvéseket és a céltesztet.

  • A kiindulási terv egy Indít és egy Befejez cselekvést, egy Indít Befejez rendezést tartalmaz, és nincsenek okozati kapcsolatok. A Befejez minden előfeltétele nyitott.

  • Az állapotátmenet-függvény önkényesen kiválasztja B egy p nyitott előfeltételét és legenerál egy következő tervet egy A cselekvés minden olyan lehetséges konzisztens megválasztásához, mely teljesíti p-t. A konzisztenciát a következőképp biztosítjuk:

    1. Az okozati kapcsolatot és az AB rendezési megkötést hozzáadjuk a tervhez. Az A cselekvés lehet a terv egy már létező vagy egy új cselekvése. Amennyiben új, hozzáadjuk a tervhez az Indít A és az ABefejez megkötésekkel.

    2. Feloldunk minden konfliktust, az új okozati kapcsolat és az összes létező cselekvés, valamint az A cselekvés (ha új) és minden létező okozati kapcsolat között. Egy az és C között fennálló konfliktust azáltal oldunk fel, hogy C-t valamikor kívül helyezzük a védett intervallumon a BC vagy a C A hozzáadásával. Amennyiben konzisztens tervet adnak, beszúrjuk a követő állapotokat, valamelyikhez vagy akár mindkettőhöz.

  • A célteszt ellenőrzi, hogy a terv megoldása-e az eredeti tervkészítési problémának. Mivel csak konzisztens terveket állítunk elő, a céltesztnek csak azt kell ellenőrizni, hogy vannak-e nem nyitott előfeltételek.

Emlékezzünk, hogy keresési algoritmus által vizsgált cselekvések ebben a felírásban sokkal inkább tervfinomító lépések, mint valós cselekvések a feladattérből. Az út költsége ezért szigorú értelembe véve irreleváns, hiszen az egyetlen ami fontos, az azon terv valós cselekvéseinek költsége, amire ez az út vezetett. Mindazonáltal lehetséges egy útvonalköltség-függvény specifikálása, ami a valós terv költségeit tükrözi: minden valós cselekvésnek a tervhez való hozzáadását egységnyi költséggel, míg a finomító lépéseket 0 költséggel vesszük figyelembe. Így g(n), ahol n a terv, egyenlő lesz a tervben található valós cselekvések számával. Egy heurisztikus h(n) becslés szintén alkalmazható.

Első ránézésre azt gondolhatjuk, hogy az állapotátmenet-függvénynek minden nyitott p-hez tartalmaznia kellene egy következő állapotot, nem csak egyhez. Ez azonban, redundáns lenne és nem lenne hatékony, ugyanazon okból, amiért a kényszerkielégítési algoritmusok nem szúrnak be minden lehetséges változóhoz utódot: a nyitott előfeltételek kezelési sorrendje (csakúgy, mint a kényszerkielégítési probléma változóinak kezelési sorrendje) kommutatív. (Lásd 5.2. szakasz - A visszalépéses keresés alkalmazása kényszerkielégítési problémákra részben.) Így tetszőleges sorrendet választhatunk, és az algoritmusaink még mindig teljesek. A helyes rendezés megválasztása gyorsabb kereséshez vezethet, de minden sorrendezés ugyanazokra a megoldásjelöltekre vezet.

11.3.1. Példa a részben rendezett tervkészítésre

Most nézzük meg, hogy az RRT hogyan oldja meg a 11.1. alfejezetben szereplő pótkerék problémát. A probléma a leírását a 11.7. ábrán megismételjük.

11.7. ábra - Az egyszerű kerékcsere probléma
Az egyszerű kerékcsere probléma

A megoldás keresése egy kezdeti tervből indul, ami egy Indít cselekvést tartalmaz az Ott(Pótkerék, Csomagtartó) ∧ Ott(LaposKerék, Tengely) következménnyel és egy Befejez cselekvést az Ott(Pótkerék, Tengely) előfeltétellel. Ezután követő állapotokat állítunk elő úgy, hogy egy nyitott előfeltételt választunk a munkához (visszavonhatatlanul), majd választunk az ehhez vezető lehetséges cselekvések közül. Most nem foglalkozunk a heurisztikákkal, amik segíthetik ezt a döntést; látszólag véletlenszerű döntést hozunk. Az események sorrendje a következő:

  1. Vegyük az egyetlen nyitott előfeltételt, a Befejez cselekvés Ott(Pótkerék, Tengely) feltételét. Válasszuk ki az egyetlen alkalmazható cselekvést, a Felszerel(Pótkerék, Tengely)-t.

  2. Vegyük a Felszerel(Pótkerék, Tengely) cselekvés Ott(Pótkerék, Föld) előfeltételét. Válasszuk az Eltávolít(Pótkerék, Csomagtartó) cselekvést, ami az egyetlen alkalmazható cselekvés az előfeltétel biztosításához. A végső terv a 11.8. ábrán látható.

11.8. ábra - A nem teljes részben rendezett terv a kerékcsere problémához, miután megválasztottuk a cselekvéseket az első két nyitott előfeltételhez. A dobozok cselekvéseket testesítenek meg, a bal oldalon az előfeltételekkel, a jobb oldalon pedig a következményekkel. (Az Indít cselekvést kivéve a következményeket elhagytuk.) A fekete nyilak az okozati kapcsolatokat mutatják, melyek a nyíl fejénél szereplő állítást védik.
A nem teljes részben rendezett terv a kerékcsere problémához, miután megválasztottuk a cselekvéseket az első két nyitott előfeltételhez. A dobozok cselekvéseket testesítenek meg, a bal oldalon az előfeltételekkel, a jobb oldalon pedig a következményekkel. (Az Indít cselekvést kivéve a következményeket elhagytuk.) A fekete nyilak az okozati kapcsolatokat mutatják, melyek a nyíl fejénél szereplő állítást védik.

  1. Vegyük a Felszerel(Pótkerék, Tengely) cselekvés ¬Ott(LaposKerék, Tengely) előfeltételét. Hogy ellenkezzünk egy kicsit, válasszuk az OtthagyÉjszakára cselekvést, a kézenfekvő Eltávolít(LaposKerék, Tengely) helyett. Vegyük észre, hogy az OtthagyÉjszakára cselekvésnek szintén következménye a ¬Ott(Pótkerék, Föld), ami ütközik az

okozati kapcsolattal. Hogy feloldjuk ezt az ütközést, egy rendezési megkötést illesztünk be, ami az OtthagyÉjszakára cselekvést az Eltávolít(Pótkerék, Csomagtartó) elé rendeli. Az így előálló terv a 11.9. ábrán látható. (Miért oldja ez fel az ütközést és miért nincs erre más lehetőség?)

  1. Most az egyetlen fennmaradó nyitott előfeltétel az Ott(Pótkerék, Csomagtartó), ami az Eltávolít(Pótkerék, Csomagtartó) cselekvés előfeltétele. Az egyetlen cselekvés, ami ezt elérheti, a meglévő Indít cselekvés, de az Indít és az Eltávolít(Pótkerék, Csomagtartó) közötti okozati kapcsolat ütközik az OtthagyÉjszakára cselekvés ¬Ott(Pótkerék, Csomagtartó) következményével. Most nincs mód arra, hogy feloldjuk az ütközést az OtthagyÉjszakára cselekvéssel: nem sorolhatjuk az Indít elé (mert semmi nem kerülhet az Indít elé), és nem rendelhető az Eltávolít(Pótkerék, Csomagtartó) után (mert már van egy rendezés, ami elé helyezi). Ezért muszáj visszalépnünk, törölnünk az Eltávolít(Pótkerék, Csomagtartó) cselekvést és a két utolsó okozati kapcsolatot, és visszalépnünk a 11.8. ábrán bemutatott állapothoz.

11.9. ábra - A terv alakulása, az OtthagyÉjszakára választása után, amit a ¬Ott(LaposKerék, Tengely) eléréséhez választottunk. Hogy elkerüljük az ütközést az Ott(Pótkerék, Csomagtartó)-t védő, az Eltávolít(Pótkerék, Csomagtartó)-ból induló okozati kapcsolattal, az OtthagyÉjszakára cselekvést egy rendezési megkötéssel az Eltávolít(Pótkerék, Csomagtartó) elé helyeztük, amit a szaggatott nyíllal jelöltünk.
A terv alakulása, az OtthagyÉjszakára választása után, amit a ¬Ott(LaposKerék, Tengely) eléréséhez választottunk. Hogy elkerüljük az ütközést az Ott(Pótkerék, Csomagtartó)-t védő, az Eltávolít(Pótkerék, Csomagtartó)-ból induló okozati kapcsolattal, az OtthagyÉjszakára cselekvést egy rendezési megkötéssel az Eltávolít(Pótkerék, Csomagtartó) elé helyeztük, amit a szaggatott nyíllal jelöltünk.

Összefoglalva, a tervkészítő bebizonyította, hogy az OtthagyÉjszakára nem használható fel kerékcserére.

  1. Vegyük újra a Felszerel(Pótkerék, Tengely) cselekvés ¬Ott(LaposKerék, Tengely) előfeltételét. Ez alkalommal válasszuk az Eltávolít(LaposKerék, Tengely) cselekvést.

  2. Vegyük újra az Eltávolít(Pótkerék, Csomagtartó) cselekvés Ott(Pótkerék, Csomagtartó) előfeltételét, és válasszuk az Indít cselekvést, hogy ezt elérjük. Ez alkalommal nincsenek ütközések.

  3. Vegyük az Eltávolít(LaposKerék, Tengely cselekvés Ott(LaposKerék, Tengely) előfeltételét, valamint ennek eléréséhez az Indít cselekvést. Ez egy teljes és konzisztens tervet ad, vagy más szavakkal egy megoldást, amint azt a 11.10. ábra mutatja.

11.10. ábra - A kerékcsere probléma végső megoldása. Vegyük észre, hogy az Eltávolít(Pótkerék, Csomagtartó) és az Eltávolít(LaposKerék, Tengely) tetszőleges sorrendben végrehajtható a Felszerel(Pótkerék, Tengely) előtt.
A kerékcsere probléma végső megoldása. Vegyük észre, hogy az Eltávolít(Pótkerék, Csomagtartó) és az Eltávolít(LaposKerék, Tengely) tetszőleges sorrendben végrehajtható a Felszerel(Pótkerék, Tengely) előtt.

Bár ez a példa nagyon egyszerű, jól szemlélteti a részben rendezett tervkészítés erősségét. Először is az okozati kapcsolatok a keresési tér (fa) egy korai szűkítéséhez metszéséhez vezettek, mert kizártak olyan területeket, amelyek a feloldhatatlan ütközések miatt nem tartalmaznak megoldásokat. Másodszor a 11.10. ábra megoldása egy részben rendezett terv. Ebben az esetben ennek előnye nem nagy, mert csak két lehetséges sorba rendezés létezik, mégis egy ágens számára előnyös lehet ez a rugalmasság, például ha a kereket sűrű forgalomban kellene lecserélni.

A példa szintén rámutat néhány javítási lehetőségre. Például egy próbálkozás duplán történt: az Indít az Eltávolít(Pótkerék, Csomagtartó) cselekvéshez kapcsolódik még mielőtt az ütközés visszalépést váltana ki, és a visszalépés hatására a kapcsolat felbomlik, bár nem vesz részt az ütközésben. A keresés folytatásakor a kapcsolat újra létrejön. Ez tipikus az időrendi visszalépés esetén és elkerülhető, ha függőségvezérelt visszalépést használunk.

11.3.2. Részben rendezett tervkészítés kötetlen változókkal

Ebben a fejezetben a változókat tartalmazó elsőrendű cselekvés reprezentációra alkalmazott részben rendezett tervkészítés során felmerülő komplikációkkal foglalkozunk. Tegyük fel, hogy a kockavilág (lásd 11.4. ábra) problémát kell megoldani a Rajta(A, B) nyitott előfeltétellel és a

Cselekvés(Mozgat(b, x, y),

Előfeltétel: Rajta(b, x) ∧ Üres(x) ∧ Üres(y)

Következmény: Rajta(b, y) ∧ Üres(x) ∧ ¬Rajta(b, x) ∧ ¬Üres(y))

cselekvéssel. Ez a cselekvés teljesíti a Rajta(A, B) literált, mert a Rajta(b, u) következmény egyesíthető a Rajta(A, B)-vel a {b/A, y/B} behelyettesítéssel. Alkalmazzuk tehát ezt a behelyettesítést a cselekvésre, aminek az eredménye a

Cselekvés(Mozgat(A, x, B),

Előfeltétel: Rajta(A, x) ∧ Üres(x) ∧ Üres(B)

Következmény: Rajta(A, B) ∧ Üres(x) ∧ ¬Rajta(b, x) ∧ ¬Üres(B))

Ez az x változót kötetlenül hagyja. Ez annyit tesz, hogy a cselekvés annyit mond, hogy mozgasd A-t valahonnan, de azt nem, hogy honnét. Ez egy másik példa a legkisebb megkötés elvre: elhalaszthatjuk a döntéseket egészen addig, amíg a terv egy másik lépése ezt meghozza nekünk. Tegyük fel például, hogy a Rajta(A, D) a kiinduló állapotunk. Az x-et D-vel behelyettesítve az Indít cselekvés használható fel, hogy elérjük a Rajta(A, x)-et. A módszer, hogy több információt kivárunk, mielőtt megválasztjuk x-et, gyakran sokkal hatékonyabb, mint az x minden értékének kipróbálása és a visszalépés, ha ez sikertelen.

A változók jelenléte az előfeltételekben és a cselekvésekben nehezíti az ütközések detektálását és feloldását. Például amikor a Mozgat(A, x, B) a terv része lesz, a

okozati kapcsolatra is szükség van. Ha van egy M2 cselekvés ¬Rajta(A, z) következménnyel, akkor ez csak akkor okoz ütközést, ha a z értéke B. Hogy kezeljük ezt a lehetőséget, kiterjesztjük a tervek reprezentációját, hogy tartalmazzanak zX alakú egyenlőtlenségi kényszereket (inequality constraints), ahol z egy változó és X egy változó vagy egy konstansszimbólum. Ebben az esetben az ütközést a z B hozzáadásával oldhatjuk fel, ami azt jelenti hogy a terv később B kivételével bármire behelyettesítheti z-t. Bármikor amikor egy behelyettesítést hajtunk végre a tervben, ellenőriznünk kell, hogy az nem ellenkezik-e az egyenlőtlenségi korlátokkal. Például egy x/y behelyettesítés ütközik az x y kényszerrel. Az ilyen ellentétek nem oldhatók fel, ezért a tervkészítő visszalépésre kényszerül.

A 12.6. alfejezetben egy bővebb példát adunk a részben rendezett tervkészítésre, ami a változókat tartalmazó kockavilág probléma.

11.3.3. Heurisztikák a részben rendezett tervkészítésre

A teljesen rendezett tervkészítéssel összehasonlítva a részben rendezett tervkészítés egyértelmű előnye, hogy a probléma részfeladatokra bontható. A hátránya, hogy nem reprezentálja megfelelően az állapotokat, így nehezebb megbecsülni, hogy a részben rendezett terv milyen messze van a céltól. Jelenleg jóval kevesebb az ismeretanyag arról, hogy hogyan adható pontos heurisztika a részben rendezett tervkészítéshez, mint a teljesen rendezett tervkészítések esetén.

A legkézenfekvőbb heurisztika, hogy megszámoljuk az eltérő nyitott előfeltételeket. Ez javítható azáltal, ha kivonjuk azon nyitott előfeltételek számát, melyek illeszkednek az Indít állapot egy literáljaival. Hasonlóan a teljesen rendezett esethez ez túlbecsüli a költséget, ha vannak cselekvések, melyek több célt érnek el, és alulbecsül, ha negatív kölcsönhatások vannak a terv lépései között. A következő alfejezet egy olyan megközelítést mutat be, ami lehetővé teszi, hogy sokkal pontosabb heurisztikákat kapjunk egy relaxált problémából.

A heurisztikus függvényt arra használjuk, hogy kiválasszuk a tovább finomítandó tervet. Ezzel a választással az algoritmus követő állapotokat generál egyetlen kiválasztott nyitott előfeltételből kiindulva. Mint a változókiválasztás a kényszerkielégítési algoritmusban, ez a választás nagy hatással van a hatékonyságra. A kényszerkielégítési probléma legjobban-korlátozott-változó (most-constrained-variable) heurisztikája alkalmazható a tervkészítő algoritmusokra, és látszólag jól működik. Az alapötlet, hogy válasszuk azt a nyitott feltételt, mely a lehető legkevesebb módon elégíthető ki. Ennek a heurisztikának két speciális esete van. Először, ha egy nyitott feltétel nem érhető el egyetlen cselekvéssel sem, akkor a heurisztika kiválasztja. Ez jó ötlet, hiszen a teljesíthetetlenség korai érzékelése sok munkát megspórolhat. Másodszor, ha egy nyitott feltétel csak egyféleképp teljesíthető, akkor célszerű kiválasztani, hiszen ez egy elkerülhetetlen döntés, ami további megkötéseket eredményezhet a későbbi választásokhoz. Habár minden nyitott feltételhez meglehetősen költséges kiszámolni, hogy azok hányféleképpen teljesíthetők, és ez nem is mindig éri meg, a kísérletek azt mutatják, hogy a két speciális eset kezelése jelentős gyorsulást eredményezhet.