CSCI561留学生辅导、讲解Python程序语言、辅导Artificial Intelligence、讲解Python设计

CSCI561 Fall 2018 Foundations of Artificial Intelligence

Homework 3

Due November 23, 2018 23:59:59

BONUS: 20 points if submitted by November 19, 2018 23:59:59

https://news.utexas.edu/sites/default/files/styles/news_article_main_image/public/photos/autonomous_vehicles_830.jpg?itok=WvKF9fpF

Problem Description:

You are the CTO of a new startup company,SpeedRacer, and you want your

autonomou cars to navigate throughout the city of Los Angeles. Thecars can move

North, South, East, or West. The city can be represented in a grid, asbelow:

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

There will be some obstacles, such as buildings,road closings, etc. If a car crashes

into a building or roadclosure, SpeedRacer hasto pay $100. Youalso spend $1 for

gas when at each grid location along the way. The cars will startfrom a given

SpeedRacer parking lot,and will end atanotherparkinglot. Whenyou arrive at your

destination parking lot, you will receive $100.Your goal is tomakethe most

money over timewith the greatest likelihood. Your carshave a faultyturning

mechanism, so they have a chance of going in a direction other thanthe one

suggested by your model. They will go in the correct direction 70% ofthe time, with

a 10%  chance of going in each of the other three directions instead.

The first part of your task is to design an algorithm that determineswhere your cars

should try to go in each city grid location given your goal of makingthe most money.

Then, to make sure thatthis isa good algorithm when you present it tothe rest of

your board, youshould simulatethe carmoving through the citygrid. Todo this,

you will use your policy from your start location. You will thencheck to see ifthe car

went inthe correct direction using a random number generator withspecific seeds

to makesure you can reproduce your output. Youwill simulate yourcar moving

throughthe city grid 10 times using the randomseeds 1, 2, 3, 4, 5, 6, 7,8, 9, and 10.

You will reportthe mean over these 10 simulations as an integerafter using the

floor operation (e.g.,numpy.floor(meanResult)). An example ofthis process is

given in detailbelow.

Input: The file input.txt in the current directory of your program will be formatted

as follows:

First line: strictly positive 32-bit integer s, size of grid [grid is a square of size sxs]

Second line: strictly positive 32-bit integer n, number of cars

Third line: strictly positive 32-bit integer o, number of obstacles

Next o lines: 32-bit integer x, 32-bit integer y, denoting the location of obstacles

Next n lines: 32-bit integer x, 32-bit integer y, denoting the start location of each

car

Next n lines: 32-bit integer x, 32-bit integer y, denoting the terminal location of

each car

0,4 1,4 2,4 3,4 4,4

Output:

n lines: 32-bit integer, denoting the mean money earned in simulation for each

car, integer result of floor operation

Example:

Input.txt

3

1

1

0,1

2,0

0,0

Output.txt

95

For example, say you have a 3x3 grid, as follows, with 1 car instartposition 1,0

(green):

99 -1 -1

-101 -1 -1

-1 -1 -1

You determine that based on thelocations of certain obstacles andpeople,you

should move in these directions in each cell:

99

- - -

- -

Then, you should do simulation using this policy. Beginning at thestart position,

move inthe direction suggestedby yourstart policy. There is a10% chance thatyou

will move South, so check your direction using random generationwith random

seed = 1 (e.g.,random.random()). In this case,you actually moveSouth, so you will

receive-$1. You will now try to move North based on your policy.With the random

seed = 1, you successfully moveNorth. Therefore, you now have -$2.Repeat at your

next locations,until you end at your terminal state. Record thetotal money youhave

at the end. Let’s say that thetotal is $91. Then, repeat thisprocess9more times. You

will average $91 with the 9 other results and report the integerfloor of that average.

If the result is 91.65093, for example, you should record 91 inyouroutput file.

Standard rounding rules apply. (draw random samplefrom adistribution: if value is

<= 0.7 make thecorrecttransition, otherwise randomly pick uniformlyalternative

direction) (rounding) Some codedemonstrating how to dothis isgivenbelow:

for in range(len(cars)): for inrange(10): pos = cars[i]

np.random.seed(j+1) swerve = np.random.random_sample(1000000)

k=0 while pos != ends[i]: move=policies[i][pos]

if swerve[k] > 0.7: if swerve[k] > 0.8:if swerve[k] > 0.9:move= turn_left(turn_left(move))

else:move = turn_left(move) else:move= turn_right(move)k+=1

Guidelines

This is a programming assignment. You are provided sample input and output files. Please

understand that the goal of these 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

1. Use Python 2.7 to implement your homework assignment. You areallowedto

use standard libraries only. You have to implement any other functions or

methodsby yourself.

2. Create a file named “hw3cs561f2018.py”. When you submit thehomework

on labs.vocareum.com, the following commands will be executed:

pythonhw3cs561f2018.py

3. Create a file named “output.txt” and print its output there.For each test case,

the grading script willput an “input.txt” file in your work folder, runs your

program(which reads “input.txt”), andcheck the “output.txt”filegenerated

by yourcode. The grading script will replace the filesautomatically, soyou

do NOT need to do anything for that part.

4. Homework must be submitted through Vocareum.Please only uploadyour

code tothe “/work” directory.Don’t create any subfolder or uploadany

other files. Please refer to http://help.vocareum.com/article/30-gettingstarted-students

to get started with Vocareum.

5. Your program must handle all testcases within a maximum runtime of 3

minutes per test case on Vocareum.

6. It is recommended tosubmit your program 24 hours ahead of thedeadline to

avoid any submission issues on Vocareum. Late submissions will not be

graded.

HelpfulHints:

1. Tie breaking. If values are the samefor your available moves,choose to

move indirections in this order of preference:North, South, East, West.

2. Carscan be in the same gridcell atthe same time. There isnoneed to

consider multi-agent coordination.

3. Calculating expectedvalue. When consideringfuture moves, makesure to

give them a lesser weight, specifically0.9. You can stop calculating when you

are within 0.1of the optimal value.

4. It is very importantto use the exact parameters we provide foryour

simulation, as different answers will be markedas incorrect.

5. We will not give unsolvable inputs. This means that we won’tgiveany

irregular inputs that don’t conform tothe format we’ve described inthis

document.

6. Think about representing theproblem.

a. Whatis a good representation of states and operators?

b. How can you use thisto simplify theproblemrepresentation?

c. How will you evaluate the “score” of a state?

7. Think about complexity.

a. How can you use the input parameters to determine which algorithm

will beable togenerate a solution within 3 minutes?