On the modern battlefield cordon and search missions (also known as village searches) are conducted daily. Creating resource allocations that link search teams (e.g. soldiers, robots, unmanned aerial vehicles, military working dogs) to target buildings is difficult and time consuming in the static planning environment and is even more challenging in a time-constrained dynamic environment. Conducting dynamic resource allocation during the execution of a military village search mission is beneficial especially when the time to develop a static plan is limited and hence the quality of the plan is relatively poor. Dynamic heuristics can help improve the static plan because they are able to incorporate current state information that is unavailable prior to mission execution and thus produce more accurate results than static heuristics alone can achieve. There are currently no automated means to create these dynamic resource allocations for military use. Using robustness concepts, this paper proposes and compares dynamic resource allocation heuristics that create mission plans that are resilient against uncertainty in the environment and that save valuable time for military planning staff.
MaxwellPMaciejewskiAASiegelHJPfisterGSmithJFrieseR. Robust static planning tool for military village search missions: model and heuristics. J Defense Model Sim2013; 10(1): 31–47.
2.
CoffmanEG (ed.). Computer and Job-Shop Scheduling Theory. New York, NY: John Wiley & Sons, 1976.
3.
IbarraOHKimCE. Heuristic algorithms for scheduling independent tasks on non-identical processors. J ACM1977; 24(2): 280–289.
4.
AliSMaciejewskiAASiegelHJKimJ. Measuring the robustness of a resource allocation. IEEE Trans Parallel Distrib Sys2004; 15(7): 630–641.
5.
ShestakVSmithJMaciejewskiAASiegelHJ. Stochastic robustness metric and its use for static resource allocations. J Parallel Distrib Comput2008; 68(8): 1157–1173.
6.
ChekuriCKhannaS. A polynomial time approximation scheme for the multiple knapsack problem. SIAM J Comput2006; 35(3): 713–728.
7.
AhnerDBussARuckJ. Using a low-resolution entity model for shaping initial conditions for high resolution combat models. In 2007 Winter Simulation Conference, 2007, pp. 1344–1352.
8.
AydinM. An Exploratory Analysis of Village Search Operations. Master’s Thesis, Naval Postgraduate School, June2004.
9.
BabilotM. Comparison of a Distributed Operations Force to a Traditional Force in Urban Combat. Master’s Thesis, Naval Postgraduate School, September2005.
10.
FultonLVLasdonLSMcDanielRRJr. Two-stage stochastic optimization for the allocation of medical assets in steady-state combat operations. J Defense Model Sim2010; 7(2): 89–102.
11.
PopkenDCoxL. A simulation-optimization approach to air warfare planning. J Defense Model Sim2004; 1(3): 127–140.
12.
DesrochersMDesrosiersJSolomonM. A new optimization algorithm for the vehicle routing problem with time windows. Operat Res1992; 40(2): 342–354.
13.
PotvinJ. Genetic algorithms for the traveling salesman problem. Ann Operat Res1996; 63: 339–370.
14.
PapadimitriouG. The Euclidean travelling salesman problem is NP-complete. Theor Comput Sci1977; 4(3): 237–244.
15.
TangLLiuJRongA. A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron & Steel Complex. Eur J Operat Res2000; 124: 267–282.
YuZJinhaiLGouchangG. An implementation of evolutionary computation for path planning of cooperative mobile robots. In 4th World Congress on Intelligent Control and Automation, June 2002, pp. 1798–1802.
18.
MavrovouniotisMYangS. Ant colony optimization with immigrants schemes in dynamic environments. In Parallel Problem Solving from Nature (PPSN XI) (Lecture Notes in Computer Science, Vol. 6239). Berlin: Springer, 2011, pp. 371–380.
19.
YangS. Genetic algorithms with memory- and elitism-based immigrants in dynamic environments. Evol Computat2008; 16(3): 385–416.
20.
PowellWBouzaiene-AyariBBergerJ. The effect of robust decisions on the cost of uncertainty in military airlift operations. ACM Trans Model Comput Sim2011; 9(4): 39.
21.
ChungTKressMRoysetJ. Probabilistic search optimization and mission assignment for heterogeneous autonomous agent. In 2009 IEEE International Conference on Robotics and Automation, May 2009, pp. 939–945.
22.
KanohHHaraK. Hybrid genetic algorithm for dynamic multi-objective route planning with predicted traffic in a real-world road network. In 10th Annual Conference on Genetic and Evolutionary Computation, July 2008, pp. 657–664.
23.
BanksJ (ed.). Handbook of Simulation: Principles, Methodology, Advances, Applications, and Practice. New York, NY: John Wiley & Sons, 1998.
24.
BraunTSiegelHJBeckN. A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems. J Parallel Distrib Comput2001; 61(6): 810–837.
25.
AlcarazJMarotoC. A robust genetic algorithm for resource allocation in project scheduling. Ann Operat Res2001; 102: 83–109.
26.
WangLMaciejewskiAASiegelHJRoychowdjuryVPEldrigeBD. Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach. J Parallel Distrib Comput1997; 47(1): 8–22.
27.
BlickleTThieleL. A Comparison of Selection Schemes Used in Genetic Algorithms. Technical Report TIK-Report Number 11, Version 2, CEN Lab, Swiss Federal Institute of Technology, December1995.
28.
ZilbersteinS. Using anytime algorithms in intelligent systems. AI Mag1996; 17(3): pp. 73–83.
29.
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.
30.
BilbaoJMiguelAHKambezidisHD. Air temperature model evaluation in the north Mediterranean belt area. J Appl Meteorol2002; 41: 872–884.
31.
BruhnJEFryWEFickGW. Simulation of daily weather data using theoretical probability distributions. J Appl Meteorol1980; 19: 1029–1036.
32.
HillRDMoateCPBlacknellD. Estimating building dimensions from synthetic aperture radar image sequences. IET Radar Sonar Nav20082(3): 189–199.
33.
PrinsC. A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Operat Res2004; 31(12): 1985–2002.
