Consider the problem of finding the shortest path between two points on a plane that has convex polygonal obstacles as shown in the above diagram. This is an idealization of the problem that a robot has to sole to navigate in a crowded environment.
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?
c. Can you suggest an admissible heuristic for A* search?

d. Show in the figure the first two levels of states of a beam search with k=3.

Want an answer?

No answer yet. Submit this
question to the community.