Application of the A* algorithm to problems of the Euclidean shortest paths in the plane with polygonal obstacles
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
References
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.
Instytut Matematyki, Uniwersytet Śląski w Katowicach & Instytut Fizyki, Uniwersytet Śląski w Katowicach Poland
The Copyright Holders of the submitted text are the Author and the Journal. The Reader is granted the right to use the pdf documents under the provisions of the Creative Commons 4.0 International License: Attribution (CC BY). The user can copy and redistribute the material in any medium or format and remix, transform, and build upon the material for any purpose.
- License
This journal provides immediate open access to its content under the Creative Commons BY 4.0 license (http://creativecommons.org/licenses/by/4.0/). Authors who publish with this journal retain all copyrights and agree to the terms of the above-mentioned CC BY 4.0 license. - Author’s Warranties
The author warrants that the article is original, written by stated author/s, has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author/s. - User Rights
Under the Creative Commons Attribution license, the users are free to share (copy, distribute and transmit the contribution) and adapt (remix, transform, and build upon the material) the article for any purpose, provided they attribute the contribution in the manner specified by the author or licensor. - Co-Authorship
If the article was prepared jointly with other authors, the signatory of this form warrants that he/she has been authorized by all co-authors to sign this agreement on their behalf, and agrees to inform his/her co-authors of the terms of this agreement.
