Čtení: 35 minHodnotí se: test 3 (opakování), zkouška

1 Prohledávání a MAPF

Po přečtení umíš

porovnat DFS, BFS a IDS podle úplnosti, času a paměti
spočítat průběh A* a ověřit přípustnost i monotonii heuristiky
popsat MAPF, makespan a CBS

Test 1 máš napsaný, ale látka se vrací v testu 3, který opakuje všechno, a u zkoušky.

1.1 Ukázka: proč A*

Hledáme cestu z S do G. Greedy by šlo za nejnižší heuristikou a mohlo minout levnější cestu. A* sečte co už stálo a co odhadem zbývá: $f(n) = g(n) + h(n)$ .

1.2 Neinformované prohledávání

$b$ je větvící faktor, $d$ nejmenší hloubka řešení, $m$ největší hloubka.

Algoritmus	Úplnost	Čas	Paměť
DFS	ne	$O(b^m)$	$O(bm)$
BFS	ano	$O(b^{d+1})$	$O(b^{d+1})$
IDS	ano	$O(b^d)$	$O(bd)$

IDS opakuje DFS s rostoucím limitem. Vypadá to plýtvavě, ale nejvíc uzlů je v poslední hloubce, takže čas zůstává $O(b^d)$ a paměť je jako u DFS.

1.3 A*

Definice 1.2 (Přípustnost a monotonie)

Heuristika je přípustná, pokud $h(s) \le h^*(s)$ , tedy nikdy nepřecení cenu k cíli. Monotonní je, pokud $h(s) \le c(s, s') + h(s')$ . Monotonie implikuje přípustnost a ta zaručí optimum.

Příklad 1.3 (Průběh A*)

Hrany: S→A 1, S→B 4, A→B 2, A→C 5, B→C 1, C→G 3. Heuristika: $h(S) = 6$ , $h(A) = 5$ , $h(B) = 3$ , $h(C) = 2$ , $h(G) = 0$ . Najdi pořadí expanzí a cenu.

Řešení

Expanze	Otevřené uzly ( $f$ )
S	A 6, B 7
A	B 6 přes A, C 8
B	C 6 přes B
C	G 7
G	cíl, cena 7

Pořadí S, A, B, C, G a cesta S, A, B, C, G za 7.

RBFS napodobuje A* s lineární pamětí, podobně jako IDS napodobuje BFS.

1.4 MAPF

Definice 1.4 (Multi-Agent Path Finding)

Na grafu se pohybuje více agentů, každý ze startu do cíle, a nesmí se srazit. Přípustné řešení je posloupnost rozmístění, kde každé vznikne povoleným pohybem.

Makespan: počet kroků, než poslední agent dojde do cíle.
Sum-of-costs: celkový počet pohybů.
Nalezení přípustného řešení je v P, optimální je těžké.

CBS má dvě úrovně. Nízká hledá nejkratší cesty s respektem k zákazům $(a_i, v_j, t)$ . Vysoká prochází strom konfliktů: při srážce vytvoří dvě větve a v každé jednomu z agentů zakáže kolizní bod.

PBS místo zákazů používá priority: agent s nižší prioritou bere cesty vyšších jako pevné překážky.

1.5 Kvíz

Kvíz

1. Který algoritmus je úplný a má paměť jako DFS? BFS IDS DFS Greedy

2. Heuristika je vzdušná vzdálenost a hrany jsou silnice. Je přípustná? Ano Ne

3. Co platí? Může být správně více možností, ale také žádná. Monotonie implikuje přípustnost Přípustná heuristika může přecenit A* s přípustnou h najde optimum

h = 0

je přípustná

4. Co přidá CBS na vysoké úrovni při konfliktu? Priority agentů Dvě větve, v každé zákaz pro jednoho agenta Novou heuristiku

5. Vysvětli rozdíl mezi makespan a sum-of-costs.

Ukázat řešení

Makespan měří, kdy skončí poslední agent. Sum-of-costs sčítá pohyby všech. Dvě řešení mohou mít stejný makespan a různý součet.

1.6 Příklady na procvičení

Cvičení 1.5

Je $h(A) = 7$ v příkladu výše přípustná?

Řešení

Ne, přímá cena z A do G je 6, takže $h(A) = 7$ přeceňuje.

1.7 Tahák

Tahák

DFS neúplné, BFS úplné a paměťově drahé, IDS úplné s malou pamětí.
$f = g + h$ . Přípustná: $h \le h^*$ . Monotonní: $h(s) \le c + h(s')$ .
Monotonní ⇒ přípustná ⇒ optimum.
MAPF: makespan, sum-of-costs, CBS zákazy, PBS priority.

Kapitolu mám prostudovanou