- Introduction
- TODO:
- Members (this year)
- Languages
- How we did
- Internal representation
- Path finding
- Avoiding Martians
- Sockets
- Parsing
- Main loop
- Graphics
- Tools we used
- Other teams
- Discussion
Introduction
This page documents the participation of the team FUN in the ICFP programming contest 2008.
This is an early draft ... document in progress.
This year we had a very nice task : control a rover on a simulated map and lead it to a goal while avoiding obstacles and moving objects (Martians).
TODO:
- Add information about the control of the rover
- Spell check and check grammar
Members (this year)
- Andrés Felipe Calderón
- Juan Manuel Caicedo
- Luis Felipe Carvajal
- Nelson Castillo (Weblog post about the contest).
- Yoda
In previous years the team was distributed. This year we all were in Bogotá, Colombia.
This year we met IRL and it helped a lot with communication. This is the first time we do this. Before we would mostly communicate using IRC.
This year we worked as a team and we all contributed to the final solution.
Languages
We used Python (with psyco in the live CD) and C++.
How we did
We didn't do very well but we had a lot of fun. We managed to send a very simple blind submission for the lightening round that tries to reach the goal. We also sent an improved version for the final submission that computes paths.
This is a video of how we did in a simple world (simple-small.wrld).
Another video of the same world.
The solution is not deterministic due to network latency mostly. This year we had a real-time task.
We didn't do well in more complex maps. But we tried! :-) This a more complex map (small-scatter.wrld) and its internal representation. The internal representations will be explained later in this document.
Another complex map (spiral.wrld) and its internal representation.
Internal representation
For the internal representation of the problem we used a graph made with the help of a Voronoi diagram that we update whenever we get to see new objects in the map.
The centroid of every triangle obtained with the Voronoi algorithm is a vertex. This was a mistake. Let us explain ourselves with two images and a video.
Note: The images are not really correct because we operate in the triangles that Voronoi algorithm gives us and not using the center of the objects, but they illustrate our point very well. In short: we shouldn't have ignored the radius of the objects.
What we did:
Notice that the node of the graph (red) leads as to a path(blue) that crashes with an object. Our algorithm ignored the radius of the objects. This was a serious bug.
This is what we should have done. Not difficult at all:
Add a vertex to the graph for each segment of the triangle or better the centroid of the red points! That way we would have gotten better path.
Now the video (we have shown similar videos before in this document).
We used this implementation fom Python with a wrapper done with swig.
Path finding
We used the Dijkstra's algorithm over the graph formed by the centroids of the triangles obtained with the Voronoi algorithm. We used some optimizations but still we consider silly paths.
We used this implementation for Dijkstra. It uses this neat implementation for a priority dictionary (Is there a more recent/better implementation out there for Python?).
Since our control wasn't working very well we decide we wouldn't consider paths when they were too narrow. We don't know if this was a wise choice.
Avoiding Martians
Were there Martians? We ignored them! :-)
We thought of having more resolution (like in finite element analysis (img)) and put Martians there temporally for each update, but we noticed we couldn't complete this on time so we decided we wouldn't implement this.
Sockets
We had no issue with sockets. Here's our implementation for the TCP/IP communication.
class Listener:
def __init__(self, host, port):
self.sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
self.sock.connect((host, port))
self.sock.setsockopt(socket.SOL_TCP, socket.TCP_NODELAY, 0)
self.hold = ''
self.ASKSIZE = 8182
def command(self, cmd):
try:
self.sock.send(cmd + ';');
except:
do_exit_program()
def getmessage(self):
""" gets one message, notice how we might leave something in self.hold """
msg = self.hold
del_idx = msg.find(';');
while del_idx == -1:
try:
chunk = self.sock.recv(self.ASKSIZE)
except:
do_exit_program()
if chunk == '':
raise RuntimeError, "socket connection broken"
msg += chunk
del_idx = chunk.rfind(';') # rfind!
del_idx = msg.find(';'); # get the (first) position of the separator
self.hold = msg[del_idx + 1:]
return msg[0:del_idx + 1]
Parsing
class Parser:
def parse(self, line):
global mars_rover
global mars_map
global mars_engine
action = line[0]
#initialization
if action == 'I':
#['500.000', '500.000', '30000', '30.000', '60.000', '20.000', '20.0', '60.0', ';']
dx, dy, time_limit, min_sensor, max_sensor, max_speed, max_turn, max_hard_turn = \
map(float, line[1:-1].split())
mars_map = Map.Map(dx, dy)
mars_rover = Map.Rover(min, max_sensor, max_speed, max_turn, max_hard_turn)
parser.add_object(mars_rover)
mars_engine = Engine.Engine(mars_map)
# Ok, this should not be here :-)
def add_simple(arr):
o = Map.map_element()
if o.parse(arr):
print >> sys.stderr, "error parsing object"
sys.exit(1)
parser.add_object(o)
add_simple(['h', 0.0, 0.0, 5]) # adding home.
for x in [-dx/2.0, dx/2.0]:
for y in [-dy/2.0, dy/2.0]:
add_simple(['b', x, y, 0.01])
if PYGAME:
canvas.setup(dx,dy)
#Telemetry
elif action == 'T':
tele = line[1:-1].split()
timestamp, vehicle_ctl = tele[:2]
tele = tele[2:]
vehicle_x, vehicle_y, vehicle_dir, vehicle_speed = map(float, tele[:4])
#mars_rover.vehicle_ctl = vehicle_ctl
mars_rover.update(vehicle_x, vehicle_y, 0.5, vehicle_dir, vehicle_speed)
telemetry_lock.acquire()
# The telemetry! Let's add it to a queue for other thread.
telemetry_queue.appendleft(tele[4:]) # parsing these objects is easy
telemetry_lock.release()
if mars_engine != None:
mars_engine.update (float(timestamp))
#Bounce against obstacle
elif action == 'B':
pass
#print >> sys.stderr, 'bounce!'
elif action == 'K':
print >> sys.stderr, 'killed!'
elif action == 'C':
print >> sys.stderr, 'we fell!'
if action == 'E':
print >> sys.stderr, 'finished, setting goal!'
mars_engine.initial_goal()
The rest of the parsing was in another thread. We did in in case that computing a route take us longer than we can afford. Some code is in C and I don't know if Python will allow the other thread (previous code) to do something while we're busy in C. I think Python will not do it. We didn't try big maps...
We used dequeue (an efficient queue for python) for communication between the threads.
# inside of a loop with busy waiting (While True, time.sleep(..), etc).
tele = []
telemetry_lock.acquire()
while len(telemetry_queue):
tele += telemetry_queue.pop()
telemetry_lock.release()
mars_map.remove_martians()
has_new = False
while len(tele):
o = Map.map_element()
tele = o.parse(tele) # parsing objects is easy once you have the array
if parser.add_object(o):
has_new = True
if has_new:
path_graph.solve(mars_map)
Main loop
# A thread is started before this main funcion
if __name__ == '__main__':
if len(sys.argv) != 3:
print ('Usage: %s hostname port' % sys.argv[0])
sys.exit(1)
listener = Listener(sys.argv[1], int(sys.argv[2]))
parser = Parser()
while True:
msg = listener.getmessage()
parser.parse(msg)
if mars_engine!= None:
cmd = mars_engine.get_command()
listener.command(cmd)
Graphics
We used pygame to draw our internal representation of the world. We had some source code available that we could reuse very fast.
Tools we used
- Python + Psyco JIT.
- Pygame for graphics.
- GCC, an excellent C/C++ compiler.
- swig - to make python wrappers for C++ libraries.
- Subversion.
- IRC, wich we used to coordinate (not all the time).
- We all used the GNU/Linux OS.
- We used QEMU (with kqemu) and KVM to test that the submission ran on the Live CD.
Other teams
Check this page for a (still growing) list of writeups and resources from other teams.
https://projects.cecs.pdx.edu/~jgmorris/icfpc08/index.cgi/wiki/TeamPages
Discussion
- Use the discussion tab if you wish to write some feedback. Thanks.
Last update: 2008-07-20 (Rev 14401)