CSCI-B-551-Assignment 0 Solved

This assignment will give you practice with posing AI problems as search and an opportunity to dust off your coding skills. Because it’s important for everyone to get up-to-speed on Python, for this particular assignment you must work individually. Future assignments will allow you to work in groups. Please read the instructions below carefully; we cannot accept any submissions that do not follow the instructions given here. Most importantly: please start early, and ask questions on Q&A Community or in office hours.

If you don’t know Python, never fear – this is your chance to learn! But you’ll have to spend some significant amount of out of class time to do it. Students in past years have recommended the Python CodeAcademy website, http://www.codeacademy.com/learn/python, and Google’s Python Class, https://developers. google.com/edu/python/. There are also a wide variety of tutorials available online. If you’re already proficient in one particular language, you might look for tutorials with names like “How to code in Python: A guide for C# programmers,” “Python for Java programmers,” etc. Feel free to share any particularly good or bad resources on Slack and/or Q&A Community. The instructors are also happy to help during office hours. If you are struggling, please come and get help! We can’t help if you don’t ask.

Guidelines for this and future assignments
Coding requirements. For fairness and efficiency, we use a semi-automatic program to grade your submissions. This means you must write your code carefully so that our program can run your code and understand its output properly. In particular:

1.    You must code this assignment in Python 3, not Python 2. Please be forewarned that

Python 2 is still quite popular, despite being obsolete, so many examples and tutorials you see online may be written in Python 2. There are many minor changes between the two versions (see https: //docs.python.org/3/whatsnew/3.0.html), but two come up particularly often. First, in Python 3, print is a function, so its arguments must be surrounded by parentheses. Second, in Python 3, dividing one integer by another integer performs floating point division, instead of integer division.

2.    Your code must obey the input and output specifications given below. Because our grading program is automatic (and is not powered by advanced AI!), it will not understand your code’s input and output unless you carefully follow the specifications given below. For example, your code should not require keyboard input (i.e., someone actually typing keys once your program is running) unless we specifically indicate it below.

3.    You may import standard Python modules for routines not related to AI, such as basic sorting algorithms and data structures like queues, as long as they are already installed on the SICE Linux servers. However, using additional modules is typically not required; we’ll usually tell you if we feel a module would be helpful.

4.    Make sure to use the program file name we specify. For example, for part 1, please call your program submission route pichu.py, as we specify below. Submitting your program with a different name, or submitting multiple versions of your code, will cause our autograder to fail and you to lose points.

5.    Please avoid using global (public) variables in your programs as they may cause your program to behave unexpectedly when run by our grading program. A global variable is one that is defined outside of any function. If you need to access the same variable in multiple functions, use return statments and function arguments instead of global variables.

6.    You should test your code on silo.sice.indiana.edu. We will test your code on this system, so this is the only way to guarantee that your program will work correctly when we run it. You may (and probably should!) do your actual day-to-day development work on your laptop, but it is important that you periodically check that your code operates correctly on our servers, as minor differences in Python versions, available modules, etc. may cause your code to work differently — and may seriously affect your grade.

To help you test, we have included an automated testing program in your github repo. We also use this testing program for autograding. Ensuring that your code works well with the testing program will help make sure we grade your code correctly. The program requires you to make a one-time installation. To install, type:

pip install pytest-timeout

Once installed you do not need to repeat this step in the future. To test your code, type:

python3 -m pytest -v

This will automatically run your programs on two sample test cases, and indicate whether your programs passed or failed. These test cases are just samples; we will run this on more cases while grading, so make sure to test your code thoroughly.

Part 1: Navigation
As those of you in the online section learned in Module 1, a certain autonomous agent likes to fly around the house and interrupt video recordings at the most inopportune moments (Figure 1). Suppose that a house consists of a grid of N×M cells, represented like this:

....XXX .XXX...

....X..

.X.X... .X.X.X. pX...X@
down, and up) indicating that solution. Your program should take a single command line argument, which is the name of the file containing the map file. For example:
Figure 1: The autonomous agent, after a bath.
 As you can see, the map consists of N lines (in this case, 6) and M columns (in this case, 7). Each cell of the house is marked with one of four symbols: p represents the agent’s current location, X represents a wall through which the agent cannot pass, . represents open space over which the agent can fly, and @ represents your location (presumably with video recording in progress).

Your goal is to write a program that finds the shortest path between the agent and you. The agent can move one square at a time in any of the four principal compass directions, and the program should find the shortest distance between the two points and then output a string of letters (L, R, D, and U for left, right,

[<>djcran@silo ~] python3 route_pichu.sh map1.txt Shhhh... quiet while I navigate!

Here’s the solution I found:

16 UUURRDDDRRUURRDD
You can assume that there is always exactly one p and one @ in the map file. If there is no solution, your program should display path length -1 and not display a path.

To help get you started, we have provided some initial code that is already available in your GitHub repo. Here’s what to do to complete the program.

1.    We’ve already created a GitHub repository for you for this assignment. You can see the name of yourrepository by logging into IU Github, at http://github.iu.edu/. In the upper left hand corner of the screen, you should see a pull-down menu. Select cs-b551-fa2021. Then in the box below, you should see a repository called youruserid-a0, (If you do not see cs-b551-fa2021 or a repository with your userid, it probably means that did not log into GitHub to create your account during the A Few Action Items activity during week 1 of class, so we were not able to add you to a team. Post a private message on Q&A Community so that we can create your repo manually.)

To get started, from the SICE Linux machines, clone the github repository:

git clone git@github.iu.edu:cs-b551-fa2021/your-repo-name If that doesn’t work, instead try: git clone https://github.iu.edu/cs-b551-fa2021/your-repo-name

where your-repo-name is the one you found on the GitHub website above. (If neither command works, you probably need to set up IU GitHub ssh keys. See Canvas for help.)

2.    Now you should see a program called route pichu.py. We have also provided two sample map files, map1.txt and map2.txt. You can run our program like this:

python3 route_pichu.py map1.txt

Unfortunately, the program does not work very well; it will probably enter an infinite loop and you’ll have to press CONTROL-C to kill it. Nevertheless, the code is a good starting point, so familiarize yourself with it. Figure out the precise search abstraction that the program is using and include it in your report. In other words, what is the set of valid states, the successor function, the cost function, the goal state definition, and the initial state?

3.    Why does the program often fail to find a solution? Implement a fix to make the code work better,and explain what you did in the report.

4.    Complete the program so that it finds and displays the correct solution. Check the starter code comments for specifications on the search() function, because our autograder (and the pytest command above in Coding Requirements) calls it directly.

Part 2: Hide-and-seek
Suppose that instead of a single agent as in Part 1, you have adopted k agents. The problem is that these agents do not like one another, which means that they have to be positioned such that no two agents can see one another. Write a program called arrange_pichus.py that takes the filename of a map in the same format as Part 1 as well as a single parameter specifying the number k of agents that you have. You can assume k≥ 1. Assume two agents can see each other if they are on either the same row, column, or diagonal of the map, and there are no walls between them. An agent can only be positioned on empty squares (marked with .). It’s okay if agents see you, and you obscure the view between agents, as if you were a wall. Your program should output a new version of the map, but with the agents’ locations marked with p. Note that exactly one p will already be fixed in the input map file. If there is no solution, your program should just display False. Here’s an example on the same sample output on the same map as in Part 1:

[<>djcran@silo ~] python3 arrange_pichus.py map1.txt 5

....XXX .XXXp..

.p..X..

.X.X... .X.X.Xp pX.p.X@
We’ve again given you some code to get started with, but it’s not fully working; the configurations it finds often allow agents to see one another, and it can be quite slow. Fix the code so that it works, and then try to make it run as quickly as possible. In your report, explain the search abstraction you’ve used – what is the state space, initial state, goal state, successor function, and cost function?

Make sure to test your program on maps other than the one we’ve given, including ones of different sizes and shapes. Check the starter code comments for specifications on the solve() function, because our autograder (and the pytest command above in Coding Requirements) calls it directly.