Problem Statement:

The picture of a city is given below in the grid format. A mother wants to drop her child in the

school. But due to the marriage function of a VIP in that city, many roads are blocked and routes

are diverted through some other roads. The mother and child start from house and have to school

in time because they started from the house as usual without knowing the diversion in ways to

school. There is a GPS agent to help them to find the shortest, quickest and safest route among the

available paths and reach the school in time. $7$ points to be added each time the agent passes

through traffic free cells ie adjacent to empty cell and $5$ points to be deducted while the agent

passes adjacent to STOP sign. The Possible actions are Move Up$,$ Move Down, Move Left, Move

Right only.

Graph representation

Use the following algorithms to solve the problem:

$1.$ IDA$*$

$2.$ Random restart Hill climbing algorithm.

Answer the following:

$1.$ Explain the environment of the agent $[20\%$ weightage$]$

$2.$ Define the heuristic and or fitness function for the given algorithms and the given

problem. $[20\%$ weightage$]$

$3.$ Use appropriate data structures and implement given informed and local search

algorithm and Print the path taken by the agent to the destination. $[40\%$ weightage$]$

$4.$ Find and print space and time complexity using code in your implementation. $[20\%$

weightage$]$