In 2013, over a dozen
large asteroids similar in size to the object that crashed into
Russia in February 2013 passed near Earth. Near-Earth Object ("NEO")
detection and characterization is a critical need for NASA, the US,
and the world as a whole. NASA has been directed to develop
capabilities to observe, track and characterize NEOs and other deep
space objects that could pose a threat to the Earth. As a result,
NASA is developing concepts for a highly capable deep space radar
array consisting of sets of commercially available monolithic
NASA's Ka-Band Object
Observation and Monitoring ("KaBOOM") project plans to use
commercial 12 meter Ka-band radar dishes to build large arrays
capable of simultaneously tracking many objects. This raises the
possibility that the detection range for Earth-bound asteroids can be
inexpensively extended and maintained. One of the challenges faced
by NASA is determining the optimum selection of individual antennas
within the array for a given track observation. This is a complex
analysis and goes directly to development of the concept of
operations and cost of operations (in terms of maintenance and total
Refer to the KaBOOM
for more information.
In this particular
challenge, your task is to optimize the use of an array of radar
dishes when tracking a number of NEOs over a time period. This
tracking allows scientists to gather information from each object
such as imagery and accurate trajectory. The goal is to maximize the
science return over the set of objects in the given time period while
also minimizing the energy consumption.
For each moment in the
time period, you will need to specify which antennas should form a
subarray, and which asteroid each subarray should target. You will
also need to specify the transmitting power of each antenna.
When you relocate an antenna to
a new target, it rapidly slews towards the target with constant angular
velocity. When the antenna reaches the new target, it will continue
to turn at a much lower rate to continue to keep the target in its
beam as it tracks. Also, when the antenna reaches the new target, it
will immediately join any existing subarray targeting that asteroid,
and the output signal power from the subarray will be
updated with the contribution from the new antenna. While an antenna
is slewing to a new target, it does not emit any signal, regardless
of the specified output power. Subarrays also receive the reflected
signal back from the asteroid they are targeting. It takes some time
for the signal to travel back and forth to the asteroid, so it is not
the same antennas transmitting the signal that receives it. The round
trip delay time is two times the distance to the asteroid divided by
the speed of light. The returning signal does not come for free; it
also has some noise that includes background
noise, and noise that is induced from other antennas off-axis
radiation that hits signal-receiving equipment.
The rate of the information gained for an asteroid at any moment is
calculated as the power signal-to-noise ratio in logarithmic decibel scale.
in a subarray receives the reflected signal automatically without you
needing to specify anything. Antennas can transmit and receive
The simulation updates in discrete events.
There is no explicit timer and the simulation is constant between events.
You will need to implement a function that returns your next command.
You can return two kinds of commands:
Changing transmitting power is instantaneous, but relocating an antenna takes some time. If you decide to interrupt the relocation, the antenna will be partially moved. Between each pair of consecutive events, a relocating antenna rotates with constant angular velocity towards its target. If the targeted asteroid happens to move during relocation, the antenna will start rotating towards the new target position until it finally catches up. Once a relocating antenna reaches its target, it will stay in sync with the target.
You can relocate multiple antennas simultaneously.
You can turn an antenna off by relocating to index -1.
- change transmitting power to p for antenna j at time t
- start to relocate antenna j to asteroid i at time t
Your command will be added to a list of events that will eventually
happen. The simulation will then proceed and execute event after
event until one of two things happens:
If a new asteroid appears, your program will be informed, and you will
be requested for a new command. Your previous command will be ignored
in this case so that you have the ability to change your mind
based on the new information.
Otherwise, if no new asteroid appears before your
specified command, the command starts to be executed, and you will be
requested for a new command, and the process repeats.
Besides your commands and new asteroid appearances, there are three other
kinds of events:
- a new asteroid appears
- your command starts to be executed
These events are deterministic and generated automatically by
the simulation. Your program will not be notified about these events,
and they will not interrupt your commands.
Asteroid positions are constant between change position events.
- asteroid i changes position to u at time t
- antenna j is done relocating at time t
- the returned signal from asteroid i changes at time t
Asteroids may go below the horizon.
The positions of the asteroids are given relative to the
antenna array. The z-axis points towards the sky in the positive direction. This means that asteroid
positions with negative z-values are below the horizon and not visible.
If an antenna is tracking an asteroid that is below the horizon it automatically turns
idle and relocates to the place the asteroid will appear over the horizon in the future.
Your score will be integrated over the time period of the simulation
and is determined by the energy you use and the information you gain
about the asteroids.
Effective signal power return
Several factors influcene the effective signal power return. These are:
- distance to the asteroid
- number of antennas transmitting, and their individual transmitting power
- number of antennas receiving the signal
- reflectivity and cross section area of asteroid
- peak gain: power transmitted in peak direction compared to an isotropic source
- how accurate the trajectory information of the object is
Signal power loss due to distance
When a signal propagates through space it spreads over an increasingly large surface, so the power per
unit area decreases quadratically with distance. Once the signal reaches the target and is reflected back,
the process begins again, only now the "transmitting" power is only as much as was available at the
target. So the total power loss for the round trip is proportional to the fourth power of the distance.
combined signal power in a subarray is greater than the sum of their
individual effects. This is because the combined gain in the main
beam direction grows quadratically with the number of antennas. The
gain is multiplied both when transmitting and receiving the signal,
so the round trip signal strength is proportional to the fourth power
of the number of antennas.
Each asteroid i has a reflectivityMultiplieri for the signal strength. This reflection multiplier is constant
for each asteroid througout the simulation and is multiplied with the signal power. This value takes into
account properties such as asteroid cross section area and asteroid reflectivity.
All antennas are identical and have the same characteristics in this contest. The value peakGain is
multiplied with the signal power. This value represents the amount of power transmitted in the direction
of peak radiation to that of an isotropic source.
Accurate trajectory information
The complete trajectory of an asteroid will be given to you the first moment the asteroid appears. This
trajectory is not very accurate, but can be used for calculating values such as distance and when the
asteroid goes beyond the horizon etc. However, when aiming the antennas towards an asteroid, very
accurate trajectory information is needed because the subarray has a very focused beam. There will be
some loss in the returned signal power due to miss-targeting and this is represented by the trajectory
information factor Ti,t for asteroid i at time t. This value change over time depending on how much you
track the object and has an upper bound of 1. The formula for Ti,t will be given later.
The effective signal power return wi,t for an asteroid i at time t is calculated in the following way:
where s is the time the signal was sent, T_MIN represents the capability to aim the antennas based on
general information (possibly received from other sources), subarrayi,s are the antennas targeting the
asteroid at time s, |subarrayi,t| is the number of antennas targeting the asteroid at time t,
transmittingPowerj,s is the transmitting power of antenna j at time s, and distancei,t is the distance to the
asteroid at time t.
Note that distancei,s,
the distance the moment the signal is sent,
is used for calculating t,
the distance the moment the signal is received,
is used for calculating
The returned signal is associated with noise n that includes background noise and induced noise on
each of the receiving antennas. Each source of noise is uncorrelated, so their power sum simply summate. The
background noise is constant in this contest, and is added for each receiving antenna.
antennas in this contest have parabolic reflectors that are designed
to produce very focused beams in the direction of the dish axis, but
some of the power will be radiated off-axis. This off-axis radiation
will hit the other antennas signal-receiving equipment and induce
noise into the measurements. The induced noise for a receiving
antenna is the sum of the off-axis radiation power from all other
antennas at the location of the receiving antenna. The off-axis
radiation power is a function of the distance from the antenna, and
the angle from the peak direction. The radiation power decreases
quadratically with distance. The gain for different angles from peak
direction will be given as a numerical array. The first entry in the
array represents the angle 0°, i.e. peak direction, and the last
entry represents the angle 180°, i.e. the opposite of peak
direction. The other entries represents angles that are spread out
linearly over the array. Two such arrays will be given that are
generated for two different distances: the minimum and maximum
distance between any pair of antennas in the testcase. The gain for
distances between these values are calculated by interpolating these
arrays linearly. Similarly, the gain for angles between entries in
the array should also be interpolated linearly.
The peak direction of the receiving antenna
does not affect the induced noise.
The induced noise for a receiving antenna j at
time t is calculated in the following way:
where SHIELDING_MULTIPLIER represents the electromagnetic shielding of the signal-receiving
equipment, αj,k,t is the angle between the peak direction of antenna k and the direction towards antenna j
at time t, dj,k is the distance between antenna j and antenna k, and the function interpolateGain
interpolates the gain bilinearly as described above.
The total noise ni,t associated with a signal received from asteroid i at time t is calculated in the
where subarrayi,t are the antennas targeting the asteroid at time t.
The rate of the information gained for an asteroid i at time t is calculated as the
power signal-to-noise ratio in logarithmic decibel scale:
The antennas consume energy when they are operating.
The power consumption for an antenna is the
transmitting power when tracking a target,
or the power RELOCATE_POWER necessary to slew the antenna dish
when relocating to a new target.
required to rotate the dish while following a target is ignored in this contest.
The total energy consumption is the integral of the antenna
powers over the simulation time.
If you violate any of the following constraints your score will be zero for the test case.
Constraints are only checked when time passes between events, they are not checked between
events scheduled for the exact same time. This means that you can safely return a command
with the exact same time t as an asteroid position change, i.e. you don't need to return
a time t ± eps to ensure that your command is executed before/after the asteroid position
change to avoid breaking a constraint.
Besides inducing noise in other antennas signal-receiving equipment, the radiation emitted from
antennas might actually cause physical damage to other antennas if the peak direction of the beam
comes too close to another antenna. This is modeled as a geometrical constraint, where the ray in the
peak direction of the beam is not allowed to come closer than a certain safety radius
ANTENNA_SAFE_RADIUS to another antenna.
This constraint only applies when the antenna is transmitting.
An antenna is transmitting if it satisfies the following conditions:
- it is on, i.e. targeted asteroid index ≠ -1
- transmitting power > 0
- it is not currently relocating
- the targeted asteroid is above the horizon
Target proximity constraint
Subarrays are not allowed to simultaneously target objects where the synthesized beam from one
subarray intersects another targeted object. A subarray with few elements will have a wider beam
width. The minimum allowed angle (in radians) between two tracked targets a and b is:
where CRITICAL_ANGLE is a constant.
Maximum transmitting power
The antennas have an individual maximum transmitting power of MAX_TRANSMITTING_POWER.
If you try setting the transmitting power above this you break the constraint.
The score is the sum of the science return over the set of asteroids minus the total energy used. The
science return for an asteroid is the trajectory knowledge score plus the image knowledge score. These
knowledge score values are calculated as functions of the information rate over time.
Image knowledge score
The image knowledge score for an asteroid i at time t is calculated in the following way:
where IMAGE_SCORE_MULTIPLIER is a constant that represents the importance of image
information, scienceScoreMultiplieri is an asteroid specific constant that represents the importance of
that asteroid, initialImageInformationi is the initial image information about the asteroid at the first
appearance, Q_IMAGE is a constant that
determines how much information is needed
to get an image of good quality,
and Ii,s is the information rate for asteroid i at time s.
Trajectory knowledge score
The trajectory information of an asteroid decays over time. The trajectory information Ti,t for an
asteroid i at time t is calculated in the following way:
appeari is the time of the first appearance of the asteroid,
initialTrajectoryInformationi is the initial trajectory information about the asteroid at the first
appearance, Q_TRAJECTORY is a constant that
determines how much information is needed
to get accurate trajectory information,
and Q_LOST is a constant that
determines how slow
we lose track of objects.
The trajectory knowledge score for an asteroid i at time t is calculated in the following way:
where TRAJECTORY_SCORE_MULTIPLIER is a constant that represents the importance of
Your final score for the test case will be:
where SIMULATION_TIME is the end of the simulation time period.
If you were not able to complete the simulation (due to time limit, memory limit, crash, invalid return
value, etc.), then your score for the test case will be 0.
If your score is negative, it is reset to 0.
Your total score is the average of your scores on all test cases.
You will need to implement three methods, initialize, asteroidAppearance and nextCommand.
initialize will be called only once and before all other calls. It serves to provide your solution with
information about the test case, including antenna positions, antenna parameters, etc. The complete list
The return value from initialize will be ignored.
The initial directions of the antennas are straight up, i.e. towards (X, Y, Z) = (0, 0, 1).
The length of minDistanceGain will always equal the length of maxDistanceGain.
The number of antennas in the test case can be calculated by dividing the length of antennaPositions
- double antennaPositions, antenna ground position, formatted as: [X0, Y0, X1, Y1, ...]. The Z coordinate is 0 for all antennas.
- double peakGain, the peak gain for a single antenna
- double minDistanceGain, gain values generated for min distance between antennas
- double maxDistanceGain, gain values generated for max distance between antennas
asteroidAppearance will be called whenever a new asteroid appears. It provides all information about
The return value from asteroidAppearance will be ignored.
double trajectory is ordered, i.e. Timen < Timen+1.
The asteroid position between Timen and Timen+1 is (Xn, Yn, Zn).
- int asteroidIndex, a unique index
- double scienceScoreMultiplier
- double reflectivityMultiplier
- double initialImageInformation
- double initialTrajectoryInformation
- double trajectory, formatted as:
[Time0, X0, Y0, Z0,
Time1, X1, Y1, Z1, ...]
nextCommand will be called repeatedly until the end of simulation.
It provides the current time and you should return a string that
specifies your command. It can be one of the two following formats:
Your command should satisfy:
- time ≥ current time
- 0 ≤ antennaIndex < number of antennas
- 0 ≤ new transmit power ≤ MAX_TRANSMITTING_POWER
- new asteroid index must have appeared
Here is a list with all constants used in this problem:
- SPEED_OF_LIGHT = 299792458
- MAX_TRANSMITTING_POWER = 40000; 40 kW
- BACKGROUND_NOISE = 10-30
- SHIELDING_MULTIPLIER = 10-27
- RELOCATE_SPEED = π / (10 * 60); 10 min to relocate 180°
- RELOCATE_POWER = 5000; 5 kW
- SIMULATION_TIME = 7 * 24 * 60 * 60; 7 days
- T_MIN = 0.1
- CRITICAL_TRACKING_ANGLE = π / (180 * 60); 1 arc minute
- ANTENNA_SAFE_RADIUS = 11; 11 meters
- Q_LOST = (24 * 60 * 60) / log(2); half-life: 24h
- Q_TRAJECTORY = 6000
- Q_IMAGE = 1 000 000
- IMAGE_SCORE_MULTIPLIER = 30
- TRAJECTORY_SCORE_MULTIPLIER = 60 / SIMULATION_TIME
Test case generation
Each test case is generated using the same algorithm, but with a different seed for the random number generator.
The algorithm is described in this section.
First, the number of asteroids is chosen. It is chosen uniformly between 25 and 75, inclusive.
A random subset with that many elements is then selected from
The first column is asteroid designation and the second column is
asteroid absolute magnitude.
Next, a starting day between year 2000 and year 2020, inclusive, is chosen
uniformly at random.
The geocentric positions for the asteroid subset over a week is then calculated using
Minor Planet Ephemeris Service
with 3 minutes intervals from the starting day.
These geocentric positions are then converted so that they are relative to the antenna array origin.
The antenna array origin at the starting day is located at latitude 28.524812° longitude 0°,
and rotates one revolution around the Earth's axis in exactly 24 hours.
Next, the number of antennas are chosen uniformly at random between 8 and 20, inclusive.
A random subset with that many elements is then selected from
file that specifies the antenna ground positions.
for each asteroid i is calculated in the following way:
The initialImageInformationi is chosen
uniformly at random between 0 and 0.1.
An initial start time is then chosen uniformly at random for
each asteroid between
-0.3 · SIMULATION_TIME and SIMULATION_TIME
The first time the asteroid appears is then calculated as max(0, initial start time).
If the first time the asteroid appears is 0,
is chosen uniformly at random between 0.2 and 4.0, inclusive.
Otherwise, if the first time the asteroid appears is > 0,
is chosen uniformly at random between 0.2 and 0.4, inclusive.
The asteroid index is simply the index in the subset, between 0 and
number of asteroids - 1, inclusive.
The values peakGain, minDistanceGain and maxDistanceGain
are generated using a complex formula, but you can expect very similar
characteristics in the system test cases.
An offline tester/visualizer is
. You can use it to test/debug your solution locally.
100 extra test cases for you to play with offline is provided
You are encouraged to check the source code for exact implementation of the simulation and score calculation.
Feel free to use the simulator code in your solution.