Nov 98 Prog Challenge
Volume Number: 14
Issue Number: 11
Column Tag: Programmer's Challenge
Nov 98 Challenge
by Bob Boonstra, Westford, MA
Rendezvous and Docking
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)
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 */
float mass; /* mass in kg */
float radius; /* radius in meters */
Vector3D position; /* position vector in meters */
Vector3D velocity; /* velocity vector in meters */
BodyType bodyType; /* (self explanatory) */
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
• 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