Čtení: 45 minHodnotí se: test 3 (20 b), zkouška

5 Automatické plánování

Po přečtení umíš

určit aplikovatelné akce a spočítat stav po akci
simulovat dopředné a zpětné plánování
vyřešit kazy v plánování v prostoru plánů
sestavit plánovací graf a poznat mutexy

5.1 Ukázka: letecká přeprava

Stav je množina platných faktů, například At(C1, SFO). Akce má předpoklady a efekty. Plán je posloupnost akcí, která převede počáteční stav do stavu splňujícího cíl.

Definice 5.2 (Aplikace akce)

Akce $a$ je aplikovatelná ve stavu $s$ , pokud $precond^+(a) \subseteq s$ a $precond^-(a) \cap s = \emptyset$ . Výsledek je

\gamma(s, a) = (s \setminus effect^-(a)) \cup effect^+(a).

Platí uzavřený svět: co ve stavu není, neplatí.

Příklad 5.3 (Plán z cvičení)

Start: At(C1, SFO), At(C2, JFK), At(P1, SFO), At(P2, JFK). Cíl: At(C1, JFK), At(C2, SFO). Operátory Load, Unload a Fly. Sestav plán.

Řešení

Load(C1, P1, SFO)
Load(C2, P2, JFK)
Fly(P1, SFO, JFK)
Fly(P2, JFK, SFO)
Unload(C1, P1, JFK)
Unload(C2, P2, SFO)

Dvojice akcí jsou nezávislé, takže jako paralelní plán má délku 3.

5.2 Dopředné a zpětné plánování

Dopředné začíná ve startu a zkouší aplikovatelné akce. Větvící faktor bývá velký a mnoho akcí je k ničemu.

Zpětné začíná v cíli a bere jen relevantní akce: akce musí splnit aspoň jeden literál cíle a žádný nesmí smazat. Inverzní aplikace je

\gamma^{-1}(g, a) = (g \setminus effect^+(a)) \cup precond(a).

5.3 Plánování v prostoru plánů

Místo stavů se upravuje částečný plán: akce, precedence, vazby proměnných a kauzální podmínky. Algoritmus opravuje kazy.

Otevřený cíl: akce potřebuje předpoklad, který nikdo nezajistil. Léčba: najít nebo přidat akci a kauzální podmínku.
Hrozba: akce $c$ může smazat předpoklad $p$ kauzální vazby $a \to b$ . Léčba: dát $c$ před $a$ , za $b$ , nebo vazbou proměnných zajistit, že se literály neunifikují.

5.4 Plánovací graf

Definice 5.4 (Plánovací graf)

Střídají se stavové vrstvy $P_i$ a akční vrstvy $A_i$ . Vrstva je sjednocením všeho, co může platit. No-op akce přenáší atom do další vrstvy.

Definice 5.5 (Mutex)

Dvě akce jsou ve vzájemném vyloučení, pokud jedna maže předpoklad nebo efekt druhé, nebo mají předpoklady v mutexu. Dva atomy jsou v mutexu, pokud všechny dvojice akcí, které je produkují, jsou v mutexu.

Vrstvy monotónně rostou a mutexy ubývají. Graphplan rozšiřuje graf, dokud cíl není v poslední vrstvě bez mutexů, a pak zpětně extrahuje plán. Neúspěšné cíle si pamatuje jako nogoody. Expanze je polynomiální.

5.5 Další přístupy

SATPlan: časová expanze na $T$ kroků, proměnná pro atom a akci v každém čase.
HTN: hierarchická dekompozice úloh, jako SHOP2.

5.6 Kvíz

Kvíz

1. Ve stavu At(P1, JFK) je akce Fly(P1, JFK, SFO): Aplikovatelná Neaplikovatelná, chybí náklad Relevantní jen zpětně

2. Proč zpětné plánování nepoužije akci, která maže literál cíle? Je dražší Cíl by po ní neplatil Nemá předpoklady

3. Co je léčba hrozby? Může být správně více možností, ale také žádná. Akci dát před producenta Akci dát za konzumenta Nerovnost proměnných Smazat cíl

4. Co se děje v plánovacím grafu s rostoucí vrstvou? Atomy přibývají a mutexy ubývají Atomy ubývají Mutexy přibývají

5. Jakou délku má paralelní plán v příkladu s Load, Fly a Unload? Odpověď:

6. K čemu jsou v plánovacím grafu no-op akce?

Ukázat řešení

Ošetřují rámec: atom, který nikdo nezmění, přejde do další vrstvy. Díky nim jsou i atomy součástí mutexů.

5.7 Příklady na procvičení

Cvičení 5.6

Vyjmenuj aplikovatelné akce ve stavu At(P1, JFK), At(P2, SFO) bez nákladu, pokud jsou jediná letiště JFK a SFO.

Řešení

Jen lety: Fly(P1, JFK, SFO), Fly(P1, JFK, JFK), Fly(P2, SFO, JFK), Fly(P2, SFO, SFO). Zadání nezakazuje let na stejné letiště.

5.8 Tahák

Tahák

Aplikovatelná: $precond^+ \subseteq s$ , $precond^- \cap s = \emptyset$ .
$\gamma(s, a) = (s - e^-) \cup e^+$ .
Zpětně: relevantní akce, $\gamma^{-1}(g, a) = (g - e^+) \cup pre$ .
PSP: otevřený cíl, hrozba a její tři léčby.
Graf: střídání vrstev, no-op, mutexy, monotonie.
SATPlan: časová expanze.

Kapitolu mám prostudovanou