In the contemporary military environment, making decisions on how to best utilize resources to accomplish a mission with a set of specified constraints is difficult. A Cordon and Search of a village (a.k.a. village search) is an example of such a mission. Leaders must plan the mission, assigning assets (e.g. soldiers, robots, unmanned aerial vehicles, military working dogs) to accomplish the given task in accordance with orders from higher headquarters. Computer tools can assist these leaders in making decisions, and do so in a manner that will ensure the chosen solution is within mission constraints and is robust against uncertainty in environmental parameters. Currently, no such tools exist at the tactical or operational level to assist decision makers in their planning process and, as a result, individual experience and simplistic data tables are the only tools available. Using robustness concepts, this paper proposes a methodology, a mathematical model, and resource allocation heuristics for static planning of village searches that result in a decision-making tool for military leaders.
MaxwellPSiegelHJPotterJMaciejewskiAA. The ISTeC People-Animals-Robots laboratory: robust resource allocation. In: Proceedings in the 2009 IEEE International Workshop on Safety, Security, and Rescue Robotics, November2009.
2.
FM 3-31.1 Army and Marine Corps Integration in Joint Operations. US Army Training and Doctrine Command, Ft. Monroe, VA, November2001.
3.
FM 34-8-2 Intelligence Officer’s Handbook. US Army Training and Doctrine Command, Ft. Monroe, VA, May1998.
4.
AliSMaciejewskiAASiegelHJKimJ.Measuring the robustness of a resource allocation. IEEE Trans Parallel Distrib Syst2004; 15: 630–641.
5.
SalehHChelouahR.The design of the global navigation satellite system surveying networks using genetic algorithms. Eng Appl Artif Intell2004; 17: 111–122.
6.
AydinM.An exploratory analysis of village search operations. Master’s thesis, Naval Postgraduate School, June2004.
7.
BabilotM.Comparison of a distributed operations force to a traditional force in urban combat. Master’s thesis, Naval Postgraduate School, September2005.
FultonLVLasdonLSMcDanielRRJrCoppolaMN.Two-stage stochastic optimization for the allocation of medical assets in steady-state combat operations. J Defense Model Simulat2010; 7: 89–102.
10.
LucasT.The stochastic versus deterministic argument for combat simulations: Tales of when the average won’t do. Mil Oper Res2000; 5: 9–28.
11.
PopkenDCoxL.A simulation-optimization approach to air warfare planning. J Defense Model Simulat2004; 1: 127–140.
12.
DesrochersMDesrosiersJSolomonM.A new optimization algorithm for the vehicle routing problem with time windows. Oper Res1992; 40: 342–354.
13.
LaporteaGGendreauMPotvinJSemetF.Classical and modern heuristics for the vehicle routing problem. Int Trans Oper Res2000; 7: 285–300.
14.
PotvinJ.Genetic algorithms for the traveling salesman problem. Ann Oper Res1996; 63: 339–370.
15.
LarranagaPKuijpersCMHMurgaRHInzaIDizdarevicS.Genetic algorithms for the travelling salesman problem: a review of representations and operators. Artif Intell Rev1999; 13: 129–170.
16.
BektasT.The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega2006; 34: 209–219.
17.
TangLLiuJRongAYangZ.A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. Eur J Oper Res2000; 124: 267–282.
YuZJinhaiLGouchangGRuboZHaiyanY. An implementation of evolutionary computation for path planning of cooperative mobile robots. In: Proceedings of the 4th World Congress on Intelligent Control and Automation, June2002, pp.1798–1802.
20.
AliSMaciejewskiAASiegelHJ.Perspectives on robust resource allocation for heterogeneous parallel systems. In: RajasekaranSReifJ (eds) Handbook of parallel computing: models, algorithms, and applications. Boca Raton, FL: Chapman & Hall/CRC Press, 2008, pp.41-1–41-30.
21.
SmithJSiegelHJMaciejewskiAA. Robust resource allocation in heterogeneous parallel and distributed computing systems. In: WahB (ed.) Wiley encyclopedia of computing. Vol. 4. New York: John Wiley & Sons, 2008, pp.2461–2470.
22.
BilbaoJMiguelAHKambezidisHD.Air temperature model evaluation in the north Mediterranean belt area. J Appl Meteorol2002; 41: 872–884.
23.
BruhnJEFryWEFickGW.Simulation of daily weather data using theoretical probability distributions. J Appl Meteorol1980; 19: 1029–1036.
24.
HillRDMoateCPBlacknellD.Estimating building dimensions from synthetic aperture radar image sequences. IET Radar Sonar Navig2008; 2: 189–199.
25.
WangLMaciejewskiAASiegelHJRoychowdhuryVPEldrigeBD.Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach. J Parallel Distrib Comput1997; 47: 8–22.
26.
PrinsC.A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res2004; 31: 1985–2002.
27.
ShestakVSmithJMaciejewskiAASiegelHJ.Stochastic robustness metric and its use for static resource allocations. J Parallel Distrib Comput2008; 68: 1157–1173.
28.
IbarraOHKimCE.Heuristic algorithms for scheduling independent tasks on non-identical processors. J ACM1977; 24: 280–289.
29.
BlickleTThieleL. A comparison of selection schemes used in genetic algorithms. Technical Report TIK-Report No. 11, Ver. 2, CEN Lab, Swiss Federal Institute of Technology, December1995.
30.
NairSKThakurLSWenK.Near optimal solutions for product line design and selection: beam search heuristics. Manag Sci1995; 41: 767–785.
31.
QuinnM.Parallel programming in C with MPI and OpenMP. New York: McGraw-Hill, 2004.
32.
ValenteaJAlvesbR.Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups. Comput Oper Res2008; 35: 2388–2405.
33.
MaxwellPFrieseRMaciejewskiAASiegelHJPotterJSmithJ. A demonstration of a simulation tool for planning robust military village searches. In: Proceedings of the Huntsville Simulation Conference (HSC’10), October 2010.
