Tez No	İndirme	Tez Künye	Durumu
338224		Dinamik ortamlar için yeni bir gerçek zamanlı evrimsel seyrüsefer planlama ve güdümleme sistemi / A new real time evolutionary navigation planning and guidance system for dynamic environments Yazar:FERHAT UÇAN Danışman: DOÇ. DR. DENİZ TURGAY ALTILAR Yer Bilgisi: İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Evrimsel algoritmalar = Evolutionary algorithms    ; Genetik algoritmalar = Genetic algorithms	Onaylandı Doktora Türkçe 2013 170 s.
Gerçek zaman kısıtları altında seyrüsefer planlama, değişken ortam koşullarında hava aracının minimum yakıtla en güvenilir, en kısa yoldan intikali tamamlayabilmesi için gerekli çözümün bulunmasını gerektirir. Enlem, boylam ve yükseklik değerleri ile tanımlanan uçuş noktalarının bazıları arasında, çift yönlü geçiş yolları tanımlıdır. Bu geçiş yollarının uzunluk, güvenlik, yükseklik farkı gibi rastlantısal olarak değişebilen ölçütleri mevcuttur. Problemin en uygun çözümü, tüm amaç fonksiyonlarını birlikte eniyileyen, en kısa, en güvenilir ve düze en yakın rotanın planlanması ve güdümleme ile çevrimiçi olarak çalıştırılmasıdır. Tezde çözüm önerilen rota planlama problemi, uzunluk, yükseklik ve güvenlik ölçütlerini değerlendirdiği için çok amaçlı eniyileme problemidir. Gerçekleştirilen sistem uçuş planı tasarlama, yakıt planlama ve uçuş planı yürütme alt sistemlerinden oluşmaktadır. Uçuş planı tasarlama alt sisteminde, hava araçlarının, bir intikal başlangıç noktasından hedef noktasına en uygun rotası evrimsel algoritma ile planlanmıştır. Planlama alt sistemi, maliyeti dinamik değişebilen üç farklı kısıtlı çizge yapısını kullanmaktadır. Evrimsel uçuş planlama alt sisteminde geliştirilen genetik algoritmada, tezde özgün olarak seyrüsefer sistemi için tasarlanan çaprazlama, mutasyon ve çevrim kaldırma operatörleri kullanılmıştır. Çaprazlama oranı, mutasyon oranı gibi değerlerin uçuş planlama problemi için en uygun değerleri deneysel çalışmalarla bulunmuştur. Evrimsel uçuş planlama algoritması ile en uygun uçuş planı bulunduktan sonra bu uçuş planı yakıt planlama alt sistemine gönderilir. Yakıt akış hızına ilişkin regresyon ile bulunan yakıt akış hızı ve toplam yakıt bilgilerine göre uçuş planının mevcut yakıtla icra edilip edilmeyeceğinin analizini yapılır. Eğer uçuş planı için yakıt yeterli ise plan uçuş planı yürütme alt sistemine gönderilir ve planın icrası gerçekleştirilir. Eğer mevcut yakıt yeterli değilse uçuş planlama alt sistemi tarafından farklı bir uçuş planı araştırılır. Uçuş planı yürütme alt sistemi sağladığı yatay ve dikey güdümleme fonksiyonlarıyla tüm uçuş bacakları için, istenilen kalkış noktasından bir sonraki varış noktasına planlanan intikali gerçekleştirir. Hava aracının rotasında, istenilen uçuş rotasına göre herhangi bir sapma olduğunda, sapmayla orantılı, hava aracını yatayda ve dikeyde istenilen rotaya sokacak yalpalama ve yunuslama açısı komutları hesaplanır. Güdümleme alt sisteminde, hava aracının rota değiştirmesi gereken zamanlarda bir sonraki rotaya oturmasını sağlayacak güdümleme komutları hesaplanmaktadır.
Navigation planning under real time constraints requires finding the necessary solution for the transition of an air vehicle through the most secure and shortest path with minimum fuel consumption with changing environment conditions. There are transition paths between some of the waypoints, which are defined by latitude, longitude and altitude parameters. Constraints apply to these transition paths such as distance, security and altitude, which can change casually. The optimum solution of the problem is expected to optimize all of the objective functions. Finding such a solution is usually difficult due to the dynamically changing constraints. Because usually constraints that are considered in the problem are contradictory and interact adversely with each other. Since the problem considers distance, altitude and security conditions as distinct constraints, it becomes a multi-objective optimization problem. The designed system consists of two subsystems, one of these subsystems is the flight planning subsystem and the other one is the flight plan execution subsystem. In the flight planning subsystem, the most secure, shortest and smoothest flight path transition of the air vehicles from the source waypoint to the target waypoint is planned by an evolutionary method. The flight plan execution subsystem executes the planned flight path from the desired departure waypoint to the next arrival waypoint through the lateral and vertical navigation guidance functions. Navigation planning can be considered as searching the most convenient flight path from an initial waypoint to a destination waypoint. Generally the aim is to follow the flight path, which provides minimum fuel consumption for the air vehicle. In dynamic environments, constraints change dynamically during flight. This constitutes a special case of dynamic path planning. Dynamic path planning is a problem that is encountered in many fields in different forms. It can be used in vehicle routing systems, military applications, robotics applications and sensor networks for determining the route between two points. Since the main concern of the thesis is about flight planning, the conditions and objectives that are most applicable to the navigation problems are considered. In the thesis, the evolutionary dynamic navigation planning algorithm is developed in order to compensate for deficiencies in the existing approaches. The existing fully dynamic algorithms process unit changes in topology one modification at a time. When there are several modifications occurring in the environment simultaneously, the existing algorithms are quite inefficient because of computation time. The problems are worse in large topologies, where a large number of topology modifications may occur often. The proposed algorithm is designed to respond to the concurrent constraint updates within a shorter time for dynamic environment. The graphs which serve the purpose of representing a waypoint map are dynamic. While the navigation distance and security parameters change, the genetic algorithm plans the most feasible flight path according to the updated conditions. In the city map, each waypoint is defined by longitude, latitude and altitude parameters. The routes between waypoints have three costs; distance, change of altitude and security. The most secure navigation of the air vehicle is planned and executed with minimum fuel consumption. Some of the well-known representative methods used for the standard route planning problem are the Dijkstra, Floyd Warshall, A-Star and Bellman Ford algorithms. All of them have been designed to calculate the shortest path between two nodes of a static graph. The effects of the security, distance and altitude difference parameters may be modeled with these classical optimization techniques. However, in a dynamic environment, restarting to find the solution at each graph update increases the time complexity. Moreover, when new waypoints or routes are inserted or some of the existing routes are deleted, the classical algorithms cannot compensate for this situation without restarting the algorithm. The proposed evolutionary method considers multi-objectives and compensates for dynamic conditions by utilizing evolutionary operators and by implementing the problem-specific fitness function. The proposed evolutionary navigation planning approach reduces the number of operations in dynamic environments, because it does not restart the solution at each update, and it trends to extend best-fit individuals into the new generations. Dynamic path planning algorithms such as the algorithms suggested by Frigioni, Franciosa and Ramalingam have been used in dynamic environments. However these algorithms are quite inefficient because of computation time, when several concurrent changes occur in the environment simultaneously. These algorithms fail to reach the actual underlying average solution when the segment costs and conditions change stochastically and continuously. These algorithms run when the costs of the links in the graph are fixed for the course of a single computation. However, in a flight plan scenario, the altitude of the paths and the security of the links may approximately be known. Therefore any algorithm that would be proposed is expected to work with uncertain graphs. The proposed algorithm provides advanced search speed, quality and flexibility in dynamic schemes. The flight planning subsystem takes latitude, longitude and altitude information of waypoints as an input. Latitude is the angular distance of a point on the earth's surface to the equatorial plane, measured from the center of the sphere. Longitude is a geographic coordinate that specifies the east-west position of a point on the Earth's surface. Altitude is the angular distance, usually in the vertical direction, between a reference datum and a point or object. The longitude and latitude components specify the position of any location on the planet. A flight leg is a route between two combined waypoints. The constraints of the flight leg are defined as a vector which consists of the distance, the security value and the altitude of the flight leg. In the flight planning subsystem we used an evolutionary approach. In the proposed evolutionary approach, in order to represent the routes, variable-length chromosomes are used. Chromosomes are encoded by permutation encoding method. Each gene of a chromosome represents a node on the graph, and all genes show the whole path on the graph. The qualities of the individuals are determined by the fitness function. A general fitness function is developed in order to meet all the constraints. Chromosomes are arranged in decreasing order according to the fitness values. In order to increase the quality of the population, a selection operator which raises the chance of the better fit individuals, is used in the proposed algorithm. The selection operator, forces to search the solution within the determined locations of the search space. For the selection process, the roulette wheel selection technique is used in the proposed algorithm, in order to save the better-fit individuals for the next generation, and in order to avoid from statistical errors caused by sampling, the roulette wheel selection technique is used for selection. According to the roulette wheel selection technique, the fitness values of all individuals are added. The selection probability of an individual is found by dividing the fitness value to the overall value. During the crossover phase, the genes beyond the crossover site are exchanged between parent chromosomes. Probable crossover sites are the regions where the genes of the parent chromosomes are identical. If the parents have no identical pair of genes, the crossover operator cannot be applied. If there is more than one identical pair of genes, one of the pairs is chosen randomly. Crossover may generate infeasible chromosomes that violate the loop constraint and may form individual chromosomes with cycles. The algorithm runs a post-processing operation and removes the cycles from the individual. Navigation planning requires a flight plan check against fuel consumption. Minimum fuel consumption is also an important constraint considering two probable objectives; economical gain and extending the range of air vehicle. Flow rate estimation is a known approach in flight planning. Fuel flow can be defined accurately as a function of air temperature, flight altitude, true airspeed and gross weight for each different type of air vehicle. In the designed navigation system, the flight plan is checked for fuel consumption prior to passing the flight plan to the guidance subsystem. The guidance subsystem provides lateral and vertical guidance algorithms that provide passing through the flight legs and desired route in a real-time environment. The lateral guidance function provides roll angle commands to maintain the heading. The vertical guidance function generates an altitude error signal from a reference altitude and provides a pitch angle command, which allows the autopilot to maintain altitude. Real-time flight data is taken from the Aerosim flight simulator. AeroSim simulator provides a complete set of tools for developing nonlinear 6-degree-of-freedom aircraft dynamic models. The parameters like initial position, wind speed, initial velocity, initial altitude, initial engine speed, and sample time can be modified at the beginning of the navigation simulation. Mission execution subsystem uses real-time data provided by Aerosim in order to calculate pitch and bank angle commands that feed the pilot. The guidance subsystem provides pitch, roll and attitude commands based on data from the simulation environment, including attitude, heading, ground speed, altitude and pilot inputs. When a deviation from the flight plan occurs, the pitch and bank angle commands are calculated in order to fit the desired flight leg. Beside this, when the route switching points are reached, these angles are again calculated in order to put the air vehicle in the next flight route.