DSCI 6612: The Adventures of Mr. Bloop Case Study - Management Assignment Help

Assignment Task:

Task:

Q1. Operation Bloopy Freedom ( 14 points )
In the midst of an epic adventure, our favorite agent, Mr. Bloop, finds himself locked in a dungeon. Looking around, he finds only two objects in the room: a note and a flute. The note says: “play my favorite tune of 10 notes or less, and the door shall open with success”. Mr. Bloop tests the flute and finds out that it can play only 3 notes: D, E, G. Hence, Mr. Bloop’s freedom relies on finding the sequence of these three notes that unlocks the door.

As a diligent AI student, you want to help Mr. Bloop by formulating his predicament as a search problem:
• The initial state is silence (i.e., an empty sequence of notes)
• The successor function is to add one note (D, E, or G) to the sequence.
• The goal test is to see whether the resulting tune (i.e., sequence of notes) has unlocked the door or not. You also happen to know that there are 5 tunes that can unlock the door: GEDGE , GEDG, EGDEDGE, EDEDE, and DDDGGG.

• You can assume that if there is a tie between states, the note with alphabetical precedence wins (e.g., between E and G, E is expanded before G).

a) [3pts] Which of the 5 tunes above will be returned by breadth-first search? Why?

b) [3pts] Which of the 5 tunes will be returned by depth-first search? Why?

c) [4pts] Mr. Bloop has a feeling that some notes are more likely to be in the correct tune. You help him capture this feeling by assigning costs to each note: c(D) = 2, c(E) = 4, and c(G) = 6. With this cost structure, which of the above 5 tunes will be returned by uniform cost search? Why?

d) [4pts] Now assume that there is only one tune that can unlock the door, which is unknown as it is randomly selected from the space of all possible tunes ( with 10 notes or less). Also assume that all notes have the same cost ( e.g., c( D) = c( E ) = c( G) = 1). Given any heuristic, would A* search expand on average fewer, more, or the same number of states as depth-first search? Why?

Q2. Escape from Bloop Town (50 points)
In another adventure, Mr. Bloop finds himself behind the wheel of a bulldozer in the middle of an abandoned mining town, while holding a map of the town (Figure 1). The mining town consists of an n × n grid of cells, where some adjacent cells are blocked by walls; specifically, for any two adjacent cells (i, j) and (i 0 , j 0 ), let W ((i, j), (i 0 , j 0 )) = 1 if there is a wall between the two cells and 0 otherwise. For example, in Figure 1, W ((1, 1),(1, 2)) = 0 and W((1, 2),(1, 3)) = 1.
Mr. Bloop can either move to an adjacent cell if there’s no intervening wall with cost 1, or he can knock down a wall with the bulldozer with cost c without changing his position. Also, the bulldozer is quite rusty and can knock down at most b0 walls. Mr. Bloop's goal is to get from his initial position (i0, j0) to the exit at (n, n) with minimum cost.

(1, 1) (2, 1) (3, 1)

(1, 2) (2, 2) (3, 2)

(1, 3) (2, 3)
exit
(3, 3)

Figure 1: An example of a mining town. The goal is to go from the initial location (i0, j0) = (2, 2) to the exit (n, n) = (3, 3) with the minimum cost.

b. (10 points)
Solving the search problem above is taking forever and Mr. Bloop doesn’t want to be stuck in the mining town all day long. So he decides to use A*. (i) [5 points] Define a consistent heuristic function h(((i, j), b)) based on finding the minimum cost path using the relaxed state (i, j) where we assume Mr. Bloop has an infinite bulldozing budget and therefore does not need to track it. Show why your choice of h is consistent and what you would precompute so that evaluating any h(((i, j), b)) takes O(1) time and precomputation takes O(n 2 log n) time.

(ii) [5 points] Noticing that sometimes h is the true future cost of the original search problem, you wonder when this holds more generally. For what ranges of b0 and c would this hold? Assume for this part that there is a path that doesn’t require breaking down any walls.

≤ b0 ≤ c

Your lower bounds need not be tight, but you need to formally justify why they hold.

c. (15 points)
Having solved the search problem above, Mr. Bloop is eager to set out on his journey through the mining town, but he realizes that breaking down walls is harder than he thought. Suppose that each attempt to break down a wall has an  > 0 probability of failing. Recall that b0 is the maximum number of walls Mr. Bloop can break down, not the number of attempts, and each attempt to break down a wall has cost c.

(i) [5 points] Suppose that each attempt to break down a wall is independent (e.g., if you fail once, the next attempt at the same wall also has probability  of failing regardless of your previous failures). You are interested in minimizing the expected cost of exiting the maze. While the natural solution is to treat this as an MDP, it turns out you can still cast this problem as a search problem. In particular, define a modified Cost(((i, j), b), a) function, and write one sentence about why this choice gives Mr. Bloop the optimal policy.

(ii) [5 points] Suppose instead that each attempt to break down a wall is perfectly de-pendent (e.g., if you fail once, you will always fail to break down that wall). Let us model this problem as an MDP. What should the states of the MDP be? What is the number of states in the worst case as a function of b0 and n (use big-Oh notation)? In this problem suppose b0 << n.

(iii) [5 points] If the probability of successfully breaking down a wall is (1 − )/k, where k > 0 is the number of times Mr. Bloop has tried to break down a wall. What should the states of the MDP be now?

This DSCI 6612 Management Assignment has been solved by our Management Experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.

Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.