2. [2+4]Consider the problem of finding the shortest path between two points on

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

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.