Lessons Learned from the Effort to Solve Cooperative Path-Finding Optimally: Reductions to Propositional Satisfiability

Kód výsledku v IS VaVaI

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

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Lessons Learned from the Effort to Solve Cooperative Path-Finding Optimally: Reductions to Propositional Satisfiability

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 in CPF is to relocate a set of agents to given goal locations so that they do not collide with eachother. Recent findings indicate that a simple direct encoding outperforms the more elaborate encodings based on binary encodings of multi-value state variables. The direct encoding is further improved by a hierarchical build-up that uses auxiliary variables to reduce its size in this work. The conducted experimental evaluation shown that the simple design of the encoding together with new improvements which reduced its size significantly are key enablers for faster solving of the encoded CPFs than withexisting encodings. It has been also shown that the SAT based methods dominates over A* based methods in envi-ronments with high occupancy by agents.

Název v anglickém jazyce

Lessons Learned from the Effort to Solve Cooperative Path-Finding Optimally: Reductions to Propositional Satisfiability

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 in CPF is to relocate a set of agents to given goal locations so that they do not collide with eachother. Recent findings indicate that a simple direct encoding outperforms the more elaborate encodings based on binary encodings of multi-value state variables. The direct encoding is further improved by a hierarchical build-up that uses auxiliary variables to reduce its size in this work. The conducted experimental evaluation shown that the simple design of the encoding together with new improvements which reduced its size significantly are key enablers for faster solving of the encoded CPFs than withexisting encodings. It has been also shown that the SAT based methods dominates over A* based methods in envi-ronments with high occupancy by agents.

Druh

O - Ostatní výsledky

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ů