KickSat Sprite CGP

How’s that for a cryptic title? The KickSat project will deploy 200 satellites, called “Sprites”, each the size of a business card into low earth orbit in December 2013. Along with Don Smith and my colleagues at Part-Time Scientists, I am writing software for one of these Sprites. The most interesting challenge is communications. At roughly 1 byte per second and no battery to power a radio through a solar outage, getting a lot of data from the communication stream is difficult. Us humans are pursuing the classic route of performing trade studies to select a communication protocol. Meanwhile, the Cartesian Genetic Programming (CGP) machinery grinds away looking for an even better protocol. I’ve reached out to the creator of CGP, Julian Miller, who has also brought in Simon Harding to assist. I cannot overstate the value of their input on tuning parameters and setting up the problem. Final results will be posted here in early September. In the meantime, here is the structure of the CGP system.

The Sprite has a 3 axis magnetometer, a 3 axis gyro, a temperature sensor, and a small persistent memory. Figuring just the sensor readings themselves, we have 7 telemetry points to be sent to the ground. Adding values for system uptime, reboot count, min/max readings, sensor noise, and sensor correlations further raises this count.

The generic structure is to reduce the resolution to 8 bits per telemetry point and to send points in either a round-robin or random sequence with an indicator telling us which data point follows. Pairs of telemetry values are grouped into a single ID and sent together. Success is defined by recovering the sensor data from both complete and corrupted packets. With amount of redundancy built into the Sprite’s low level protocol, we aren’t concerned really with byte-level corruption as much as with packet truncation due to loss of power.

Each “world” consists of a CGP individual to encode a packet and another individual to decode a packet. The encoder is presented with 16 separate inputs, 1 for each bit in 2x 8-bit sensor readings. The encoder outputs 16 separate outputs, each interpreted as a binary value (>0 –> 1, <= 0 –> 0). These constitute the packet that will be sent.

A packet is made from the encoder output and presented to the decoder. It takes 16 inputs, each a tri-state bit. 1, 0, and -1 with -1 meaning “unknown” as can happen with truncated packets from the satellite. The decoder’s output is 16 tri-state bits (>0 –> 1, == 0 –> 0, < 0 –> -1 unknown) and are mapped to 2x 8-bit sensor readings.

The high order bits on each 8-bit sensor reading are the most valuable. In a corrupted packet, the reward for getting the highest order bit of a sensor reading correct is 128. The second is 64, and on down. In a normal packet, the rewards are 3* the corrupted reward schedule. This does lead successfully to the achieving perfection on bits 0 and 8 first (the MSB of the two sensor readings) and to getting normal packets working before truncated packets (though only slightly). If all test cases are perfectly handled, then the total size of the encoder and decoder is used to drive down the size.

100 random 8-bit pairs are used for each generation in each world. Validation is done with 1000 random pairs and there is strong correlation between generation test scores and validation scores. Testing the full set of 65,536 pairs has not been worth it for validation. Each encoder and decoder pair is given a new set of random test cases with each generation. Each random pair is presented normally (input->encoder->packet->decoder->reward) as well with truncation (input->encoder->packet->set last 8 bits to -1 ->decoder->reward).

Though separate individuals, the final reward score is assigned to both the encoder and decoder, causing them to advance or fail together. This is based on my past experience with CGP protocol simulation that showed very, very, very slow progress when ranking each separately.

The population structure is 1+7. That is, the 1 best individual (or child that is not worse than the parent) is promoted and 7 mutant children created. There is a 1+7 population for encoders and a 1+7 population for decoders.


0 Responses to “KickSat Sprite CGP”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

August 2013
« Jul    

%d bloggers like this: