 Background
In 2013, over a dozen
large asteroids similar in size to the object that crashed into
Russia in February 2013 passed near Earth. NearEarth 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
antennas.
NASA's KaBand Object
Observation and Monitoring ("KaBOOM") project plans to use
commercial 12 meter Kaband radar dishes to build large arrays
capable of simultaneously tracking many objects. This raises the
possibility that the detection range for Earthbound 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
capacity required).
Refer to the KaBOOM
official minisite
for more information.
Problem specification
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
necessarily
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 offaxis
radiation that hits signalreceiving equipment.
The rate of the information gained for an asteroid at any moment is
calculated as the power signaltonoise ratio in logarithmic decibel scale.
All antennas
in a subarray receives the reflected signal automatically without you
needing to specify anything. Antennas can transmit and receive
signals simultaneously.
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:
 change transmitting power to p for antenna j at time t
 start to relocate antenna j to asteroid i at time t
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.
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:
 a new asteroid appears
 your command starts to be executed
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:
 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
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.
Asteroids may go below the horizon.
The positions of the asteroids are given relative to the
antenna array. The zaxis points towards the sky in the positive direction. This means that asteroid
positions with negative zvalues 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.
Beamforming
The
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.
Reflection multiplier
Each asteroid i has a reflectivityMultiplier_{i} 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.
Peak gain
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 misstargeting and this is represented by the trajectory
information factor T_{i,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 T_{i,t} will be given later.
Formula
The effective signal power return w_{i,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), subarray_{i,s} are the antennas targeting the
asteroid at time s, subarray_{i,t} is the number of antennas targeting the asteroid at time t,
transmittingPower_{j,s} is the transmitting power of antenna j at time s, and distance_{i,t} is the distance to the
asteroid at time t.
Note that distance_{i,s},
the distance the moment the signal is sent,
is used for calculating t,
while distance_{i,t},
the distance the moment the signal is received,
is used for calculating
w_{i,t}.
Noise
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.
Induced noise
The
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 offaxis. This offaxis radiation
will hit the other antennas signalreceiving equipment and induce
noise into the measurements. The induced noise for a receiving
antenna is the sum of the offaxis radiation power from all other
antennas at the location of the receiving antenna. The offaxis
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 signalreceiving
equipment, α_{j,k,t} is the angle between the peak direction of antenna k and the direction towards antenna j
at time t, d_{j,k} is the distance between antenna j and antenna k, and the function interpolateGain
interpolates the gain bilinearly as described above.
The total noise n_{i,t} associated with a signal received from asteroid i at time t is calculated in the
following way:
where subarray_{i,t} are the antennas targeting the asteroid at time t.
Information rate
The rate of the information gained for an asteroid i at time t is calculated as the
power signaltonoise ratio in logarithmic decibel scale:
Energy consumption
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.
The power
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.
Constraints
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.
Nearfield constraint
Besides inducing noise in other antennas signalreceiving 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.
Score
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, scienceScoreMultiplier_{i} is an asteroid specific constant that represents the importance of
that asteroid, initialImageInformation_{i} 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 I_{i,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 T_{i,t} for an
asteroid i at time t is calculated in the following way:
where
appear_{i} is the time of the first appearance of the asteroid,
initialTrajectoryInformation_{i} 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
trajectory information.
Final score
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.
Implementation
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
is:
 double[] antennaPositions, antenna ground position, formatted as: [X_{0}, Y_{0}, X_{1}, Y_{1}, ...]. 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
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
by two.
asteroidAppearance will be called whenever a new asteroid appears. It provides all information about
the asteroid:
 int asteroidIndex, a unique index
 double scienceScoreMultiplier
 double reflectivityMultiplier
 double initialImageInformation
 double initialTrajectoryInformation
 double[] trajectory, formatted as:
[Time_{0}, X_{0}, Y_{0}, Z_{0},
Time_{1}, X_{1}, Y_{1}, Z_{1}, ...]
The return value from asteroidAppearance will be ignored.
double[] trajectory is ordered, i.e. Time_{n} < Time_{n+1}.
The asteroid position between Time_{n} and Time_{n+1} is (X_{n}, Y_{n}, Z_{n}).
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
Constants
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); halflife: 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
this
file.
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
this
file that specifies the antenna ground positions.
The
reflectivityMultiplier_{i}
and
scienceScoreMultiplier_{i}
for each asteroid i is calculated in the following way:
The initialImageInformation_{i} 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
inclusive.
The first time the asteroid appears is then calculated as max(0, initial start time).
If the first time the asteroid appears is 0,
initialTrajectoryInformation_{i}
is chosen uniformly at random between 0.2 and 4.0, inclusive.
Otherwise, if the first time the asteroid appears is > 0,
initialTrajectoryInformation_{i}
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.
Tools
An offline tester/visualizer is
available
. You can use it to test/debug your solution locally.
100 extra test cases for you to play with offline is provided
here
.
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.
