HW Assignment 2 Solution

We will strictly enforce the following rules, ask questions now if something is unclear.




Guidelines. Students may discuss problems in the assignment. In fact, discussions are encouraged across HW/MP groups. However, each group must write down the answers independently. If discussions are held, one should also note down the people involved in the discussion (this will help especially if multiple groups make identical mistakes). For the written part of the solution, submit as a SINGLE TYPESET PDF (either from latex or converted from a word editing software). You may use scanned hand drawn gures. See course website for the rules on late submissions.




In your submission, name your PDF le as NETID.pdf where NETID is your actual netid. For a group with two people, use NETID1 NETID2.pdf as the name. We do not allow more than two people to form a submission group for this course. To make it exible, we will not use the \group" function on Sakai. Any member of a group can submit. If we receive more than one submission from a group, we will only grade the one with a later timestamp.













Problem 1 [10 points]. In class, we discussed that to do trilateration in 2D, we need three landmarks. However, in practice, we can often use a single tall building (instead of three buildings) to know where we roughly are in a big city. Why is that? Note that you cannot assume the availability of other information, e.g., which direction is north. As a hint, think about a building like the Marina Bay Sands.




Problem 2 [5 points]. Search space size. Recall that the 8-puzzle problem has eight movable pieces and one empty swap cell on a 3 3 game board. What is the size of the state space if six of the pieces are labeled and two are unlabeled? That is, the game pieces can be thought of as being labeled 1; 2; 3; 4; 5; 6; ; . Explain your reasoning.







Problem 3 [15 points]. Uniform-cost and A* searches. The gure on the right provides a graph with associated edge costs and a table with values of a heuristic function. Using the generic search algorithm covered in class (a search node may be truncated if it is known to be suboptimal), manually execute uniform-cost and A searches for a path from S to G. For each search, provide as your answer a search tree (as we have done during in class) and write down the nal solution path with the cost. You may draw your search tree manually and scan them into your document for submission.




Problem 4 [5 points]. Con guration space. We know that a car that runs on a at surface has a three dimensional con guration space R2 S1. What if




A
8
2


4 G
6








B




C
3


1


















State


h(x)
















S




7
















A




6
















B




2
















C




1
















G




0
















the car is running on the surface of the Earth, which may be viewed as a perfect ball? What is the C-space for the car in this case? Provide a brief justi cation of your answer.




Problem 5 [18 points]. DoF in 2D. Exercise 2.9 of Modern Robotics, do only (a), (b), (f).




Show your work.




Problem 6 [12 points]. DoF in 3D. Exercise 2.7 of Modern Robotics. Show your work.




Problem 7 [15 points]. C-space obstacles. Let W be the bounded 2D square region with the bottom left corner being (0; 0) and the top right corner being (10; 10). There are 3 polygonal obstacles whose boundaries are de ned by the following list of points in the clockwise direction:




1. (1; 4); (4; 3); (4; 1),









Page 1 c Jingjin Yu Rutgers University
CS 460/560 HW Assignment 2 Due date: 1:00am










(6; 6); (7; 7); (8; 6); (7; 5),



(2; 8); (4; 8); (4; 7); (2; 7).



Now consider a rectangular (rigid body) robot with width 0:6 and length 0:8 that only translates (i.e., the robot does not rotate) inside W . Answer the following questions.




Compute the free con guration space, Cfree, for the robot when it moves inside W .



Draw W , the obstacles, and the free con guration space Cfree (you may use python to do this or draw it manually) in a gure. Is Cfree connected? If not, how many components (i.e., continuous pieces) does Cfree have?



Provide a collision free path, in the form of a list of points where the path turns, that moves the center of the rectangular robot from xI = (6:5; 2) to xG = (7; 9). That is, the path should be a sequence of straight line segments connecting the xI and xG; the points that you provide are the points where these lines segments meet. Draw your path on the same gure from the previous question.






Problem 8 [20 points]. 2D transformation and collision detection. Let a rigid body be de ned by the polygon formed with points A = (8; 4); B = (10; 6); C = (12; 5); D = (11; 3); E = (9; 2) in the clockwise direction. Apply the transformation that rotates the rigid body by 40 degrees followed by a translation of (3, 4). Provide solution to the following questions.




What is the transformation matrix T ?



Where are the points A{E after the transformation?



Does the transformed rigid body collide with the polygon formed by connecting the points F = (3; 11); G = (9; 12); H = (6; 6); I = (2; 7) in the clockwise direction? If so, which edges of the two bodies intersect?



Suppose another transformation moves the original A to (13; 8) and the original E to (15; 9). What is the transformation matrix T 0 in this case?































































Page 2 c Jingjin Yu Rutgers University