Dynamic Path Planning with Regular Triangulations

• Autorzy: Brož P. , Zemek M. , Kolingerová I. , Szkandera J.

Identyfikatory

DOI

10.22630/MGV.2014.23.3.6

• Języki publikacji: EN

Abstrakty

EN

Path planning is a well known problem that has been extensively studied in many scientific disciplines. In general, it defines a task of finding a path between two given spots in an abstract environment so that the path satisfies certain criterion of optimality. Although there are many methods solving this objective, they usually assume the examined space does not change in runtime. Modern applications, however, do not have to meet these requirements, especially in case of virtual reality or computer games. Therefore, we propose a general model for real-time path planning in dynamic environment where the obstacles can nondeterministically appear, disappear, change the position, orientation or even shape. The model uses a triangulation for dynamic space subdivision among bounding spheres of the obstacles and a heuristic algorithm to repair an already found path after any change of the scene. The presented solution is the first one using regular triangulation. At the price of the suboptimal result, it provides an efficient and fast way to plan a path with the maximal clearance among the moving and changing obstacles. In comparison to raster based techniques and methods using the Delaunay triangulation (Voronoi diagram), it requires less time to preprocess and generates paths with a larger clearance.

Słowa kluczowe

EN

path planning; path finding; motion planning; virtual reality; robotics; proteins; suboptimality; gap-filling

• Wydawca: Institute of Information Technology of the Warsaw University of Life Sciences – SGGW
• Czasopismo: Machine Graphics and Vision
• Rocznik: 2014
• Tom: Vol. 23, No. 3/4
• Strony: 119--142
• Opis fizyczny: Bibliogr. 27 poz., il., wykr.

Twórcy

autor

Brož P.

• Faculty of Applied Sciences, University of West Bohemia, Pilsen, Czech Republic

autor

Zemek M.

• Faculty of Applied Sciences, University of West Bohemia, Pilsen, Czech Republic

autor

Kolingerová I.

• Faculty of Applied Sciences, University of West Bohemia, Pilsen, Czech Republic

autor

Szkandera J.

• Faculty of Applied Sciences, University of West Bohemia, Pilsen, Czech Republic

• https://orcid.org/0000-0001-9953-4712

Bibliografia

• [1] Watson D. F. : Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes, The Computer Journal, 2:167-172, 1981.
• [2] Fortune S. : A sweepline algorithm for Voronoi diagrams, SCG’86: Proceedings of the second annual symposium on Computational geometry, p. 313-322, 1986.
• [3] Aurenhammer F. : Power Diagrams: Properties, Algorithms and Applications, SIAM Journal on Computing, 16:78-96, 1986.
• [4] Edelsbrunner H., Shah N.R. : Incremental Topological Flipping Works for Regular Triangulations, ACM Annual Symposium on Computational Geometry, 8:43-52, 1992.
• [5] Eppstein D. : Finding the k-Shortest Paths, 35th Annual Symposium on Foundations of Computer Science, p. 154-165, 1994.
• [6] Stentz A. : Optimal and Efficient Path Planning for Partially-Known Environments, Proceedings IEEE International Conference on Robotics and Automation, San Diego, California, USA, p. 3310-3317, 1994.
• [7] Barber C. B., Dobkin D. P., Huhdanpaa H. : The quickhull algorithm for convex hulls, ACM Trans. Math. Softw., 22:469-483, 1996.
• [8] Goodman J. E., O’Rourke J. : Handbook of Discrete and Computational Geometry, CRC Press LLC, 1997.
• [9] Skiena S. S. : The Algorithm Design Manual, Springer-Verlag, New York, 1997.
• [10] Cignoni P., Montani C., Scopigno R. : DeWall: A fast divide and conquer Delaunay triangulation algorithm in Ed, Computer-Aided Design, 30:333-341, 1997.
• [11] Bandi S., Thalmann D. : Space Discretization for Efficient Human Navigation, Computer Graphics Forum, 17(3):195-206, 1998.
• [12] Dor D., Halperin S., Zwick U. : All-Pairs Almost Shortest Paths, SIAM Journal on Computing, 29(5):1740-1759, 2000.
• [13] Shewchuk J. R. : Sweep algorithms for constructing higher-dimensional constrained Delaunay triangulations, SCG ’00: Proceedings of the sixteenth annual symposium on Computational geometry, p. 350-359, 2000.
• [14] Arikan O., Chenney S., Forsyth D. A. : Efficient Multi-Agent Path Planning, Computer Animation and Simulation, p. 151-162, 2001.
• [15] Champandard A. J. : Path-Planning from Start to Finish (Internet source: www.ai-depot.com/BotNavigation), 2001.
• [16] Geraerts R., Overmars M. H. : A Comparative Study of Probabilistic Roadmap Planners, Proc. Workshop on the Algorithmic Foundations of Robotics (WAFR’02), p. 43-57, 2002.
• [17] Vigo M., Pla N., Cotrina J. : Regular Triangulations of Dynamics Sets of Points. Computer Aided Geometric Design 19:127-149, 2002.
• [18] Devillers O., Teillaud M. : Perturbations and Vertex Removal in a 3D Delaunay Triangulation. Proceedings 14th ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, p. 313-319, 2003.
• [19] Shewchuk J.R. : Stabbing Delaunay tetrahedralizations, Discrete Comput. Geom., 32:343, 2004.
• [20] Wallgrn J. O. : Autonomous Construction of Hierarchical Voronoi-Based Route Graph Representations, Spatial Cognition IV. Reasoning, Action, and Interaction, 3343:413-433, 2005.
• [21] Beyer T., Schaller G., Deutsch A., Meyer-Hermann M. : Parallel dynamic and kinetic regular triangulation in three dimensions, Computer Physics Communications, 172:86-108., 2005
• [22] Ledoux H., Gold C.M., Baciu G. : Flipping to Robustly Delete a Vertex in a Delaunay Tetrahedralization. ICCSA (1):737-747, 2005.
• [23] Broz P., Kolingerova I., Zitka P., Apu R.A., Gavrilova M. : Path planning in dynamic environment using an adaptive mesh, Proceedings of the SCCG, p. 172-178, 2007.
• [24] Broz P. : Exact and heuristic path planning methods for a virtual environment, Proceedings of the CESCG, 2007.
• [25] Medek P., Benes P., Sochor J. : Computation of tunnels in protein molecules using Delaunay triangulation. Proceedings of the WSCG, 2007.
• [26] Zemek M., Kolingerova I. : Hybrid algorithm for deletion of a point in regular and Delaunay triangulation. Spring Conference on Computer Graphics, Budmerice, Slovakia, p. 149-2156, 2009.
• [27] Zemek M. : Regular triangulation in 3D and its applications. Technical report, University of West Bohemia, Faculty of Applied Sciences, Department of Computer Science and Engineering, 2009, (Internet source: www.kiv.zcu.cz/site/documents/verejne/vyzkum/publikace/technicke-zpravy/2009/tr-2009-03.pdf).