GPS Navigation Agent

Problem statement

Given below is the picture of a city as a grid. Due to road maintenance activities after

heavy rains, some paths are blocked for traffic. You are in your office and have to reach

home. 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.

a$.$ A$*$

b$.$ Iterative Deepening Depth First Search

Take into consideration the following while calculating the cost:

No diagonal movements allowed. If there are no straight paths, you can move diagonally with

a penalty of $3$ points. You cannot pass through other buildings. $5$ points to be added when

your path passes adjacent $($next$)$ to other buildings. $3$ points to be detected when your path

passes adjacent$($next$)$ to road blocks. Find the optimum path which passes through minimum

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

concern. You cannot travel through buildings and road blocks.

Evaluations will be based on the following.

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

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

$2.$ Use given algorithms and implement the algorithms in PYTHON $(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 your implementation to calculate the space complexity and time

complexity and print the same.

text book for ACI. $(20\%$ marks$)$