Dynamic Path Planning with Regular Triangulations

Article Sidebar


PDF

Published:
Dec 14, 2014
Issue
Vol. 23 No. 3/4 (2014)
Section
Original research papers
CitedBy/Share
Crossref
Scopus
Google Scholar
Europe PMC

Main Article Content

Petr Brož
Faculty of Applied Sciences, University of West Bohemia, Pilsen, Czech Republic
Ivana Kolingerová
Faculty of Applied Sciences, University of West Bohemia, Pilsen, Czech Republic
Jakub Szkandera
Faculty of Applied Sciences, University of West Bohemia, Pilsen, Czech Republic
https://orcid.org/0000-0001-9953-4712
Michal Zemek
Faculty of Applied Sciences, University of West Bohemia, Pilsen, Czech Republic

DOI: https://doi.org/10.22630/MGV.2014.23.3.6
Keywords : path planning, path finding, motion planning, virtual reality, robotics, proteins, suboptimality, gaps filling
Abstract
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.

Article Details

How to Cite
Brož, P., Kolingerová, I., Szkandera, J., & Zemek, M. (2014). Dynamic Path Planning with Regular Triangulations. Machine Graphics and Vision, 23(3/4), 119–142. https://doi.org/10.22630/MGV.2014.23.3.6
References

Watson D. F.: Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes, The Computer Journal, 2:167-172, 1981. (Crossref)

Fortune S.: A sweepline algorithm for Voronoi diagrams, SCG’86: Proceedings of the second annual symposium on Computational geometry, p. 313-322, 1986. (Crossref)

Aurenhammer F.: Power Diagrams: Properties, Algorithms and Applications, SIAM Journal on Computing, 16:78-96, 1986. (Crossref)

Edelsbrunner H., Shah N. R.: Incremental Topological Flipping Works for Regular Triangulations, ACM Annual Symposium on Computational Geometry, 8:43-52, 1992. (Crossref)

Eppstein D.: Finding the k-Shortest Paths, 35th Annual Symposium on Foundations of Computer Science, p. 154-165, 1994.

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.

Barber C. B., Dobkin D. P., Huhdanpaa H.: The quickhull algorithm for convex hulls, ACM Trans. Math. Softw., 22:469-483, 1996. (Crossref)

Goodman J. E., O’Rourke J.: Handbook of Discrete and Computational Geometry, CRC Press LLC, 1997.

Skiena S. S.: The Algorithm Design Manual, Springer-Verlag, New York, 1997.

Cignoni P., Montani C., Scopigno R. : DeWall: A fast divide and conquer Delaunay triangulation algorithm in Ed, Computer-Aided Design, 30:333-341, 1997. (Crossref)

Bandi S., Thalmann D.: Space Discretization for Efficient Human Navigation, Computer Graphics Forum, 17(3):195-206, 1998. (Crossref)

Dor D., Halperin S., Zwick U.: All-Pairs Almost Shortest Paths, SIAM Journal on Computing, 29(5):1740-1759, 2000. (Crossref)

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. (Crossref)

Arikan O., Chenney S., Forsyth D. A.: Efficient Multi-Agent Path Planning, Computer Animation and Simulation, p. 151-162, 2001. (Crossref)

Champandard A. J.: Path-Planning from Start to Finish (Internet source: http://www.ai-depot.com/BotNavigation), 2001

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. (Crossref)

Vigo M., Pla N., Cotrina J.: Regular Triangulations of Dynamics Sets of Points. Computer Aided Geometric Design 19:127-149, 2002. (Crossref)

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.

Shewchuk J.R.: Stabbing Delaunay tetrahedralizations, Discrete Comput. Geom., 32:343, 2004. (Crossref)

Wallgrün J. O.: Autonomous Construction of Hierarchical Voronoi-Based Route Graph Representations, Spatial Cognition IV. Reasoning, Action, and Interaction, 3343:413-433, 2005. (Crossref)

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. (Crossref)

Ledoux H., Gold C.M., Baciu G.: Flipping to Robustly Delete a Vertex in a Delaunay Tetrahedralization. ICCSA (1):737-747, 2005. (Crossref)

Brož P., Kolingerová 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 (Crossref)

Brož P.: Exact and heuristic path planning methods for a virtual environment, Proceedings of the CESCG, 2007

Medek P., Beneš P., Sochor J.: Computation of tunnels in protein molecules using Delaunay triangulation. Proceedings of the WSCG, 2007.

Zemek M., Kolingerová I.: Hybrid algorithm for deletion of a point in regular and Delaunay triangulation. Spring Conference on Computer Graphics, Budmerice, Slovakia, p. 149-2156, 2009. (Crossref)

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, (Internet source: https://www.kiv.zcu.cz/site/documents/verejne/vyzkum/publikace/technicke-zpravy/2009/tr-2009-03.pdf), 2009.

Statistics

Downloads

Download data is not yet available.
Recommend Articles