×

Multiple UAVs path planning algorithms: a comparative study. (English) Zbl 1165.90358

Summary: Unmanned aerial vehicles (UAVs) are used in team for detecting targets and keeping them in its sensor range. There are various algorithms available for searching and monitoring targets. The complexity of the search algorithm increases if the number of nodes is increased. This paper focuses on multi UAVs path planning and Path Finding algorithms. Number of Path Finding and Search algorithms was applied to various environments, and their performance compared. The number of searches and also the computation time increases as the number of nodes increases. The various algorithms studied are Dijkstra’s algorithm, Bellman Ford’s algorithm, Floyd-Warshall’s algorithm and the AStar algorithm. These search algorithms were compared. The results show that the AStar algorithm performed better than the other search algorithms. These path finding algorithms were compared so that a path for communication can be established and monitored.

MSC:

90B10 Deterministic network models in operations research
05C85 Graph algorithms (graph-theoretic aspects)
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cavendish, D., & Gerla, M. (1998). Internet QoS routing using the Bellman-Ford algorithm. In International Conference on High Performance Networking (HPN’98).
[2] Chabini, I., & Ganupati, S. (2001). Design and implementation of parallel dynamic shortest path algorithms for intelligent transportation systems applications, Transportation Research Record No. 1771. Washington, DC: National Academy Press.
[3] Cherkassky B.V., Goldberg A.V., Radzik T. (1996) Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming 73(2): 129–174 · Zbl 0853.90111
[4] Cvetanovic Z., Nofsinger C. (1990) Parallel Astar search on message-passing architectures. IEEE Computer Society 1: 82–90
[5] Finn, A., Kabacinski, K., & Drake, S. P. (2007). Design challenges for an autonomous cooperative of UAV’s. Defence Science & Technology Organisation, Department of Defence, Australia, IDC 2007.
[6] Fu, L. (1996). Real-time vehicle routing and scheduling in dynamic and stochastic traffic networks. Unpublished Ph.D. Dissertation, University of Alberta, Edmonton, Alberta.
[7] Gallo G., Pallottino S. (1984). Shortest path methods. In: Florian M. (eds). Transportation planning models. Amsterdam, Elsevier Science Publishers, pp. 227–256 · Zbl 0592.90087
[8] Gayraud, T., & Authie, G. (1992). A parallel algorithm for the all pairs shortest path problem. In Proceedings of the International Conference on Parallel Computing. · Zbl 0798.68129
[9] Hart E.P., Nilsson N.J., Raphael B. (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Transaction, System Science and Cybernetics, SSC- 4(2): 100–107
[10] Hung S.M., Divoky J.J. (1988) A computational study of efficient shortest path algorithms. Computers and Operations Research 15(6): 567–576 · Zbl 0659.90087
[11] Jacob R., Marathe M., Nagel K. (1999) A computational study of routing algorithms for realistic transportation networks. Journal of Experimental Algorithmics 4: 1–19 · Zbl 1073.68887
[12] Li W.-W. (2005) New trends in route guidance algorithm research of intelligent transportation system. Journal of Zhejiang University 39: 819–824
[13] Murray J.J., Cox C.J., Lendaris G.G., Saeks R. (2002) Adaptive dynamic programming. IEEE Transactions on Systems, Man and Cybernetics 32: 140–153
[14] Newell, A., & Simon, H. A. (1972). Human problem solving. Englewood Cliffs, NJ: Prentice-Hall.
[15] Nilsson J.N. (1971) Problem-solving methods in artificial intelligence. McGraw-Hill, NewYork
[16] Pearl, J. (1984). Heuristics: Intelligent search strategies for computer problem solving. Addison-Wesley Publishing Company.
[17] Royer, E. M., & Toh, C.-K. (1999). A review of current routing protocols for ad-hoc mobile wireless networks. IEEE Personal Communications Magazine, April 1999, 46–55.
[18] Sathyaraj, B., Chellappa Doss, R. (2005). Route maintenance using mobility prediction for mobile ad hoc networks. IEEE international conference: Mobile adhoc and sensor systems conference, MASS 2005.
[19] Tan G.-Z., He H., Sloman A. (2006) Global optimal path planning for mobile robot based on improved Dijkstra algorithm and ant system algorithm. Journal of Central South University of Technology 13: 80–86
[20] Vuren V.T., Jansen G.R.M. (1988) Recent developments in path finding algorithms: A review. Transportation Planning and Technology 12: 57–71
[21] Zhan F.B., Noon C.E. (1998) Shortest path algorithms: An evaluation using real road networks. Transportation Science, 32(1): 65–73 · Zbl 0987.90514
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.