Detail publikace

Roadmap Methods vs. Cell Decomposition in Robot Motion Planning

ŠEDA, M.

Originální název

Roadmap Methods vs. Cell Decomposition in Robot Motion Planning

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

angličtina

Originální abstrakt

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

Klíčová slova

motion planning, cell decomposition, roadmap methods, visibility graph, Voronoi diagram

Autoři

ŠEDA, M.

Rok RIV

2007

Vydáno

15. 2. 2007

Nakladatel

WSEAS Press

Místo

Corfu Island (Greece)

ISBN

978-960-8457-59-1

Kniha

Proceedings of the 6th WSEAS International Conference on Signal Processing, Robotics and Automation ISPRA '07

Strany od

127

Strany do

132

Strany počet

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",
  pages="127--132",
  publisher="WSEAS Press",
  address="Corfu Island (Greece)",
  isbn="978-960-8457-59-1"
}