Narrow passage identification using cell decomposition
approximation and minimum spanning tree

D 2015

Narrow passage identification using cell decomposition approximation and minimum spanning tree

ABBADI, Ahmad; Radomil MATOUSEK a Lukas KNISPEL

Základní údaje

Originální název

Narrow passage identification using cell decomposition approximation and minimum spanning tree

Autoři

ABBADI, Ahmad; Radomil MATOUSEK a Lukas KNISPEL

Vydání

Brno, International Conference of Soft Computing, Mendel Journal series, od s. 131-138, 8 s. 2015

Nakladatel

BUT FME

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

elektronická verze "online"

Kód RIV

RIV/00216224:14330/15:00083544

Organizační jednotka

Fakulta informatiky

ISSN

Klíčová slova anglicky

Narrow passage; cell decomposition; minimum spanning tree MST; Motion planning; sampling based algorithm

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 5. 5. 2016 04:28, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

Narrow passage problem is a problematic issue facing the sampling-based motion planner. In this paper, a new approach for narrow areas identification is proposed. The quad-tree cell-decomposition approximation is used to divide the free workspace into smaller cells, and build a graph of adjacency for these. The proposed method follows the graph edges and finds a sequence of cells, which have the same size, preceded and followed by a bigger cell size. The sequence, which has the pattern bigger-smaller-bigger cells size, is more likely to be located in a narrow area. The minimum spanning tree algorithm is used, to linearize adjacency graph. Many methods have been proposed to manipulate the edges cost in the graph, in order to make the generated spanning tree traverse through narrow passages in detectable ways. Five methods have been proposed, some of them give bad results, and the others give better on in simulations

Přiložené soubory

Mendel_JS2015_paper_131_137.pdf

Citovat

ABBADI, Ahmad; Radomil MATOUSEK a Lukas KNISPEL. Narrow passage identification using cell decomposition approximation and minimum spanning tree. Online. In International Conference of Soft Computing, Mendel Journal series. Brno: BUT FME, 2015, s. 131-138. ISSN 1803-3814.

@inproceedings{1308350,
   author = {Abbadi, Ahmad and Matousek, Radomil and Knispel, Lukas},
   address = {Brno},
   booktitle = {International Conference of Soft Computing, Mendel Journal series},
   keywords = {Narrow passage; cell decomposition; minimum spanning tree MST; Motion planning; sampling based algorithm},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Brno},
   pages = {131-138},
   publisher = {BUT FME},
   title = {Narrow passage identification using cell decomposition approximation and minimum spanning tree},
   year = {2015}
}

TY  - CONF
ID  - 1308350
AU  - Abbadi, Ahmad - Matousek, Radomil - Knispel, Lukas
PY  - 2015
TI  - Narrow passage identification using cell decomposition approximation and minimum spanning tree
PB  - BUT FME
CY  - Brno
KW  - Narrow passage
KW  - cell decomposition
KW  - minimum spanning tree MST
KW  - Motion planning
KW  - sampling based algorithm
N2  - Narrow passage problem is a problematic issue facing the sampling-based motion planner. In this paper, a new approach for narrow areas identification is proposed. The quad-tree cell-decomposition approximation is used to divide the free workspace into smaller cells, and build a graph of adjacency for these. The proposed method follows the graph edges and finds a sequence of cells, which have the same size, preceded and followed by a bigger cell size. The sequence, which has the pattern bigger-smaller-bigger cells size, is more likely to be located in a narrow area. The minimum spanning tree algorithm is used, to linearize adjacency graph. Many methods have been proposed to manipulate the edges cost in the graph, in order to make the generated spanning tree traverse through narrow passages in detectable ways. Five methods have been proposed, some of them give bad results, and the others give better on in simulations
ER  -

ABBADI, Ahmad; Radomil MATOUSEK a Lukas KNISPEL. Narrow passage identification using cell decomposition approximation and minimum spanning tree. Online. In \textit{International Conference of Soft Computing, Mendel Journal series}. Brno: BUT FME, 2015, s.~131-138. ISSN~1803-3814.

Přehled o publikaci