Military route planning in battlefield simulation: effectiveness problems and potential solutions
DOI:
https://doi.org/10.26636/jtit.2003.4.201Keywords:
battlefield simulation, route planning, shortest paths, effectiveness problems, computational complexityAbstract
Path searching is challenging problem in many domains such as simulation war games, robotics, military mission planning, computer generated forces (CGF), etc. Effectiveness problems in military route planning are related both with terrain modelling and path planning algorithms. These problems may be considered from the point of view of many criterions. It seems that two criterions are the most important: quality of terrain reflection in the terrain model and computational complexity of the on(off)-line path planning algorithm. The paper deals with two above indicated problems of route planning effectiveness. Comparison of approaches used in route planning is presented. The hybrid, terrain merging-based and partial path planning, approach for route planning in dynamically changed environment during simulation is described. It significantly increase effectiveness of route planning process. The computational complexity of the method is given and some discussion for using the method in the battlefield simulation is conducted. In order to estimate how many times faster we can compute problem for finding shortest path in network with n big squares (b-nodes) with relation to problem for finding shortest path in the network with V small squares (s-nodes) acceleration function is defined and optimized.
Downloads
References
[1] J. R. Benton, S. S Iyengar, W. Deng, N. Brener, and V. S. Subrahmanian, "Tactical route planning: new algorithms for decomposing the map", in Proc. IEEE Int. Conf. Tools for AI, Herndon, 1995, pp. 268-277.
View in Google Scholar
[2] A. Bley, "On the complexity of vertex-disjoint length-restricted path problems", Konrad-Zuse-Zentrum fur Informationstechnik, Berlin, 1998 (see also: http://www.zib.de/PaperWeb/abstracts/SC-98-20/).
View in Google Scholar
[3] C. Campbell, R. Hull, E. Root, and L. Jackson, "Route planning in CCTT", in Proc. 5th Conf. Comput. Gener. Forc. Behav. Repres., Tech. Rep., Institute for Simulation and Training, 1995, pp. 233-244.
View in Google Scholar
[4] C. G. Cassandras, C. G. Panayiotou, G. Diehl, W.-B. Gong, Z. Liu, and C. Zou, "Clustering methods for multi-resolution simulation modeling", in Proc. Conf. Enabl. Technol. Simul. Sci., Int. Soc. Opt. Eng., Orlando, USA, 2000, pp. 37-48.
View in Google Scholar
[5] C. Cooper, A. Frieze, K. Melhorn, and V. Priebe, "Average case complexity of shortest-paths problems in the vertex-potential model", Rand. Struct. Algor., vol. 16, pp. 33-46, 2000.
View in Google Scholar
[6] P. K. Davis, J. H. Bigelow, and J. McEver, "Informing and calibrating a multiresolution exploratory analysis model with high resolution simulation: the interdiction problem as a case history", in Proc. 2000 Winter Simul. Conf., 2000, pp. 316-325.
View in Google Scholar
[7] P. E. Hart, N. J. Nilsson, and B. Raphael, "A formal basis for the heuristic determination of minimum cost paths", IEEE Trans. Syst. Sci. Cybern., vol. SSC-4, no. 2, pp. 100-107, 1968.
View in Google Scholar
[8] J. James, B. Sayrs, J. Benton, and V. S. Subrahmanian, "Uncertainty management: keeping battlespace visualization honest", http://citeseer.nj.nec.com/ 386770.html
View in Google Scholar
[9] L. Joe and P. M. Feldman, "Fundamental research policy for the digital battlefield", Res. Rep. DB-245-A, RAND Co., Santa Monica, USA, 1998.
View in Google Scholar
[10] C. R. Karr, M. A. Craft, and J. E. Cisneros, "Dynamic obstacle avoidance", in Proc. Conf. Distrib. Interact. Simul. Syst. Simul. Train. Aerosp. Envir., Int. Soc. Opt. Eng., Orlando, USA, 1995, pp. 195-219.
View in Google Scholar
[11] T. Kreitzberg, T. Barragy, and B. Nevin, "Tactical movement analyzer: a battlefield mobility tool", in Proc. 4th Join Tactic. Fus. Symp., Laurel, 1990.
View in Google Scholar
[12] B. Logan, "Route planning with ordered constraints", in Proc. 16th Works. UK Plann. Schedul. Spec. Int. Group, Durham, UK, 1997.
View in Google Scholar
[13] B. Logan and A. Sloman, "Agent route planning in complex terrains", Tech. Rep. CSRP-97-30, University of Birmingham, School of Computer Science, Birmingham, 1997.
View in Google Scholar
[14] M. Longtin and D. Megherbi, "Concealed routes in ModSAF", in Proc. 5th Conf. Comput. Gener. Forc. Behav. Repres., Tech. Rep., Institute for Simulation and Training, 1995, pp. 305-314.
View in Google Scholar
[15] J. S. B. Mitchell, "Geometric shortest paths and network optimization", in Handbook of Computational Geometry, J. R. Sack and J. Urrutia. Elsevier Science Publ., B.V. North-Holland, Amsterdam, 1999.
View in Google Scholar
[16] D. K. Pai and L. M. Reissell, "Multiresolution rough terrain motion planning", Department of Computer Sciences, University of British Columbia, Tech. Rep. TR 94-33, Vancouver, 1994.
View in Google Scholar
[17] M. D. Petty, "Computer generated forces in distributed interactive simulation", in Proc. Conf. Distrib. Interact. Simul. Syst. Simul. Train. Aerosp. Envir., Int. Soc. Opt. Eng., Orlando, USA, 1995, pp. 251-280.
View in Google Scholar
[18] S. Rajput and C. Karr, "Unit route planning", Tech. Rep. IST-TR94-42, Institute for Simulation and Training, Orlando, USA, 1994.
View in Google Scholar
[19] G. A. Schiavone, R. S. Nelson, and K. C. Hardis, "Interoperability issues for terrain databases in distributed interactive simulation", in Proc. Conf. Distrib. Interact. Simul. Syst. Simul. Train. Aerosp. Envir., Int. Soc. Opt. Eng., Orlando, USA, 1995, pp. 89-120.
View in Google Scholar
[20] G. A. Schiavone, R. S. Nelson, and K. C. Hardis, "Two surface simplification algorithms for polygonal terrain with integrated road features", in Proc. Conf. Enabl. Technol. Simul. Sci., Int. Soc. Opt. Eng., Orlando, USA, 2000, pp. 221-229.
View in Google Scholar
[21] A. Schrijver and P. Seymour, "Disjoint paths in a planar graph - a general theorem", SIAM J. Discr. Math., no. 5, pp. 112-116, 1992.
View in Google Scholar
[22] H. Sherali, K. Ozbay, and S. Subrahmanian, "The time-dependent shortest pair of disjoint paths problem: complexity, models and algorithms", Networks, no. 31, pp. 259-272, 1998.
View in Google Scholar
[23] A. Stentz, "Optimal and efficient path planning for partially-known environments", in Proc. IEEE Int. Conf. Robot. Automat., ICRA’94, vol. 4, pp. 3310-3317.
View in Google Scholar
[24] P. D. Stroud and R. C. Gordon, "Automated military unit identification in battlefield simulation", LAUR-97-849, SPIE Proc., vol. 3069, Los Alamos National Laboratory, Los Alamos, 1997.
View in Google Scholar
[25] Z. Tarapata, "Algorithm for simultaneous finding a few independent shortest paths", in Proc. 9th Eur. Simul. Symp., ESS’97, Soc. Comput. Simul., Passau, Germany, 1997, pp. 89-93.
View in Google Scholar
[26] Z. Tarapata, "Simulation method of aiding and estimation of transportation columns movement planning in stochastic environment", in Proc. 13th Eur. Simul. Multiconf., Soc. Comput. Simul. Int., Warsaw, Poland, 1999, pp. 613-619.
View in Google Scholar
[27] Z. Tarapata, "Computer simulation of individual and grouped military objects redeployment", Bull. Milit. Univ. Technol., no. 1, pp. 147-162, 2000.
View in Google Scholar
[28] Z. Tarapata, "Computer tool for supporting and evaluating convoys redeployment planning", Oper. Res. Decis., no. 1, pp. 91-107, 2000.
View in Google Scholar
[29] Z. Tarapata, "Some aspects of multi-convoy redeployment modelling and simulation", in Proc. 21st AFCEA Eur. Symp. & Exposit., Prague, 2000 (compact disk publication).
View in Google Scholar
[30] Z. Tarapata, "Modelling, optimisation and simulation of groups movement according to group pattern in multiresolution terrainbased grid network", in Proc. Reg. Conf. Milit. Commun. Inform. Syst., Zegrze, Poland, 2001, vol. I, pp. 241-251.
View in Google Scholar
[31] Z. Tarapata, "Fast method for redeploying multi-convoy in multiresolution grid network", Bull. Milit. Univ. Technol., 2003 (in press).
View in Google Scholar
[32] C. Undeger, F. Polat, and Z. Ipekkan, "Real-time edge follow: a new paradigm to real-time path search", SCS Publications, 2001 (see also: http://citeseer.nj.nec.com/489498.html).
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2003 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
