3. Automatické plánování
DATUM POSLEDNÍ AKTUALIZACE STRÁNKY: 22. 2. 2023 Editace a obsah (poslední úpravy): L. Smítková Janků
Student si vybere jednu úlohu a jednu variantu zadání (a) nebo (b) nebo (c) a tu řeší.
Varianta (a): Popis úlohy v PDDL a vygenerování plánu z již existujícího plánovače.
Varianta (b): Tvorba vlastního plánovače specifického pro konkrétní úlohu.
Varianta (c): Kompilace úlohy do jazyka PDDL podle vstupních parametrů.
Zadání varianty (a) - Doménové inženýrství
Vyberte si jednu z níže uvedených úloh. Popište ji v jazyce PDDL a vygenerujte plán, který vede k řešení úlohy s nejmenším počtem kroků (optimální plán). Alternativně můžete hledat plány, které vedou k řešení, ale nejsou optimální, nebo plány, které nejsou optimální, např. plány, které najdou řešení v čase kratším než je stanovený čas. Zvažte různé způsoby vyjádření dané úlohy v PDDL. Kódy v PDDL a vygenerovaný plán (nebo plány) nahrajte na gitlab a řešení předveďte cvičícímu.
Zadání varianty (b) - Tvorba plánovače
Vytvořte vlastní plánovač pro konkrétní úlohu z níže uvedených úloh. Soustřeďte se na vlastní algoritmus prohledávání a generování plánu, volit můžete z různých typů neinformovaného a informovaného systamatického prohledávání, je možné použít i lokální prohledávání. Řešení nebude obsahovat parser jazyka PDDL, místo toho bude zadání úlohy resp. její STRIPSová reprezentace zabudovaná přímo do programu. Důležité je, aby řešení používalo principů klasického plánovaní tj. reprezentaci stavů pomocí logických atomů, akce s logickými předpoklady a efekty atd. Řešení nahrajte na gitlab a předveďte cvičícímu.
Zadání varianty (c) - Kompilace úloh
Vytvořte kompilátor dané úlohy do jazyka PDDL. Předpokládejme úlohu s určitými vstupními parametry, cílem je vytvořit program, jehož výstupem bude kód v jazyce PDDL, který bude představovat zadání úlohy ve formě klasického plánovacího problému. Řešením vytvořeného PDDL pak bude řešení konkrétního zadání původní úlohy. Ve výstupním kódu PDDL tedy budou zohledněny vstupní parametry úlohy, tj. například vstupní graf, vstupní číselný parametr atd.
Úlohy
Lišák
Mějme klasické posouvací puzzle o velikosti N x N bloků. Jeden blok v mřížce chybí a na jeho místo můžete posunout sousední blok (shora, zdola, zleva či zprava). Každý blok má své jedinečné číslo od 1 do (N^2-1). Na začátku jsou v mřížce bloky rozmístěny náhodně. Uvazujte, ze lze pohybovat v jednom smeru vice bloky najednou, napr. je-li volne policko na prvnim radku uplne vpravo, lze pohnout celym prvnim radkem o jedno policko vpravo najednou.
Sokoban
V mřížce se stěnami jsou krabice, které musí skladník posunout tlačením na předepsané místo. Úkolem skladníka je dostrkat krabice na cílové místo s co nejmenším počtem kroků. Krokem je přesun skladníka (nikoliv krabice) o jedno místo.
MAPF (Multi-agentní hledání cest, Multi-agent Path Finding)
Úloha se podobá Lišákovi s tím, že místo mřízky máme obecný souvislý neorientovaný graf. Místo dlaždic (bloků) máme očíslované agenty, kteří jsou ve vrcholech, vždy nejvýše jeden agent ve vrcholu. Nějaké vrcholy jsou volné a podobně jako u Lišáka, je možný tah agentem do sousedního volného vrcholu. Cílem je najít posloupnost tahů tak, aby každý agent dorazil do svého cílového vrcholu.
Skladová logistika (Warehouse logistics)
Máme skladiště reprezentované jako mřížkovou mapu, na různých místech ve skladišti jsou uskladněné různé předměty. Dále máme skupinu robotů, přičemž každý robot uveze jeden předmět. Úkolem je pomocí robotů odvézt předměty na zadaná cílová místa. Zpravidla je předmětů násobně více než robotů, rozmístění předmětů ve skladišti je rovnoměrné, ale cílových míst pro předměty je relativně malý počet (v praxi se jedná o místa, kde se předměty zabalují). Výjádřete úlohu jako klasické plánování.
Traveling purchaser problem (TPP)
Jedná se o problém obchodního cestujícího, který navíc nakupuje zboží. Máme řadu produktů a řadu trhů. Na každém trhu je poskytováno omezené množství každého produktu za známou cenu. Cílem obchodního cestujícího je nakoupit zboží podle daného seznamu s minimalizováním nákladů na zboží a nákladů na cestování mezi trhy.
Factory Balls Forever
V každém levelu hry Factory Balls Forever je třeba obarvit míček podle zadaného vzoru. Vzory lze vytvářet pomocí zakrývání určitých částí míčku, přičemž obarvena je zvolenou barvou vždy celá nezakrytá část. Povrch míčku představuje spojitou plochu a je tak třeba při modelování úlohy jako klasického plánování myslet na překonání rozporu mezi spojitou podstatou úlohy a jením diskrétním vyjádřením jako klasického plánování.
Minecraft
Plánovací problém Minecraft se podobá doméně Svět kostek (Blocks World - viz. přednáška), kde navíc máme robota, který manipuluje s kostkami. Robot se pohybuje volně po prostorové mřížce (může létat), kde každá buňka odpovídá bloku (kostce). Robot může vzít blok, pokud se nachází na sousedním políčku. Pokud robot drží blok, může jej položit na sousední políčko. Úkolem je pomocí robota postavit z kostek věž o určité výšce (například 3).
Plánovače
Webové rozhraní "PDDL Editor" s plánovačem: http://editor.planning.domains
Lze použít spolu s jiným plánovačem (odkaz), obsahuje import úloh z řady ročníků ICP.
Plánovač Fast Downward http://www.fast-downward.org/HomePage
Plánovač Fast Forward: https://fai.cs.uni-saarland.de/hoffmann/ff.html (ke stažení zde: https://fai.cs.uni-saarland.de/hoffmann/ff/FF-v2.3.tgz)
Plánovače z některého z ročníků International Planning Competition: https://ipc2018-classical.bitbucket.io/#planners
Řešené úlohy na plánování v PDDL - ukázky
Prezentace ze cvičení - úlohy Hanojské věže, Logistika a Kostičky https://gitlab.fit.cvut.cz/BI-ZUM/bi-zum/blob/master/media/sources/media_tutorials_04_sem4.pdf
Na stránce https://fai.cs.uni-saarland.de/hoffmann/ff-domains.html je sbírka řešených nejznámějších úloh z oblasti plánování (řešení v PDDL). U každé úlohy je uveden popis domén v PDDL a generátor. Pomocí generátoru si můžete vygenerovat PDDL obsahující popis problému.
International Planning Competition - přehled všech ročníků
Vhodné další zdroje k samostudiu dostupné ONLINE (dobrovolné)
I. E-knihy dostupné online přes knihovnu ČVUT - Plánování
Automated Planning : Theory and Practice, Malik Ghallab, , Dana S. Nau, , and Paolo Traverso, Elsevier Science & Technology https://ebookcentral.proquest.com/lib/cvut/reader.action?docID=333985&ppg=46
II. Knihy a další zdroje volně dostupné na internetu
Steven M. LaValle, Planning algorithms, Cambridge University Press, 2006. http://planning.cs.uiuc.edu/
PDDL wiki https://planning.wiki/ref
PDDL https://www.researchgate.net/publication/2278933_PDDL_-_The_Planning_Domain_Definition_Language
Introduction to PDDL http://www.cs.toronto.edu/~sheila/2542/w09/A1/introtopddl2.pdf
Řešené úlohy na plánovní v PDDL https://fai.cs.uni-saarland.de/hoffmann/ff-domains.html