July 15, 2008 at 21:08ICFP 2008 report: team ryba
Inspired by many other Adept reports, we participated in ICFP 2007 and ended up in 4th place. Impressions from last year were the most positive and this year we gathered again, though in a slightly different composition. This time, we also had a lot of fun and coped with the task as a whole, it remains to wait for the conference and find out a little good :)
From left to right: adaptive grid, path graph, trajectories An
excellent introduction for those who do not know what the International Conference on Functional Programming Contest is, how it goes and what task this year was
A little about the team.
Team ryba ICFP 2008 crew (in alphabetical order :)
Mike Aizatsky
Alexey Gopachenko
Maxim Mossienko
Roman Shevchenko
We all are of the opinion that the best tool is a proven one that you own the best. It just so happened that for us it is Java, so the question of choosing a language did not arise, especially taking into account the experience of ICFP 2007.
Like last year, Roma gathered us. Personally, I prepared very thoroughly - I slept 15 hours before the very beginning%) Based on the results of the last time, the correct conclusions were made and we agreed to try to work no more than 8 hours a day - and if possible all at the same time. The place was also chosen verified - JetBrains office. Everyone except Mike used their workstations under WinXP, later on each one worked VMWare Server with LiveCD. Mike used his Mac Book Pro and native server as soon as it became available. Development Environment - of course IntelliJ IDEA.
Throughout the competition, Roma monitored the competition website, mailing list and compliance with formalities (scripts, packaging, performance checks and sending results). He also downloaded and checked LiveCD in advance and prepared the Subversion repository for the project.
As soon as the task was published, we plunged into reading for 10 minutes.
The results of the following five-minute brainstorming at the blackboard:
Mike knows exactly how to search for a path on a map and immediately proceeds
to make everything move as quickly as possible to
write and link components: incoming / outgoing messages, world model, search for a route, taxiing, visualization
you need a simple server simulator - because it is not known when the organizers will post it
Mike's solution involved constructing a graph of possible paths and finding the shortest using Dijkstra's algorithm . The graph is built on the centers of the grid cells, which is obtained by adaptive recursive division into quadrants%) Writing and checking (using graph paper and a pen :) Mike took all this for an hour or two.
Meanwhile, Max quickly writes a protocol, starting with the most needed objects for Telemetry, Obstacle, etc. Romka - by visualizing how the rover sees the world, I started loading maps with an eye to server implementation. In order not to waste time and not burden the project too much, I used the code from www.json.org/java. Pretty quickly, we reached the goal: I uploaded a map, built a representation of the world in the basic objects written by Max, and Romka painted all this for us. There is no server yet and this is our only way to see the map. We regret to see that the sample cards are very simple and very similar, and even with the same parameters for the rovers and Martians.
Now Mike can test subdivision and search for a way on real maps. The best way to quickly evaluate the work of tessellation is visual and Mike appends the corresponding pieces of code to our visualizer. At this moment, for the first time, we see something like the one pictured above. You can see right away that the search is working correctly, you only need to adjust the detail and achieve maximum performance. Having received food for thought (and more convenient tools), Mike again dives his code.
Just when I was bracing myself to simulate physics, a model server became available. Max was just ready to network code, we picked up a LiveCD and saw the creeping Martians. Having looked at how everything works, we decided that we would not need our simulator. Very on time :)
I quickly sketched a “naive” duty cycle, 1 telemetry => 1 command (Accelerate Directly). We start it and enchantedly observe on the server how the rover quickly rolls forward, bounces off walls and stones.
We conclude that physics is quite reasonable, and Martians are surprisingly dumb. Nevertheless, as planned, we include all visible Martians in the graph as a "temporary" obstacle.
Meanwhile, 6 hours have passed since the start of the competition. We agreed to sleep well and start tomorrow at 15:00 and dispersed.
At the end of the day we can:
connect to the server and disassemble the message flow
stupidly crawl forward :)
divide the map into a grid of passable / forbidden zones (for simplicity, we now describe squares around obstacles)
build the shortest path on the map, including any mazes
Having appeared first, I proceed to the arrival itself - I listen to telemetry, I update the internal map and the status of the rover. After that, I turn on the calculation of the path on the current map from the current position of the rover to the telemetry processing cycle. I see that my (very powerful) machine does not have time "in real time" and latency is accumulating. Given the fact that Mike immediately warned that the calculation would seriously accelerate, I decided not to pay attention to it.
I’m watching a map gradually appear on the client, Martians are passing by. We process the end of the round and the score. For some time, we observe how Martians rush onto the rover one by one and almost always miss if it moves. Romka continues to work on visualization.
Then I came up with a way to significantly increase the development comfort under Windows - start the server in a loop: while true; do server map.wrld; done - this way you could simply start the client at any time and watch the work without being distracted by the server console. Later I added svn up there and got the opportunity to conveniently and quickly change the map.
Max comes and we decide that it's time to learn to steer. Here we find that we completely forgot trigonometry :( I will not describe this shame ... In general, while we reread the definition of elementary trigonometric functions, late Mike appeared and saved everyone with the help of a pseudo-scalar product of vectors :) Moreover, it turns out he spent all morning optimizing his code and came already with a new search for the way.
As soon as we put all the parts together, the rover immediately began to reach the base very successfully. Sometimes they could not cope with the management, because did not take into account the variable latency of the telecontrol system.
we took into account our problems with telemetry calculation
took into account the fact that the server can send an outdated steering position
By 22:00 we got quite stable results on test cards, and after fine tuning and checking under LiveCD we sent a code to ligntning round.
For an hour or two we played with the code and discussed what and how to improve, and finally forced ourselves to go to rest.
Latency, optimization
Yes, because of our schedule, we got 4 days :) That day we were three of us - Mike could not join us.
First, we decided to throw the Martians off the path search map. Since they always missed at high speed (which is no wonder) We decided that we would go along the road and dodge at the last moment. This allowed recalculating the path only if new objects became visible.
Tuning
Max - speedfinding
Yes, the task was very different from previous years, but we found it interesting enough. Yes, the preparation clearly let us down, but specifically our team did not meet any obstacles. Although it would be more convenient to get a server under win, albeit without graphics. I really didn’t like the fact that there was little test data and a complete lack of an official way to evaluate your success ...
Cool
colocation
graph
There
stable module interfaces
statistics of tuning results
switching to other strategies
Team reports on the official projects.cecs.pdx.edu/~jgmorris/icfpc08/index.cgi/wiki/TeamPages wiki
article habrahabr.ru/blog/icfpc/46589.html
From left to right: adaptive grid, path graph, trajectories An
excellent introduction for those who do not know what the International Conference on Functional Programming Contest is, how it goes and what task this year was
A little about the team.
Team ryba ICFP 2008 crew (in alphabetical order :)
Mike Aizatsky
Alexey Gopachenko
Maxim Mossienko
Roman Shevchenko
We all are of the opinion that the best tool is a proven one that you own the best. It just so happened that for us it is Java, so the question of choosing a language did not arise, especially taking into account the experience of ICFP 2007.
Like last year, Roma gathered us. Personally, I prepared very thoroughly - I slept 15 hours before the very beginning%) Based on the results of the last time, the correct conclusions were made and we agreed to try to work no more than 8 hours a day - and if possible all at the same time. The place was also chosen verified - JetBrains office. Everyone except Mike used their workstations under WinXP, later on each one worked VMWare Server with LiveCD. Mike used his Mac Book Pro and native server as soon as it became available. Development Environment - of course IntelliJ IDEA.
Day One (Friday 23:00 - Saturday 04:30)
Throughout the competition, Roma monitored the competition website, mailing list and compliance with formalities (scripts, packaging, performance checks and sending results). He also downloaded and checked LiveCD in advance and prepared the Subversion repository for the project.
As soon as the task was published, we plunged into reading for 10 minutes.
The results of the following five-minute brainstorming at the blackboard:
Mike knows exactly how to search for a path on a map and immediately proceeds
to make everything move as quickly as possible to
write and link components: incoming / outgoing messages, world model, search for a route, taxiing, visualization
you need a simple server simulator - because it is not known when the organizers will post it
Mike's solution involved constructing a graph of possible paths and finding the shortest using Dijkstra's algorithm . The graph is built on the centers of the grid cells, which is obtained by adaptive recursive division into quadrants%) Writing and checking (using graph paper and a pen :) Mike took all this for an hour or two.
Meanwhile, Max quickly writes a protocol, starting with the most needed objects for Telemetry, Obstacle, etc. Romka - by visualizing how the rover sees the world, I started loading maps with an eye to server implementation. In order not to waste time and not burden the project too much, I used the code from www.json.org/java. Pretty quickly, we reached the goal: I uploaded a map, built a representation of the world in the basic objects written by Max, and Romka painted all this for us. There is no server yet and this is our only way to see the map. We regret to see that the sample cards are very simple and very similar, and even with the same parameters for the rovers and Martians.
Now Mike can test subdivision and search for a way on real maps. The best way to quickly evaluate the work of tessellation is visual and Mike appends the corresponding pieces of code to our visualizer. At this moment, for the first time, we see something like the one pictured above. You can see right away that the search is working correctly, you only need to adjust the detail and achieve maximum performance. Having received food for thought (and more convenient tools), Mike again dives his code.
Just when I was bracing myself to simulate physics, a model server became available. Max was just ready to network code, we picked up a LiveCD and saw the creeping Martians. Having looked at how everything works, we decided that we would not need our simulator. Very on time :)
I quickly sketched a “naive” duty cycle, 1 telemetry => 1 command (Accelerate Directly). We start it and enchantedly observe on the server how the rover quickly rolls forward, bounces off walls and stones.
We conclude that physics is quite reasonable, and Martians are surprisingly dumb. Nevertheless, as planned, we include all visible Martians in the graph as a "temporary" obstacle.
Meanwhile, 6 hours have passed since the start of the competition. We agreed to sleep well and start tomorrow at 15:00 and dispersed.
At the end of the day we can:
connect to the server and disassemble the message flow
stupidly crawl forward :)
divide the map into a grid of passable / forbidden zones (for simplicity, we now describe squares around obstacles)
build the shortest path on the map, including any mazes
Day Two (Saturday 16:00 - Sunday 03:00), Lightening round
Having appeared first, I proceed to the arrival itself - I listen to telemetry, I update the internal map and the status of the rover. After that, I turn on the calculation of the path on the current map from the current position of the rover to the telemetry processing cycle. I see that my (very powerful) machine does not have time "in real time" and latency is accumulating. Given the fact that Mike immediately warned that the calculation would seriously accelerate, I decided not to pay attention to it.
I’m watching a map gradually appear on the client, Martians are passing by. We process the end of the round and the score. For some time, we observe how Martians rush onto the rover one by one and almost always miss if it moves. Romka continues to work on visualization.
Then I came up with a way to significantly increase the development comfort under Windows - start the server in a loop: while true; do server map.wrld; done - this way you could simply start the client at any time and watch the work without being distracted by the server console. Later I added svn up there and got the opportunity to conveniently and quickly change the map.
Max comes and we decide that it's time to learn to steer. Here we find that we completely forgot trigonometry :( I will not describe this shame ... In general, while we reread the definition of elementary trigonometric functions, late Mike appeared and saved everyone with the help of a pseudo-scalar product of vectors :) Moreover, it turns out he spent all morning optimizing his code and came already with a new search for the way.
As soon as we put all the parts together, the rover immediately began to reach the base very successfully. Sometimes they could not cope with the management, because did not take into account the variable latency of the telecontrol system.
we took into account our problems with telemetry calculation
took into account the fact that the server can send an outdated steering position
By 22:00 we got quite stable results on test cards, and after fine tuning and checking under LiveCD we sent a code to ligntning round.
For an hour or two we played with the code and discussed what and how to improve, and finally forced ourselves to go to rest.
Day Three (Sunday 16:00 - Monday 03:00)
Latency, optimization
Day Four (Monday 13:00 - 23:00)
Yes, because of our schedule, we got 4 days :) That day we were three of us - Mike could not join us.
First, we decided to throw the Martians off the path search map. Since they always missed at high speed (which is no wonder) We decided that we would go along the road and dodge at the last moment. This allowed recalculating the path only if new objects became visible.
Tuning
Max - speedfinding
Conclusion
Yes, the task was very different from previous years, but we found it interesting enough. Yes, the preparation clearly let us down, but specifically our team did not meet any obstacles. Although it would be more convenient to get a server under win, albeit without graphics. I really didn’t like the fact that there was little test data and a complete lack of an official way to evaluate your success ...
Cool
colocation
graph
There
stable module interfaces
statistics of tuning results
switching to other strategies
Links
Team reports on the official projects.cecs.pdx.edu/~jgmorris/icfpc08/index.cgi/wiki/TeamPages wiki
article habrahabr.ru/blog/icfpc/46589.html