2. [2+4]Consider the problem of finding the shortest path between two points on
ID: 3724800 • Letter: 2
Question
2. [2+4]Consider the problem of finding the shortest path between two points on a plane that has convex polygonal obstacles as shown in Figure below. a) Suppose the state space consists of all positions (x,y) in the plane. How many states are there? How many paths are there to the goal? b) 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?Explanation / Answer
ANSWER:
x * y possible states. Infinite because you can have loops
Because the shortest distance between two points is a straight line, so the shortest distance between two points with an obstacle.
in the way is to wrap the path as close to a straight lines around those obstacles as possible.
A good state space is therefore the points along the polygons plus the start and goal as all moves will involve starting at ending on one of these points.
State Space = sum(Polygon Perimeters) + 2.
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;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.