Rectilinear Voronoi diagram-based motion planning in the piane with obstacles

• Autorzy: Šeda, M.

Warianty tytułu

PL

Planowanie ruchu na płaszczyźnie z przeszkodami bazowane na prostoliniowym diagramie Woronoja

• Konferencja: International Conference Mechatronics 2004 (5 ; 23-25.09.2004 ; Warsaw, Poland)
• Języki publikacji: EN

Abstrakty

EN

A Voronoi diagram of a set of sites in the Euclidean plane is a collection of regions that divide up the plane. Each region corresponds to one of the sites and all the points in one region are closer to the sile representing the region than to the other site. Voronoi diagrams have a surprising variety of uses, e.g. nearest neighbour search, facility location, path planning, etc. In this paper, we investigate the problem of 8-directional robot motion planning where the goal is to find a collision-free path from the starting to the target position in the 2D space containing point and rectangular obstacles. In contrast to the traditional approaches frequently based on genetic algorithms, we propose a method for solving this problem using rectilinear Voronoi diagrams.

PL

Diagram Woronoja złożony z zestawu miejsc na płaszczyźnie euklidesowej jest zbiorem obszarów, które rozdzielają tę płaszczyznę. Każdy obszar odpowiada jednemu z miejsc. a wszystkie punkty w jednym obszarze są bliższe miejscu reprezentującemu ten obszar niż innym miejscom. Diagramy Woronoja mają zaskakująco wiele zastosowań, np. poszukiwanie najbliższego sąsiada, lokalizacja obiektu, planowanie trajektorii, itd. W artykule badamy problem związany z planowaniem 8-kierunkowego ruchu robota, gdzie celem jest odnalezienie bezkolizyjnej trajektorii z pozycji startowej do docelowej w przestrzeni dwuwymiarowej zawierającej punktowe oraz prostokątne przeszkody. W przeciwieństwie do tradycyjnych podejść, które bazują często na algorytmach genetycznych, proponujemy rozwiązanie tego problemu metodą wykorzystującą prostoliniowe diagramy Woronoja.

Słowa kluczowe

PL

planowanie ruchu; diagram Woronoja; metryka prostoliniowa

EN

motion planning; Voronoi diagram; rectilinear metric

• Czasopismo: Elektronika : konstrukcje, technologie, zastosowania
• Rocznik: 2004
• Tom: Vol. 45, nr 8-9
• Strony: 24-26
• Opis fizyczny: Bibliogr. 8 poz., rys.

Twórcy

autor

Šeda, M.

• Brno University of Technology, Faculty of Mechanical Engineering, Institute of Automation and Computer Science

Bibliografia

• 1. Aurenhammer, F.: Voronoi Diagrams - A Survey of a Fundamental Geometrie Data Structure. ACM Computing Surveys, 1991, No. 3, v. 23, p. 345-405
• 2. de Berg, M., van Kreveld, M., Overmars M. and Schwarzkopf O.: Computational Geometry: Algorithms and Applications. Springer-Verlag Berlin 2000
• 3. Fortune S.: Voronoi Diagrams and Delaunay Triangulations. In Du D. A., Hwang F. K. (eds.): Euclidean Geometry and Computers. World Scientific Publishing Singapore 1992, p. 193-233
• 4. Guha S. and Suzuki I.: Proximity Problems for Points on a Rectilinear Piane with Rectangular Obstacles. Algorithmica, 1997, Vol. 17, p. 281-307
• 5. Seda M. and Dvorak J.: Robot Navigation Using Genetic Algorithm and Case-Based Reasoning. In Book of Extended Abstracts of the National Conference with International Participation Engineering Mechanics 2003. Svratka Czech Republic 2003, p. 328-329 + 8 p. on CD-ROM
• 6. Shamos M. I. and Hoey O.: C/osest Point Prob/ems. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science FOCS'75. Berkeley California, 1975, p. 151-162
• 7. Sugihara K. and Smith J.: Genetic Algorithms for Adaptive Planning of Path and Trajectory of a Mobile Robot in 20 Terrains. IEICE Transactions on lnformation and Systems. 1999, No 1, v. E82-D, p. 309-317
• 8. Zilouchian A. and Jamshidi M.: /ntelligent Control Systems Using Soft Computing Methodologies. CRC Press Boca Raton Florida 2001