Detail publikace
Plánování pohybu v rovině s překážkami pomocí rektilineárního Voronoiova diagramu
ŠEDA, M.
Český název
Plánování pohybu v rovině s překážkami pomocí rektilineárního Voronoiova diagramu
Anglický název
Rectilinear Voronoi Diagram-Based Motion Planning in the Plane with Obstacles
Typ
článek v časopise - ostatní, Jost
Jazyk
en
Originální abstrakt
A Voronoi diagram of a set of sites in the Euclidean plane is a collection of regions that divide up the plane. Each region corresponds to one of the sites and all the points in one region are closer to the site representing the region than to the other site. Voronoi diagrams have a surprising variety of uses, e.g. nearest neighbour search, facility location, path planning, etc. In this paper, we investigate the problem of 8-directional robot motion planning where the goal is to find a collision-free path from the starting to the target position in the 2D space containing point and rectangular obstacles. In contrast to the traditional approaches frequently based on genetic algorithms, we propose a method for solving this problem using rectilinear Voronoi diagrams.
Český abstrakt
Voronoiův diagram množiny bodů v euklidovské rovině je rozklad roviny na oblasti splňující, že jejich počet je roven počtu zadaných bodů, v každé oblasti leží právě jeden zadaný bod a všechny ostatní body oblasti jsou ke svému generujícímu bodu blíže než ke všem dalším zadaným bodům. Voronoiovy diagramy mají překvapivě široký počet aplikací, např. hledání nejbližšího souseda, rozmístění zařízení, plánování cesty atd. V příspěvku zkoumáme problém hledání bezkolizní cesty robotu mezi výchozí a cílovou pozicí v rovině s bodovými a obdélníkovými překážkami při omezení pohybu robotu na 8 směrů. Na rozdíl od tradičních přístupů často založených na genetických algoritmech zde navrhujeme metodu využívající rektilineární Voronoiovy diagramy.
Anglický abstrakt
A Voronoi diagram of a set of sites in the Euclidean plane is a collection of regions that divide up the plane. Each region corresponds to one of the sites and all the points in one region are closer to the site representing the region than to the other site. Voronoi diagrams have a surprising variety of uses, e.g. nearest neighbour search, facility location, path planning, etc. In this paper, we investigate the problem of 8-directional robot motion planning where the goal is to find a collision-free path from the starting to the target position in the 2D space containing point and rectangular obstacles. In contrast to the traditional approaches frequently based on genetic algorithms, we propose a method for solving this problem using rectilinear Voronoi diagrams.
Klíčová slova anglicky
motion planning, Voronoi diagram, rectilinear metric
Rok RIV
2004
Vydáno
01.09.2004
ISSN
0033-2089
Časopis
Elektronika
Ročník
2004
Číslo
8-9
Počet stran
3
BIBTEX
@article{BUT46231,
author="Miloš {Šeda},
title="Rectilinear Voronoi Diagram-Based Motion Planning in the Plane with Obstacles",
journal="Elektronika",
year="2004",
volume="2004",
number="8-9",
month="September",
issn="0033-2089"
}