Question 1: Consider the below initial and goal states (Two equally acceptable goals are given) for a formation problem and answer the following questions. The agent can move the red duck on top of the other red duck in this problem as well as the yellow ducks on top of the other yellow ducks, and no ducks are allowed to be placed above Height 3 of any column. An agent should find a path is... series to legal moves from the Initial state to achieve the Goal state [3+2+5 10 Marks] Initial State Height 3 Height 2 Height 1 Height 0 Goal State 1 & Goal State 2 a. Depict the search tree for up to exactly 4 levels and find the heuristic values of all the generated nodes. (Given initial state can be assumed to be on level-0.) b. Among the below two defined heuristics (H1 and H2), if you are restricted to choose only one of them, which one would you choose and why? Tile in the below definition does not include the empty tiles. Justify your choice with brief answer with appropriate numerical illustration w.r.t to the given problem. hi(n) Goal orientation with respect to positioning of yellow ducks + Goal orientation with respect to positioning of red ducks he(n)-No.of legal moves possible with respect to red and yellow ducks. Note for Calculation: For Goal orientation, If at least two yellow ducks are placed in same column add a cost of +5 else add a cost of +10. Similarly, If at least two red ducks are placed in same column add a cost of +5 else add a cost of +10. Here hi (Initial state)- 10+10-20 In initial state. The no.of.legal moves for yellow ducks are 2 and for red duck is 0. Here the h: CInitial State)-2+0=2 c. Use the following heuristic function H(n)- hl(n)+h2(n) for the results obtained in part a., and then apply A search algorithm till first 5 closed list updates. Show the status of OPEN and CLOSE list at each level.