Rectilinear Voronoi Diagram-Based Motion Planning in the Plane with Obstacles

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F04%3APU46992" target="_blank" >RIV/00216305:26210/04:PU46992 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Rectilinear Voronoi Diagram-Based Motion Planning in the Plane with Obstacles

Original language description

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 othersite. 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 paath 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.

Czech name

Plánování pohybu v rovině s překážkami pomocí rektilineárního Voronoiova diagramu

Czech description

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 pozzicí 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.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

JD - Use of computers, robotics and its application

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2004

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Elektronika

ISSN

0033-2089

e-ISSN

—

Volume of the periodical

2004

Issue of the periodical within the volume

8-9

Country of publishing house

PL - POLAND

Number of pages

3

Pages from-to

24-26

UT code for WoS article

—

EID of the result in the Scopus database

—