Computer Science Department –

CS 520: Assignment 1 – Path Planning and Search Algorithms

This project is intended as an exploration of various search algorithms, both in the traditional application of path

planning, and more abstractly in the construction and design of complex objects. You will first generate and solve

simple mazes using the classical search algorithms (BFS/DFS/A∗

). Once you have written these algorithms, you

will utilize other search algorithms to generate mazes that your initial algorithms have trouble solving.

1 Part 1: Path Planning

Generating Environments: In order to properly compare these algorithms, they need to be run multiple times

over a variety of environments. A map 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 – A path exists from start to finish.

Figure 2: Unsuccessful – No path exists from start to finish.

Maps 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

1

Computer Science Department – Rutgers University Fall 2018

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 3: Maps generated with p = 0.1, 0.3, 0.5 respectively.

Path Planning: Once you have the ability to generate maps with specified parameters, implement the ability to

search for a path from corner to corner, using each of the following algorithms:

• Depth-First (Graph) Search

• Breadth-First (Graph) Search

• A∗

: where the heuristic is to estimate the distance remaining via the Euclidean Distance

d((x1, y1),(x2, y2)) = p

(x1 − x2)

2 + (y1 − y2)

2. (1)

• A∗

: where the heuristic is to estimate the distance remaining via the Manhattan Distance

d((x1, y1),(x2, y2)) = |x1 − x2| + |y1 − y2|. (2)

For any specified map, applying one of these search algorithms should either return failure, or a path from start to

goal in terms of a list of cells taken. (It may be beneficial for some of these questions to return additional information

about how the algorithm ran as well.)

Questions:

1) For each of the implemented algorithms, how large the maps can be ( in terms of dim ) for the algorithm to

return an answer in a reasonable amount of time (less than a minute) for a range of possible p values? Select

a size so that running the algorithms multiple times will not be a huge time commitment, but that the maps

are large enough to be interesting.

2) Find a random map with p ≈ 0.2 that has a path from corner to corner. Show the paths returned for each

algorithm. (Showing maps as ASCII printouts with paths indicated is sufficient; however 20 bonus points are

available for coding good visualizations.)

3) For a fixed value of dim as determined in Question (1), for each p = 0.1, 0.2, 0.3, . . . , 0.9, generate a number of

maps and try to find a path from start to goal – estimate the probability that a random map has a complete

path from start to goal, for each value of p. Plot your data. Note that for p close to 0, the map is nearly

empty and the path is clear; for p close to 1, the map is mostly filled and there is no clear path. There is some

threshhold value p0 so that for p < p0, there is usually a clear path, and p > p0 there is no path. Estimate p0.

Which path finding algorithm is most useful here, and why?

2

Computer Science Department – Rutgers University Fall 2018

4) For a range of p values (up to p0), generate a number of maps and estimate the average or expected length of

the shortest path from start to goal. You may discard all maps where no path exists. Plot your data. What

path finding algorithm is most useful here?

5) For a range of p values (up to p0), estimate the average length of the path generated by A∗

from start to goal

(for either heuristic). Similarly, for the same p values, estimate the average length of the path generated by

DFS from start to goal. How do they compare? Plot your data.

6) For a range of p values (up to p0), estimate the average number of nodes expanded in total for a random map,

for A∗ using the Euclidean Distance as the heuristic, and using the Manhattan Distance as the heuristic. Plot

your data. Which heuristic typically expands fewer nodes? Why? What about for p values above p0?

7) For a range of p values (up to p0), estimate the average number of nodes expanded in total for a random map

by DFS and by BFS. Plot your data. Which algorithm typically expands fewer nodes? Why? How does either

algorithm compare with A∗

in Question (6)?

Bonus 1) Why were you not asked to implement UFCS?

2 Part 2: Building Hard Mazes

In the previous section, mazes were generated essentially distributing obstructions at random through the environment. Examining these mazes, you found that certain algorithms had various advantages and disadvantages. In this

section, you are going to try to construct mazes that are hard for these algorithms to solve, either in terms of a) the

length of the shortest path, b) total number of nodes expanded, or c) the maximum size of the fringe.

One potential approach would be the following: for a given solution algorithm, generate mazes at random and solve

them, and keep track of the ‘hardest’ maze you’ve seen so far. However, this search approach necessarily does not

learn from any of its past results – having discovered a particularly difficult maze, it has no mechanism for using that

to discover new, harder mazes. Every round starts again from scratch.

One way to augment this approach would be a random walk. Generate a maze, and solve it to determine how

‘hard’ it is. Then at random, add or remove an obstruction somewhere on the current maze, and solve this new

configuration. If the result is harder to solve, keep this new configuration and delete the old one. Repeat this process.

This has some improvements over repeatedly generating random mazes as above, but it can be improved upon still.

For this part of a project, you must design a local search algorithms (other than a random walk) and implement

it to try to discover hard to solve mazes. Mazes that admit no solution may be discarded, we are only interested in

solvable mazes.

Questions:

8) What local search algorithm did you pick, and why? How are you representing the maze/environment, to be

able to utilize your chosen search algorithm? What design choices did you have to make to apply this search

algorithm to this problem?

9) Unlike the problem of solving a maze, for which the ‘goal’ is well-defined, it is difficult to know when we have

constructed the ‘hardest’ maze. That being so, what kind of termination conditions can you apply to your

search algorithm to generate ‘hard’ if not the ‘hardest’ mazes? What kind of shortcomings or advantages do

you anticipate your approach having?

3

Computer Science Department – Rutgers University Fall 2018

10) For each of the following algorithms, do the following: Using your local search algorithm, for each of the following

properties indicated, generate and present three mazes that attempt to maximize the indicated property. Do

you see any patterns or trends? How can you account for them? What can you hypothesize about the ‘hardest’

maze, and how close do you think you got to it?

a) DFS

a.i) Length of solution path returned

a.ii) Total number of nodes expanded

a.iii) Maximum size of fringe during runtime

b) BFS

b.i) Length of solution path returned

b.ii) Total number of nodes expanded

b.iii) Maximum size of fringe during runtime

c) A∗ with Euclidean Distance Heuristic

c.i) Length of solution path returned

c.ii) Total number of nodes expanded

c.iii) Maximum size of fringe during runtime

d) A∗ with Manhattan Distance Heuristic

d.i) Length of solution path returned

d.ii) Total number of nodes expanded

d.iii) Maximum size of fringe during runtime

4

## Reviews

There are no reviews yet.