×

hCHAC: a family of MOACO algorithms for the resolution of the bi-criteria military unit pathfinding problem. (English) Zbl 1348.90641

Summary: This paper presents a family of Multi-Objective Ant Colony Optimization (MOACO) algorithms, globally identified as hCHAC, which have been designed to solve a pathfinding problem in a military context considering two objectives: maximization of speed and safety. Each one of these objectives include different factors (such as stealth or avoidance of resource-consuming zones), that is why in this paper we generate different members of the hCHAC family by aggregating the initial cost functions into a different amount of objectives (from one to four) and considering a different parametrization set in each case. The hCHAC algorithms have been tested in several different (and increasingly realistic) scenarios, modelled in a simulator and compared with some other well-known MOACOs. These latter algorithms have been adapted for the purpose of this work to deal with this problem, along with a new multi-objective greedy approach that has been included as baseline for comparisons. The experiments show that most of the hCHAC algorithms outperform the other approaches, yielding at the same time very good military behaviour in the tactical sense. Within the hCHAC family, hCHAC-2, an approach considering two objectives, yields the best results overall.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90C90 Applications of mathematical programming
90C29 Multi-objective and goal programming

Software:

MACS-VRPTW; CHAC; TSPLIB
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Leenen, L.; Vorster, J.; le Roux, H., A constraint-based solver for the military unit path finding problem, (Proceedings of the 2010 spring simulation multiconference, (2010), ACM), 25
[2] Stentz A. Optimal and efficient path planning for unknown and dynamic environments. Technical report. CMU-RI-TR-93-20. Pittsburgh, PA: Robotics Institute, Carnegie Mellon University; August 1993.
[3] Dorigo, M.; Stützle, T., The ant colony optimization metaheuristic: algorithms, applications, and advances, (Glover, G. K.F., Handbook of metaheuristics, (2002), Kluwer), 251-285 · Zbl 1102.90378
[4] Reinelt, G., The traveling salesman: computational solutions for TSP applications, (Lecture notes in computer science, vol. 840, (1994), Springer Verlag)
[5] García-Martínez, C.; Cordón, O.; Herrera, F., A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP, European Journal of Operational Research, 180, 1, 116-148, (2007) · Zbl 1114.90103
[6] Deb, K., An efficient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering, 186, 2-4, 311-338, (2000) · Zbl 1028.90533
[7] Zitzler E, Laumanns M, Thiele L. SPEA 2: improving the strength pareto evolutionary algorithm for multiobjective optimization. In: Giannakoglou K, et al., editors. Evolutionary methods for design, optimisation and control with application to industrial problems (EUROGEN 2001). International Center for Numerical Methods in Engineering (CIMNE); 2002. p. 95-100.
[8] Dorigo, M.; Gambardella, L. M., Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1, 1, 53-66, (1997)
[9] Spanish Army—Ground Army (Ejército de Tierra Español) en. \(\langle\)http://en.wikipedia.org/wiki/Spanish_Army\(\rangle\).
[10] Mora, A. M.; Merelo, J. J.; Millán, C.; Torrecillas, J.; Laredo, J. L.J., CHAC. A MOACO algorithm for computation of bi-criteria military unit path in the battlefield, (Pelta, D.; Krasnogor, N., Proceedings of the workshop on nature inspired cooperative strategies for optimization, NICSO’2006, (2006)), 85-98 · Zbl 1176.90305
[11] Deneubourg, J. L.; Pasteels, J. M.; Verhaeghe, J. C., Probabilistic behaviour in ants: a strategy of errors?, Journal of Theoretical Biology, 105, 259-271, (1983)
[12] Grassé, P.-P., La reconstruction du nid et LES coordinations inter-individuelles chez bellicositermes natalensis et cubitermes sp. la theorie de la stigmerie, Insectes Sociaux, 6, 41-80, (1959)
[13] Dorigo, M.; Maniezzo, V.; Colorni, A., The ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics Part B: Cybernetics, 26, 1, 29-41, (1996)
[14] (Lawler, E. L.; Lenstra, J. K.; Kan, A. H.G. R.; Shmoys, D. B., The traveling salesman problem, (1985), John Wiley & Sons Ltd.) · Zbl 0563.90075
[15] Osyczka A. Multicriteria optimization for engineering design. In: Gero JS, editor. Design optimization. Academic Press, pp. 193-227.
[16] Pareto V. Cours d’economie politique, vols. I and II. Lausanne: F. Rouge.
[17] Coello, C. A.C.; Veldhuizen, D. A.V.; Lamont, G. B., Evolutionary algorithms for solving multi-objective problems, (2002), Kluwer Academic Publishers · Zbl 1130.90002
[18] Bellman, R., On a routing problem, Quarterly of Applied Mathematics, 1, 16, 87-90, (1958) · Zbl 0081.14403
[19] Dijkstra, E. W., A note on two problems in connexion with graphs, Numerische Mathematik, 1, 269-271, (1959) · Zbl 0092.16002
[20] Manley K. Pathfinding: from \(\operatorname{A}^\ast\) to LPA. \(\langle\)http://csci.morris.umn.edu/UMMCSciWiki/pub/CSci3903s03/KellysPaper/seminar.pdf\(\rangle\); 2003.
[21] Cherkassky, B. V.; Goldberg, A. V.; Radzik, T., Shortest paths algorithms: theory and experimental evaluation, Mathematical Programming, 73, 129-174, (1996) · Zbl 0853.90111
[22] Stewart, B. S.; White, C. C., Multiobjective A^{⁎}, Journal of the ACM, 38, 4, 775-814, (1991) · Zbl 0799.68173
[23] Loui, R. P., Optimal paths in graphs with stochastic or multidimensional weights, Communications of the ACM, 26, 9, 670-676, (1983) · Zbl 0526.90085
[24] Gambardella, L.; Taillard, E.; Agazzi, G., MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows, (Corne, F. G.D.; Dorigo, M., New ideas in optimization, (1999), McGraw-Hill), 73-76
[25] Barán B, Schaerer M. A multiobjective ant colony system for vehicle routing problem with time windows. In: IASTED international multi-conference on applied informatics, no. 21 in IASTED IMCAI; 2003. p. 97-102.
[26] Iredi, S.; Merkle, D.; Middendorf, M., Bi-criterion optimization with multi colony ant algorithms, (Zitzler, E.; Deb, K.; Thiele, L.; Coello, C. A.C.; Corne, D., Proceedings of the first international conference on evolutionary multi-criterion optimization (EMO 2001). Lecture notes in computer science, vol. 1993, (2001), Springer Berlin), 359-372
[27] Alaya, I.; Solnon, C.; Ghedira, K., Ant colony optimization for multi-objective optimization problems, (19th IEEE international conference on tools with artificial intelligence, ICTAI 2007, vol. 1, (2007)), 450-457
[28] Thyagarajan, M. K.K.; Batta, R.; Szczerba, R., Planning dissimilar paths for military units, Military Operations Research Journal, 10, 1, 25-42, (2005)
[29] Carlyle, W. M.; Royset, J. O.; Wood, R. K., (Routing military aircraft with a constrained shortest-path algorithm, (2007))
[30] Akgün, I.; Tansel, B., Optimization of transportation requirements in the deployment of military units, Computers & Operations Research, 34, 4, 1158-1176, (2005) · Zbl 1102.90300
[31] Mora, A. M.; Merelo, J. J.; Laredo, J. L.J.; Millán, C.; Torrecillas, J., CHAC, a MOACO algorithm for computation of bi-criteria military unit path in the battlefield: presentation and first results, International Journal of Intelligent Systems, 24, 7, 818-843, (2009) · Zbl 1176.90305
[32] Mora, A.; Merelo, J.; Castillo, P.; Laredo, J.; Cotta, C., Influence of parameters on the performance of a moaco algorithm for solving the bi-criteria military path-finding problem, (WCCI 2008 proceedings, (2008), IEEE Press), 3506-3512
[33] Bull, S., World war II infantry tactics, (2005), Company and Battalion, Osprey Publishing
[34] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach, IEEE Transactions on Evolutionary Computation, 3, 4, 257-271, (1999)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.