Problem statement

Given below is the picture of a city as a grid. Due to heavy rains and water clogging,

some paths are blocked for traffic. You are in your office and have to reach home quickly

because of further rain and flood warnings. You have a GPS agent to help you find the

shortest, quickest and safest route through the available paths avoiding the blockades so that

you reach home safely. You are provided with the map of the city with the current situation

marked. Use the following algorithms to find the shortest, and safest path. Use the following

algorithms to find the safest path. Interpret if the path obtained is the shortest with

justification.

a$.$ Depth First Search

b$.$ Iterative Deepening A$*$

Note $1$:

No diagonal movements allowed. You cannot pass through other buildings. $5$ points to be

added when your path passes adjacent $($next to and not diagonally$)$ to other buildings. $3$ points

to be detected when your path passes adjacent to road blocks. The path which passes through

minimum number of squares and maximum points is the shortest and safest path.

Evaluations will be based on the following.

$1.$ Explain the PEAS $($Performance measure, Environment, Actuator, Sensor.$)$ for your

agent. $(20\%$ marks$)$

$2.$ Use Depth First Search and Iterative Deepening A$*$ and implement the algorithms in

PYTHON. Compare to interpret the results in terms of the algorithm working,

performance & shortest path if obtained relevant to the given problem. $(20\%+20\%=$

$40\%$ marks$)$

$3.$ Print the path, the total points for the path and the number of squares in the path.

$(20\%$ marks$)$

$4.$ Include code in you implementation to calculate the space complexity and time

complexity and print the same. $(20\%$ marks$)$

Note $2$:

$$ You are provided with the python notebook template which stipulates the structure of

code and documentation. Use well intended python code.

$$ Use separate MS word document for explaining the theory part. Do not include theory

part in the Python notebook except Python comments.

$$ The implementation code must be completely original and executable.

$$ Please keep your work $($code$,$ documentation$)$ confidential. If your code is found to be

plagiarized, you will be penalized severely. Parties involved in the copy will be

considered equal partners and will be penalized severely. Collaboration among

different group members will also be considered as plagiarism.