1. Automatické plánování, plánovací graf, kompilace plánování do jiných formalismů jako je SAT nebo CSP, hierarchické plánování, plánování v prostoru plánů. Plánování pohybu a problém lokalizace v robotice. (NI-UMI)¶

Automatické plánování¶

Automatické plánování je oblast umělé inteligence, která se zabývá hledáním posloupnosti akcí vedoucích k dosažení určitého cíle. Jedna se o úlohy s velkou složitostí od NP až po EXPSPACE

Praktické využití:

Robotika (humanoidní a manipulační roboti)
Doprava (montáž výrobků, logistika)
Hry (strategické plánování, návrh úrovní)

Druhy plánování:

Klasické
Stochastické/pravděpodobnostní (akce s pravděpodobností úspěchu)
Plánování pro dynamické prostředí (prostředí se mění nezávisle na agentovi)

Vlastnosti plánování¶

Klasické plánování:

Plně pozorovatelné prostředí
Deterministické akce
Konečný stavový prostor
Statické prostředí
Diskrétní stavy
Offline plánování (nejdřív plán, pak vykonání)

Stochastické/pravděpodobnostní:

Akce mají pravděpodobnost úspěchu
Nejistý výsledek akcí
Nutnost zvažovat různé možné výsledky

Plánování pro dynamické prostředí:

Prostředí se mění nezávisle na agentovi
Nutnost adaptace na změny
Možná potřeba přeplánování

Základní komponenty¶

Vyjadřovací prostředky:

Jazyk:
- Konstanty
- Predikátové symboly
Stavy:
- Konečné množiny základních atomů
- Predikátové symboly s dosazenými konstantami
- Platí princip uzavřeného světa
Cíl:
- Částečná specifikace stavu
- Definován konečnou množinou literálů
Operátor $o(name(o), precond(o), effects(o))$ :
- $name(o)$ - jméno a seznam parametrů
- $precond(o)$ - množina literálů pro aplikaci
- $effects(o)$ - množina literálů po provedení
Akce:
- Základní instance operátoru vzniklá substitucí
- Aplikovatelná když $precond^+(A) \subseteq S$ a $precond^-(A) \cap S = \emptyset$
- Efekt: $(S - effect^-(A)) \cup effect^+(A)$

Plánovací doména:

Definována jazykem $L$ a množinou operátorů $O$
Určuje:
- Množinu stavů $S$
- Množinu akcí $A$
- Funkci následníka $y: S \times A \rightarrow S$

Jednoduché plány a řešení¶

Plánovací problém je trojice $(Σ,s_0,S_g)$ využívající jazyk $L$ a operátory $O$ , kde:

$Σ = (S,A,γ)$ je stavový prostor s přechody
$s_0$ je počáteční stav
$S_g$ je množina cílových stavů
Problem je najit přechod z $s_0$ do jednoho z cílových stavu $S_g$
Plan je posloupnost akci $\pi = [a_i,a_2,a_3,...,a_n]$ kde $a_i$ je instancí nějakého operatoru z $O$
Priklad:
s0 = {
- attached(p1,loc1),
- in(c1,p1),
- in(c3,p1),
- top(c3,p1),
- on(c3,c1),
- on(c1,pallet),
- attached(p2,loc1),
- in(c2,p2),
- top(c2,p2),
- on(c2,palet),
- belong(crane1,loc1),
- empty(crane1),
- adjacent(loc1,loc2),
- adjacent(loc2,loc1),
- at(r1,loc2),
- occupied(loc2),
- unloaded(r1)}

Dopředné plánování¶

Princip:

Začínáme v počátečním stavu $s_0$
Aplikujeme možné akce a generujeme následníky
Hledáme cestu do cílového stavu
Používá se prohledávání stavového prostoru (BFS, DFS, ...)

Vlastnosti:

Vysoký větvící faktor
Vhodné pro problémy s málo možnými akcemi
Jednodušší implementace

Zpětné plánování¶

Princip:

Začínáme v cílovém stavu
Aplikujeme inverzní operátory
Hledáme cestu do počátečního stavu

Inverzní aplikace operátorů:

Pro operátor $o$ definujeme inverzní operátor $o^{-1}$ :
- Předpoklady $o^{-1}$ jsou efekty $o$
- Efekty $o^{-1}$ jsou předpoklady $o$
Lze využít proměnné (liftování):
- Technika která zavádí proměnné místo konkrétních konstant
- Používá nejobecnější unifikaci (mgu)
- Nutno udržovat posloupnost unifikací
- Redukuje větvící faktor

Výhody:

Menší větvící faktor než u dopředného plánování
Cílový stav je často specifikován částečně
Efektivnější pro problémy s jasně definovaným cílem
Liftování dále snižuje větvící faktor

Nevýhody:

Složitější implementace
Nutnost definovat inverzní operátory
Ne všechny operátory lze invertovat
Nutnost správy unifikací při použití proměnných

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

Princip:

Postupné opravování částečného plánu, který obsahuje:
- Množinu částečně instanciováných operátorů
- Množinu podmínek:
  1. Precedenční (akce $a$ předchází $b$ )
  2. Vazbové (rovnosti, nerovnosti, substituce)
  3. Kauzální (akce $a$ nastavuje předpoklad $p$ pro akci $b$ )

Algoritmus:

Začínáme s částečným plánem obsahujícím fiktivní akce:
- $a_0$ : $precond(a_0) = \emptyset, effect(a_0) = s_0$
- $a_{\infty}$ : $precond(a_{\infty}) = g, effect(a_{\infty}) = \emptyset$
Iterativně opravujeme kazy:
- Kaz 1: Otevřený cíl
  - Situace: Akce má předpoklad $p$ , který není nastaven
  - Řešení:
    1. Najít akci produkující $p$
    2. Instanciovat proměnné/nastavit vazby
    3. Nastavit kauzální podmínku
- Kaz 2: Hrozba
  - Situace: Akce $c$ může smazat předpoklad $p$ produkovaný akcí $a$ pro akci $b$
  - Řešení (jedna z možností):
    1. Přidat precedenci $b$ před $c$
    2. Přidat precedenci $c$ před $a$
    3. Přidat vazbovou podmínku nerovnosti
Proces končí, když neexistují žádné kazy

Výstup:

Částečně uspořádaný plán
Každé úplné uspořádání plánu je validním řešením

Problémy předchozích algoritmů¶

velký větvící faktor
- aplikovatelných základních instancí operátoru je mnoho
- různé permutace akcí vedou ke stejnému výsledku
příliš dlouhé plány
- plánujeme na mikroúrovni pomocí jednoduchých akcí
- algoritmus nevidí celkový kontext

Plánovací graf¶

Základní koncept:

Vrstevnatý orientovaný graf pro analýzu dosažitelnosti stavů
Střídají se stavové ( $P_0,P_1,...$ ) a akční ( $A_1,A_2,...$ ) vrstvy
Komprimuje stavový prostor a aproximuje dosažitelnost

Struktura grafu¶

Hrany:

Z $P_i$ do $A_{i+1}$ :
Ukazují předpoklady akce
Vedou z atomu do akce, pro niž je atom předpokladem
Z $A_i$ do $P_i$ :
Ukazují efekty akce
Pozitivní (plná čára)
Negativní (čárkovaná čára)

Vlastnosti:

Platí $P_0 \subseteq P_1 \subseteq P_2 \subseteq ...$
Atomy se přenášejí do další vrstvy (axiom rámce)
Negativní efekty nemažou předchozí atomy

Paralelní plány¶

Definice: $\Pi = [\pi_1, \pi_2,..., \pi_k]$

Posloupnost množin akcí $\pi_i$ , kde $\pi_i \subseteq A_i$
Akce lze provést paralelně nebo v libovolném pořadí
Reprezentuje $|\pi_1|! \times |\pi_2|! \times ... \times |\pi_k|!$ sekvenčních plánů

Nezávislost akcí:

Pro dvojici akcí $(a,b)$ : $effect^-(a) \cap (precond(b) \cup effect^+(b)) = \emptyset \wedge effect^-(b) \cap (precond(a) \cup effect^+(a)) = \emptyset$
Množina akcí je nezávislá, pokud je každá dvojice nezávislá

Mutexy (vzájemné vyloučení)¶

Typy:

Mezi akcemi:
- Akce jsou závislé
- Předpoklad jedné akce je mutex s předpokladem druhé
Mezi atomy:
- Každá akce produkující první atom je mutex s každou akcí produkující druhý atom
- Neexistuje akce produkující oba atomy

Vlastnosti mutexů:

Monotonie: $\mu P_i \supseteq \mu P_{i+1}, \mu A_i \supseteq \mu A_{i+1}$
Používají se pro zpřesnění aproximace dosažitelnosti

GRAPHPLAN algoritmus¶

Fáze:

Expanze plánovacího grafu:
- Přidávání vrstev dokud není cílový stav bez mutexů
- Polynomiální časová a prostorová složitost
Extrakce paralelního plánu:
- Hledání bez-mutexových množin akcí
- Využívá tabulku nogoodů pro detekci selhání
- Rekurzivní proces od cíle k počátku

Vlastnosti:

Úplný algoritmus
Efektivní komprese stavového prostoru
Detekce zacyklení pomocí tabulky nogoodů

Převod plánovaní do jiných formalizmu¶

Převod na SAT¶

Základní princip:

Atomům přiřadíme výrokové proměnné
Stavy odpovídají ohodnocení proměnných
Cíl vynutíme pomocí klauzulí

Časová expanze:

Pro každý časový krok $t$ zavedeme:
- Proměnné pro atomy: $p_t \in \{True, False\}$
- Proměnné pro akce: $a_t \in \{True, False\}$
Podmínky:
- Předpoklady akce: $a_t \Rightarrow \bigwedge_{p \in precond(a)}p_t$
- Efekty akce: $a_t \Rightarrow \bigwedge_{e \in effect(a)}e_{t+1}$
- Počáteční stav: $\bigwedge_{p \in s_0} p_0 \wedge \bigwedge_{p \notin s_0} \neg p_0$
- Cílový stav: $\bigwedge_{p \in g^+} p_T \wedge \bigwedge_{p \in g^-} \neg p_T$
- Axiomy rámce:
  - $\neg p_t \wedge p_{t+1} \Rightarrow \bigvee_{p \in effect^+(a)} a_t$
  - $p_t \wedge \neg p_{t+1} \Rightarrow \bigvee_{p \in effect^-(a)} a_t$

SATPLAN:

Využívá plánovací graf pro určení atomů a akcí
Mutexy z plánovacího grafu přirozeně podporují jednotkovou propagaci

Převod na CSP¶

Hlavní rozdíly oproti SAT:

Používá stavové proměnné místo výrokových
Automatická detekce stavových proměnných pomocí klik v grafu mutexů
Podmínky jsou zajištěny vlastnostmi funkcí a přiřazení

Struktura:

Stavové proměnné:
- $loc(r)_t \in Locations$ pro roboty $r$ a čas $t$
- $act_t \in Actions$ pro akce v čase $t$
Podmínky:
- Podobné jako u SAT, ale využívají stavové proměnné
- Například: $act_t = Move(r1,l1,l2) \Rightarrow loc(r1)_t = l1 \wedge loc(r1)_{t+1} = l2$

Hierarchické plánování (HTN)¶

HTN (Hierarchical Task Network) je přístup k plánování, který řeší problém příliš dlouhých plánů pomocí hierarchické dekompozice úkolů.

Základní princip¶

Operátory reprezentují komplexnější akce
Obsahují návod (metody) jak operátor vykonat
Návod se skládá z:
- Rozkladu na jednodušší úkoly
- Podmínek pro rozklad

Metoda je definována jako čtveřice:

m = (name(m), task(m), subtasks(m), constr(m))

Úkolová síť¶

Skládá se z:

Stavu $s$
Úkolové sítě $(U,C)$ , kde:
- $U$ jsou uzly
- $C$ jsou podmínky
Množiny operátorů $O$ (primitivní)
Množiny metod $M$ (komplexní)

Dekompozice úkolové sítě¶

Proces:

Postupná dekompozice úkolů v síti
Přidávání podmínek precedence
Rozklad složitých úkolů na jednodušší

Výhody:

Lepší nasměrování k cíli než klasické plánování
Možnost integrace expertních znalostí domény
Použitelné pro reálné úlohy (ne jen akademické příklady)
Flexibilita při modifikaci a optimalizaci sítě úkolů

Plánování pohybu a problém lokalizace v robotice¶

Typy pohybů

z bodu do bodu (celý robot, nebo jen efektor)
souladný (robot v kontaktu s překážkou)

Konfigurační prostor

poloha, orientace, natočení kloubů
hledání cesty spojující počáteční a cílovou konfigurace (v konfigurační spojitém prostoru)
reprezentace pomocí pracovních souřadnic
- pozice prvků robota (kleští, zápěstí)
- plně popisuje pozici
- vhodná na detekci kolizí
reprezentace pomocí konfigurací
- natočení kloubů ramena a zápěstí
dopředná kinematika:
- známe otočení kloubů, tj. konfiguraci, chceme určit polohu efektoru (lineární transformace)
inverzní kinematika:
- známe pozici efektoru reprezentovanou pracovními souřadnicemi, chceme určit konfiguraci (složitá transformace)

Řešení spojitosti

rozklad na buňky
skeletonizace:
- spojitý problém hledání cesty se převede na hledání cesty v diskrétním prostoru (grafu)
- Voroného diagram = množina bodů, které mají stejnou vzdálenost ke dvěma a více překážkám; tvoří graf, v němž je problém hledání cesty jednodimenzionální
- pravděpodobnostní mapa = generujeme náhodné konfigurace; spojíme ty, mezi nimiž vede „snadná“ cesta

Mimo kinematický stav (konfiguraci) je nutno uvažovat i dynamický stav (rychlost). Řešení pomocí metody kontroleru = je-li hodnota nějaké stavové proměnné xt odchýlena od požadované y(t), robot ji kompenzuje působením at (síla efektoru).

Lokalizace

známe počáteční polohu a přechodový model pro pohyb
Skuteční roboti jsou poněkud méně předvídatelní (nejsou determinističtí)
Vědět kde se co nachází je pro robota klíčové, jedná se o nejběžnější příklad procesu vnímání
- Pro lokalizaci se používají různé modely
  - Monte Carlo
  - Kálmánův Filtr