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
- Sketch a search tree representing the maze
- What kind of search is implemented during the left (right) side traverse?
- Describe and illustrate a greedy algorithm for finding the exit
- Develop and illustrate an A* algorithm for finding the exit
Note: Assumed SLD values are based on relative positions of the points
