Helicopters (7000 points)

It's 2010, it's Challenge 24, and it's time for a Networked Game! This time, it's about helicopters.

Our location is a small section of a little blue-green planet. This section is about 250 square kilometers, and happens to be conveniently bordered by an insanely high mountain chain (called the Edge Mountain). It has hills, valleys, rivers, cows, but above all, helipads.

The local people are an industrious sort, and have a lot of cargo to deliver to their fellow citizens. The preferred kind of transportation uses computer controlled helicopters - and it's your task to write the AI.

The Setup

Each team has three helicopters to control. Helicopters are controlled through TCP connections (a separate connection for each helicopter), using a text-based protocol. The helicopters will send sensor information and act on control input at a rate of 10 Hz.

Each helicopter is equipped with a range of sensors:

Helicopters are controlled through four primary control inputs:

The Pitch and Roll inputs are together called the Cyclic. There is a hidden fifth input, the Throttle, but this is a modern type of helicopter, and the engine is controlled automatically.

For physical calculations, you can model the body of the helicopter as a brick (cuboid) that is 12 meters long, 3.43 meters wide and tall. Its center of mass is shifted from the middle, by 1.715 meters towards the nose. The main rotor disc has a radius of 5.14 meters, and has its center point 1.767 meters above the center of mass.

Each team has a bank account. Fuel purchases and other costs will be deducted from this account, while prizes for successful cargo deliveries will be added to it. Teams have infinite credit, so you can go in the red as deeply as you want...

The video feed from the video camera of each helicopter may be watched on the stream server (URL specified outside this document). One team can watch only one of their three helicopter cameras at once.

Scoring

Throughout the 24 hours, the game is divided into six 4 hours long campaigns. In each campaign, teams begin with their bank accounts reset to 0 (however, no other stats - like map exploration percentage, number of deliveries etc. - are reset). At the end of each campaign, teams are ordered by how much money they have. Each team gets a final score depending on its place on this list (base score), multiplied by the campaign factor.

This means that at the end of 24 hours, a team's final score is calculated as: 11.111*(B1 * F1 + B2 * F2 + B3 * F3 + B4 * F4 + B5 * F5 + B6 * F6), where Bn is the base score the team achieved during campaign n and Fn is the factor of campaign (see the tables below).

In case of a tie, the points for the first shared rank are used (e.g. if the 2nd, 3rd, 4th places are tied, all three teams get points for being the 2nd; the 5th placed team gets points for being the 5th).

If in a campaign a team ends up with a non-positive amount of money, they get 0 points for the campaign, regardless of their placement.

rank at the end of the campaign base score
1st 100
2nd 80
3rd 66
4th..30th 52-(rank-4)*2
campaign number starts at campaign factor
1 9:00, Sat 0.2
2 13:00, Sat 0.4
3 17:00, Sat 0.6
4 21:00, Sat 0.8
5 01:00, Sun 1
6 05:00, Sun 1.5

This means the maximum score a team can get from making a lot of money is (about) 5000 points.

There are some other ways of getting more points:

This means, the grand total achievable score, adding up score for campaigns (5000), intro missions (1000) and achievements (1000) is 7000 points.

Helipads

These are the places where the helicopters can land. (It may be possible to land elsewhere on the terrain, but such a landing will receive none of the benefits of helipads.)

Each helicopter begins stationary on a helipad. Should a helicopter crash, it will be moved to the nearest unoccupied helipad (after being restored to full operation - fortunately this is a pretty fast process, and takes the whole of 1 second).

Landed helicopters are refueled automatically (at a certain cost per fuel unit, which is removed from the team's bank account).

Cargo deliveries are available at certain helipads. Helicopters can take the cargo, then deliver it to the destination, which is always another helipad. Landing on the destination helipad will deliver the cargo, and automatically award the delivery prize.

Crashing

You will crash a lot, so it's useful to be aware how it exactly works.

There are three ways a helicopter can crash:

Note that this list doesn't include such things as falling on the ground very fast, or maneuvering your helicopter's body into the main rotor disc of another helicopter. These things are absolutely harmless. (Destroying a helicopter of an enemy team in such a way is counted as a frag, and is even awarded with a little money.)

It is theoretically possible (if very difficult) to get stuck without crashing (e.g. by landing sideways on the edge of a cliff). In such cases, ask the organizers so they may reset your helicopter by a friendly smiting from the skies.

Crashing incurs a certain cost. More importantly, the cargo on the crashed helicopter is lost as well.

The Terrain

The world is described through a three-dimensional coordinate system. From smaller to larger values, the X coordinate goes from west to east; the Y coordinate goes from south to north; and the Z coordinate goes from the water level upwards. The measurement unit is the meter.

The world around the helicopters consists of the terrain and a few objects (such as helipads). The layout of the world is initially unknown; controlled helicopters will notify you of the things they see through their sensors.

The terrain can be modelled as a height field, where the water level is 0 (and everything at level 0 is water). Terrain is divided into 32x32 meter sectors. For each sector, the helicopter will report height lines and any objects it sees.

Height lines are lines given using beginning and ending X, Y coordinate pairs, and a Z height. They give the contours of a certain height level of the terrain (that is, the terrain that lays under the given line segment has the constant height Z). They're not guaranteed to form closed polygons. However, height lines have a "direction": looking from the beginning towards the end, on the right side of the line the terrain will be higher, on the left side it will be lower.

Note that the height lines are just a representation of the terrain, not the terrain itself. It is not guaranteed that there are no higher points near a height line of a certain level, for example. It might be a good idea to keep a flight clearance of at least the difference between the levels of the two highest height line levels of the given sector.

Objects are static (unmoving) things in the world. They are modelled as cylinders, perpendicular to the X, Y plane. Objects are always given by their X, Y, Z coordinates (identifying the center point of the top disc of the cylinder), and the radius of the cylinder. The bottom of the cylinder touches the underlying terrain.

Deliveries

There is a constantly changing pool of available delivery jobs. All teams see the same pool, and helicopters from any team can take available jobs. A taken delivery job will disappear from the pool immediately, and won't reappear (no matter if it's delivered successfully or not).

Each delivery job has the following properties:

To complete a delivery, a helicopter has to land on the source helipad, take the selected job, then fly to the destination helipad and land on it. One helicopter can take only one job at a time.

There are longer deliveries than the fuel tank on the helicopters can last. In this case, the helicopter will have to land on a helipad somewhere between for refueling.

The weight of cargo differs by cargo type (but is otherwise unknown). Some types of cargo may make your helicopter noticeably heavier.

Delivery prizes depend on multiple things: the kind of cargo, the deadline, but most importantly, the distance. It is much more difficult to take cargo on long distances, but the rewards are higher too.

Intro Missions

Controlling the helicopters through a complete delivery job is a challenging task. There are three easier practice tasks each team can do for extra points. Each mission can be tried any number of times, free of cost, but each team can complete one only once.

Each mission is done by a single helicopter, starting from a landed position (on any helipad). Missions are started by issuing an explicit command.

Helicopter Control

Helicopters will use the last set of four controls they received through their corresponding TCP connection. Each control is given as a floating point number. A typical AI will wait for a 10 Hz update, calculate new controls, and reply with the new controls right away.

For the purpose of explaining the controls, we'll use a local coordinate system for a helicopter: the X axis points towards the nose, the Y axis to the left, and the Z axis up.

The first control is the collective. It results in an upward force (a push towards the direction of the main rotor). The control input has to be between [0 .. 13].

The second control is the pitch. It produces a torque around the Y axis. A positive value will make the helicopter lean forward: push the nose down and the tail up. The control input has to be between [-1 .. 1].

The third control is the roll. It produces a torque around the X axis. A positive value will make the helicopter bank right (turn around the forward axis clockwise). The control input has to be between [-1 .. 1].

The fourth control is the pedal. It controls the force produced by the tail rotor. A positive value will push the tail to the right (and thus the nose will tend to look left). The control input has to be between [-1 .. 1].

Control Protocol

In general, the control protocol is line based.

Unless otherwise indicated, all sent data fields are floating point numbers.

If a data field has a string type, the string never contains whitespace, and there are no quotes around it.

Each sent line (in either direction) consists of one or more words (strings or numbers), separated by single spaces, ending with a single unix newline.

Control Protocol: Authentication

After a TCP connection is made to the helicopter control server, the team has to log in by sending their team password on a single line. The server will reply with either of:

ERROR invalid password
(and will close the connection), or:
OK choose helicopter (1..3)

After the "OK" answer, the client has to send the number of the helicopter it wishes to control (1 or 2 or 3), on a single line. One helicopter can have only one open control connection at a time.

After a successful authentication, the server will begin to send updates.

Control Protocol Summary

Server to Client

 POS x y z V vx vy vz QUAT qx qy qz qw FUEL fuel
 CRASH
 RADAR type dx dy dz
 PROXI type dx dy dz V vx vy vz QUAT qx qy qz qw
 TAKEOFF
 LANDING
 SECTOR sx sy heightlines objects
 HL z x1 y1 z2 y2
 OBJ type x y z r
 JOB id deadline cargo fx fy fz tx ty tz cost prize timeout
 TAKEN id
 TIMEOUT id
 FAIL
 WIN
 NOCARGO
 CARGO id deadline cargo fx fy fz tx ty tz cost prize
 FREESTYLE
 MISSION 1 tx ty tz
 MISSION 2 tx ty tz
 MISSION 3 tx ty tz countdown
 ACCOMPLISHED

Client to Server

 collective pitch roll pedal
 TAKE id
 JETTISON
 MISSION number
 FREESTYLE

Control Protocol: Server to Client: Helicopter

The server sends updates at 10 Hz. Each such update consists of 0 or more "optional" lines, and a single POS line at the end, which is always sent.

POS x y z V vx vy vz QUAT qx qy qz qw FUEL fuel

Again, the POS line is always sent as the final line of a 10 Hz update - so a client update of the controls should follow.

Lines below in this section are all "optional" lines.

CRASH

The helicopter is in a crashed state. It will remain so for a few cycles (the CRASH line will always be sent in these cycles). Control input is ignored for crashed helicopters.

RADAR type dx dy dz

Detection report from the long range radar. Such a report will be sent for each detected helicopter once a second.

PROXI type dx dy dz V vx vy vz QUAT qx qy qz qw

Detection report from the battle (proximity) radar. Such a report will be sent for each detected helicopter in every cycle.

The long range and battle radars are independent. If a helicopter is in range for the battle radar, long range reports will still be sent once a second.

The proximity radar can track up to 8 helicopters at once.

TAKEOFF

The helicopter is now in flight.

LANDING

The helicopter has landed on a helipad successfully. At the beginning of a control connection, either TAKEOFF or LANDING will be sent, as part of the first report.

Control Protocol: Server to Client: Sector Description

SECTOR sx sy heightlines objects

This line begins a world sector description report. These reports are sent when the helicopter first sees a terrain sector since the beginning of the control connection - thus, for each connection and each sector, the report will be sent only once.

All data fields are integers.

A sector description report consists of:

HL or OBJ lines are never sent outside a sector description report. Other report lines are never mixed in sector description reports.

Sector descriptions stay constant for the duration of the contest (so reports for the same sectors should be identical).

HL z x1 y1 z2 y2
This is a height line or contour line, as part of a sector description.
OBJ type x y z r
This is a static, unmoving object, as part of a sector description.

Control Protocol: Server to Client: Delivery

JOB id deadline cargo fx fy fz tx ty tz cost prize timeout

A new delivery job is available. On a new connection, such a line will be sent for all currently available jobs as part of the first report.

TAKEN id

A delivery job has been taken, and is no longer available.

TIMEOUT id

A delivery job has timed out, and is no longer available.

FAIL

The controlled helicopter has failed the delivery job (because of a timeout, or maybe because it crashed).

WIN

The controlled helicopter has completed the delivery successfully.

NOCARGO

The helicopter is not carrying any cargo.

CARGO id deadline cargo fx fy fz tx ty tz cost prize

The helicopter is carrying cargo. id identifies the delivery job. All given data is just like with the JOB line.

At the beginning of the control connection, either CARGO or NOCARGO will be sent, as part of the first report.

Control Protocol: Server to Client: Intro Missions

FREESTYLE

The helicopter has no active mission.

MISSION 1 tx ty tz

Intro mission 1 is active.

MISSION 2 tx ty tz

Intro mission 2 is active.

MISSION 3 tx ty tz countdown

Intro mission 3 is active.

ACCOMPLISHED

The helicopter has accomplished the selected intro mission.

Control Protocol: Client to Server

Helicopter controls are updated on sent control lines. When the client sends no control line in a cycle, the controls stay in the previous position, except on a crash or disconnect (after which all controls are reset to zero).

collective pitch roll pedal

Sending four numbers on a line updates the helicopter controls.

TAKE id

Take on a delivery job.

The controlled helicopter has to have no onboard cargo, and has to be landed on the proper helipad. If the job is taken successfully, the proper updates will be sent on the next cycle (i.e. CARGO and TAKEN).

JETTISON

Drop current cargo. The delivery job is failed and the cargo is lost.

MISSION number

Try intro mission.

The helicopter has to be landed on a helipad. If the mission is started successfully, a MISSION line will be sent on the next cycle.

FREESTYLE

Abort current intro mission.

Note that for each 0.1s cycle, only the last of the given TAKE, JETTISON, MISSION, FREESTYLE commands is processed (although this shouldn't cause problems in normal operation).

Appendix: Quaternions

In the coordinate system of the helicopter the X axis points forward, the Y axis to the left and the Z axis up.

The orientation of the helicopter with respect to the world coordinate system is represented by a unit quaternion qx qy qz qw. (The quaternion (qx,qy,qz) = sin(alpha/2) u, qw = cos(alpha/2) represents the rotation, where u is the unit length rotation axis and alpha is the rotation angle).

Formulas for calculating the roll, pitch and yaw angles of the helicopter from a quaternion:

roll = atan2(2*(qw*qx + qy*qz), 1-2*(qx*qx + qy*qy))
pitch = asin(2*(qw*qy - qx*qz))
yaw = atan2(2*(qw*qz + qx*qy), 1-2*(qy*qy + qz*qz))

Formulas for rotating a vector v = (vx,vy,vz) from the helicopter coordinate system to the world coordinate system:

t1 =  qw*qx
t2 =  qw*qy
t3 =  qw*qz
t4 = -qx*qx
t5 =  qx*qy
t6 =  qx*qz
t7 = -qy*qy
t8 =  qy*qz
t9 = -qz*qz
rotvx = 2*((t7 + t9)*vx + (t5 - t3)*vy + (t6 + t2)*vz) + vx
rotvy = 2*((t5 + t3)*vx + (t4 + t9)*vy + (t8 - t1)*vz) + vy
rotvz = 2*((t6 - t2)*vx + (t8 + t1)*vy + (t4 + t7)*vz) + vz

For example if v = (1,0,0) then rotv is the forward pointing unit vector in the world coordinate system.

The inverse rotation of a quaternion is -qx -qy -qz qw.

Appendix: Flight Dynamics

The helicopter is modelled through a rigid body. The forces applied to the body are gravity, profile drag, rotor blade drag and the control input forces.

In order to fly a helicopter one should master hovering first: keeping the helicopter at a given position in a stable way.

Starting from a helipad in a straight position, after increasing the lifting force above the helicopter weight using the collective, it will take off.

The rotor blades have some drag so the helicopter will start rotating slowly (yaw angle will increase), which can be compensated by the tail rotor using the pedal. (A small control input is enough, no need to apply full thrust). The pedal input can be used to keep the helicopter looking at a specific direction, or to turn to another direction.

The tail rotor applies a horizontal force at the tail so the helicopter will drift sideways slowly if you try to keep the direction in hovering.

Sideways or forward drift can be compensated by increasing the roll or pitch angles a bit. Note that the control inputs are mapped to torques (or forces), so they control the acceleration not the exact angle (or position). Once the helicopter is leaning to some direction the main rotor no longer points exactly upwards so it starts pulling the helicopter sideways.

To maneuver the helicopter locally, only small control inputs are needed (except the collective which should approximately compensate the helicopter weight), and small angle changes are enough.

To move forward a longer distance, first direct the helicopter toward the destination, then increase the pitch angle and the lifting force together: the upward component of the lifting force should compensate the weight, the forward pointing component will accelerate the helicopter in forward flight.

The speed of the helicopter is limited by the profile drag force, which increases about the square of the velocity and points to the opposite direction of the velocity. The helicopter shape is streamlined in such a way that when moving forward the drag is less than when moving sideways.

Fuel consumption is a complicated function of the control inputs and the current state. See the following figures:
fuel consumption in vertical climb
fuel consumption in forward level flight

Appendix: Flight Control

For those who have no idea how to approach the helicopter motion control problem we give a hint. This is not guaranteed to be the best solution though.

If the position x should be kept at some required value r and the control input is the acceleration (or force) a, then a simple PD controller is sufficient. At each iteration the control input is calculated as

e = r - x
delta_e = e - prev_e
prev_e = e

a = kp*e + kd*delta_e

for some non-negative kp and kd constants.

e is the error term, delta_e is the error change rate. Since r is fixed delta_e can be replaced by the change rate of -x, which is -velocity (in case the velocity is already known).

For example such a controller is enough to keep the helicopter at a given angle around the z axis using the pedal input. Of course the pedal control affects other parts of the dynamics as well, not just the yaw angle, but if the side effects are small, then this simple approach might work.