Plánovací graf je datová struktura používaná v umělé inteligenci (AI) pro problémy s plánováním . Vizuálně znázorňuje stav světa v průběhu času jako graf a pomáhá najít řešení zkoumáním potenciálních akcí a jejich důsledků.
Klíčové součásti:
* Vrstvy: Graf je uspořádán do vrstev, kde každá vrstva představuje samostatný bod v čase.
* Uzly: Každá vrstva obsahuje uzly představující propozice (fakta o světě) a akce které lze provést.
* Okraje: Hrany spojují uzly napříč vrstvami a zobrazují závislosti .
* Okraje perzistence: Propojte tvrzení, která zůstávají pravdivá z jedné vrstvy do druhé.
* Předběžné okraje: Připojte akce k návrhům, které musí být pravdivé, než bude možné akci provést.
* Okraje efektu: Připojte akce k návrhům, které se po provedení akce stanou pravdivými.
Konstrukce:
Graf plánovače se vytváří iterativně, počínaje počátečním stavem a přidáváním vrstev pro každý časový krok. Každá vrstva je tvořena:
1. Přidávání návrhů: Všechny výroky pravdivé v předchozí vrstvě zůstanou zachovány. Jsou přidány nové návrhy vyplývající z akcí v předchozí vrstvě.
2. Přidání akcí: Jsou přidány všechny akce, jejichž předpoklady jsou v aktuální vrstvě splněny.
Použití:
Graf plánovače se používá k nalezení plánu podle:
* Rozpoznání cíle: Hledání vrstvy, kde jsou všechny návrhy cílů pravdivé.
* Zpětné plánování: Sledování cesty z cílové vrstvy do výchozího stavu, výběr akcí a jejich předpokladů.
* Heuristika: Odhad nákladů na dosažení cíle na základě struktury grafu.
Výhody:
* Vizuální znázornění: Poskytuje intuitivní pochopení procesu plánování.
* Efektivní vyhledávání: Umožňuje rychlé prozkoumání možných plánů.
* Heuristické pokyny: Poskytuje statistiky pro vedení hledání směrem k optimálnímu plánu.
Nevýhody:
* Složitost: U složitých problémů může exponenciálně růst.
* Omezená expresivita: Nemůže reprezentovat všechny typy plánovacích problémů.
Příklad:
Představte si jednoduchý plánovací problém, kdy potřebujete přesunout blok z místa A do místa B. Graf plánovače by ukazoval počáteční stav (blok v A), možné akce (blok přesunu) a cílový stav (blok v B). Graf také ukazuje předpoklady (blok musí být v A, aby se mohl přesunout) a efekty (posunutím bloku bude v B).
Na závěr:
Plánovací graf je cenným nástrojem pro řešení plánovacích problémů. Jeho vizuální reprezentace a efektivní možnosti vyhledávání z něj činí široce používanou techniku v plánování AI. Při výběru vhodného plánovacího algoritmu je však třeba vzít v úvahu jeho složitost a omezení.