Přejít k obsahu


Dynamic Path Planning with Regular Triangulations

Citace:
BROŽ, P., ZEMEK, M., KOLINGEROVÁ, I., SZKANDERA, J. Dynamic Path Planning with Regular Triangulations. Machine Graphics & Vision, 2014, roč. 24, č. 3/4, s. 119-142. ISSN: 1230-0535
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Dynamic Path Planning with Regular Triangulations
Rok vydání: 2014
Autoři: Ing. Petr Brož , Ing. Michal Zemek , Prof. Dr. Ing. Ivana Kolingerová , Ing. Jakub Szkandera
Abstrakt CZ: V článku je navržen obecný model pro plánování cest v dynamickém prostředí v reálném čase, kde se překážky mohou nedetrministicky objevovat, mizet, měnit svoji pozici, orientaci nebo dokonce tvar. Model využívá triangulaci pro dynamické dělení prostoru mezi obalové koule překážek a heuristický algoritmus pro opravu už nalezené cesty po změně scény. Prezentované řešení je první využívající regulární triangulaci. Za cenu suboptimálního výsledku poskytuje účinný a rychlý způsob plánování cesty s maximálním volným prostorem mezi pohybujícími se a měnícími se překážkami. Ve srovnání s ratsrově založenými technikami a metodami užívajícími Delanayovu triangulaci (Voronoi diagram) vyžaduje méně času na předzpracování a generuje cesty s větším volným prostorem.
Abstrakt EN: 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.
Klíčová slova

Zpět

Patička