ICTSA Programming Competition 2011

I decided to take part in the ICTSA programming competition, which is renowned for having challenging problems to solve, along with a friend of mine. The problem that was released this year (described in full at the competition site) involved a robot that could traverse a map, containing different altitude values. The aim of the problem was to create a route for the robot to follow, maximizing the area of the map taken by photographs, while minimizing the energy costs encountered by traversing the map.

We approached the problem in a number of different ways, such as optimization algorithms and evolutionary algorithms (including genetic algorithms, harmony search, simulated annealing and others). We also considered decision trees, mimicking the way IBM’s Deep Blue played chess, by looking forward and considering each step. Other algorithms that we considered included Bresenham’s Line Algorithm and Bresenham’s Circle Algorithm (for the photography range and the line of sight algorithm), as well as the use of quadtrees.

Designing a circle algorithm

We decided on the fact that due to the constraints of the problem (such as energy requirements), we couldn’t necessarily generate a random path and evolve it, since the chosen path might not be valid. Generating a valid path on the fly seemed a much better way to handle the problem.

The first step we took was to determine statistics of the map while parsing the map file. This would allow us to determine which altitudes were more common on the map. The statistics were stored in a SortedDictionary.

The second step we took was dividing the map into quarters. We then divided these sections into quarters, and then repeated this step a third time. This allowed us to consider map segments instead of the whole map. Each segment, which we called clusters, had their own form of statistics. We then used these statistics to decide which segment the robot should visit first.

From the robot’s point of view, the procedure was as follows:

  1. Determine the area that has been successfully photographed.
    • This was done by using a variant of Bresenham’s Circle Algorithm, and a variant of Bresenham’s Line Algorithm.
  2. Determine which cluster the robot is located in.
    • This was done easily by comparing the robot’s location to the limits of the cluster.
  3. Determine which clusters are nearby.
    • This was done by recursively travelling through the nodes in the quadtree to find the adjacent clusters (to the north, south, west or east of the robot’s current cluster).
  4. Take a decision on which cluster to travel to.
    • Since we had access to certain statistics for each cluster (such as average altitude, minimum altitude, maximum altitude and area already photographed), we could calculate which cluster was the best cluster to travel to.
  5. Try out 5 moves in the chosen direction
    • If for example, the chosen cluster was the cluster to the North, the robot would try out NNNNN as its chosen path string. The energy requirement to calculate this test string would be considered, and if the energy requirement was too high, the first character in the string would be replaced with an X (a rest and gain energy command) and the process repeated. If however, the whole test string would result in 5 Xs, the robot would take the next best direction.
  6. Add the moves to the total command list, move the robot and repeat the procedure

There are several other things I learnt from this competition:

  • Get a working version up and running as soon as possible
    • We only started coding on Sunday morning, as we spent more time designing the solution to the problem and considering different approaches. After talking to several other competitors after the end of the competition, I realized that some had working versions by Saturday morning! That meant that they had an advantage of a whole day.
  • Avoid optimizing too early
    • Again, we spent more time considering how to optimize our program, rather than trying to pump out a working solution as soon as possible. We should have spent Sunday optimizing an already existing program, not beginning to write our code.

All in all, I thoroughly enjoyed taking part in this competition, and would gladly accept more challenges.

m4s0n501

Leave a Reply