Log in

No account? Create an account
Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

[ website | composition.al ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

ICFP wrap-up [Jul. 14th, 2008|03:26 pm]
Lindsey Kuper

I'm looking for the shortest path
to the one that you're on.
-- Uncle Tupelo, "The Long Cut"

  • Lines of PLT Scheme: 485
  • Repository commits: 52
  • Pots of coffee consumed: 4
  • Number of computers we used: 4
    • my laptop
    • Alex's laptop
    • Alex's desktop
    • and, for running the LiveCD, a spare Linux box that he had in the closet, which was of course named bombadil1
  • Our totally awesome final results on the sample maps:
    • spiral.wrld:
      • Round 1: crashed into crater; score = 41790
      • Round 2: crashed into crater; score = 43820
      • Round 3: reached home; score = 18970
      • Round 4: crashed into crater; score = 40130
      • Round 5: reached home; score = 16430
    • small-scatter.wrld:
      • Round 1: reached home; score = 26930
      • Round 2: crashed into crater; score = 49870
      • Round 3: crashed into crater; score = 38920
      • Round 4: reached home; score = 22010
      • Round 5: crashed into crater; score = 39450

And here's the README I wrote to submit with our project, which I feel captures the spirit in which we participated:

Our rover has two modes, GO-HOME and EVADE [1], which are implemented as a
stack, CURRENT-STRATEGY. The GO-HOME mode is always the bottom-most item on
the stack. On each iteration through our main loop, the ANYTHING-WORRYING?
predicate examines each of the objects in our view and lets us know if we
should be concerned about any of them. If not, we happily continue toward the
center of the map; if so, we evade the bad stuff using an extremely
sophisticated pathfinding algorithm known as "accelerate and turn left". [2]

As if there were any way in which our rover-controlling software could
possibly be improved, we've also begun to implement a system for storing map
data, so that later runs in a trial can benefit from information gathered
during earlier runs. Implementation of the remaining parts of this system are
left as an exercise for the reader.

 -- Lindsey Kuper and Alex Rudnick (Team K&R)

[1] Which are also our team's preferred two modes of social interaction.

[2] We also find this strategy to be eminently useful at track meets, unless
we're participating in the 100-meter dash or pole vault events.

In all seriousness: This was awesome. Here's what we submitted, minus the revision history. One thing I'm proud of is figuring out that we needed to use atan (although it was Alex who pointed out that we should be using two-argument atan, which is the Scheme name for atan2, apparently). Embarrassingly, even after the code was written, I had to spend a lot of time alone with pencil and paper convincing myself that simple eleventh-grade trigonometry wasn't magic. Another thing I'm proud of is the current-strategy stack, which I implemented by myself during the last couple hours of the contest after Alex went to work. I mean, the strategies themselves are dumb, but by golly, they're on a stack! And Alex did all the work that had to do with collecting and saving information on initial runs to use on later runs of the same map, but sadly, we didn't have time to do anything with that information. It was an awesome idea, though.

Since neither of us are that great at Scheme, we spent a lot of time just looking up stuff, and the PLT docs turned out to be awesome. (This article about networking with PLT Scheme was a big help on the first day, too. Thank you, Shriram Krishnamurthi!) Overall, I had a lot of fun, and can't wait to participate again next year. What we did for the contest didn't have a whole lot to do with what I've been learning from SICP, but it had everything to do with programming and working as a team. Woohoo!

  1. Most guys I know seem to have either a metaphorical or actual Linux-box-named-bombadil in their closet.

From: (Anonymous)
2008-07-14 10:56 pm (UTC)


Next time, you might try complex numbers instead of the trig functions. They're even easier to use for coordinate computations (since you can construct rectangular ones or angle/magnitude ones).

(Reply) (Thread)
[User Picture]From: lindseykuper
2008-07-15 02:02 pm (UTC)

Re: atan

Using complex numbers to represent vectors? I never thought about that. Yeah, that probably would have been easier!
(Reply) (Parent) (Thread)
[User Picture]From: jes5199
2008-07-15 04:09 pm (UTC)

Re: atan

Paul and I managed to remember that this was possible at 1pm on Monday.
Before that point, the two-hour matrix-math session had been considered the most productive part of the contest
(Reply) (Parent) (Thread)
[User Picture]From: pixelherder
2008-07-15 06:27 pm (UTC)

Re: atan

I'd have simply used dot products. Given two vectors, A=[A_x, A_y] and B=[B_x, B_y], the dot product is simply:

A . B = A_x B_x + A_y B_y

Geometrically, however:

A . B = |A| |B| cos theta --- where theta is the angle between the two vectors.

So if A were, say, a unit vector along the current heading, [cos direction, sin direction], and B were a vector towards a target then you could take the dot product of A and B, divide by B's length and test if that was greater than or equal to cos threshold. If so, then A and B point within an angle of threshold of each other. The nice thing about that is that you can just precompute the cosine of the threshold. Then the only slow operation is computing the unit vector for the heading and normalizing B, but those are going to be handy for other calculations too so they're cost is ammortized.

There's other fun stuff with the dot product too. Since cos pi/2 is 0, then the dot product of the current heading with the vector to the target (normalized or not) will be positive if your facing towards it, negative if not, and 0 if you're perpendicular to it. You can easily get the vector to the left of the current heading by swapping x and y and negating x. That will give you [-sin direction, cos direction]. If you take the dot product of this with the vector to a target, then you'll larger positive values the more you need to turn left and smaller negative numbers the more you need to turn right. If the vector towards the target were normalized then 1 would mean hard left and -1 would mean heard right.

You could equivalently express subtracting the current position from the targets position and taking those two dot products as a single 2x2 matrix-vector multiply. That essentially gives you a change of basis to a coordinate system with the rover at the origin and its current heading parallel to an axis.
(Reply) (Parent) (Thread)
From: (Anonymous)
2008-07-16 03:05 am (UTC)

Re: atan

quadratic equations and realtime trig are bullshit unless you have all day, this guy is closer to the mark as far as steering something at mach 2 toward a moving target or using an integer-only microcontroller to drive a real pathfinding algo; pre-computed taqbles and matrix math will get er done
(Reply) (Parent) (Thread)