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

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

About: Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs 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 is to relocate set of agents to given goal positions so that they do not collide with each other. A novel 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. 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. A novel 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. (en)
Title	Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs (en)
skos:prefLabel	Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs Compact Representations of Cooperative Path-Finding as SAT Based on Matchings in Bipartite Graphs (en)
skos:notation	RIV/00216208:11320/14:10287451!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	D - Článek ve sborníku
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	7904
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/14:10287451
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	A*; bipartite graphs; matchings; encodings; propositional satisfiability (SAT); cooperative path-finding (CPF) (en)
http://linked.open.../riv/klicoveSlovo	bipartite graphs A* cooperative path-finding (CPF) propositional satisfiability (SAT) encodings matchings
http://linked.open...ontrolniKodProRIV	[80A7587695CE]
http://linked.open...v/mistoKonaniAkce	Greece
http://linked.open...i/riv/mistoVydani	Greece
http://linked.open...i/riv/nazevZdroje	Proceedings of the 26th International Conference on Tools with Artificial Intelligence
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://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2014-11-10 (xsd:date)
number of pages	8 (xsd:int)
http://purl.org/ne...btex#hasPublisher	IEEE
https://schema.org/isbn	978-1-4799-6572-4
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, 48 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software