Your cart is currently empty!
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 rst generate and solve simple mazes using the classical search algorithms (BFS/DFS/A ). Once you have written these algorithms, you will utilize…
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 rst 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.
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 nish.
Figure 2: Unsuccessful – No path exists from start to nish.
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
it should be lled or empty. When lling cells, exclude the upper left and lower right corners (the start and goal, respectively). It is convenient to de ne 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 speci ed 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
p
d((x1; y1); (x2; y2)) = (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)) = jx1 x2j + jy1 y2j: | (2) |
For any speci ed 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 bene cial for some of these questions to return additional information about how the algorithm ran as well.)
Questions:
empty and the path is clear; for p close to 1, the map is mostly lled 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 nding algorithm is most useful here, and why?
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?
Bonus 1) Why were you not asked to implement UFCS?
In the previous section, mazes were generated essentially distributing obstructions at random through the environ-ment. 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 di cult 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 con guration. If the result is harder to solve, keep this new con guration 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:
a.i) Length of solution path returned a.ii) Total number of nodes expanded a.iii) Maximum size of fringe during runtime
b.i) Length of solution path returned
b.ii) Total number of nodes expanded
b.iii) Maximum size of fringe during runtime
d.i) Length of solution path returned
d.ii) Total number of nodes expanded
d.iii) Maximum size of fringe during runtime
4