Graphplan - Graphplan - Wikipedia

Graphplan je algoritmus pro automatické plánování vyvinutý uživatelem Avrim Blum a Merrick Furst v roce 1995. Graphplan bere jako vstup problém plánování vyjádřený v PÁSKY a produkuje, je-li to možné, sled operací pro dosažení stavu cíle.

Název grafplán je kvůli použití románu plánování graf, aby se snížilo množství hledání potřebné k nalezení řešení z přímého průzkumu stavový prostorový graf.

V stavový prostorový graf:

  • uzly jsou možné stavy,
  • a hrany označují dosažitelnost prostřednictvím určité akce.

Naopak v Graphplan plánovací graf:

  • uzly jsou akce a atomová fakta, uspořádané do alternativních úrovní,
  • a hrany jsou dvou druhů:
    1. od atomové skutečnosti k činům, pro které je podmínkou,
    2. od akce k atomovým faktům je pravda nebo nepravda.

první úroveň obsahuje skutečná atomová fakta identifikující počáteční stav.

Rovněž jsou udržovány seznamy nekompatibilních skutečností, které nemohou být pravdivé současně, a nekompatibilních akcí, které nelze provést společně.

Algoritmus poté iterativně rozšiřuje plánovací graf, což dokazuje, že neexistují žádná řešení délky l-1 před hledáním plánů délka l zpětným zřetězením: za předpokladu, že jsou cíle pravdivé, Graphplan hledá akce a předchozí stavy, ze kterých lze cílů dosáhnout, a prořezává jich co nejvíce díky informacím o nekompatibilitě.

Úzce souvisejícím přístupem k plánování je Plánování jako uspokojivost (Satplan ). Oba snižují problém s automatizovaným plánováním a hledají plány různých délek fixního horizontu.

Reference

externí odkazy