Military route planning in battlefield simulation: effectiveness problems and potential solutions

• Autorzy: Tarapata Z.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

battlefield simulation; route planning; shortest paths; effectiveness problems; computational complexity

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2003
• Tom: nr 4
• Strony: 47--56
• Opis fizyczny: Bibliogr. 32 poz., tab., rys.

Twórcy

autor

Tarapata Z.

• Institute of Mathematics and Operations Research, Faculty of Cybernetics, Military University of Technology, Warsaw

Bibliografia

• [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.
• [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/).
• [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.
• [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.
• [5] C. Cooper, A. Frieze, K. Melhorn, and V. Priebe, “Averagecase complexity of shortest-paths problems in the vertex-potential model”, Rand. Struct. Algor., vol. 16, pp. 33–46, 2000.
• [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.
• [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.
• [8] J. James, B. Sayrs, J. Benton, and V. S. Subrahmanian, “Uncertainty management: keeping battlespace visualization honest”, http://citeseer.nj.nec.com/ 386770.html
• [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.
• [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.
• [11] T. Kreitzberg, T. Barragy, and B. Nevin, “Tactical movement analyzer: a battlefield mobility tool”, in Proc. 4th Join Tactic. Fus. Symp., Laurel, 1990.
• [12] B. Logan, “Route planning with ordered constraints”, in Proc. 16th Works. UK Plann. Schedul. Spec. Int. Group, Durham, UK, 1997.
• [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.
• [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.
• [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.
• [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.
• [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.
• [18] S. Rajput and C. Karr, “Unit route planning”, Tech. Rep. IST-TR- 94-42, Institute for Simulation and Training, Orlando, USA, 1994.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [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.
• [27] Z. Tarapata, “Computer simulation of individual and grouped military objects redeployment”, Bull. Milit. Univ. Technol., no. 1, pp. 147–162, 2000.
• [28] Z. Tarapata, “Computer tool for supporting and evaluating convoys redeployment planning”, Oper. Res. Decis., no. 1, pp. 91–107, 2000.
• [29] Z. Tarapata, “Some aspects of multi-convoy redeployment modelling and simulation”, in Proc. 21st AFCEA Eur. Symp. & Exposit., Prague, 2000 (compact disk publication).
• [30] Z. Tarapata, “Modelling, optimisation and simulation of groups movement according to group pattern in multiresolution terrain-based grid network”, in Proc. Reg. Conf. Milit. Commun. Inform. Syst., Zegrze, Poland, 2001, vol. I, pp. 241–251.
• [31] Z. Tarapata, “Fast method for redeploying multi-convoy in multiresolution grid network”, Bull. Milit. Univ. Technol., 2003 (in press).
• [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).