Název: Vylepšení syntézy kontrolerů pro POMDP s využitím abstrakce a podobnosti.
Překlad názvu: Using inheritance dependencies to accelerate abstraction-based synthesis of finite-state controllers for POMDPs.
Autoři: Shevchenko, Aleksandr ; Macák, Filip (oponent) ; Češka, Milan (vedoucí práce)
Typ dokumentu: Bakalářské práce
Rok: 2024
Jazyk: eng
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [eng] [cze]
Částečně pozorovatelný Markovský rozhodovací proces (POMDP) je důležitým modelem pro autonomní plánování, který se používá v mnoha oblastech, jako je robotika a biologie. Tato práce se zaměřuje na metodu Abstraction-Refinement pro induktivní syntézu konečně stavových kontrolérů (FSC) pro POMDP. Klasická verze AR vyžaduje model checking quotient MDP pro celou množinu kompatibilních akcí podrodiny v každé iteraci. My navrhujeme algoritmus, který využívá dědičné závislosti ke snížení velikosti masky pro quotient MDP a ke zrychlení model checkingu pro podrodiny FSC. Také představujeme chytrou verzi tohoto algoritmu, která zachovává všechny jeho výhody a snižuje jeho slabiny. Během experimentů se ukázalo, že náš přístup také ovlivňuje činnost jiných částí syntézy, jako je např. model building. V závislosti na modelu POMDP, pozorujeme jak zrychlení, tak zpomalení ve srovnání s AR. V průměru naše metoda zrychluje celkovou dobu syntézy 1.2 krát a v některých případech až desetkrát. Partially observable Markov decision process is an important model for autonomous planning used in many areas, such as robotics and biology. This work focuses on the Abstraction-Refinement framework for the inductive synthesis of finite-state controllers (FSCs) for POMDPs. The classic version of AR requires model checking of a quotient MDP for an entire set of compatible choices of the subfamily in each iteration. We propose an algorithm that uses inheritance dependencies to reduce the size of the quotient MDP’s mask and accelerate model checking for subfamilies of FSCs. We also introduce a smart version of this algorithm, which preserves all its advantages and reduces its weaknesses. During the experiments, it turned out that our approach also affects the operation of other parts of the synthesis, e.g. model building. Depending on the POMDP model, we observe both speedups and slowdowns in comparison to AR. On average, our approach speeds up the overall synthesis time by 1.2 times, and in some cases up to the factor 10.
Klíčová slova: finite-state controller synthesis; inheritance dependencies for Markov models; model checking; Partially observable Markov decision process; dědičné závislosti pro Markovské modely; model checking; syntéza konečně stavových kontrolérů; Částečně pozorovatelný Markovský rozhodovací proces

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: https://hdl.handle.net/11012/246617

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-617587


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Bakalářské práce