16-735 Homework 1
Michael Dille
8/29/2007

 

1. Download a software package, develop your own, or use one that you have to draw some obstacles, select two points, and draw a line between them.

I started by defining a simple text representation of maps supporting undiscretized polygonal obstacles: 

[width] [height]
i [initx] [inity]
g [goalx] [goaly]
(repeated for additional goals)
o [vertex1 x] [vertex1 y] ... [vertexn x] [vertexn y]

I then wrote a simple utility to load these maps and display them using the GLUT GL toolkit.

Screenshot:

Source code: Available here

This appears to compile and run fine on linux.andrew.cmu.edu, and should do the same on most other Linux systems. No attempt was made to target other OSes.

 

2. Develop a simple, yet complete, path planning algorithm and be prepared to "implement" it on a person in Wedneday's class.

I'm compromised since I took Howie's General Robotics as an undergrad, so I'll list my favorite simple algorithm, which I believe is Bug2.

  1. Start heading in a straight line towards the goal
  2. When an obstacle is hit, turn right and start following its outline
  3. If you intersect the line between the start and the goal (and you are closer to the goal along this line than you have been before), start following that line again (go to step 1). If the point of first contact with this obstacle is reached, return failure (no path exists).