Artificial and Computational Intelligence

Assignment $1$

PS $-$ Way to Playground

Rennish wants to go to the playground from his home. Before reaching the playground, he has to

buy some things for playing the game. His tasks include:

Withdrawing cash from the ATM.

Purchasing snacks and energy drinks from the supermarket.

Purchasing balls from the sports store.

Purchasing water bottles from the grocery shop.

Retrieving the team uniform from the dry cleaners.

After completing the above tasks, he has to reach the playground.

The objective is to determine the most effective paths that will minimize the overall distance

traveled while ensuring that Rennish makes at least one visit to each destination before reaching

the playground.

Given:

The locations of Rennish's home, Playground, supermarket, ATM, Sports Store, Grocery

Shopand Dry Cleanersin the city.

The distances between each pair of locations.

It's your responsibility to implement an algorithm that decides the path Rennish should follow to

complete his shopping as soon as possible. The approach must take into consideration the

restriction that each place can only be visited precisely once as the final destination is

playground, where he will play the game.

Numerous search algorithms, heuristics, and optimization techniques can be used to overcome

this issue. You should also assess the time and space complexity of the solution and provide a

succinct explanation of the method's efficiency.

Use the following algorithms to solve the stated problem:

i$.A^{*}$

ii$.$ Iterative Deepening Depth First Search

Answer the following:

Explain the PEAS and task environment of the agent $[20\%$ weightage$]$

Define the heuristic and or fitness function for the given algorithms and the given

problem. weightage$]$

Use appropriate data structures and implement search algorithms $($informed and local

search$)$ to find the path that covers all the places with shortest distance provided in

the graph. The starting point is to be obtained from the user as input. $[40\%$

weightage$]$

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

weightage$]$

NOTE:

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 $[$PEAS$].$ 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.