Multiresolution formation preserving path planning in 3-D virtual environments

Download

index.pdf

Date

2011

Author

Hoşgör, Can

Metadata

Show full item record

Item Usage Stats

197
views

94
downloads

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.

Subject Keywords

Computer software., Navigation.

URI

http://etd.lib.metu.edu.tr/upload/12613709/index.pdf
https://hdl.handle.net/11511/21104

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

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...
Formation preserving path finding in 3-D terrains Bayrak, Ali Galip; Polat, Faruk (Springer Science and Business Media LLC, 2012-03-01) Navigation of a group of autonomous agents that are required to maintain a formation is a challenging task which has not been studied much especially in 3-D terrains. This paper presents a novel approach to collision free path finding of multiple agents preserving a predefined formation in 3-D terrains. 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...
RG-Trees: Trajectory-Free Feedback Motion Planning Using Sparse Random Reference Governor Trees Gölbol, Ferhat; Ankaralı, Mustafa Mert; Saranlı, Afşar (2018-10-05) Sampling based methods resulted in feasible and effective motion planning algorithms for high dimensional configuration spaces and complex environments. A vast majority of such algorithms as well as their application rely on generating a set of open-loop trajectories first, which are then tracked by feedback control policies. However, controlling a dynamic robot to follow the planned path, while respecting the spatial constraints originating from the obstacles is still a challenging problem. There are some ...
Multiagent moving target search in fully visible grid environments with no speed difference Eroğul, Can; Polat, Faruk; Department of Computer Engineering (2006) In this thesis, a new real-time multi-agent moving target pursuit algorithm and a moving target algorithm are developed and implemented. The environment is a grid world, in which a coordinated team of agents cooperatively blocks the possible escape routes of an intelligent target in real-time. Most of the moving target search algorithms presume that the agents are faster than the targets, so the pursuit is sure to end in favor of the agents. In this work, we relax this assumption and assume that all the mov...
Topological Navigation Algorithm Design and Analysis Using Spherical Images Şahin, Yasin; Koku, Ahmet Buğra; Department of Mechanical Engineering (2022-8-23) A topological navigation algorithm that has the capability of mapping and localization based on visual contents is proposed. Keypoint detection and feature matching are conducted on spherical images to extract significant features among sequential frames. Robot movement direction is estimated based on historical angle differences of significant features to reach the final destination. The navigation process is supported with visual egocentric localization to gain simultaneous localization and mapping compet...

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.