To access the full text documents, please follow this link: http://hdl.handle.net/2099.1/13827

Ground Stations Scheduling with Genetic Algorithm
Sun, Junzi
Xhafa Xhafa, Fatos; Chester, Ed; Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
TThis work presents a Genetic Algorithm (GA) approach to Ground Station (GS) andSpacecraft (SC) Scheduling problem, which is based on the space missions andground stations from ESA (European Space Agency).Genetic Algorithm has been used for optimization for many years. The first part of thework is to study how GA has been developed and put in position to science andengineering field. A general GA process is been introduced in this section, whichdescribes basic operations of encoding, mutation, crossover, and selection. Thereare strengths and limitations of Genetic Algorithms for optimization, which aredescribe in this section too.The GS-SC scheduling problem is a highly resource-constrained. So in section 1.2,the concept of Resource-Constrained Schedule is studied and defined. And thedifficulties of this kind of schedule are presented.The second part of the work defines the basic concepts of ground stations andspacecrafts, which is based on ESA examples. A mathematical model of GroundStations and spacecrafts is built based on the definitions and assumption of thesystem. It is simplified so that it can be understood and modeled easily. There arethree parts of the model: inputs, outputs and intermediate parameters. The system isto take the input data of spacecraft access windows and time requirements, andusing an algorithm to generate a valid schedule solution.STK (Satellite Tool Kit) is been selected for data generation of this work. Spacemission of selected ones are simulated and executed. The STK generates one of theimportant input data: Access Window information of GSs to all SCs. Together withdefined mission requirement data, they are converted and stored in the schedulesystem using a pre-defined structure, which is waiting for further GA process.The GA process is the core chapter in this work. It describes the most important partof work that is approaching the solution of the entire problem. It starts from theencoding method, where two encoding methods are invested and tested, binaryvector encoding and decimal vector encoding. It has been proved in this work thatthe decimal encoding has a better performance and computation speed than theother one. There are advantages and weaknesses that are both examined. Alsocrossover and mutation methods are introduced.The focus of this designated GA is on designing its fitness functions. This task isrelated with the constraints and objectives for the ground stations and space missionrequirements. A technique of Fitness Modules (FM) is been developed to satisfyingthe varieties of mission objects. Those modules can be sequential or parallel in thefitness evaluation process. The introducing of FM concept gives the answer to addand remove mission objectives without affecting the existing GA fitness functions.Thus the final evaluating fitness is by summarizing all FMs with different weights. Inthis simplified model four FMs that represent four mission objectives are designed,these are, Fitness for Spacecraft Access Windows, Fitness for CommunicationClashes, Fitness for Communication Time Requirement, and Fitness for MaximizingGround Station Usage.Every GA needs a selection method of choosing chromosomes for populationreproduction. There are some traditional selection methods, which are selected,described and studied. Also we have proposed a combinational selection method toaccelerate the population fitting value.The last part of the work is to simulate the entire process in computer environment.Matlab is selected because of its excellent mathematical calculations capability. TheGA is coded and executed with multiple times, in order to get the average results.Those data are all been illustrated. And one of the best schedules is been generatedas the solution of the problem. The designed GA solved defined problemsuccessfully.In the end, the weakness of this GA is mentioned, and future work direction ispointed out.
In this Master Thesis will be conducted a study on the family of scheduling problems from spacecrafts domain. The objective is to identify special cases of problems in this domain and their relevance from a practical perspective. The considered problems will be modeled as optimization problems and their resolution will be tackled using heuristic approaches (Genetic Algorithms). An experimental analysis will be done using both simulation techniques & benchmarking and real data.
2012-06-26
Àrees temàtiques de la UPC::Aeronàutica i espai
Genetic algorithms
Space vehicles
Optimització matemàtica
Vehicles espacials
Algorismes genètics
Restricted access - author's decision
Research/Master Thesis
Universitat Politècnica de Catalunya
         

Show full item record

 

Coordination

 

Supporters