Detail publikace
Identifikace "narrow passage" s využitím aproximativní dekompozice prostoru a minimální kostry grafu
ABBADI, A. MATOUŠEK, R. KNISPEL, L.
Český název
Identifikace "narrow passage" s využitím aproximativní dekompozice prostoru a minimální kostry grafu
Anglický název
Narrow passage identification using cell decomposition approximation and minimum spanning tree
Typ
článek v časopise ve Scopus, Jsc
Jazyk
en
Originální abstrakt
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
Český abstrakt
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
Anglický abstrakt
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
Klíčová slova anglicky
Narrow passage, cell decomposition, minimum spanning tree MST, Motion planning, sampling based
Rok RIV
2015
Vydáno
23.06.2015
Místo
Brno
ISSN
1803-3814
Kniha
Mendel 2015, 21st International Conference on Soft Computing
Ročník
2015
Číslo
21
Strany od–do
131–138
Počet stran
8
BIBTEX
@article{BUT115144,
author="Ahmad {Abbadi} and Radomil {Matoušek} and Lukáš {Knispel},
title="Narrow passage identification using cell decomposition approximation and minimum spanning tree",
booktitle="Mendel 2015, 21st International Conference on Soft Computing",
year="2015",
volume="2015",
number="21",
month="June",
pages="131--138",
address="Brno",
issn="1803-3814"
}