$24
Artificial Intelligence Homework 1 Solution
Description
You are helping the LA Dept of Transportation (LADOT) to develop a pilot scooter program for LA. There are a limited number of police officers available to monitor and address issues that may arise from scooters, ranging from traffic and safety violations to accidents with cars, bikes, other scooters and pedestrians. The scooter companies have given LADOT access to scooter routes over the course of one day. In order to maximize the scooter activity monitored by the officers, you will take as input the route information, the monitored city area dimensions, and the number of officers available to then generate the best placement of the officers. The officers can only be in one place for one day, and there can only be one officer on each street. When an officer and scooter are at the same location at the same time, the officer is able to address a safety issue, and one “Activity point” is gained. The goal is to place the officers in locations that do not conflict with each other, while maximizing the total “Activity points” for the day (12 time steps in a day). The problem follows these rules:
Officers cannot be in same square, same row, same column, or along the same diagonal. (Think of queens on a chess board)
Officers cannot move.
Activity points are collected at each time step t when officers are in same square as scooters. One point per each scooter.
The grid coordinate system will be indexed starting from the top-left corner. An example of a 5 by 5 grid is given below with each cell’s coordinates:
0,0
1,0
2,0
3,0
4,0
0,1
1,1
2,1
3,1
4,1
0,2
1,2
2,2
3,2
4,2
0,3
1,3
2,3
3,3
4,3
0,4
1,4
2,4
3,4
4,4
T = 1
The two police officers have been placed and are unable to move. The red and blue lines show the limitations on placing officers; no officer may be placed on the same row, column, or diagonal as another officer. Since no scooters are in the same square as either of the officers, no value is gained at T=1.
T = 2
At T=2, the scooters have both moved one square. Since a scooter has moved onto a square with an officer, 1 Activity point is gained at T=2. This process continues at T steps forward, with the officers keeping their positions.
Input: The file input.txt in the current directory of your program will be formatted as follows:
First line: strictly positive 32-bit integer n, the width and height of the n x n city area, n <= 15.
Second line: strictly positive 32-bit integer p, the number of police officers
Third line: strictly positive 32-bit integer s, the number of scooters
Next s*12 lines: the list of scooter x,y coordinates over time, separated with the End-of-line character LF. With s scooters and 12 timesteps in a day, this results in 12 coordinates per scooter.
Output:
Max activity points: strictly positive 32-bit integer m
Guidelines
This is a programming assignment. You will be provided sample inputs and outputs. Please understand that the goal of the samples is to check that you can correctly parse the problem definitions, and generate a correctly formatted output. The samples are very simple and it should not be assumed that if your program works on the samples it will work on all test cases. There will be more complex test cases and it is your task to make sure that your program will work correctly on any valid input. You are encouraged to try your own test cases to check how your program would behave in some complex special case that you might think of. Since each homework is checked via an automated A.I. script, your output should match the specified format exactly. Failure to do so will most certainly cost points. The output format is simple and examples are provided. You should upload and test your code on vocareum.com, and you will submit it there.
Grading
Your code will be tested as follows: Your program must not require any command-line argument. It should read a text file called “input.txt” in the current directory that contains a problem definition. It should write a file “output.txt” with your solution to the same current directory. Format for input.txt and output.txt is specified below. End-of-line character is LF (since Vocareum is a Unix system and follows the Unix convention).
The grading A.I. script will
Create an input.txt file, delete any old output.txt file.
Run your code.
Test your output.txt file
Academic Honesty and Integrity
All homework material is checked vigorously for dishonesty using several methods. All detected violations of academic honesty are forwarded to the Office of Student Judicial Affairs. To be safe you are urged to err on the side of caution. Do not copy work from another student or off the web. Keep in mind that sanctions for dishonesty are reflected in your permanent record and can negatively impact your future success. As a general guide:
Do not copy code or written material from another student. Even single lines of code should not be copied.
Do not collaborate on this assignment. The assignment is to be solved individually. Do not copy code off the web. This is easier to detect than you may think.
Do not share any custom test cases you may create to check your program’s behavior in more complex scenarios than the simplistic ones considered below.
Do not copy code from past students. We keep copies of past work to check for this.
Do ask the professor or TA if you are unsure about whether certain actions constitute dishonesty. It is better to be safe than sorry.
Homework Rules
Use Python 2.7 to implement your homework assignment. You are allowed to use standard libraries only. You have to implement any other functions or methods by yourself.
Create a file named “hw1cs561f2018.py”. When you submit the homework on labs.vocareum.com, the following commands will be executed:
python hw1cs561f2018.py
Create a file named “output.txt” and print its output there. For each test case, the grading script will put an “input.txt” file in your work folder, runs your program (which reads “input.txt”), and check the “output.txt” file generated by your code. The grading script will replace the files automatically, so you do NOT need to do anything for that part.
Homework must be submitted through Vocareum. Please only upload your code to the “/work” directory. Don’t create any subfolder or upload any other files. Please refer to http://help.vocareum.com/article/30-getting-started-students to get started with Vocareum.
Your program must handle all test cases within a maximum runtime of 3 minutes per test case on Vocareum.
It is recommended to submit your program 24 hours ahead of the deadline to avoid any submission issues on Vocareum. Late submissions will not be graded.
Helpful Hints:
We will not give unsolvable inputs. This means that we won’t give more officers than can be assigned without conflicts, or any irregular inputs that don’t conform to the format we’ve described in this document.
All officers must be allocated.
Some inputs may have more than one valid solution. We will accept all solutions that achieve the maximum possible Activity points for the given input.
Each scooter route for a day consists of 12 timesteps. For example, if a testcase has 2 scooters the input file will contain a list of 24 scooter positions.
Think about representing the problem.
What is a good representation of states and operators?
While the scooters may be moving at each timestep, the officers cannot move. How can you use this to simplify the problem representation?
How will you evaluate the “score” of a state?
Think about complexity.
How does grid size affect branching factor?
How does the number of officers affect search tree depth?
How can you use the input parameters to determine which algorithm will be able to generate a solution within 3 minutes?
Sample input and output files are posted on DEN.
