Links

git: link

coursework document: link

Description

The Informatics Large Practical course is entirely based on coursework. The task changes every year but the overall theme stays the same. This year the task brief was:

"The task for the Informatics Large Practical is to program an autonomous drone which will collect readings from air quality sensors distributed around an urban geographical area as part of a (fictitious) research project to analyse urban air quality. The research project which is collecting and analysing the air quality readings is beginning with a small-scale feasibility study around the University of Edinburgh’s Central Area. If this feasibility study is successful, the researchers will apply for funding to conduct their research on a much larger scale, collecting and analysing air quality readings all across the city of Edinburgh."

The design requirements can be summarised as:

  • Earth is approximated as flat (i.e. coordinates treated as points on a plane)
  • Drone can collect sensor data from a range of 0.0002 degrees
  • Given list of 33 sensors (out of 99 total) in the Edinburgh area from an API (this gives you the reading and battery values, the drone would read), produce flight path instructions for that day as well as a visualisation of the flight and readings in GeoJSON format
  • Sensors have battery readings available, if battery is too low (under 10%) then reading is to be falsy
  • Drone must not leave its confinement area (a square round the university)
  • Drone must not collide with any buildings, provided as outlines via the API
  • Drone must come back to the initial location (or as close as possible)
  • Drone has a limited number of 'moves', only 150 straight line segments of length 0.0003 degrees
  • The drone can only turn in a multiple of 10 degrees (each node on the map has 36 neighbours)

As well as some other minor details regarding the formats of the output and formalities regarding the way the drone must move.

Solution

My entire report can be found here:

Informatics Large Practical - Solution Report

As a tl;dr:

  • I created 4 java modules: client, visualisation, simulation, pathfinding
  • The client abstracted away the way the data was provided from the API
  • The visualisation module dealt with the mapping the output of the 'simulation' to the given output formats
  • The pathfinding module dealt with general pathfinding problems as well as TSP problems
  • Finally the simulation module contained the 'business logic' for this particular problem and combined all the other modules

Neighbour Node Generation

Pretty much all the other algorithms required some sort of transition function from any node on the graph to its neighbours, which dealt with collisions with both obstacles and the confinement area. I used a sneaky little data structure: Bounding Volume Hierarchy to be precise, which essentially progressively divides space in a tree like manner (on the longest axis looking at the inner AABB's midpoints) and divides the AABB's inside it into left and right subtrees again and again until reaching just a single AABB at each leaf node. This lets me do O(log n) queries for checking if a node collides with anything on the map (n being the possible colliding AABB's number)

BVH.jpeg

TSP

I used the Nearest Insertion Heuristic together with 2-opt post-optimisation too get close to optimal TSP solutions (at most 2 times the optimal solution length)

Nearest Insertion Algorithm.png

Pathfinding

Pathfinding proved to be a little tricky purely due to the sheer volume of nodes needing to be checked. At first I employed an A* tree search, which worked fine if the heuristic was relaxed by at least a factor of 1.5 (otherwise it would just hang), this lead to less optimal solutions but at least allowed for reasonably quick solutions. This was still a little slow so I implemented spatial hashing (using a modified cantor hash) to try and prune the nodes which we've already visited before (approximately). This introduced floating point value problems, which I dealt with by cantering coordinates around the centre of the confinement area as opposed to using raw earthly coordinates.

Pathfinding Algorithm.png

Path segmenting

The output format of the flight path requires that for each segment the drone:

  1. Start at a point
  2. Choose a direction,
  3. Move in that direction
  4. Only then read a sensor

This also means that each segment can only be tied to reading a single sensor, due to the way pathfinding works, this can lead to some paths requiring additional moves to be inserted to satisfy those constraints.

Say we go through all of the nodes that A* put on the goal path one-by-one, imagine sliding it like sliding a window over the connected points and always calling the first point P and the second N.

a valid segment then is one like P -> N where P does not 'read' any sensors and N reads at most one sensor. However we can have situations where P reads one or more sensors and where N reads more than one sensor. (A point is said to read a sensor when it is the last one on the path from the previous sensor to this one).

I deal with those situations by making the drone move in a random direction and back, or if just dealing with one 'reading' by shifting the reading from an P point to an overlapping N point (since at every slide we overlap P and N points constantly).

This is visualised below:

segmentation of path.png

The orange and blue P/N boxes symbolize positions of the 'window' and the green boxes symbolize sensor readings at the given point.

Results

I run this algorithm 35000 times on different data, and found that the limit of moves was never exceeded, in fact no path took more than 111 moves and the average was 90 +- 6.7, with average execution times standing at 103ms. Really solid!

When it comes to my mark, I got a 100% in the first part of the coursework and 89% in the second, with an overall 92% grade (loosing marks only in the report part of the coursework).

I say that's a win!