Publication detail
Roadmap Methods vs. Cell Decomposition in Robot Motion Planning
ŠEDA, M.
Czech title
Metody silniční mapy vs. dekompozice v plánování pohybu robota
English title
Roadmap Methods vs. Cell Decomposition in Robot Motion Planning
Type
conference paper
Language
en
Original abstract
The task of planning trajectories plays an important role in transportation, robotics, information systems (sending messages), 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. We present drawbacks of this approach (combinatorial explosion, limited granularity and generating infeasible solutions). 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 abstract
Úloha plánování trajektorie hraje významnou roli v dopravě, robotice, informačních systémech (rozesílání zpráv) 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. Předpokládáme-li pohyb pouze v omezeném počtu směrů (8-směrový, horizontálně/vertikální), pak úlohu vzhledem k její kombinatorické povaze lze řešit dekompozičními metodami s využitím heuristických technik. V článku prezentujeme nevýhody těchto přístupů (kombinatorická exploze, omezená jemnost dekompozice, generování nepřípustných řešení). 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
English abstract
The task of planning trajectories plays an important role in transportation, robotics, information systems (sending messages), 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. We present drawbacks of this approach (combinatorial explosion, limited granularity and generating infeasible solutions). 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
Keywords in English
motion planning, cell decomposition, roadmap methods, visibility graph, Voronoi diagram
RIV year
2007
Released
15.02.2007
Publisher
WSEAS Press
Location
Corfu Island (Greece)
ISBN
978-960-8457-59-1
Book
Proceedings of the 6th WSEAS International Conference on Signal Processing, Robotics and Automation ISPRA '07
Pages from–to
127–132
Pages count
6
BIBTEX
@inproceedings{BUT22394,
author="Miloš {Šeda},
title="Roadmap Methods vs. Cell Decomposition in Robot Motion Planning",
booktitle="Proceedings of the 6th WSEAS International Conference on Signal Processing, Robotics and Automation ISPRA '07",
year="2007",
month="February",
pages="127--132",
publisher="WSEAS Press",
address="Corfu Island (Greece)",
isbn="978-960-8457-59-1"
}