Detail publikace
Srovnání metod silniční mapy a metod dekompozice v plánování pohybu robota
ŠEDA, M.
Český název
Srovnání metod silniční mapy a metod dekompozice v plánování pohybu robota
Anglický název
A Comparison of Roadmap and Cell Decomposition Methods in Robot Motion Planning
Typ
článek v časopise - ostatní, Jost
Jazyk
en
Originální abstrakt
The task of planning trajectories plays an important role in transportation, robotics, information systems, etc. In robot motion planning, the robot should pass around obstacles from a given starting position to a given target position, touching none of them, i.e. the goal is to 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 (eight directional or horizontal/vertical) the task, with respect to its combinatorial nature, can be solved by decomposition methods using heuristic techniques. The cell decomposition methods may include a case-based reasoning procedure. Robot motion planning algorithms can be modified by considering a robot as a point and enlarging the obstacles in the workspace accordingly. In order to avoid the explicit construction of the obstacle region, sampling-based motion planning algorithms have been proposed such as probabilistic roadmap methods or rapidly exploring random trees. We present drawbacks of these approaches 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
Český abstrakt
Úloha plánování trajektorie hraje významnou roli v dopravě, robotice, informačních systémech 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, Voronoiův diagram) a metody založené na dekompozici na buňky. Dekompoziční metody mohou zahrnovat proceduru případového usuzování. Algoritmy plánování dráhy robota mohou být modifikovány, uvážíme-li robota jako bod a příslušným způsobem zvětšíme velikost překážek. Abychom zamezili explicitní konstrukci oblasti překážek, mohou být použity algoritmy založené na vzorkování plánu pohybu jako jsou pravděpodobnostní metody silniční mapy nebo rychle rostoucí náhodné stromy. 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
Anglický abstrakt
The task of planning trajectories plays an important role in transportation, robotics, information systems, etc. In robot motion planning, the robot should pass around obstacles from a given starting position to a given target position, touching none of them, i.e. the goal is to 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 (eight directional or horizontal/vertical) the task, with respect to its combinatorial nature, can be solved by decomposition methods using heuristic techniques. The cell decomposition methods may include a case-based reasoning procedure. Robot motion planning algorithms can be modified by considering a robot as a point and enlarging the obstacles in the workspace accordingly. In order to avoid the explicit construction of the obstacle region, sampling-based motion planning algorithms have been proposed such as probabilistic roadmap methods or rapidly exploring random trees. We present drawbacks of these approaches 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
Klíčová slova anglicky
motion planning, cell decomposition, sampling methods, roadmap method, Voronoi diagram
Rok RIV
2007
Vydáno
15.02.2007
ISSN
1991-8763
Časopis
WSEAS TRANSACTIONS on SYSTEMS and CONTROL
Ročník
2
Číslo
2
Strany od–do
101–108
Počet stran
8
BIBTEX
@article{BUT45263,
author="Miloš {Šeda},
title="A Comparison of Roadmap and Cell Decomposition Methods in Robot Motion Planning",
journal="WSEAS TRANSACTIONS on SYSTEMS and CONTROL",
year="2007",
volume="2",
number="2",
month="February",
pages="101--108",
issn="1991-8763"
}