Consider the route finding problem between 2 points in a plane that has convex p
ID: 3585413 • Letter: C
Question
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 textbookExplanation / Answer
The state space implemented as Coordinate class
includes the coordinate position, the goal, and predecessor.
This class includes methods to access, the predecessor, test
equality, compute the distance from the goal, and to test if the
state itself is the goal. A class called
CoordinateSuccessorFunction has a method called
getSuccessors. This method will take the current state as input
and return a list of its successors as an arraylist data structure.
Its header is as follows public ArrayList
getSuccessors(Coordinate currentState).
An example of how it works is how to go from the start state
to its successors. The if-statement below accomplishes it:
if(currentState.equals(cord0))
{
//Successors of cord0.
list.add(cord1); list.add(cord2); list.add(cord6);
list.add(cord7);
}
Other states are treated in a similar fashion. The heuristic
function to speed up the search process is in the Coordinate
state class and is implemented as:
public int distFromGoal()
{
int distance = 0;
distance+=Math.sqrt(Math.pow(goal.xposition.x,2)+Math.pow(goal.y
position.y, 2));
return distance;
}