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

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Lessons Learned from the Effort to Solve Cooperative Path-Finding Optimally: Reductions to Propositional Satisfiability Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	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 each other. 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 with existing encodings. It has been also shown that the SAT based methods dominates over A* based methods in envi-ronments with high occupancy by agents. 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 each other. 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 with existing encodings. It has been also shown that the SAT based methods dominates over A* based methods in envi-ronments with high occupancy by agents. (en)
Title	Lessons Learned from the Effort to Solve Cooperative Path-Finding Optimally: Reductions to Propositional Satisfiability Lessons Learned from the Effort to Solve Cooperative Path-Finding Optimally: Reductions to Propositional Satisfiability (en)
skos:prefLabel	Lessons Learned from the Effort to Solve Cooperative Path-Finding Optimally: Reductions to Propositional Satisfiability Lessons Learned from the Effort to Solve Cooperative Path-Finding Optimally: Reductions to Propositional Satisfiability (en)
skos:notation	RIV/00216208:11320/14:10287452!RIV15-MSM-11320___
http://linked.open...avai/riv/aktivita	I P
http://linked.open...avai/riv/aktivity	I, P(GAP103/10/1287)
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Surynek, Pavel
http://linked.open.../riv/druhVysledku	O - Ostatní výsledky nezařaditelné do žádného z výše uvedených druhů výsledku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	26023
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/14:10287452
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	A*; SAT encodings; propositional satisfiability (SAT); cooperative path-finding (CPF) (en)
http://linked.open.../riv/klicoveSlovo	A* SAT encodings cooperative path-finding (CPF) propositional satisfiability (SAT)
http://linked.open...ontrolniKodProRIV	[69C7F5950BEF]
http://linked.open...in/vavai/riv/obor	JD
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	1 (xsd:int)
http://linked.open...vavai/riv/projekt	PlanEx: Bridging Planning and Execution
http://linked.open...UplatneniVysledku	2014
http://linked.open...iv/tvurceVysledku	Surynek, Pavel
http://localhost/t...ganizacniJednotka	11320

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 112 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software