Název: Modelování kooperativního hledání cest
Překlad názvu: Modeling of Cooperative Path Finding
Autoři: Ježek, Milan ; Surynek, Pavel (vedoucí práce) ; Majerech, Vladan (oponent)
Typ dokumentu: Bakalářské práce
Rok: 2015
Jazyk: cze
Abstrakt: [cze] [eng]
V této práci jsou popsány nové modely pro řešení kooperativního hledání cest (cpf) s požadavkem na minimální makespan a je provedeno jejich experimentální porovnání se stávajícími modely. Nové modely uvedené v práci zkoumají možnosti kódování problému cpf pomocí celočíselného lineárního programování s binárními proměnnými (bip) a jako problém splnitelnosti omezujících podmínek (csp). Při testech se ukázaly hlavně poměrně dobré výsledky nového modelu IP active-edges při vyšším množství agentů, kdy jen mírně zaostával za nejlepším SAT modelem. Nový model pro csp dosáhl nejrychlejších časů v testech s nízkým množstvím překážek a interakcí mezi agenty, zatímco v opačném případě se jeho výkon dramaticky snižoval. Powered by TCPDF (www.tcpdf.org) In this thesis we describe new models for solving the cooperative pathfinding (cpf) with the requirement of minimal makespan and experimental comparison with current models is performed. These new models investigate the possibilities of encoding the cpf problem into binary integer programming (bip) or constraint satisfaction problem (csp). Mainly the new active-edges IP model tests with high number of agents yielded good results, where it fell only slightly behind the best SAT model. A new csp model reached the fastest times in tests with low number of obstacles and agent interactions while struggling heavily in the opposite cases. Powered by TCPDF (www.tcpdf.org)
Klíčová slova: cooperative path-finding; CSP; IP; SAT; cooperative path-finding; CSP; IP; SAT

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/76384

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


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Bakalářské práce