Printable Version of this PageHome PageRecent ChangesSearchSign In

The Drunken Sailor

This page is still under construction, pictures are coming.

My first 7001 mini-project...
Here's the assignment: main.pdf
Here's my report: The Drunken Sailor.doc, The Drunken Sailor.pdf, html version will be up soon.

Read my report, and then watch these videos (requires DivX5, I think). (Unfortunately, the mencoder DivX encoder created a few corrupt frames in a few of the videos. I want to use some other codec instead (especially since all of my frames are extremely RLE-compressible, but I haven't been successful in using any other codec yet.)
A* with goal estimation (sailor3)A* with goal estimation (sailor3 detailed)The other algorithm (sailor5)
Test1sailor3-test1-3fps.avisailor3-expand-nodes-test1-30fps.avioutput-sailor5-test1.log.avi
Test2sailor3-test2-3fps.avisailor3-expand-nodes-test2-30fps.avioutput-sailor5-test2.log.avi
Arkintrapsailor3-arkintrap-3fps.avisailor3-expand-nodes-arkintrap-30fps.avioutput-sailor5-arkintrap.log.avi
Intranetersailor3-intraneter-3fps.avisailor3-expand-nodes-intraneter-30fps.avioutput-sailor5-intraneter1.log.avi

In the "A* with goal estimation" videos, you are looking at the agent's internal map of the world. The red square is the agent, white represents a barrier, blue represents the general goal heading the agent was given, yellow represents the area which could contain the goal, and the green square is the estimated goal, it's just the center of the yellow area. The black area spaces is assumed to be empty. As the agent moves around, the possible goal area is narrowed thanks to new information supplied by the compass.

In the "(detailed)" videos, all of the above applies, but there are also little green lines. These represents the A* tree as it's being expanded. When it expands into the yellow area (potential goal area) the search ends and the agents makes its move.

In the other algorithm, the agent doesn't keep track of all the different barriers; there is no internal map. There's one in the video, but that's just for your benefit. Again, the red square represents the agent. This time the little green lines mean the agent is checking to see if that direction is blocked off. If it's not blocked off, it will move there.

The agent starts by moving in the direction of the goal heading until it reaches an obstacle, then it tries to circumnavigate the obstacle (either clockwise or counterclockwise, randomly) until it is closer to the ship than the point it encountered the obstacle. When you watch the video, you'll see that when it encounters an obstacle, a blue area will light up. That area is the agent's definition of "closer to the ship than the point it encountered the obstacle". It will move along the edge of the obstacle until it enters that blue area, and then it will continue moving in the direction of the goal heading.

Misc videos of failed algorithms:
sailor2-test1-lost-goal-3fps.aviSailor2 (predecessor to sailor3) uses a +/- 22.5 degree angle around the approximate goal heading to triangulate the estimated goal location (sailor3 uses +/- 45 degrees). As you can see here though, +/- 22.5 degrees was too restricted, and all potential goal nodes (yellow area) are eliminated by the last frame; movement ceases at that point.
output-sailor4-reversed-test2.log.aviSailor4 (predecessor to sailor5) chooses before it begins whether it will be trying to circumnavigate obstacles by moving clockwise or by moving counterclockwise (sailor5 chooses randomly each time it encounters an obstacle). This video shows an example where sailor4 will loop forever. For reference, here's an exceptionally lucky run of Sailor5 (random choices) on the same map: output-sailor5-reversed-test2.log.avi

Last modified 7 December 2012 at 12:04 pm by arya