Consider the route finding problem between 2 points in a plane that has convex polygons as obstacles (see figure 1). Find the shortest path. This is an idealistic navigation problem for a robot (e.g. navigating through a museum) 16 points in total 1. Suppose the state space consists of all positions (r, y) on the plane. How many states are there? How many paths are there to the goal? 2 points 2. Explain briefly why the shortest path from one polygon vertex to any other in the scene must consist of straight-line segments joining some of the vertices of the polygons. Define a good state space now. How large is this state space? 2 points] 3. Define the necessary functions to implement the search problem, including a successor 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. (Also think about the neighbors on the same polygon.) Use the straight-line distance for the heuristic function. Figure 1: A scene with random polygonal obstacles. S and G are the start and goal states. See page 114 textbook