Lab 6: Sampling-based Path Planning

Initial Codebase for Gradescope Submission

Background

In robotics, a central challenge is motion planning—finding a collision-free path from a start position to a goal while avoiding obstacles. Sampling-based path planning tackles this problem by randomly sampling points in free space and incrementally building a tree or graph. This approach avoids explicitly computing the entire configuration space and scales more effectively to higher dimensions.

A widely used method in this family is the Rapidly-Exploring Random Tree (RRT), which grows a tree by steering from the nearest node toward random samples. Over time, many variants of RRT have been developed to improve efficiency and solution quality.

In this assignment, you will implement RRT and its bidirectional variant RRT-Connect in a 2D environment with obstacles, and learn how to generate collision-free paths using these algorithms.

Learning Objectives

By completing this assignment, you will:

Understand the fundamentals of sampling-based path planning.
Implement the RRT algorithm and extend it to RRT-Connect.
Compare single-tree and bidirectional tree planning approaches.

Environment Setup

Language: Python 3.9+
Required packages:
```
pip install numpy matplotlib
```
rrt.py – contains the scaffold for RRT.
rrt_connect.py – contains the scaffold for RRT-Connect.
replay.py – visualization utilities for replaying the planning process.
framework.py - include to compenstate code

Note: Obstacles are represented as circles (cx, cy, r) in a bounded 2D map (default size: [0,10] × [0,10]).

Assignment Tasks

Task 1: Collision Detection (40 pts)

Objective: Implement a function to determine whether a sampled node collides with any obstacle.

Description: You will complete the is_collision() function in framework.py. Given a 2D position and a list of circular obstacles (x, y, radius), your function should compute Euclidean distances, inflate each radius by a small tolerance, and return a boolean indicating if the position lies inside or on any inflated obstacle boundary.

Task 2: Extend Tree Node (40 pts)

Objective: Implement a function to extend from a current node toward a target by at most a specified step size.

Description: You will complete the cal_next_node_value() function in framework.py. Given a current node, a target/sample, and max_step, your function should compute the direction from the current node to the target and return the next node along that line. If the target is closer than max_step, extend directly to it; otherwise, move exactly max_step toward it.

Task 3: Bi-Tree Growth (20 pts)

Objective: Implement a helper to alternate growth between two trees for bidirectional planning.

Description: You will complete the swap_trees() function in framework.py. Each time it is called, the function should toggle a boolean swap_flag and return the two trees in reversed order. This enables the planner to extend alternately from the start tree and the goal tree across iterations.

Implementation Guidelines

Code Structure

Only modify code within ## TODO sections in framework.py
Do not change function signatures or import statements
Maintain consistent tensor shapes and data types

Debugging Tips

Use breakpoint() to check intermediate results
Visualize intermediate results when possible

Hand-in Requirements

Submission Format

Submit only one file: framework.py
Platform: Gradescope autograder

File Requirements

Your framework.py must contain all implemented functions
Do not modify function signatures or imports
Include necessary comments explaining your implementation approach

Autograder Testing

Your submission will be tested against multiple test cases
Partial credit will be awarded for partially correct implementations
Timeout limit: 10 minutes in total