Homework6

Michael Edelson

medelson@andrew

I finally caved and switched to pngs instead of jpegs. The image compression was absolutely killing me. Thus, the new input format is based off of previous times, but is a png file. The other difference is obstacles are forced to be convex. They are separated by colors (shades of blue) with a maximum possible of 255 obstacles including the edges of the world (although you could enclose the robot in a triangular world and it should work if you, for some reason, needed 252 other obstacles instead of 251). The only problem with this is that people are terrible at seeing shades of blue, so it’s hard to see where one obstacle ends and another begins when they touch.

Robot Sensing

The robot can see the nearest point on every obstacle in the world. It can see obstructed obstacles as well as obstacles next to it, but it only has distance and angle to obstacle.

Initial Conditions:
The robot starts at the green dot. The graph is simply a dummy head node.

Algorithm:

States:

1 object distinctly closest:

Move away from that object

2 objects distinctly closest (tied for closest)

Travel at the average of the angle of to the two closest points

There is a flag that can be set when departing a node to add 180 degrees to this number so that it may reverse-traverse an edge if necessary
If there is no room to go forward (entering a corner)

Place a node there that is labelled as searched

Flip the 180 degree flag so that the robot travels backwards towards the rest of the graph

3+ objects distinctly closest (tied for closest)

If there’s already a node here, start to the left of the robot’s current heading and find the first unexplored edge to the left.

If there’s no node already there, create one, add it to the graph so that one edge connects to whatever the previous node had been, and store the number of edges at that node

If all immediate edges are searched, it starts a depth-first search on the node, starting with the left-most edge to find a node with an unexplored edge

If all edges are searched

Done!