11. Tervkészítés

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

Általános tudnivalók, tételek, definíciók:

Klasszikus tervkészítési környezet:

• teljesen megfigyelhető
• véges
• statikus
• diszkrét

11.1. A tervkészítési probléma

Nehézségek:

• szükségtelen cselekvések
• jó heurisztika megtalálása
• problémadekompozíció

A tervkészítési problémák nyelve

STRIPS: klasszikus alapnyelv

• állapotok leírása: világ (zárt világ: nem felsorolt állítások hamisak) logikai dekompozíciója, állapotok leírás pozitív literálok konjunkciójaként
• célok leírása: egy részlegesen definiált állapot, amit pozitív literálok konjunkciója ad meg
• cselekvések leírása: az előfeltétel és következmény határozza meg
  • három fő sémája:
    1. megnevezés és paraméterlista: az azonosítást szolgálja
    2. előfeltétel: függvényektől mentes pozitív literálok konjunkciója
    3. következmény: függvényektől mentes literálok konjunkciója
  • hozzáadás lista: pozitív literálok listája
  • törlés lista: negatív literálok listája
  • alkalmazható cselekvés: minden állapotban, mikor kielégíti az előfeltételeket
  • STRIPS feltételezés: minden a következményben nem szereplő literál változatlan marad
• megoldás: olyan cselekvés sorozat, amely a kiinduló állapotból a célállapotba visz

11.2. Tervkészítés állapottér-kereséssel

Előrefelé keresés az állapottérben

A tervkészítési probléma állapottér-keresési problémaként formalizálva:

• kiindulási állapot
• cselekvés: végrehajtható, mikor az előfeltevések igazak
• célteszt: ellenőrzi, hogy az állapot kielégíti-e a tervkészítési probléma célját
• lépésköltség: tipikusan 1

Hátrafelé keresés az állapottérben

• másnéven regressziós keresés
• releváns cselekvés: ha egy konjunktív cél szempontjából eléri a cél egy konjunktját
• konzisztens cselekvés: kielégít egy literált, és nem ront el másikat
• megfelelő elődállapot:
  • A: releváns és konzistens cselekvés
  • G: egy cél leírása
  1. az A minden pozitív következményét, ami szerepel G-ben, töröljük
  2. az A minden, még nem szereplő előfeltételét hozzáadjuk

Állapottér-keresési heurisztikák

• elfogadható heurisztika: ami nem becsül túl
• A* keresés egy elfogadható heurisztikával alkalmas az optimális megoldások keresésére
• két megközelítés:
  • relaxált probléma származtatása
  • részcélfüggetlenség feltételezés (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)
    • optimista: vannak negatív kölcsönhatások a részcélokhoz készített résztervek között
    • pesszimista (elfogadhatatlan): a résztervek redundás cselekvéseket tartalmaznak

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

• általános stratégia: legkisebb megkötés
• részben rendezett tervkészítő: olyan algoritmus, ami be tud illeszteni két cselekvést úgy a tervbe, hogy nem határozza meg azok sorrendjét
• a terv 4 komponense:
  • cselekvés
  • rendezési kényszer
  • okozati kapcsolat
  • nyitott előfeltétel: ha nem teljesül a terv egy akciójának hatására, cél a halmaz kiürítése
• konzisztens terv: amiben nincsenek ciklusok a rendezési megkötésekben és nincsenek ellentmondások az okozati kapcsolatokkal; mentes a nyitott előfeltételektől
• egy részben rendezett megoldás minden sorba rendezése egy teljes megoldás

11.6. A tervkészítési módszerek elemzése

Egy feladatnak sorba rendezhető részcéljai vannak, ha létezik a részcélok egy olyan rendezése, hogy a tervkészítő sorrendben elérheti őket anélkül, hogy a korábban már elért részcélokat felszámolná.