Application of the A* algorithm to problems of the Euclidean shortest paths in the plane with polygonal obstacles

Anna Wojak

Published: 2008-09-30

Vol. 22 (2008)

Application of the A* algorithm to problems of the Euclidean shortest paths in the plane with polygonal obstacles

Anna Wojak

Abstract

The Euclidean shortest path between two points s and t in the plane with the cellular decomposition in the presence of obstacles is considered. The A* algorithm for a visibility graph (VG) is used to avoid widened obstacles. Computational experiments show that the proposed algorithm is often faster and it analyzes fewer nodes than the classical Dijkstra algorithm.

Keywords:

shortest path , obstacles , visibility graph

Download files

PDF

Citation rules

Wojak, A. (2008). Application of the A* algorithm to problems of the Euclidean shortest paths in the plane with polygonal obstacles. Annales Mathematicae Silesianae, 22, 69–82. Retrieved from https://journals.us.edu.pl/index.php/AMSIL/article/view/14053

Similar Articles

R. C. Brewster, C. M. Mynhardt, L. E. Teshima, The realizability of theta graphs as reconfiguration graphs of minimum independent dominating sets , Annales Mathematicae Silesianae: 2024: Online First
Peter Imkeller, Nicolas Perkowski, A Fourier analysis based new look at integration , Annales Mathematicae Silesianae: Vol. 37 No. 2 (2023)
Zbigniew Gajda, A characterization of functions with dense graph in the plane or half-plane , Annales Mathematicae Silesianae: Vol. 2 (1986)
Anna Bień, Gamma graphs of some special classes of trees , Annales Mathematicae Silesianae: Vol. 29 (2015)
Ron Brown, Jonathan L. Merzel, The space of real places on ℝ(x, y) , Annales Mathematicae Silesianae: Vol. 32 (2018)
Bruce Ebanks, The cosine-sine functional equation on semigroups , Annales Mathematicae Silesianae: Vol. 36 No. 1 (2022)
Maciej Ślęczka, Exponential convergence for Markov systems , Annales Mathematicae Silesianae: Vol. 29 (2015)
Binayak S. Choudhury, Nikhilesh Metiya, Sunirmal Kundu, Debashis Khatua, Existence, data dependence and stability of fixed points of multivalued maps in incomplete metric spaces , Annales Mathematicae Silesianae: Vol. 37 No. 1 (2023)
Dorota Bród, On a new one parameter generalization of Pell numbers , Annales Mathematicae Silesianae: Vol. 33 (2019)
Nur Şeyma Yilmaz, Andrzej Włoch, Engin Özkan, Dominik Strzałka, On doubled and quadrupled Fibonacci type sequences , Annales Mathematicae Silesianae: Vol. 38 No. 2 (2024)

You may also start an advanced similarity search for this article.

References

1. Ahuja R.K., Magnanti T.M., Orlin J.B., Network Flows – Theory, Algorithms and Applications, Prentice-Hall, Englewood Cliffs, NJ, 1993.
2. Chabini I., Lan S., Adaptation of the A* algorithm for computation of faster paths in deterministic discrete-time dynamic networks, IEEE. Trans. on Intel. Trans. Syst. 3 (2002), 60–74.
3. Cormen T.H., Leiserson C.E., Rivest R.L., Introduction of Algorithms, Second Edition, The MIT Press, 2001.
4. Hart E.P., Nilson N.J., Raphael B., A formal basis for the heuristic determination of minimum cost path, IEEE Trans. Syst. Sci. Cybern. 4 (1968), 100–107.
5. Hersberger J., Suri S., On computing Euclidean shortest paths in the plane, Proc. 34 Annu. IEEE. Sympos. Found, Comput. Sci. (1993), 508–517.
6. Ghosh S.K., Mount D.M., An output-sensitive algorithm for computing visibility graphs, SIAM J. Computing 20 (1991), 888–910.
7. Kapoor S., Maheshwari S.N., Mitchell J.S.B., An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane, Discrete Comput. Geom. 18 (1997), 377–383.
8. Mitchell J.S.B., Geometric Shortest Paths and Network Optimization, In: Handbook of Computational Geometry, Elsevier Science (J.-R. Sack and J. Urrutia, eds.), 2000, pp. 633–701.
9. O’Rourke J., Computational Geometry in C, Cambridge University Press, New York, 1995.
10. Pallottino S., Shortest paths Method – Complexity Interrelations and New Propositions, Consiglio Nazionale delle Ricerche, Istituto per le Aplicazioni del Calcolo “Mauro Picone”, Roma, 14 (1984), 257–267.
11. Pohl I., Heuristic search viewed as path finding in a graph, Artif. Intell. 1 (1970), 193–204. Google Scholar

Vol. 22 (2008)
Published: 2008-09-30

ISSN: 0860-2107

eISSN: 2391-4238

10.1515/amsil

Publisher

University of Silesia Press

Submit