CS 440程序代做、代写algorithm编程、代做Python，Java编程

日期：2021-02-17 04:23

Computer Science Department - Rutgers University Spring 2021

CS 440: This Maze is on Fire 16:198:440

A maze will be a square grid of cells / locations, where each cell is either empty or occupied. An agent wishes to

travel from the upper left corner to the lower right corner, along the shortest path possible. The agent can only

move from empty cells to neighboring empty cells in the up/down direction, or left/right - each cell has potentially

four neighbors.

Figure 1: Successful and Unsuccessful Maze Environments.

Mazes may be generated in the following way: for a given dimension dim construct a dim x dim array; given a

probability p of a cell being occupied (0 < p < 1), read through each cell in the array and determine at random if

it should be filled or empty. When filling cells, exclude the upper left and lower right corners (the start and goal,

respectively). It is convenient to define a function to generate these maps for a given dim and p.

Figure 2: Maps generated with p = 0.1, 0.3, 0.5 respectively.

1

Computer Science Department - Rutgers University Spring 2021

Preliminaries

? Problem 1: Write an algorithm for generating a maze with a given dimension and obstacle density p.

? Problem 2: Write a DFS algorithm that takes a maze and two locations within it, and determines

whether one is reachable from the other. Why is DFS a better choice than BFS here? For as large a

dimension as your system can handle, generate a plot of ‘obstacle density p’ vs ‘probability that S can

be reached from G’.

? Problem 3: Write BFS and A? algorithms (using the euclidean distance metric) that take a maze and

determine the shortest path from S to G if one exists. For as large a dimension as your system can

handle, generate a plot of the average ‘number of nodes explored by BFS - number of nodes explored by

A?

’ vs ‘obstacle density p’. If there is no path from S to G, what should this difference be?

? Problem 4: What’s the largest dimension you can solve using DFS at p = 0.3 in less than a minute?

What’s the largest dimension you can solve using BFS at p = 0.3 in less than a minute? What’s the

largest dimension you can solve using A? at p = 0.3 in less than a minute?

Consider, as you solve these three problems, simple diagnostic criteria to make sure you are

on track. The path returned by DFS should never be shorter than the path returned by BFS.

The path returned by A? should not be shorter than the path returned by BFS. How big can and

should your fringe be at any point during these algorithms?

However, we are are not just interested in solving static mazes - these mazes are on fire, actively burning down around

you. We model this in the following way: for every move the agent makes, the fire then advances (described below),

and they alternate back and forth. The agent would like to exit the maze prior to running into the fire. Under this

model, while an agent might utilize a search algorithm to generate an optimal path through the the current state

of the maze (analyzing the current state and planning a future path through it), it will not necessarily be valid for

future states of the maze. This means that while the agent may plan a short path through the maze, whether or not

it will be able to take that path depends on the fire. In this case, the environment is dynamic, changing over time.

We model the advancement of the fire in the following way: any cell in the maze is either ‘open’, ‘blocked’, or ‘on

fire’. Starting out, a randomly selected open cell is ‘on fire’. The agent can move between open cells or choose to

stay in place, once per time step. The agent cannot move into cells that are on fire, and if the agent’s cell catches

on fire it dies. But each time-step the agent moves move, the fire may spread, according to the following rules: For

some ‘flammability rate’ 0 ≤ q ≤ 1

? If a free cell has no burning neighbors, it will still be free in the next time step.

? If a cell is on fire, it will still be on fire in the next time step.

? If a free cell has k burning neighbors, it will be on fire in the next time step with probability 1 ? (1 ? q)

k

.

We might express this with the following pseudocode for advancing the fire one step:

2

Computer Science Department - Rutgers University Spring 2021

def advance_fire_one_step(current maze):

create a copy of the current maze

for every (x,y) in the current maze:

if (x,y) is not on fire in current maze and (x,y) is not an obstacle:

count the number of neighbors of (x,y) in current maze that are on fire

store that as k

prob = 1 - (1-q)^k

if random() <= prob

mark (x,y) as on fire in maze copy

return maze copy

Note, for q = 0, the fire is effectively frozen in place, and for q = 1, the fire spreads quite rapidly. Additionally,

blocked cells do not burn, and may serve as a barrier between the agent and the fire.

How can you solve the problem (to move the agent from upper left to lower right, as before) in this situation?

Consider the following base line strategies:

Strategy 1) At the start of the maze, wherever the fire is, solve for the shortest path from upper left to lower right, and

follow it until the agent exits the maze or burns. This strategy does not modify its initial path as the fire

changes.

Strategy 2) At every time step, re-compute the shortest path from the agent’s current position to the goal position, based

on the current state of the maze and the fire. Follow this new path one time step, then re-compute. This

strategy constantly re-adjusts its plan based on the evolution of the fire. If the agent gets trapped with no

path to the goal, it dies.

For each strategy, for as large a dimension as your system can handle, and obstacle density p = 0.3, generate a plot

of ‘average successes vs flammability q’. Which is the superior strategy? For each test value of q, generate and solve

at least 10 mazes, restarting each 10 times with new initial fire locations. Note: Please discard any maze where

there is no path from the start to the goal node. Additionally, please discard any maze where there is no path from

the initial position of the agent to the initial position of the fire - for these mazes, the fire will never catch the agent

and the agent is not in danger. Your prior functions will be useful here.

Come up with your own strategy to solve this problem (+5 points are available if you come up with a clever acronym

for your strategy), and try to beat both the above strategies. How can you formulate the problem in an approachable

way? How can you apply the algorithms discussed? Note, Strategy 1 does not account for the changing state of the

fire, but Strategy 2 does. But Strategy 2 does not account for how the fire is going to look in the future. How could

you include that?

A full credit solution must take into account not only the current state of the fire but potential future states of the

fire, and compare the strategy to Strategy 1 and Strategy 2 on a similar average successes vs flammability graph.

Additionally, while your strategy may increase survivability, analyze the time costs of your strategy compared to the

other two - in a real burning maze, you have limited time to make your decisions about where to move next. Be

clear and explicit in your writeup, presenting your reasoning and ideas behind your strategy.

3

Computer Science Department - Rutgers University Spring 2021

? Problem 5: Describe your improved Strategy 3. How does it account for the unknown future?

? Problem 6: Plot, for Strategy 1, 2, and 3, a graph of ‘average strategy success rate’ vs ‘flammability

q’ at p = 0.3. Where do the different strategies perform the same? Where do they perform differently?

Why?

? Problem 7: If you had unlimited computational resources at your disposal, how could you improve on

Strategy 3?

? Problem 8: If you could only take ten seconds between moves (rather than doing as much computation

as you like), how would that change your strategy? Describe such a potential Strategy 4.

Your report needs to be clear to the point that the grader can understand and reconstruct your

strategy from your description. If they can’t, they’re justified in giving no credit, and you’ll

have to argue for it back later.

4