Description
Robot moves towards a source of heat placed at the exit of a maze:
It explores the maze using a heat range finder it’s equipped with.
Traversing on the left side and then on the right side of the maze the robot has built a map of the maze.
Special points have been labeled: A (entrance), M (exit), C, E, F, G, H, J, L, N, B, D, I, K (internal points
where a choice can be made as to which direction to go)
Each point has been assigned a straight-line-distance (SLD) value with respect to M
(1) Sketch a search tree representing the maze
(2) What kind of search is implemented during the left (right) side traverse?
(3) Describe and illustrate a greedy algorithm for finding the exit
(4) Develop and illustrate an A* algorithm for finding the exit
Note: Assumed SLD values are based on relative positions of the points
Submit to Beachboard by Oct. 30.
B
F
A
E
D
C
G
H
J
I K
N M
L