Publication detail
Computing Paths Using Computational Geometry Data Structures
ŠEDA, M.
Czech title
Výpočet cest s využitím datových struktur počítačové geometrie
English title
Computing Paths Using Computational Geometry Data Structures
Type
conference paper
Language
en
Original abstract
Finding the shortest path from a specified starting position to a target position is a fundamental problem in transportation, routing, and communications applications. In robot motion planning, the robot should pass around the obstacles touching none of them, i.e. the goal is to find a collision-free path from the starting to the target position. This task has many specific formulations depending on the shape of obstacles, allowable directions of movements, knowledge of the scene, etc. Research on of path planning has yielded many fundamentally different approaches to its solution, mainly based on various decomposition and roadmap methods. In this paper, we investigate a possible use of visibility graphs and Voronoi diagrams in point-to-point motion planning and propose a method for solving this problem on in the Euclidean plane.
Czech abstract
Hledání nejkratších cest z určené počáteční do koncové pozice je základní úlohou v dopravě, okružních problémech i komunikačních aplikacích. 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. ve scéně s překážkami tak, aby nedošlo ke kolizi s některou z překážek. Tato úloha má řadu specifických formulací, které závisí na tvaru překážek, povolenému způsobu pohybu, znalosti scény atd. Výzkum této problematiky přinesl několik odlišných přístupů řešení většinou založených na různých dekompozicích scény a metodách silniční mapy. V příspěvku zkoumáme možné využití grafů viditelnosti a Voronoiových diagramů) v plánování trasy robotu mezi dvěma pozicemi v euklidovské rovině.
English abstract
Finding the shortest path from a specified starting position to a target position is a fundamental problem in transportation, routing, and communications applications. In robot motion planning, the robot should pass around the obstacles touching none of them, i.e. the goal is to find a collision-free path from the starting to the target position. This task has many specific formulations depending on the shape of obstacles, allowable directions of movements, knowledge of the scene, etc. Research on of path planning has yielded many fundamentally different approaches to its solution, mainly based on various decomposition and roadmap methods. In this paper, we investigate a possible use of visibility graphs and Voronoi diagrams in point-to-point motion planning and propose a method for solving this problem on in the Euclidean plane.
Keywords in English
planning, computational geometry, visibility graph, Voronoi diagram
RIV year
2005
Released
26.09.2005
Publisher
Bachcesehir University Istanbul
Location
Antalya (Turkey)
ISBN
9958-617-28-5
Book
Proceedings of the 9th International Research/Expert Conference Trends in the Development of Machinery and Associated Technology TMT 2005
Pages count
4
BIBTEX
@inproceedings{BUT15917,
author="Miloš {Šeda},
title="Computing Paths Using Computational Geometry Data Structures",
booktitle="Proceedings of the 9th International Research/Expert Conference Trends in the Development of Machinery and Associated Technology TMT 2005",
year="2005",
month="September",
publisher="Bachcesehir University Istanbul",
address="Antalya (Turkey)",
isbn="9958-617-28-5"
}