×

CHAC, A MOACO algorithm for computation of bi-criteria military unit path in the battlefield: Presentation and first results. (English) Zbl 1176.90305

Summary: We present a MultiObjective Ant Colony Optimization (MOACO) algorithm, called CHAC, designed to solve the problem of finding the path for a military unit that minimizes the cost in resources while maximizing safety. Unlike previous MOACO algorithms, CHAC uses a single colony and two different state transition rules: One that combines the heuristic and pheromone information of both objectives and another based on the dominance concept of multiobjective optimization problems. These rules have been evaluated in different scenarios (maps with different degrees of difficulty), outperforming a greedy algorithm (taken as baseline), and yielding a good military behavior in the tactical sense. In comparison, the combined rule is slightly better than the rule based on dominance.

MSC:

90B50 Management decision making, including multiple objectives

Software:

CHAC
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Stenz, Tech. Rep. CMU-RI-TR-93-20 (1993)
[2] Stenz A. Optimal and efficient path planning for partially-known environments. In: Proc ICRA, San Diego, CA: 1994; pp 3310-3317.
[3] Dorigo, New ideas in optimization pp 11– (1999)
[4] Dorigo, Handbook of metaheuristics pp 251– (2002)
[5] Coello Coello (2002)
[6] Barán B, Schaerer M. A multiobjective ant colony system for vehicle routing problem with time windows. In: IASTED Int Multi-Conference on Applied Informatics, number 21 in IASTED IMCAI; 2003. pp 97-102. Also available at http://www.scopus.com/scopus/inward/record.url?eid=2-s2.0-1442302509&partner=40&rel=R4.5.0.
[7] Iredi, Proc the First Int Conf on Evolutionary Multi-Criterion Optimization (EMO 2001), Lecture Notes in Computer Science 1993 pp 359– (2001)
[8] Mariano CE, Morales E. MOAQ: An ant-Q algorithm for multiple objective optimization problems. In: Genetic and Evolutionary Computation Conference (GECCO-99); 1999. 894-901.
[9] Mariano CE, Morales E. A multiple objective Ant-Q algorithm for the design of water distribution irrigation networks. Technical Report HC-9904, Instituto Mexicano de Tecnología del Agua, Mexico; 1999. Available at http://www.lania.mx/ccoello/mariano99a.ps.gz
[10] López-Ibáñez, Proc Fourth Int Workshop on Ant Colony Optimization (ANTS 2004); Lecture Notes in Computer Science 3172 pp 214– (2004)
[11] García-Martínez, A taxonomy and an empirical analysis of multiple objective ant colony optimization algorithms for the bi-criteria TSP, Eur J Oper Res 180 (1) pp 116– (2007) · Zbl 1114.90103
[12] Manley K. Pathfinding: from A* to LPA. Available at http://khorshid.ece.ut.ac.ir/acm/ejournal/public/pdf/from-a-star-to-lpa.pdf
[13] Yap P, Schaeffer J. Path-finding on a grid. In: Caulfield JH., Chen SH, Cheng HD, Duro R, Caufield JH, Chen SH, Cheng HD, Duro R, Honavar V. editors, In: Proc of the 6th Joint Conf on Information Sciences, JCIS 2002: 2002.
[14] Lee, An immunity-based ant colony optimization algorithm for solving weapon-target assignment problem, Appl Soft Comput 2 (1) pp 39– (2002)
[15] Montana, 1999 Cong on Evolutionary Computation, Washington, DC pp 1118– (1999)
[16] Maloney PS. An application of neural net technology to surveillance information correlation and battle outcome prediction. In: Proc IEEE 1989; 2:948-955. National Aerospace and Electronics Conference, NAECON, 1989.
[17] Thyagarajan, Planning dissimilar paths for military units, Military Oper Res J 10 (1) pp 25– (2005)
[18] Saab, Shortest path planning on topographical maps, IEEE Trans. Systems, Man, Cybern A 29 (1) pp 139– (1999)
[19] Akgün, Optimization of transportation requirements in the deployment of military units, Comput Oper Res 34 (4) pp 1158– (2005) · Zbl 1102.90300
[20] Bull, Company and battalion (2005)
[21] Zitzler, Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach, IEEE Trans Evol Comput 3 (4) pp 257– (1999)
[22] Mora, EvoWorkshops 2007. Applications of Evolutionary Computing. Lecture Notes in Computer Sciences 4448 pp 712– (2007)
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.