Problem 3. Heuristics for Informed Search [15 Points] A delivery robot is moving in an nm maze. A simple version of the maze is shown in the figure. The robot is programmed to deliver multiple parcels to their destinations. Each parcel starts at some node in the maze and has its own delivery destination. The initial position of the parcels is shown in the figure, and the number on each parcel is its target destination. At every step the robot can take one of the following actions: - Move: Move in one of these directions: { Up, Right, Down, Left } - Pick: Pick-up a parcel in a location - Drop: Put down a parcel at a location. The cost of each move action is 1 , and the costs of Pick and Drop are zero. The robot starts at square number 1 and can move through dotted lines - but the solid lines represent walls. The robot wants to deliver all parcels to their destinations with minimal cost. Note that multiple parcels can be placed at the same square. You might come up with different ways of addressing these questions; For each part, there might be several possible heuristic functions. You will get credit if your heuristic follows requested requirements -- clearly write down the assumptions and conditions in which your solution is plausible. A) If the robot can carry only one parcel at a time, define an admissible heuristic function for searching the space. Explain in plain english why the heuristic is admissible. Is your heuristic consistent? Why? Make sure your heuristic is not h(x)=0. (5 points) B) If the robot can carry multiple parcels at a time, is the function h(x)= "count of packages that are not delivered" admissible and consistent? Why or why not? (4 points) C) If the robot can carry multiple parcels at a time, define two admissible heuristic functions. Explain in plain english why each heuristic is admissible. Are your heuristics consistent? Why? Make sure your heuristic is not h(x)=0, and it is not a function of actual cost because it is not practical to compute the actual cost in a general case. Hint: the heuristic function can be a function of carried parcels and un-carried parcels. (6 points)