FlatLand: Graph Search Navigation
FlatLand implements four graph traversal algorithms — BFS, DFS, Dijkstra, and Random — to navigate a point robot through a 2D world filled with obstacles, developed as part of the RBE550 Motion Planning course at Worcester Polytechnic Institute. The project compares algorithm behavior and performance across environments with varying obstacle coverage densities.
Algorithms
Breadth-First Search (BFS) — Explores nodes layer by layer, guaranteeing the shortest path in terms of number of edges. Effective but memory-intensive in large environments.
Depth-First Search (DFS) — Explores as deep as possible before backtracking. Finds a path quickly but does not guarantee optimality.
Dijkstra’s Algorithm — Weighted graph search that expands nodes in order of cumulative cost, guaranteeing the shortest path in terms of total distance.
Random Traversal — Selects neighbors uniformly at random, serving as a baseline to compare against structured search strategies.
Coverage Analysis
Each algorithm was evaluated across environments with increasing obstacle coverage (5% to 40%), measuring success rate and path quality.
5% Coverage
10% Coverage
20% Coverage
30% Coverage
35% Coverage
40% Coverage
Performance Comparison
