Omezující podmínky v plánování

Abstrakt: V této práci se zabýváme plánovacími problémy a problémy booleovské splnitelnosti. Obě oblasti představují intenzivně řešenou problematiku v rámci umělé inteligence.

Plánovací problém je formulován jako úloha nalezení posloupnosti akcí, pomocí nichž lze dosáhnout daného cíle. Jedna z nejúspěšnějších technik pro řešení plánovacích problémů je založena na koncepci tak zvaného plánovacího grafu. Příslušný algoritmus, který tuto koncepci využívá, se nazývá GraphPlan. V práci jsme identifikovali určitou neefektivitu původního algoritmu GraphPlan a to konkrétně při hledání množiny akcí, které dohromady podporují jistý cíl. Navrhli jsme tento pod-problém modelovat jako problém splňování podmínek, který jsme následně řešili známou metodou udržování hranové konzistence. V práci bylo navrženo několik variant, jak lze hranovou konzistenci v modelu udržovat. Model problému a samotný řešící proces pomocí udržování hranové konzistence jsme pak integrovali zpět do hlavního algoritmu GraphPlan pro řešení plánovacího problému. Provedené experimenty ukázaly, že navrženým modelem a řešící technikou lze až několikanásobně zlepšit celý řešící proces oproti původní verzi algoritmu GraphPlan v mnoha měřitelných charakteristikách (celkový čas řešení, počet návratů, …).

V práci jsme dále navrhli silnější techniku na prořezávání prohledávaného prostoru při řešení problému hledání podporujících akcí. Techniku jsme nazvali projektivní konzistence. Nový druh konzistence je založen na porozumění struktuře řešeného problému. Ukázalo se, že když je problém hledání podpor interpretovaný jako graf, pak je tento graf poměrně dobře strukturovaný - obsahuje malé množství relativně velkých úplných podgrafů. Této vlastnosti bylo využito při vylučování akcí z dalšího uvažování pomocí speciálního odvozovacího mechanismu. Ukázalo se, že tato metoda významně zmenšuje prohledávaný prostor. Provedené experimentální vyhodnocení prokázalo dokonce výrazné zlepšení oproti předchozí metodě založené na udržování hranové konzistence.

Návrhy konzistencí pro plánovací grafy vyústily v popis speciální třídy problémů hledání podpor, které lze řešit v polynomiálním čase. Jestliže problém hledání podpor splňuje jisté podmínky, lze jej tedy snadno řešit a říkáme, že se jedná o polynomiálně řešitelný případ. Navíc byly navrženy heuristiky, které vedou prohledávání tak, aby v obecném případě došlo ke zjednodušení problému na polynomiálně řešitelný případ co nejdříve. Experimentální ověřování navrženého přístupu ukázalo, že technika založená na polynomiálně řešitelném případu je nejúspěšnější ze všech navržených technik. Některé problémy se dokonce podařilo vyřešit bez prohledávání. Na jistých třídách problémů byla tato technika dokonce konkurenceschopná vůči existujícím špičkovým plánovacím systémům.

Přínos této práce spočívá také v příspěvku k řešení problémů booleovské splnitelnosti. Byla navržena speciální technika pro předzpracování problému založená na porozumění strukturální informaci zakódované v problému. Navržená metoda byla nazvána kliková konzistence a jedná se v podstatě o adaptaci projektivní konzistence pro booleovskou splnitelnost. Technika pro předzpracování problému buď rozhodne daný problém booleovské splnitelnosti, nebo problém zjednoduší a ten je poté předán k dořešení obecnému řešícímu systému. Provedené experimenty ukázaly, že kliková konzistence dokáže významně urychlit řešení tříd velmi obtížných problémů booleovské splnitelnosti a to i vůči špičkovým řešícím systémům.

Pomocí následujících odkazů lze stáhnout text disertační práce (v angličtině) a další související materiály (rozšířený abstrakt v angličtině, PowerPointovou prezentaci v češtině a webovou prezentaci v češtině):

• Doktorská disertace  (v angličtině)  
• Rozšířený abstrakt  (v angličtině)  
• Webová Prezentace  (v češtině)  [zvláštní webová stránka]
• Prezentace  (v češtině)  
  [PowerPoint 2007 formát .pptx]  [PowerPoint 2003 formát .ppt]
• Přiložené médium    
  [komprimovaný archiv .zip]  [prohlížet jednotlivé soubory]

Klíčová slova: plánování, programování s omezujícími podmínkami, GraphPlan, plánovací grafy, projektivní konzistence, kliková konzistence, CSP, SAT