November 1998 Programmer's Challenge

Rendezvous and Docking

Mail solutions to: progchallenge@mactech.com
EXTENDED Due Date: 11:59pm ET, Saturday, 14 November 1998

These are exciting times for space buffs like myself. We’ve been watching the Russian efforts to keep Mir operating, and the visits of the space shuttle to that space station. We’ve watched a variety of planetary gravity assist maneuvers to send the Galileo spacecraft to Jupiter and its moons and the Ulysses spacecraft into polar orbit around the sun. A satellite that did not achieve its intended geostationary orbit is being recovered using innovative gravity assist maneuvers around the moon. And over the next few years, the United States and its international partners will be launching and assembling the International Space Station.

Let’s imagine that NASA has asked the Programmer’s Challenge to develop some efficient software for navigating around the solar system and efficiently completing a rendezvous with another object. The prototype for the code you should write is:

#if defined(__cplusplus)
extern "C" {
#endif

typedef float SimTime;      /* seconds */

typedef struct Vector3D {  /* right-handed coordinate system x-y-z */
  float x;
  float y;
  float z;
} Vector3D;

typedef enum {kDestroyed=0, kShip, kTarget, kOtherMass} BodyType;

typedef struct SimConstants {
  float G;                    /* in Newtons*meters/(kg**2) */
  SimTime minTimeStep;    /* simulation timeStep will be >= minTimeStep */
  SimTime maxTimeStep;    /* simulation timeStep will be <= maxTimeStep */
  float maxAcceleration;  /* meters/(sec**2) */
  float timePenalty;      /* meters/sec per millisecond */
} SimConstants;

typedef struct Body {
  float mass;          /* mass in kg */
  float radius;        /* radius in meters */
  Vector3D  position;  /* position vector in meters */
  Vector3D  velocity;  /* velocity vector in meters/sec */
  BodyType  bodyType;  /* (self explanatory) */
} Body;

pascal void InitSim(
  const SimConstants simConstants,   /* simulation constants */
  const SInt8 numBodies,    /* number of bodies in the simulation */
  const Body theBodies[]    /* parameters of simulation bodies */
);


pascal Boolean AdvanceTime(    /* return TRUE if docking complete or giving up */
  const SimTime timeStep,      /* propagate forward this amount of time */
  Vector3D *shipAcceleration,  /* return ship acceleration vector applied this step */
  Body theBodies[]             /* return body parameters at the end of this time step */
);

#if defined(__cplusplus)
}
#endif

You will be given a number of Body objects moving through space. One of those objects will be a ship under your control, and another will be a target object. The rest will be objects that exert gravitational influences on one another. Your objective is to guide your ship to the target and complete a rendezvous, minimizing a cost formula that depends on the fuel expended by your ship and the time to complete the rendezvous. First, your InitSim routine will be provided with a number of parameters for the problem, and then your AdvanceTime routine will be called repeatedly to propagate all of the objects in our simulated solar system.

In order to be able to score this Challenge, we’ll have to agree on the equations of motion. To the best of my recollection, the equations we will use are the non-relativistic approximations of the versions that govern the real world.

The gravitational force exerted by one object ([j]) on another object ([i]) is given by:

  m[i]*r’’[i] = — G* m[i]*m[j]*(r[i]-r[j]) / |(r[i]-r[j])|**3,

where:

  r[k] is the position vector for object k,
  r’’[k] is the acceleration vector for object k,
  G is the gravitational constant provided in simConstants
  m[k] is the mass of object k
  |v| denotes the magnitude of vector v

The position (r) and velocity (r’) vectors for an object at the end of timeStep t are:

  r’new = r’ + r’’*t
  rnew = r + + r’*t + r’’*(t**2)/2

where

  r, r’ are the position and velocity vectors at the start of the timeStep
  rnew, r’new are the position and velocity vectors at the end of the timeStep
  t is the duration of the timeStep
  r’’ is the vector sum of all gravitational and ship accelerations acting on the object

Your InitSim routine will be given a set of simConstants that govern the simulation, the number of bodies (numBodies) included in the simulation, and a set of characteristics for each simulated Body, including mass, radius, position vector, velocity vector, and the type of body this is. Exactly one Body (kShip) will be your ship and exactly one will be your target (kTarget).

The simConstants will include the gravitational constant G used to propagate objects, the maximum acceleration (vector magnitude) your ship can endure without breaking up, the maximum and minimum time increments to be used for propagation, and a scaling factor used for scoring.

Each time AdvanceTime is called, you should determine the shipAcceleration you want to apply to your ship, compute the gravitational forces of each object on every other object, compute the new position and velocity of each object, and return the shipAcceleration and the updated Body values in parameters provided.

In the event of a collision, where the object spheres intersect, the smaller object is absorbed by the larger object, increasing its mass, and the velocity of the larger object is changed to conserve the momentum vector (mass * velocity). You only need to worry about collisions at the end of a timeStep. If this means that one of your objects passes through another object undetected, we will attribute that to pseudo quantum mechanical uncertainty in our nonrelativistic universe.

To allow longer simulations to complete, it may be necessary to vary the timeStep value used. Each timeStep will be between minTimeStep and maxTimeStep in duration. The timeStep values will be calculated so that they may increase when the largest gravitational force is smaller and your ship is far from the target, and may decrease when one or more of the gravitational forces becomes large, or when your ship comes close to the target.

Our simulated solar system has a few simplifying characteristics compared with the real world. Fortunately, all of the bodies in the system are perfect spheres of uniform density, so the center of mass is exactly at the center of the sphere, allowing gravity to be modeled as if they were point masses. Our ship has the ability to instantly accelerate in any direction, at any magnitude from zero to maxAcceleration. And for our purposes, a rendezvous is considered accomplished when the ship and the target are within 10 ship radii of intersecting, and their relative velocities differ in magnitude by less than 1 meter/sec or .0001 times the velocity of the ship.

The winner will be the solution that successfully completes the rendezvous at the lowest cost. Cost for this Challenge is primarily determined by the amount of fuel your ship uses, calculated as the sum of the magnitudes of the acceleration vectors you apply during each timeStep. In order to keep execution time reasonable, and in the spirit of the Challenge, the score will be incremented by the total amount of execution time spent in your InitSim and AdvanceTime routines, multiplied by a timePenalty scaling factor. I will not know how large to set the timePenalty scaling factor until I see how long the solutions take to execute, but the same timePenalty factor will be used for everyone. My intent is to structure the problems and the timePenalty value so that most solutions complete in minutes or tens of minutes.

All distance, mass, and time values will be in the mks (meters, kilograms, seconds) system.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal.

Questions and answers from the Challenge mailing list are available.

Test code for this Challenge is now available.

You can get a head start on the Challenge by reading the Programmer's Challenge mailing list. It will be posted to the list on or before the 12th of the preceding month. To join, send an email to listserv@listmail.xplain.com with the subject "subscribe challenge-A". You can also join the discussion list by sending a message with the subject "subscribe challenge-D".