/ プログラム/ 発表一覧/ 著者一覧企業展示一覧/ jsai2017ホーム /

3O1-4 Independence Detection in SAT-based Multi-Agent Path Finding

*セッションの無断動画配信はご遠慮下さい。

Tweet #jsai2017 このエントリーをはてなブックマークに追加

05月25日(Thu) 13:50〜15:30 O会場(ウインクあいち-10F 1007会議室)
3O1 基礎・理論「基礎・理論-論理・推論・プランニング」

演題番号3O1-4
題目Independence Detection in SAT-based Multi-Agent Path Finding
著者Surynek Pavel(AIST)
Svancara Jiri(Charles University)
Felner Ariel(Ben Gurion University)
Boyarski Eli(Bar Ilan University)
時間05月25日(Thu) 14:50〜15:10
概要The problem of optimal multi-agent path finding (MAPF) is addressed in this paper. The task is to find optimal paths for mobile agents where each of them need to reach a unique goal position from the given start with respect to the given cost function. Agents must not collide with each other which is a source of combinatorial difficulty of the problem. An abstraction of the problem where discrete agents move in an undirected graph is usually adopted in the literature. Specifically, it is shown in this paper how to integrate independence detection (ID) technique developed for search based MAPF solving into a compilation-based technique that translates the instance of the MAPF problem into propositional satisfiability formalism (SAT). The independence detection technique allows decomposition of the instance consisting of a given number of agents into instances consisting of small groups of agents with no interaction across groups. These small instances can be solved independently and the solution of the original instance is combined from small solutions eventually. The reduction of the size of instances translated to the target SAT formalism has a significant impact on performance as shown in the presented experimental evaluation.
論文PDFファイル