24-354 General Robotics
Fall-03. Prof. Howie Choset

        You have 1 hour and 15 minutes to complete the exam.

        Please write all answers either on the exam or in a blue book

        You must attempt all five problems

        Good Luck

Problem #1 (25 points)

(a.) (20 points) Draw the generalized Voronoi diagram for the configuration space for the square shaped robot in the orientation shown.
(b.) (5 points) Draw the shortest path with respect to the L2 metric between the start and goal locations shown.


Problem #2 (25 points)

Given the following workspace (with robot shown at the start configuration) and configuration space for a two link manipulator with no joint limits:

(a.)  (15 points) Plan the shortest path in configuration space from the start configuration to the goal configuration. Draw the path on the figure. Note: Theta 1 is the first joint angle, and Theta 2 is the second joint angle. Neither joint angle has limits.

(b.)  (5 points) Draw five intermediate configurations on the left figure between the start and goal configurations along this path, and show their location in the configuration space, again along the path.

(c.)  (5 points) For the configuration space shown below, indicate the path between start and goal on the figure if it exists.




Problem #3 (25 points)

For the following subproblems, assume that you have a fill function, as outlined below, as well as all of the other vision functions we described in class or implemented in homework, such as threshold, edge detection, etc. If you introduce a new function, be sure to write out a function prototype for it.

void fill(char* image, int x, int y, int replace_value, int color)

The function Ďfillí takes the pointer to an image, an x-y location, and a replace_value which we would like to replace in the image.The function then replaces all of the pixels of replace_value which are contained in the same connected blob as the location x,y with the value color.

(a.)(10 points) Write some psuedo-code that determines whether an image passed to it contains an A, B, and C. Again, when writing out this code be sure to clearly define which "subroutines" you are using. You donít have to explicitly write out the subroutine but you should write the function prototype, such as the one given above for fill. State that you are using it and what it does.


(b.)(10 points) Write some pseudo-code that distinguishes among A, B, C, and D.


(c.)(5 points)Write some pseudo-code that distinguishes among A, B, C, and P.


Problem #4 (15 points)

(a.)    In class, we convolved a mask M with a one-dimensional signal S to detect edges.What was this mask M?


(b.)   Once you have the convolved signal (S*M), how do you detect only the rising edges?i.e. what operation do you perform on the convolved signal (S*M) to determine the rising edges.


(c.)    In the signal shown below, how do you detect the indicated edge? (i.e., what operation do you perform on S*M to determine the indicated edge.


Problem #5(10 points)

Write out a definition for a robot including three key characterics of a robot.