Literature by the same author
plus at Google Scholar

Bibliografische Daten exportieren
 

Parallel near-optimal pathfinding based on landmarks

Title data

Reischl, Maximilian ; Knauer, Christian ; Guthe, Michael:
Parallel near-optimal pathfinding based on landmarks.
In: Computers & Graphics. Vol. 102 (2022) . - pp. 1-8.
ISSN 0097-8493
DOI: https://doi.org/10.1016/j.cag.2021.11.007

Official URL: Volltext

Abstract in another language

We present a new approach for path finding in weighted graphs using pre-computed minimal distance fields. By selecting the most promising minimal distance field at any given node and switching between them, our algorithm aims to find the shortest path possible. As we show, this approach scales excellently for various topologies, graph sizes and hardware specifications while maintaining a mean length error below 1 and reasonable memory consumption. By utilizing a simplified structure and keeping backtracking to a minimum, we are able to leverage the same approach on the massively parallel GPUs or any other shared memory parallel architecture, reducing the run time even further.

Further data

Item Type: Article in a journal
Refereed: Yes
Keywords: Computer science; Computing methodologies and applications; Computer graphics; Computational geometry
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science > Professor Applied Computer Science V > Professor Applied Computer Science V - Univ.-Prof. Dr. Michael Guthe
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Computer Science > Professor Applied Computer Science VI > Professor Applied Computer Science VI - Univ.-Prof. Dr. Christian Knauer
Result of work at the UBT: Yes
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
Date Deposited: 07 May 2024 08:11
Last Modified: 07 May 2024 08:57
URI: https://eref.uni-bayreuth.de/id/eprint/89498