Attitude Control System for a Spaceflight Simulator

#1

Currently I’m working on a Spaceflight Simulator game that will allow the pilot to fly his spacecraft into space, intersect with an orbiting space station and land his spacecraft inside the station’s landing bay by using reaction control thrusters. If successful, the pilot will takeoff from the landing bay, deorbit into the earth’s atmosphere and glide his spacecraft back to earth under no power and land on a runway.

The spaceflight simulator will have a high degree of realism making such maneuvers as landing inside and taking off from a station’s landing bay very difficult.

To assist the pilot in achieving these maneuvers, I will create an Attitude Control System (ACS) that is capable of maintaining the desired attitude autonomously. The ACS will be adaptive so if the pilot loses control, it will bring the spacecraft back to its proper orientation.

This thread will be a work in progress with code snippets to explain how the ACS works and some graphs and/or reports showing some preliminary test results. This thread is mostly for those who are interested in Game AI. It will not contain a lot of eye candy. The reason I’m posting here is to get feedback from those who know better than I about AI and/or those who are interested in learning and may benefit from what is explained here.

At the end of this thread, I will post a link that will allow those interested to install a demostration of the ACS. The demostration will display a spacecraft currently in orbit where the pilot can use his joystick and/or keyboard to activate the reaction control thrusters and the main thrusters to spin the spacecraft out of control. A function key will be available to activate the ACS that will regain control of the ship.

There is nothing new about what I’m doing here. Some of you may already know of games that display this kind of intelligence. But this is a beginner project for me and hopefully what I learn from it will lead to more unique challenges in the future.

In the next update I will display a diagram showing the main components of the ACS with explanations of each component.

#2

Here is a rough diagram of the Attitude Control System’s (ACS) Architecture.

The Control Administrator, Fuzzy Neural Controller and the Genetic Optimizer make up the ACS. All three of these components will consist of C++ objects. My first attempt will be to make this system a real-time learning system so the ACS will continue learning during the simulation. :shrug:

My first step in constructing the ACS will be to build the Genetic Algorithm class that is the superclass of the Genetic Optimizer.

#3

I am not a coder, rather an artist. But this is very interesting to me. Thanks for sharing. Please continue to post updates.

#4

EricChadwick: Thanks man! I appreciate your support!

A Genetic Algorithm (GA) is a search optimization technique that uses a population of individuals to find the optimal solution(s) to a problem. How good a solution an individual represents depends on its fitness score. Let’s say that we have a GA with a population size of 100 meaning there are 100 individuals (or possible solutions) in the population. Each individual is tested by running a simulation of the problem using that individual. The result of that simulation represents the individual’s fitness score. The next individual is then used in the simulation and this continues until all individuals have been used.

The next step is to go through a generation process that creates a new population of individuals based on the current population. The better fit individuals are selected to mate and produce new
individuals. Mating involves the use of genetic operators. Crossover and mutation are the most common. The new individuals now become the current population and the process starts again. From computing the fitness score for each individual to producing a new population is called a generation. Each new generation produces better solutions to the problem. After a pre-determine number of generations has been processed the simulation is terminated.

Here are some links that will explain in detail how a GA works:

http://samizdat.mines.edu/ga_tutorial/
http://www.pmsi.fr/gainita.htm
http://www.hao.ucar.edu/public/research/si/pikaia/tutorial.html
http://cgm.cs.mcgill.ca/~soss/cs644/projects/marko/
http://geneticalgorithms.ai-depot.com/Tutorials.html

An individual’s representation can be in various forms but the two most common are binary coded and real coded individuals.

11001110 is a binary chromosome with a chromosome length of 8.
2.39 0.12 0.98 1.09 1.16 -0.22 -1.89 0.03 is a real coded chromosome with a length of 8.

For our GA we have the following classes defined:

class Individual {
public:
// Constructor for Individual.
Individual ( int _chromlen ) ;

// Destructor for Individual.
~Individual ( ) {}

// other member functions go here ...

private:
int chromlen ;
double fitness , decode ;
} ;

Individual will contain the length of the chromosome, the decode value and the fitness score.

class BinaryIndividual : public Individual {
public:

// other member functions go here ...

private:
// Binary chromosome representation.
int chromosome [ MAX_CHROMLEN ] ;
} ;

BinaryIndividual is a subclass of Individual that contains the binary chromosome. If we wanted to create a real coded chromosome, we create a subclass of Individual called RealIndividual that contains a real coded chromosome.

class GeneticAlgorithm {
public:
// Constructor for GeneticAlgorithm
GeneticAlgorithm ( int _popsize , int _chromlen , int _maxgen ,
double _crossprob , double _mutateprob ) ;
~GeneticAlgorithm ( ) ;

// other member functions go here ...

private:
int popsize , chromlen , maxgen ;
double crossprob , mutateprob ;
} ;

GeneticAlgorithm class contains the parameters for the GA. They are population size, chromosome length, maximum number of generations, crossover probability and mutation probability.

class BinaryGeneticAlgorithm : public GeneticAlgorithm {
public:
// other member functions go here …
private:
// Initialize the population.
void initializePopulation ( ) ;

BinaryIndividual * population [ MAX_POPULATION ] , * newpopulation [ MAX_POPULATION ] ;

} ;

BinaryGeneticAlgorithm class contains the current and new populations and uses an initialization function to create the initial population.

In the next update I will explain in further detail how this GA works and come up with a test example.

#5

You’re playing God here! Or as I prefer to think of it, pure clean natural selection. Neat to see you explaining how the code works.

btw, I’m reading a great book these days, by Carl Sagan and Ann Druyan, “Shadows of Forgotten Ancestors.” I’m at the point where they’re revealing how Darwin arrived at his revolutionary discoveries, and much he got correct even without knowing about molecular biology, DNA/RNA/mutations/etc. Great reading, dovetails in with your post…

#6

hey jfelrod1960. I find your ACS to be really interesting. I would appreciate it if you could help me with creating a neural network AI script that also incoperate path-finding ability for a game character Or NPC (non-playable characters). If you could show how ito insert it into a Game engine.

Keep up the work. hope you complete you project, so you may share wtih the threaders.

Thanks…

#7

some interesting math needs to go through that GA. will be interested to see how you do that. orbital mechanics is tough stuff!

[Edit* - compressible flow?]

#8

linkmatrix: I will start with the FNC later next week. This may help you. If not then we can come up with something more specific.

csven: I agree with you completely. I hope you continue to check out the thread. I will include entries about the spacecraft’s state. But will not go into much detail. Another CGTalker who is an aerospace engineer has really been very kind about answering my questions. But it will be the FNC updating the motion equations. The optimizer (GA) only responds to the failure scores of its population elements. It will have no knowledge of orbital mechanics.

One other thing … I hope this design will work. :eek:

#9

i will be. my first degree is aero so i’m curious. btw, who’s your helper? always cool to see other aeros :slight_smile:

#10

I’m still working on the Genetic Algorithm that is the base class for the Genetic Optimizer. In this entry, I want to explain how the Genetic Optimizer (“optimizer”) will work in the ACS.

The optimizer’s responsibility is to find the right parameters for the Fuzzy Neural Controller (FNC) to use. It basically sits and waits until it receives a “failure score” from the Control Administrator (CA). I call this a failure score because in Genetic Algorithms, each individual in the population receives a score to show it’s fitness level. An individual’s fitness level indicates its chances of being selected for mating to produce new individuals for the next generation. A failure score sent to the optimizer indicates that a failure has occurred and its score shows how well the individual has performed.

When the ACS is initialized, one of it’s responsibilities is to create the optimizer from a file that contains the parameters for building it. Things like population size, chromosome length, crossover and mutation probabilities, stuff like that. Once the optimizer is created, an individual is selected and sent to the FNC. As long as a failure does not occur the optimizer does nothing. The FNC and the CA is doing all the work. But once a failure has been dectected by the CA, the optimizer will receive a failure score for that individual. The optimizer at that point will record the fitness for that individual, select the next individual and send it to the FNC and then return control back to the CA. The CA and FNC will continue as before. If the optimizer has used all the individuals in the population, which I hope will never occur, then it will generate a new population of individuals, select the first individual to send to the FNC and then return control back to the CA.

What is an example of a failure in the ACS? Well suppose the ACS has to keep a yaw angle within ±3 degrees and the spacecraft yaw angle is outside that boundary. The ACS will attempt to adjust the angle back within that boundary and if successful, nothing changes. The optimizer was never called and all continues as before. But if the CA determines that the FNC cannot regain control and place the spacecraft back within that ±3 degrees boundary, then it will call the optimizer to send a new set of parameters (another individual) for the FNC. Hopefully it will do a better job in controlling the angle displacement.

Crits welcomed.

#11

csven: I hope my “helper” has contacted you. I pointed him to your entry. He stays pretty busy with his work.

Well I finished the GA and ran a test. First let me explain a few things.

I changed the parameter list in the GeneticAlgorithm class to include the crossover method and a uniform crossover probability if a uniform crossover method is selected.

The generation process that is used to generate a new population first performs a sort on the population based on the fitness score of each individual. Next a roulette wheel selection is performed to select 2 parents. After selection comes the crossover procedure. Three types of crossover are included. Single point crossover, Two point crossover and Uniform crossover. Refer to the links on this thread to find out more about crossover. After crossover is mutation that is done on the children created from the crossover method. These steps will create two children for the new population and the process is repeated starting with selection until the new population is completed.

Like I said earlier in the thread, the GA responds to the fitness scores of the population. It has no knowledge of the problem domain. I wanted to see how good this GA works so I tried it on a very well known problem called the Order-4 fully deceptive interleaved problem.

Refer to this link that discusses Deception in Genetic Search:
http://www.cs.dal.ca/~mheywood/CSCI6506/HandOuts/N04-Deception.pdf

The interleaved term is used because the groups of 4 bits are interleaved within the chromosome of the individual. Making the problem even harder. If you read the above paper you will see what 4 bits I’m referring to.

Also you can refer to this link:
http://www.ri.cmu.edu/pubs/pub_2769.html

The paper “A Massively Distributed Parallel Genetic Algorithm (mdpGA)” uses this problem for one of its tests.

The highest fitness score an individual can achieve is 300. I performed 3 separate runs where each run consist of 30 trials.

Here are the parameters used in the GA for all 3 runs.
population size: 1000
chromosome length: 40 (10 * 4 bit strings)
max generation: 1000
crossover probability: 1.00
mutation probability: 0.001

The only difference in the runs were the crossover methods.
Single point crossover
Two point crossover
Uniform crossover with a probability of 0.30.

For each run on I calculated an average maximum fitness per generation. Below is a graph.

As you can see, the averages are not even close to the 300 mark. Uniform crossover and single point crossover perform much poorly than two point crossover. I believe this GA would not perform well as a genetic optimizer for the ACS.

I will continue with building the GeneticOptimizer class which will be a subclass of the GeneticAlgorithm but I will need to improve the GeneticAlgorithm’s ability to find better solutions before using it in the ACS. Not much is done with the GeneticOptimizer class since all the work is ing the GA. The optimizer basically provides an interface to the Control Administrator and the FNC.

The next update will begin with the FNC.

#12

Man…u are researching on some crazy stuff …weeeeee…more please i am interested…and u can imagine that we don’t see programmers of you kind here in Greece…please post more…this is awesome…:deal:

#13

Looks like interesting stuff, I want to see how it ends. I wonder if I’ll be doing any programming like this as an electrical engineer. Even if i wont ill probably still do this type of stuff for the hell of it:scream: .

#14

Wow you should talk to my brother, he is an advanced matrix programmer, he talks to my about physics theoretical and applied, gene coding, code mutation, etc… Very interesting stuff. I will tell him about you. Perhaps there is something that could come from this meeting. Very interesting code you posted by the way.

#15

I have studied physics…I find the “breakdown” of the world so facinating…looks like you are attracting more artists to this thread than programmers…good or bad here we are…
…My mind Is GLOwinG… :wise:

#16

I decided not to create the spaceflight game anymore, but concentrate on game AI. I’m continuing this Attitude Control System (ACS) project to be used in a real-time AI animation. I will start by redesigning this GA tonight hopefully it will work better.

Updates to soon follow …

#17

very intresting
like to see more here…:thumbsup:

#18

wow, great stuff man.
Will it be open-source? As our game studio is quite interested in AI :smiley:

#19

Too soon to say yet Joe. Seems like everytime I work on this, something else comes in. I will have more updates soon. I have been working on this, just haven’t posted any results in a while.

#20

Have a Happy new year!