CS 6601 Final Exam
Search Part A
Coal processing consists of several process steps including crushing, screening, and beneficiation/preparation. Each process step is usually carried out in specialized facilities at different locations. Coal often must be transported between steps in various forms to and from the different locations as it is transformed from its raw form into a final product that fulfills the specific needs and demands of the customer. The transportation flow of coal to and from these locations across all of
the coal supply chains in the United States can be visualized as a very large graph where every vertex represents the location of a single point in the supply chain (facility where coal is processed) and every edge represents a possible transport route between two facilities.
Assumptions: 1. Assume that the number of vertices and edges will cause any search algorithm to exceed the storage space on your computer, (treat the supply
chain graph as infinite [having an infinite number of vertices and edges]). 2. Assume the transportation cost is $1 per ton of coal for the transport routes between any two locations (i.e. every edge has unit edge weight).
Suppose you are given a pair of vertices, a source facility and a destination facility. Your objective is to nd a valid path (transportation route) through which 1 ton of coal can be transported from the source to the destination. Which of the search algorithms given below are least likely to nd and return one such valid, nite path,
assuming one exists, when run on the coal supply chain graph? The path does not need to be optimal. [Select one]
Depth- rst search
Breadth- rst search
Uniform-cost search
A* search with an inadmissible heuristic
Suppose you are given a source facility and destination facility but now the objective for you is to nd an optimal least-cost nite transport path guaranteed to exist from the source to the destination to transport 1 ton of coal. Which of the search algorithms from the choices below will nd an optimal least-cost transportation path when run on the supply chain graph? [Select all that apply]
A* Search using a consistent heuristic Iterative deepening Depth- rst Search Bi-directional Uniform Cost Search Breadth- rst Search
Instructions
Given the problem speci cation and graph, answer the following questions.
Search Part B
It is the year 2040 – and the age of self-driving cars is almost here, and Georgia Tech is the pioneer of the new revolution, leading the first effort to make affordable self-driving cars available to the public for the first time in Atlanta! The best news? You are one of the highly qualified AI researchers at Georgia Tech working to make this dream a reality.
The diagram below shows a network of roads and highways all over Atlanta. The number on each edge represents the time, in minutes, to drive from one district / landmark of Atlanta to another, under normal traffic conditions.
Your close friend, Ryan, is a fellow researcher at UGA (University of Georgia) who would like to drive to Georgia Tech to visit you and take one of your prototype self- driving cars for a spin!
3 Ryan has successfully reached Georgia Tech, and you and Ryan decide to hang out before testing your prototype self-driving car the next day. Following the Atlanta Braves’ victory in the 2040 World Series of Major League Baseball, traf c has experienced an upsurge on some routes. Luckily, the self-driving car software uses live traf c conditions, to dynamically update its built-in heuristic function for every district / landmark with new estimates of driving time between each node and the destination
Ryan prepares to go back to UGA in the self-driving car from Georgia Tech. Assume the newly updated heuristic values computed by the self-driving software for every district / landmark (estimated time to drive from district / landmark to UGA) are in the following table:
District/Landmark
Heuristic Value Order Expanded
Snellville 5 Stone Mountain 10 East Atlanta Village 22 Ponce City Market 14 Downtown 13 Midtown 14
Harts eld-Jackson Airport 9 Georgia Tech 17
The self-driving car uses the A* Search algorithm starting from Georgia Tech to nd the optimal path to UGA, based on the information in the network and the heuristic values above. You can assume that the chosen route drive times remain the same.
Select the correct order of expansion for each landmark/area (e.g., “UGA”, “Snellville”, “Midtown”)
Instructions
Given the problem speci cation and the graph, answer the following questions
Search Part C
Fast-forward to 2077, self-driving cars are now a thing of the past, now there are flying cars that allow us to move around more quickly than ever before! We are now trying to compare possible heuristics that estimate the flight time in a flying car from a start state to the goal state. Consider this simpler search map of Atlanta with only 3 districts / landmarks, it has directed edges with each corresponding edge costs representing the actual time it takes to fly in a flying car from one district / landmark to the other. The search map and a set of 4 heuristics are shown below:
h(Snellville) h(Hartsfield-Jackson Airport) h(Downtown)
For each heuristic function indicate whether it is admissible and/or consistent with respect to the search problem
Heuristic Admissible Consistent
From Russel & Norvig’s chapter on Search. For 2 admissible heuristic (h1, h2) if for any node n, h2(n) >= h1(n), then h2 will never expand any more nodes than A* using h1. We say that h2 dominates h1 (see your book for further details and conditions). Read each of the following statements and select the statements that are true.
Heuristic function III dominates IV
Heuristic function IV dominates III
Of the heuristic functions III and IV, neither one dominates the other Heuristic function I dominates III
Heuristic function III dominates I
Of the heuristic functions I and III, neither one dominates the other
Instructions
Using the problem explanation and the game playing tree answer the following questions
Game Play Part A
In a world devastated by a deadly fungal infection, a young survivor named Ellie struggles to survive against hordes of humanity turned into esh-eating monsters by the infection. She’s lost almost everything other than a group of survivors, she remains tough. In spite of her traumatic past, she has become an critical member of her community, due to her ability to help defend the camp from the infected.
Ellie’s community is suddenly attacked by a massive wave of the infected coming from different lanes, and she takes up a position at the entrance armed with her bow and arrow. As the waves of infected grow stronger and more numerous, Ellie realizes that she needs to do more than just shoot them. She starts laying traps and obstacles along the lanes, using her knowledge of their weaknesses to slow them down, and giving herself time to take them out. Additionally, she also uses help from other survivors Joel, Tommy, Bill, Henry, and Frank (not Abby).
Meanwhile, the fungal infection causing Cordyceps brain infection has evolved into a gestalt intelligence known as the Hive. The Hive can use the unique abilities of different infected types to disassemble traps and take down defending survivors. It can also echo-locate the traps and human movement to launch attacks on Ellie’s community.
The situation can be represented as an adversarial search problem. Let Ellie play the maximizing (triangle facing up) player and the Hive be the minimizing player (triangle facing down). Ellie has four lanes to defend, and she can choose from ve strategies to set up for three of the lanes during the day. One lane is guarded by Henry, so there is nothing for her to worry about. The effectiveness of each strategy (circles) will be evaluated based on the amount of damage it can in ict on the infected. However, some of the infected have taken AI classes, enabling the Hive to learn the same utility function and choose the weakest lane to attack.
Use the one-turn (two-plies) game tree shown below where Ellie and Henry prepare the lanes during the day, and the Hive attacks the lane at night, assume the Hive always explores the branches from left to right:
程序代写 CS代考 加微信: cstutorcs
If the Hive is capable of running alpha-beta pruning, what is the maximum number of leaf nodes (circles) that it can prune? (Hint: it is an integer between 0 and 16 no rounding is needed)
If Ellie is aware that the Hive can use alpha-beta pruning, is it possible for her to make the Hive explore all her and Henry’s strategies for each lane? (Hint: What is the minimum number of leaf nodes that the Hive could prune?)
True False
Game Play Part B
Joel a survivor and a seasoned veteran, shares his knowledge of the Hive with Ellie, explaining the dangers of those infected with the fungus. The Hive collective plays optimally it acts as an intelligent being, it will always choose the weakest lane so Ellie must use an intelligent strategy to defend the lanes with limited resources. Working with John, Ellie designs a game tree meant to counter the Hive’s strategy, allowing her to protect her resources strategically.
In this game tree, Ellie is the maximizing player (triangle pointing up), and the Hive is the minimizing player (triangle pointing down). Ellie has three potential ways to set up her resources at four lanes (level 2 of the game tree), with the utility value of each resource node (green circles labeled as ‘A’ to ‘R’) being a different integer from 1-18. The Hive will always choose the weakest lane to attack, and Ellie will use this information to defeat the infected when they are at their weakest, using extra Molotov cocktails.
Assume the Hive will explore the branches from left to right and Ellie has no idea what the range of the utility value is.
What are the maximum number of leaf nodes (green circles) Ellie can prune running standard alpha beta pruning left to right on the game tree. Assume nodes A through R are assigned unique integers ranging from 1-18, but the pruning algorithm has no knowledge of the range of values
assigned nor that the assignments are unique.
Hint: It is an integer between 0 and 18, no rounding needed)
Given Ellie’s pruning in Q9, what is the minimum possible value for the root node (triangle at the very top) of the game tree? Hints: It is an integer between 1 and 18, no rounding needed
Assuming Ellie is using alpha-beta pruning and has pruned the maximum number of leaf nodes, what is maximum possible value for the root node (triangle at the very top) of the game tree? Hints: It is an integer between 1 and 18.
Instructions
Note on rounding and precision (for all questions in this section): For all answers, round to 3 digits of precision. Do not round any of your intermediate results. Radians to Degrees: Angle in Radians * 180/pi = Angle in Degrees
Optimization Part A
It’s 2026. Owing to your love for AI, you were recently hired as an autonomous driving engineer at StarnerFleet, a leading car company. Bumblebee, the agship car you’re going to be working on, is equipped with the state-of-the-art perception and localization systems. The perception system senses the surroundings of the car and builds a map. While the localization system uses the perception data to determine the location of the car in the map.
At the present stage of development, you’re tasked with designing a robust vehicle control system for Bumblebee. When provided with a desired path and a desired velocity, the control system outputs the throttle, steering and brake values that make the car match the desired path and velocity as closely as possible. The desired path is provided by the path planning and obstacle avoidance systems as an array of locations of the car in the future, at associated timesteps. Here,
is the current timestep, represents ‘desired’ and the number of timesteps is a hyperparameter . Keeping these requirements in mind, you attempt to predict the behavior of the vehicle using a simple 2D vehicle model:
Here, and are the and coordinates of the car at timestep . is the velocity of the car, is the angle of the car’s heading direction w.r.t the -axis measured counter-clockwise, is length of the car, and are the steering wheel’s angle and the acceleration of the car at time respectively.
Given the time crunch, you decide to focus solely on the car’s lateral control – the steering angle – and leave the longitudinal control – the throttle and brake – to your colleagues. Consider acceleration . You know that Bumblebee will match the desired turn, only if the steering angle output by your lateral controller is correct. As you ponder over the problem, a thought pops up: What if my lateral controller could minimize the deviation of the car from the desired path? If done over all possible steering angles, could this lateral control problem be formulated as an optimization problem!? Precisely.
We nd the steering angle at the current timestep, such that for the predicted future locations of the car you minimize (subject to steering constraint ), or the cross-track error given by,
{Note on precision} (for all questions in this section): whenever there’s an assignment from the right hand side expression to the left hand side expression, apply a rounding to 3 digits after the assignment. All answers need to be reported to 3 digits of precision. Any intermediate results in the right hand side need not be rounded.
11 To build intuition on the turning behavior of Bumblebee, you contrive a traf c scenario as depicted below.
Bumblebee is about to make a right turn on an intersection. Using the vehicle model, predict the future positions of the vehicle given the particular initial conditions. For simplicity, we’ll predict only three timesteps in the future, i.e. , assuming a constant steering angle rad across all timesteps. , ,
. The desired
coordinates at each timestep are given by the path planner as tabulated below.
1.366 2.366
What is the value of (cross-track error) in this scenario?\\ Fill in the predicted vehicle states in the table below:
0.306 1.952
.643 1.000
12 What is the value of E (cross-track error) at time=3
13 The optimization problem for the lateral control is a 1D problem, involving only as the variable. You realize that your controller can iteratively nd a steering angle that minimizes E using techniques like gradient descent. The update rule for gradient descent for a learning rate is given as
Where k is the gradient descent iteration. Assume the same traf c scenario of N = 3, L = 1, , v0 = 1, x0 = 0 Compute the gradient at rad, which is the initial steering angle you may nd the following derivatives useful:
Provide the answer for at :
The rate at which your lateral controller operates should be at par with the perception and path planning system for responsive vehicle maneuvers. However, gradient descent being computationally intensive for your controller hardware, you found out that you can only perform one iteration of gradient descent before your controller sends steering commands to the vehicle.
Using the update rule and the gradient from the previous section to perform one iteration of gradient descent. Compute the steering command , that Bumblebee will execute for the right turn. Use a learning rate of
Learning rates can have a drastic impact on the gradient descent algorithm and determine if it can converge quickly to an optimum or converge at all. To build intuition on Bumblebee’s response to the traf c scenario previously discussed you try to write code that performs gradient descent until convergence, and nd the optimal steering angle to be
However, your controller hardware cannot run thousands of iterations per second. You wish to gauge how safe you controller is with just one iteration. Drag and drop the learning rates into the areas that corresponding to the effect that choosing that particular learning rate will have on the turning of the car. Assume the same traf c scenario, with the same initial steering angle
Use your mouse to drag the item to the proper category
NOTE: due to limitations of the tool we represent eta ( ) as n in the choices
Bumblebee underturns w.r.t desired turn Bumblebee overturns w.r.t desired turn
Possible answers
n=0.1 n=0.2 n=0.05 n=0.5 n=0.001
Owing to the complexity of the objective function (cross-track error), you decide to try simulated annealing as an optimization algorithm for your lateral controller. You consider the probability of accepting a candidate steering angle based on predicted cross-track errors to be,
Where, is the number of timesteps predicted in the future, is the cross-track error resulting from the current steering angle , is the cross- track error resulting from a candidate steering angle and is the annealing temperature.
Consider the traf c scenario depicted in question 1. Your simulated annealing based lateral controller is considering three candidate steering angles to execute:
Steering angles = 0.2
= 0.4 = 0.6
and , leading to predicted cross-track errors , and , while the current cross-track error is . Fill in the following table for the probability of acceptance for the three steering angles at an annealing temperature .
Energy difference Probability of acceptance (0 to 1) -0.853
Constraint Satisfaction Problem Part A
The Midtown School of Science and Technology’s Academic Decathlon team has returned from the competition! As the coach for the team, you are in charge of organizing the post-competition banquet party and ensuring that everyone has a great time at the party. Of course that means understanding the unique relationships between the 6 team members: Betty, Flash, Liz, MJ, Ned, and Peter.
You’ve returned to good old classroom 404, which has a round table with 6 seats. You can see a diagram of the table below with the seats numbered 1 through 6. Note that the chairs are identical
Your students are high schoolers with complicated relationships, so it’s expected that they have some strong feelings about where they are willing to sit. You’ve noted that Ned and Peter are best friends, MJ is spying on Peter, Flash doesn’t like Peter, Ned is avoiding eye contact with Flash, and Betty has recently become superstitious of odd numbers. Recognizing that this is a perfect CSP problem, you de ne the problem as follows:
There are 6 variables: Betty, Flash, Liz, MJ, Ned, and Peter, each with a starting domain size of 6 (the seats which you’ve conveniently numbered). There are also several constraints that you’ve de ned:
1. No two people can be assigned the same seat. (Global Constraint)
2. Liz must be assigned seat 1. (Unary Constraint)
3. Betty must NOT be assigned an odd numbered seat. (Unary Constraint)
4. Ned and Peter must be assigned adjacent seats. (Binary Constraint)
5. MJ and Peter must be assigned adjacent or opposite seats. (Binary Constraint) 6. Peter and Flash must NOT be assigned adjacent seats. (Binary Constraint)
7. Ned and Flash must NOT be assigned opposite seats. (Binary Constraint)
It’s time for the team party! Use what you have learned to solve the following CSP questions.
*Please represent all assignments as values without curly braces. Please represent all variable domains as sets with curly braces and sorted in ascending order.
18 Using CSP techniques help reduce the search space when seeking a complete assignment. How many complete assignments would you have to consider if your search procedure did not use constraints? (See AIMA Ed. 4 Sec. 6.1.1)
How many complete seating solutions are there for the party? (See AIMA Ed. 4 Sec. 6.1)
Programming Help
Betty Flash
20 On a whim, you decide to assign seat 4 to Flash. This results in the following state of the domains:
Betty: {2, 4, 6} Liz: 1
Flash: 4 MJ: {1, 2, 3, 4, 5, 6}
Betty: {2, 4, 6} Liz: 1 Ned: {1, 2, 3, 4, 5, 6} Flash: {1, 2, 3, 4, 5, 6} MJ: {1, 2, 3, 4, 5, 6} Peter: {1, 2, 3, 4, 5, 6}
If you were to enforce arc consistency on the variable Peter what would be the new state of the domains? (order as above, least to greatest number) (See AIMA Ed. 4 Sec. 6.2.2)
Liz: {1} Ned:
Ned: {1, 2, 3, 4, 5, 6}
Peter: {1, 2, 3, 4, 5, 6}
If you were to make the graph arc consistent what would be the new state of the domains? (order as above, least to greatest number) (See AIMA Ed. 4 Sec. 6.2.2) Betty
Flash 4 MJ:
21 You are worried that your whimsical move might not have been the best move, so you go back and mess around with the assignments again. This time you end up with the following state of the domains:
Betty: {2, 4, 6} Liz: 1 Ned: {1, 2, 5, 6}
Flash: {3, 4} MJ: {1, 2, 3, 4, 5, 6} Peter: {1, 2, 5, 6}
If you were to enforce path consistency on the variables {Peter, Ned} with respect to variable Flash, what would be the new relation (set of tuples) for the constraint between Peter and Ned? Answer in the form of (Value for Peter, Value for Ned), (Value for Peter, Value for Ned), … (See AIMA Ed. 4 Sec. 6.2.3)
C = < (Peter, Ned), { } >
Liz: 1 Ned:
Probability Part A
As a teaching assistant for CS 3600 and CS 6601, it is useful for you to understand how your undergraduate students are performing in comparison to your graduate students. Please answer the following questions on probability to help the staff improve.
You’ve received 2200 student submissions, 900 of which are from graduate students and 1300 of which are from undergraduate students. If we sample 10 submissions from this pool where each one is picked out of the entire body of 2200 submissions, what is the probability that at least 3 of the submissions are from undergraduate students?
Bayes Net Part A
Having spent her life carefully logging her own behavior, circumstances, and exam results, Alice has developed a reliable Bayesian network model of the probability she will get an A on an exam.
When a class begins before 10am (call this “early”), Alice only attends all of the lectures with a probability of 0.2. If it begins at 10am or later, this probability rises to 0.9. Because she tries to avoid early classes, the probability that a class she takes starts before 10am is only 0.1.
How much time Alice can spend on a class is dependent on how many other courses she’s taking and whether she is training for a marathon that semester. If she is training for a marathon (call this “marathon”) while taking 6 or more courses (call this “overloaded”), she will be able to allocate adequate time per course (call this “adequate”) with probability 0.1. If she is taking fewer than 6 courses and not training for a marathon, the probability she can allocate adequate time per course is 0.8. When she is either training for a marathon or taking 6 or more courses (but not both), this probability is 0.4. The probability that she takes 6 courses in a semester is 0.4. The probability that she trains for a marathon during a given semester is 0.5.
Alice is peer pressured into joining a semester-long Texas Hold ‘Em poker club (call this “poker”) with probability 0.3.
When she spends adequate time on a course, attends all of the lectures, and doesn’t join the poker club, she feels prepared (call this “prepared”) with probability 0.8; when two out of those three conditions are met, she feels prepared with probability 0.6; when one of those three conditions are met, she feels prepared with probability 0.3; when none of those conditions are met, she feels prepared with probability of 0.1.
When Alice is incredibly busy, she is more likely to be in a forgetful state (call this “forgetful”) for the semester. When Alice is training for a marathon, overloading with 6 or more courses, and allocating adequate time to each course, the probability she is in a forgetful state is 0.9. When two of the three are true, it is 0.7. When one of the three is true, it is 0.4. Otherwise, if none are true, it is 0.2.
Alice also keeps begonias in her apartment. When she forgets to water them, some of the plants are more likely to dry out and die (call this “dry out”). When Alice is in a forgetful state, she waters the begonias regularly (call this “waters”) with 0.2 probability. Otherwise, that probability is 0.7. The probability that at least one of her begonia plants dries out at some point in the semester is 0.6 if she does not water them regularly. It’s only 0.1 if she does.
Although Alice tries her best to spread her studying out throughout the semester, she also wants to cram (call this “cram”) before exams. However, when she is in a forgetful state, she sometimes forgets to cram for an exam. When she is in a forgetful state, the probability she crams for an exam is only 0.3. Otherwise, that probability is 0.8.
On the day of exams, Alice wants to have her lucky breakfast (call this “lucky”): a bowl of Lucky Charms, of course. However, she doesn’t always remember to keep it in stock within her pantry. When she is in a forgetful state, she will have it on hand with 0.4 probability. When she is not in a forgetful state, she’ll have it on hand with 0.9 probability. If she has it on hand, she will eat it on exam mornings.
When Alice eats Lucky Charms, she eats about one fth of the box for breakfast. So, given that she has Lucky Charms on hand the morning of an exam, there is a 0.2 probability she will put the empty box (call this “empty”) in the recycling bin afterward (her recycling is picked up daily late at night, so empty boxes in the recycling bin imply that she has nished a box that morning). When she does not have Lucky Charms on hand, that probability is 0.
The dif culty level of the exam also impacts Alice’s grade on it, and is determined by who is writing the exam. When the professor writes an exam, the exam is dif cult (call this “dif cult”) with a probability of 0.2. When the teaching staff writes it (call this “staff”), it is dif cult with probability 0.9. The probability that the staff will write the exam is 0.6.
Additionally, when the teaching staff is busy writing the exam, they are slow to return graded assignments (call this “slow”) with probability 0.6. When they do not write the exam, they are slow to return graded assignments with probability 0.2.
Alice tends to do better on exams when they are not dif cult, she has had Lucky Charms for breakfast, she is well prepared, and remembers to cram for it. When all four of those are true, she gets an A (call this “A”) with 0.9 probability. When 3 out of 4 are true, she gets an A with 0.8 probability. When 2 out of the 4 are true, she gets an A with 0.7 probability. When just one of those is true, she gets an A with 0.5 probability. When none are true, she gets an A with 0.2 probability.
Below is the illustration of Alice’s Bayesian Network:
Given this network and the information in the story, answer the following questions:
Before we observe any evidence, which nodes are marginally independent of Alice’s ability to allocate adequate time per course (“adequate”)? Select all that apply (no partial credit):
marathon forgetful overloaded waters
dry out cram lucky empty dif cult staff slow prepared poker lectures early
浙大学霸代写 加微信 cstutorcs
Suppose Alice wants to leverage Variable Elimination to calculate the marginal probability of feeling prepared for a course’s exam (“prepared”) before seeing any data. Which nodes make up the smallest set that contains sufficient information to calculate this probability? Select all that apply (no partial credit).
marathon forgetful overloaded waters
dry out cram lucky empty dif cult staff slow prepared poker lectures early
A adequate
Which event nodes are in the Markov Blanket of the node “lucky?” Select all that apply (no partial credit).
marathon forgetful overloaded waters
dry out cram empty dif cult staff slow prepared poker lectures early
A adequate
Bayes Net Part B
Suppose we apply the network to Alice’s ML class, which starts at 9:45am. The assignments have been returned slowly, and there is no empty Lucky Charms box in Alice’s recycling bin after breakfast the morning of an exam. Do the probabilities of the following events go up, down, or remain unchanged within the Bayesian Network compared to the original story? Consider each statement independently (don’t combine information from different questions).
Below is the illustration of Alice’s Bayesian Network:
Instructions
Hint: you do not need to carry out full calculations to solve these.
Given this network and the additional information, answer the following questions:
At least one of Alice’s begonias dried out sometime this semester
Down Unchanged
The ML exam is difficult
Down Unchanged
Alice joins the poker club this semester, given that she does not feel prepared
Down Unchanged
Machine Learning Part A
You are developing a model to classify between tigers and leopards. As input, you pass a flattened 2×2 image to each of the fully connected neural networks as shown in the below picture and conduct backpropagation across multiple samples. There is one output. If the value of the output is >=0.5, then you classify the image as a tiger, else, it is a leopard.
(fig 1: Neural Network 1)
(fig 2: Neural Network 2) Note:
1 The Sigmoid function: S(x) = 1 + e − x
ReLU function: ReLU(x) = max(0, x)
Which neural network