Original title: Modelování kooperativního hledání cest
Translated title: Modeling of Cooperative Path Finding
Authors: Ježek, Milan ; Surynek, Pavel (advisor) ; Majerech, Vladan (referee)
Document type: Bachelor's theses
Year: 2015
Language: cze
Abstract: [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)
Keywords: cooperative path-finding; CSP; IP; SAT; cooperative path-finding; CSP; IP; SAT

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/76384

Permalink: http://www.nusl.cz/ntk/nusl-345796


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses