]

We'll now see a basic application of A* search in the context of everyone's favorite robot, Karel! In our context, Karel has a cookie craving and is trying to reach the cell with the cookie in the fewest number of commands while not entering the lava lake. Karel is hungry and aims to use A* search to optimize the cookie search and needs your help. Note that Karel can only use the following commands: turnLeft(), turnRight(), moveForward().

1. The bottom left cell in the grid shown above is (0,0) in the Cartesian plane. Karel is currently at cell (1,0), is facing East, and wants to reach the cell containing the cookie (facing any direction). We can define C(a,b,d) to be the minimum number of commands Karel needs to reach the cookie starting from cell (a,b) and initially facing direction d. Assume for this part that Karel has an admissible heuristic h(a,b,d). What can we say about how h(1,0,East) compares to C(1,0,East)? A mathematical expression relating h(1,0,East) to C(1,0,East) along with a brief justification.

2. How would we define an admissible heuristic h(a,b,d) for Karel as described in part a? In particular, how could we relax Karel's search problem to define a different cost metric that is always optimistic? Note that Karel always knows the final (cell) position of the cookie.

   A description of a relaxed search problem and a definition of a different cost metric with a justification for why it is always optimistic.