Figure 7 shows a robot navigation field, where the red square (d2) is the robot, and green square (b7) is the goal. The shade squares (such as b2, c2, etc.) are obstacles. The robot is not allowed to move in diagonal line. Please use best first search to find the path from d2 to b7 (Using Manhattan distance as the heuristic function)

• Report nodes in the fringe (including their f(N) values), in the orders they are included in the fringe (Using table format showing below. Add rows if needed) [0.5]
• Report the order of the nodes being expanded. [0.5]
• Report the final path from d2 to b7. [0.5]

Add more rows, if needed

Fringe	Node visited/expanded

 

Transcribed Image Text:

a1 b1 c1 d1 e1 a2 a3 b2 b3 a4 c2 c3 c4 e2 b4b5 b6 b b7 d2 d3 d4 a5 a6 a7 c5 d5 c6 c7 d6 e3 e4 e5 e6 d7 a8 ag b8 c8 c9 d8 b9 e7 e8 d9 eg a1 b1 c1 d1 e1 a2 a3 b2 b3 a4 c2 c3 c4 e2 b4b5 b6 b b7 d2 d3 d4 a5 a6 a7 c5 d5 c6 c7 d6 e3 e4 e5 e6 d7 a8 ag b8 c8 c9 d8 b9 e7 e8 d9 eg