[Solved] COMP550 Homework 1

Algorithmic Robotics

Please read the honor code and the additions described in the course syllabus. Present your work and your work only. You must explain all of your answers. Answers without explanation will be given no credit.

1. (20 points) Describe two trade-offs between the Bug 1 and Bug 2 algorithms. Limit your response to no more than half a page.
2. (30 points) Suppose you are planning for a point robot in a 2D workspace with polygonal obstacles. The start and goal locations of the robot are given. The visibility graph is defined as follows:
   • The start, goal, and all vertices of the polygonal obstacles compose the vertices of the graph.
   • An edge exists between two vertices of the graph if the straight line segment connecting the vertices does not intersect any obstacle. The boundaries of the obstacles count as edges.

Answer the following questions:

• (15 points) Provide an upper-bound of the time it takes to construct the visibility graph in big-O notation. Give your answer in terms of n, the total number of vertices of the obstacles. Provide a short algorithm in pseudocode to explain your answer. Assume that computing the intersection of two line segments can be done in constant time.
• (15 points) Can you use the visibility graph to plan a path from the start to the goal? If so, explain how and provide or name an algorithm that could be used. Provide an upper-bound of the run-time of this algorithm in big-O notation in terms of n (the number of vertices in the visibility graph) and m (the number of edges of the visibility graph). If not, explain why.

3. (20 points) Let A be a unit disc centered at the origin in a workspace W =R². Assume that A is represented by a single algebraic primitive H = { (x,y) | x²+y² 1 }. Show that if this primitive is rotated about the origin that the transformed primitive is unchanged. This can be shown by showing that any point within the transformed primitive H⁰ must be within H, and vice versa.
4. (30 points) You are given the endpoints to two line segments, A₁B₁ and A₂B₂, in a 2D workspace. The line segments include their endpoints. Provide an algorithm in pseudocode to compute the intersection points of these two line segments, if one exists. Be careful and consider all corner cases. Your algorithm must provide the correct output with every input. Hint: There are many ways to represent line segments. Choosing wisely will allow for a shorter and more efficient implementation.