Yale Campus Navigation Planner

Example Output

Motivation

When I first came to Yale, I remember I never knew how to get from one place to another. I would rely on google maps to tell me how to get from my dorm to my class on science hill to the nearest dining hall. So when thinking about how planning algorithms can be used, I was drawn to building an algorithm that could find a path between places on campus.

After finding the map of campus shown above, and blocking out the areas outside of campus, the abstract idea of navigating through campus became confined to a 2D continuous space. From here, I had to choose between a selection of continuous space planning algorithms: probabilistic roadmap (PRM), rapidly-exploring random tree (RRT), RRT-Connect, and RRT*. I ultimately chose RRT-Connect.

Why RRT-Connect?
RRT-Connect is chosen because it is faster than other algorithm options and reliable in corridor-like environments like streets which are straight.

Usage

1. Clone this github repository

2. (Optional) create/activate a virtualenv: python3 -m venv .venv && source .venv/bin/activate

3. Install dependencies: pip install -r requirements.txt

4. Run the planner (The start and goal coordinates must be free space [aka not blue]. Refer to the pixel grid reference to find appropriate coordinates.):

python3 src/main.py --start 500 900 --goal 900 100 --max-iters 3000 --step-size 10 --gif outputs/yale_run.gif --seed 42

5. See the results in the outputs folder.

Pixel Grid Reference

To help pick coordinates, the map below marks every 100 pixels on the x and y axis.

Problem Statement

Given:

• A campus map image,
• A start location and goal location specified by (x, y) coordinates,
• A feasibility constraint that motion is allowed outside of buildings and on campus

Plan a collision-free path using RRT-Connect and produce:

1. A GIF that shows the incremental growth of both RRT trees,
2. An image that highlights the final connecting path once found.

High-Level Approach

1. Map Representation

   • The campus map is loaded as an image.
   • A binary free-space mask is created where:
     • White/light pixels (streets, lawns) = feasible
     • All other pixels (buildings, off campus locations) = obstacles

2. State Space

   • States are continuous (x, y) pixel coordinates.
   • Sampling is uniform over image bounds with rejection via feasibility checks with the free space mask.

3. Planning Algorithm

   • Use RRT-Connect:
     • Two trees grow simultaneously from start and goal.
     • Each iteration attempts add a vertex at a random sample state (_add_vertex) and then connect the each tree toward the new node (try_connect)
   • Feasibility is enforced via:
     • Point feasibility (is_state_feasible)
     • Edge feasibility (is_line_segment_feasible) that samples points between the source and destination of the line segment
   • Shortcuts
     • Sample points on the final path to create a straighter, shorter path

4. Visualization

   • Each iteration renders:
     • Newly added vertices
     • Tree vertices and edges
   • Frames are stacked and exported as an animated GIF.
   • Final path is highlighted in yellow.

Next Steps

• Support semantic destinations: instead of providing coordinates, allow the user to set the goal as "Yale Art Gallery", "Yale Health", or "CEID"
• Clean up map annotations so that the algorithm keeps space taken by street name labels as free space
• Estimate the time it takes to get from the final start to goal path based on the distance (aka cost) of the final path