Wielorozdzielcze modele i algorytmy planowania przemieszczania oraz ich zastosowanie w wielorozdzielczej symulacji pola walki

• Autorzy: Tarapata Z. , Godlewski P.

Warianty tytułu

EN

Multiresolution models and algorithms of movement planning and their application for multiresolution battlefield simulation

• Języki publikacji: PL

Abstrakty

PL

W pracy zaprezentowano przegląd modeli i metod poszukiwania dróg w wielorozdzielczych sieciach oraz ich analizę pod kątem efektywnościowym (dokładności i czasu obliczeń). Jedna z opisywanych metod opiera się na "agregowaniu" geograficznym sąsiednich wierzchołków (kwadratów terenu) w grafie, który reprezentuje teren w postaci tzw. kraty i planowaniu tras w "zagregowanej" sieci z wykorzystaniem specyficznej transformacji. Druga z metod wykorzystywana jest do planowania wielorozdzielczych tras w sieci drogowej. Opisano zastosowanie prezentowanych metod w wielorozdzielczej symulacji pola walki.

EN

In the paper a review of models and methods for finding paths in multiresolution networks and their effectiveness analysis have been presented. One of the methods is based on merging the geographically adjacent nodes (squares) and the planning path to a "merged" graph. The merging is done by using geographically adjacent squares of primary graph (thus, we obtain nodes of a "merged" graph) and calculating costs in the "merged" graph as longest (or shortest) of the shortest paths between some subsets of nodes belonging to "merged" nodes. Second method is applied for planning multiresolution paths in roads network. Application of presented methods in multiresolution battlefield movement planning and simulation is discussed.

Słowa kluczowe

PL

model wielorozdzielczy; algorytm wielorozdzielczy; planowanie przemieszczenia; symulacja pola walki; wielorozdzielcza symulacja walki

EN

multiresolution model; multiresolution algorithm; movement planning; battlefield simulation; multiresolution battlefield simulation

• Wydawca: Polskie Towarzystwo Symulacji Komputerowej
• Czasopismo: Symulacja w Badaniach i Rozwoju
• Rocznik: 2010
• Tom: Vol. 1, nr 4
• Strony: 391--409
• Opis fizyczny: Bibliogr. 17 poz., rys., tab.

Twórcy

autor

Tarapata Z.

autor

Godlewski P.

• Wojskowa Akademia Techniczna, Wydział Cybernetyki, 00-908 Warszawa, ul. Kaliskiego 2,

Bibliografia

• 1. Benton J.R., Iyengar S. S., Deng W., Brener N., Subrahmanian V. S.: Tactical Route Planning: New Algorithms for Decomposing the Map, International Journal on Artificial Intelligence Tools, vol. 5 (1-2), 1996.
• 2. Chen D. Z., Szczerba R. J., Uhran Jr. J. J.: Using Framed-Quadtrees to Find Conditional Shortest Paths in an Unknown 2-D Environment, Technical Report: #95-2, Uniwersytet Notre Dame, Indiana, USA, 1995.
• 3. Chen D. Z., Szczerba R. J., Uhran Jr. J. J.: Using Framed-Octrees to Find Conditional Shortest Paths in an Unknown 3-D Environment, Technical Report: #95-9, Uniwersytet Notre Dame, Indiana, USA, 1995.
• 4. Chou Y., Romeijn H. E., Smith R. L.: Approximating Shortest Paths in Largescale Networks with an Application to Intelligent Transportation Systems, INFORMS Journal on Computing Vol. 10, Issue 2 (1998) s. 163 - 179.
• 5. Djidjev H., Pantziou G., Zaroliagis C.D.: On-line and dynamic algorithms for shortest path problems, Lecture Notes in Computer Science, vol.900 (1995), 193-204.
• 6. Godlewski P.: Modelowanie i algorytmizacja procesów planowania i symulacji przemieszczania z wykorzystaniem wielorozdzielczych modeli terenu, praca magisterska pod kierunkiem Z.Tarapaty, Wojskowa Akademia Techniczna, Warszawa, 2010.
• 7. Kambhampati S., Davis L. S.: Multiresolution Path Planning for Mobile Robots, IEEE Journal of Robotics and Automation, Vol. RA-2, nr. 3, 1986.
• 8. Korf R.E.: Artificial intelligence search algorithms, in Algorithms Theory Computation Handbook, Boca Raton, FL: CRC Press (1999).
• 9. LaValle S. M.: Planning Algorithms, Cambridge University Press 2006.
• 10. Magillo P., Bertocci V.: Managing Large Terrain Data Sets with a Multiresolution Structure, INFORMS Journal on Computing Vol. 10, nr 2, 1998 s. 163 - 179.
• 11. Mitchell J. S. B.: An Algorithmic Approach to Some Problems in Terrain Navigation, Artificial Intelligence Vol. 37, nr 1-3 (1988) s. 171 - 201.
• 12. Pai D. K., Reissell L.M.: Multiresolution Rough Terrain Motion Planning, IEEE Transactions on Robotics and Automation, Vol. 14, nr 1, 1998, s. 19 - 33.
• 13. Petty M.D.: Computer generated forces in Distributed Interactive Simulation, Proceedings of the Conference on Distributed Interactive Simulation Systems for Simulation and Training in the Aerospace Environment, 19-20 April, Orlando (USA) (1995), 251-280.
• 14. Reece D., Kraus M., Dumanoir P.: Tactical Movement Planning for Individual Combatants, Proceedings of the 9th Conference on Computer Generated Forces and Behavior Representation, Orlando, Floryda, 2000.
• 15. Tarapata Z.: Military route planning in battlefield simulation: effectiveness problems and potential solutions, Journal of Telecommunications and Information Technology, nr 4 (2003), s. 47-56.
• 16. Tarapata Z.: Multiresolution models and algorithms of movement planning and their application for multiresolution battlefield simulation, ACIIDS 2010, Lecture Notes in Computer Science/LNAI, 5991 (2010) Springer-Verlag Berlin Heidelberg, s. 378-389.
• 17. Tarapata Z.: A Parallel Decomposition Algorithm for Shortest Path Problem in Large-Size Mesh Networks, Biuletyn WAT, vol. LIX, Nr 3, 2010, 295-306.