Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10287451" target="_blank" >RIV/00216208:11320/14:10287451 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs

Popis výsledku v původním jazyce

This paper addresses makespan optimal solving of cooperative path-finding problem (CPF) by translating it to propositional satisfiability (SAT). The task is to relocate set of agents to given goal positions so that they do not collide with each other. Anovel SAT encoding of CPF is suggested. The novel encoding uses the concept of matching in a bipartite graph to separate spatial constraint of CPF from consideration of individual agents. The separation allowed reducing the size of encoding significantly. The conducted experimental evalua-tion shown that novel encoding can be solved faster than exist-ing encodings for CPF and also that the SAT based methods dominates over A* based methods in environment densely occupied by agents.

Název v anglickém jazyce

Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs

Popis výsledku anglicky

This paper addresses makespan optimal solving of cooperative path-finding problem (CPF) by translating it to propositional satisfiability (SAT). The task is to relocate set of agents to given goal positions so that they do not collide with each other. Anovel SAT encoding of CPF is suggested. The novel encoding uses the concept of matching in a bipartite graph to separate spatial constraint of CPF from consideration of individual agents. The separation allowed reducing the size of encoding significantly. The conducted experimental evalua-tion shown that novel encoding can be solved faster than exist-ing encodings for CPF and also that the SAT based methods dominates over A* based methods in environment densely occupied by agents.

Druh

D - Stať ve sborníku

CEP obor

JD - Využití počítačů, robotika a její aplikace

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP103%2F10%2F1287" target="_blank" >GAP103/10/1287: PlanEx: Propojení plánování a provádění plánů</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2014

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 26th International Conference on Tools with Artificial Intelligence

ISBN

978-1-4799-6572-4

ISSN

—

e-ISSN

—

Počet stran výsledku

8

Strana od-do

875-882

Název nakladatele

IEEE

Místo vydání

Greece

Místo konání akce

Greece

Datum konání akce

10. 11. 2014

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—