Robot Motion Planning in the Plane with Polygonal Obstacles

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F08%3APU76869" target="_blank" >RIV/00216305:26210/08:PU76869 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Robot Motion Planning in the Plane with Polygonal Obstacles

Original language description

The task of planning trajectories plays an important role in transportation, robotics, etc. In robot motion planning, the robot should find a collision-free path from the starting to the target position. Research on path planning has yielded many fundamentally different approaches to the solution of this problem that can be classified as roadmap methods (visibility graph method, Voronoi diagram) and methods based on cell decomposition. Assuming movements only in a restricted number of directions (eightdirectional or horizontal/vertical) the task, with respect to its combinatorial nature, can be solved by decomposition methods using heuristic techniques. We present drawbacks of these methods. Then, using the Voronoi diagrams, we need only polynomial time for finding a solution and, choosing a Euclidean or rectilinear metric, it can be adapted to tasks with general or directional-constrained movements.

Czech name

Plánování pohybu robotu v rovině s mnohoúhelníkovými překážkami

Czech description

Úloha plánování trajektorie hraje významnou roli v dopravě, robotice apod. V úloze plánování pohybu robotu má robot projít z počáteční do koncové pozice ve scéně s překážkami tak, aby nedošlo ke kolizi s některou z překážek. Výzkum problematiky plánovánícesty přinesl řadu odlišných přístupů k jeho řešení, které lze klasifikovat jako metody silniční mapy (graf viditelnosti, Voroného diagram) a metody založené na dekompozici na buňky. Předpokládáme-li pohyb pouze v omezeném počtu směrů (8-směrový nebo horizontálně/vertikální) pak lze úlohu vzhledem k její povaze řešit dekompozičními metodami s využitím heuristických technik. V článku prezentujeme nevýhody těchto přístupů. Použijeme-li Voronoiovy diagramy, budeme potřebovat pouze polynomiální čas pro nalezení řešení a volbou euklidovské nebo rektilineární metriky lze tento přístup přizpůsobit úlohám s obecným, resp. směrově omezeným pohybem.

Type

D - Article in proceedings

CEP classification

BB - Applied statistics, operational research

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2008

Confidentiality

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

Article name in the collection

Proceedings of the 3rd International Conference Optimization of the Robots and Manipulators OPTIROB 2008

ISBN

978-973-648-784-2

ISSN

—

e-ISSN

—

Number of pages

6

Pages from-to

—

Publisher name

Bren Publishing House

Place of publication

Predeal (Romania)

Event location

Predeal (Romania)

Event date

May 30, 2008

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—