Multiresolution formation preserving path planning in 3-D virtual environments

Hoşgör, Can
The complexity of the path finding and navigation problem increases when multiple agents are involved and these agents have to maintain a predefined formation while moving on a 3-D terrain. In this thesis, a novel approach for multiresolution formation representation is proposed, that allows hierarchical formations of arbitrary depth to be defined using different referencing schemes. This formation representation approach is then utilized to find and realize a collision free optimal path from an initial location to a goal location on a 3-D terrain, while preserving the formation. The proposed metod first employs a terrain analysis technique that constructs a weighted search graph from height-map data. The graph is used by an off-line search algorithm to find the shortest path. The path is realized by an on-line planner, which guides the formation along the path while avoiding collisions and maintaining the formation. The methods proposed here are easily adaptable to several application areas, especially to real time strategy games and military simulations.


Coordinate systems for a naval virtual environment
Kılıç, Aslı; Oğuztüzün, Mehmet Halit S.; Department of Computer Engineering (2005)
The purpose of this thesis is implementing World Geodetic System (WGS) for Naval Surface Tactical Maneuvering Simulation System (NSTMSS), a High Level Architecture (HLA) based naval simulation, and also implementing body coordinate system for the ships of NSTMSS and its combination with WGS so that NSTMSS can be more accurate, and new ship dynamics models can be integrated to the NSTMSS environment more easily. To improve the coordinate system of NSTMSS these methods were used; World Geodetic System - 1984 ...
Local search versus Path Relinking in metaheuristics: Redesigning Meta-RaPS with application to the multidimensional knapsack problem
Arin, Arif; Rabadi, Ghaith (Elsevier BV, 2016-09-01)
Most heuristics for discrete optimization problems consist of two phases: a greedy-based construction phase followed by an improvement (local search) phase. Although the best solutions are usually generated after the improvement phase, there is usually a high computational cost for employing a local search algorithm. This paper seeks another alternative to reduce the computational burden of a local search while keeping solution quality by embedding intelligence in metaheuristics. A modified version of Path ...
Active stereo vision : depth perception for navigation, environmental map formation and object recognition
Ulusoy, İlkay; Halıcı, Uğur; Department of Electrical and Electronics Engineering (2003)
In very few mobile robotic applications stereo vision based navigation and mapping is used because dealing with stereo images is very hard and very time consuming. Despite all the problems, stereo vision still becomes one of the most important resources of knowing the world for a mobile robot because imaging provides much more information than most other sensors. Real robotic applications are very complicated because besides the problems of finding how the robot should behave to complete the task at hand, t...
Fuzzy spatial data cube construction and its use in association rule mining
Işık, Narin; Yazıcı, Adnan; Department of Computer Engineering (2005)
The popularity of spatial databases increases since the amount of the spatial data that need to be handled has increased by the use of digital maps, images from satellites, video cameras, medical equipment, sensor networks, etc. Spatial data are difficult to examine and extract interesting knowledge; hence, applications that assist decision-making about spatial data like weather forecasting, traffic supervision, mobile communication, etc. have been introduced. In this thesis, more natural and precise knowle...
Formation preserving navigation of agent teams in 3-d terrains
Bayrak, Ali Galip; Polat, Faruk; Department of Computer Engineering (2008)
Navigation of a group of autonomous agents that are needed to maintain a formation is a challenging task which has not been studied much in especially 3-D terrains. This thesis presents a novel approach to collision free path finding of multiple agents preserving a predefined formation in a 3-D terrain. The proposed method could be used in many areas like navigation of semi-automated forces (SAF) at unit level in military simulations and non player characters (NPC) in computer games. The proposed path findi...
Citation Formats
C. Hoşgör, “Multiresolution formation preserving path planning in 3-D virtual environments,” M.S. - Master of Science, Middle East Technical University, 2011.