A fast and simple algorithm for computing m-shortest paths in stage graph

• Autorzy: Sherwood M. , Gewali L. , Selvaraj H. , Muthukumar V.
• Języki publikacji: EN

Abstrakty

EN

We consider the problem of computing m shortest paths between a source node s and a target node t in a stage graph. Polynomial time algorithms known to solve this problem use complicated data structures. This paper proposes a very simple algorithm for computing all m shortest paths in a stage graph efficiently. The proposed algorithm does not use any complicated data structure and can be implemented in a straightforward way by using only array data structure. This problem appears as a sub-problem for planning risk reduced multiple k-legged trajectories for aerial vehicles.

Słowa kluczowe

EN

graph theory; computational complexity; mobile robots; legged trajectories; aerial vehicles; polynomial time algorithm

PL

teoria grafów; złożoność obliczeniowa

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Systems Science
• Rocznik: 2004
• Tom: Vol. 30, no 1
• Strony: 91--97
• Opis fizyczny: Bibliogr. 7 poz., rys.

Twórcy

autor

Sherwood M.

• HRH College of Engineering, University of Nevada Las Vegas, Las Vegas, NV, U.S.A.

autor

Gewali L.

• HRH College of Engineering, University of Nevada Las Vegas, Las Vegas, NV, U.S.A.

autor

Selvaraj H.

• HRH College of Engineering, University of Nevada Las Vegas, Las Vegas, NV, U.S.A.

autor

Muthukumar V.

• HRH College of Engineering, University of Nevada Las Vegas, Las Vegas, NV, U.S.A.

Bibliografia

• [1] Canny J., Reif J., New Lower Bound Techniques for Robot Motion Planning Problems, Proceedings of the 28th IEEE Symposium on Foundations of Computer Science, 1987, 49-60.
• [2] Chen D. Z., Klenk K. S., Tu H. T., Shortest Path Queries Among Weighted Obstacles in the Recti-linear Plane, SIAM Journal on Computing, Vol. 29, No. 4, 2000, 1223-1246.
• [3] Eppstein D., Finding the k Shortest Paths, SIAM Journal on Computing, Vol. 28, No. 2, 1998, 652-673
• [4] Gewali L. P., Meng A. C., Mitchell J. S. B., Path Planning in 0/1/∞ Weighted Regions with Applications, ORSA Journal on Computing, 2, 1990, 253-272.
• [5] Gewali L. P., Gewali L., Sherwood M., Algorithms for Generating Multiple Risk Reduced Paths, Proceedings of 16th International Conference on Systems Engineering, 2003.
• [5] Mata C., Mitchell J. S. B., A New Algorithm for Computing Shortest Paths in Weighted Planar Subdivisions, Proceedings of the 13th Annual ACM Symposium on Computational Geometry, 1997, 264-273.
• [6] Lanthier M., Maheswari A., Sack J. R., Approximating Shortest Paths on Weighted Polyhedral Surfaces, Algorithmica, 30, 2001, 527-562.
• [7] O'Rourke J., Computational Geometry in C, Cambridge University Press, 1998

Uwagi

Bibliografia: poz 5 powtórzona