Figure 2 Polygon 1: ((220, 616), (220, 666), (251, 670), (272, 647) Polygon 2: ((341, 655), (359, 667), (374, 651), (366, 577) Polygon 3: ((3 I 1,530), (311, 559), (339, 578). (361,560). (361, 528), (336.516)) Polygon 4: ((105, 628),. (151, 670). (180, 629), (156, 577), (113, 587) Polygon 5: ((118, 517), (245, 517), (245, 577), (118, 557)) Polygon 6: ((280, 583), (333, 583), (333, 665). (280, 665) Polygon 7: ((252, 594), (290, 562), (264, 538)) Polygon 8: ((198, 635). (217, 574), (182, 574) Note: This figure is for illustration purpose only. Positions of the polygons inside the figure may not reflect their actual coordinates. 1) Suppose the state space (i.e., a set of possible locations for the robot) consists of all possible positions (x, y) in the plane. How many possi ble states are there? How many paths are there to the goal? Provide assumptions for your answer. [10 points] 2) Based on your solution for question 1), can you find a better (and reasonable) state space for the problem? If the answer is yes, how large is the state space? If the answer is no, provide tifications why you think this is a good state space to implement your searching algorithm. [10 points] 3) Implement an algorithm to find the shortest path from the start node to the end node using an A* (A-star) heuristic search. Use the straight-line distance to the end node as a heuristic function. Show your pseudo code for this algorithm. Is this an admissible heuristic function? Why why not? [15 points] or Hint: Define the necessary functions to implement the search problem. This should include a function that takes a vertex as input and returns the set of vertices that can be reached in a straight line from the given vertex. You may need to implement a function that detects whether or not two line segments intersect. The problem can be solved using shortest path algorithms but you are required to use A* 4) Present the solutions for the following pair of starting algorithm you implemented. Show the optimal path. [15 points] point and ending point using the A* Start: (115, 655) End: (380, 560) 5) Is it possible to solve the problem using a breadth-first or a depth-first search algorithm? If the answer is yes, briefly discuss your solutions. Otherwise please explain. [10 points]