Planering i kontradiktoriska och osäkra miljöer kan modelleras som problemet med att utforma strategier i stokastiska perfekta information spel. Dessa spel är generaliseringar av Markov beslutsprocesser (MDP): det finns två (adversariella) spelare, och en källa till slumpmässighet. Det största praktiska hindret för att beräkna vinnande strategier i sådana spel är storleken på det statliga utrymmet. I praktiken arbetar man därför vanligtvis med abstraktioner av modellen. Svårigheten är att komma på en abstraktion som varken är för grov för att ta bort alla vinnande strategier (planer), eller för fin för att vara svåråtkomlig. I verifieringen har paradigmet för motexempelstyrda abstraktionsförfining varit framgångsrikt att konstruera användbara men parsimoniska abstraktioner automatiskt. Vi utvidgar detta paradigm till probabilistiska modeller (nämligen perfekta informationsspel och, som ett specialfall, MDPs). Detta gör det möjligt för oss att tillämpa det kontraexempelstyrda abstraktionsparadigmet på AI-planeringsproblemet. Som specialfall får vi planeringsalgoritmer för MDP och deterministiska system som automatiskt konstruerar systemabstractioner.
Det arbete som kommer närmast vårt i en planeringsmiljö använder CEGAR för stochastic perfekt information spel, en generalisering av Markov beslutsprocesser REF.
Counterexample-guided Planning
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}