The goal
This project explored two sides of robot autonomy. The main study built sampling-based motion planners, progressing from a point robot moving around obstacles to an L-shaped body that also had to rotate through a narrow passage. A smaller grid-world exercise compared value iteration and policy iteration as a complementary study in decision-making under uncertainty.
SYSTEM ARCHITECTURE
Point-robot RRT
sample → find nearest node → steer → check collisions → recover pathA goal-biased RRT expanded through a cluttered 2D workspace. Candidate edges were rejected when they crossed an obstacle, and a feasible route was recovered by tracing parent links once the tree reached the goal.
Oriented L-body RRT
sample position and angle → transform body → check its edges → extend treeThe planner was extended to include orientation and the full outline of an L-shaped body. Every candidate pose transformed the body geometry before collision testing, allowing the planner to find a route that rotated through a constrained opening.
Supporting 4 × 4 MDP
model uncertain moves → update state values → extract policy → compare methodsA stochastic grid world provided a compact test of decision-making with uncertain motion. Value iteration and policy iteration were implemented from the same transition and reward model and produced the same final route around the obstacle.
Development
- STAGE 01
Grow a point-robot tree to the goal
Implemented goal-biased RRT expansion, nearest-node search, bounded steering, obstacle checks, and parent-based path recovery.
- STAGE 02
Study planning parameters in clutter
Tested the point planner in simple and randomly cluttered maps, then compared runtime across obstacle counts and steering step sizes.
- STAGE 03
Plan for an L-shaped body in (x, y, θ)
Extended the planner from points to full poses, transforming the L-shaped body at every sample before checking its edges for collisions.
- STAGE 04
Solve the 4 × 4 MDP with value iteration
Implemented value iteration and policy iteration on the same stochastic grid model, then compared their resulting policies and runtime.
The hardest parts
A point path is not a robot path
A route that clears an obstacle as a line can still be impossible for a finite body. Adding orientation required transforming the complete L-shaped outline and testing its edges at every candidate pose, making collision checking a central part of the planner rather than a simple boundary test.
Planning parameters change both speed and reachability
Larger steering steps were faster on the tested maps, while smaller steps produced more variable runtimes. Because RRT is stochastic and coarse steps can miss useful configurations, these results show a project-specific tradeoff rather than a universally best setting.
The two studies answer different planning questions
RRT searched continuous geometry for a feasible path, while the grid-world methods selected actions from a known stochastic model. Keeping them separate makes the scope clear: one demonstrates motion-planning implementation; the other demonstrates dynamic-programming fundamentals.
Results
- The point-robot planner recovered collision-free paths in both a single-obstacle map and a randomly cluttered field.
- A parameter sweep showed how obstacle count and steering step size affected runtime on the tested maps.
- The oriented-body planner rotated an L-shaped footprint through a narrow wall opening without intersecting the obstacles.
- Value iteration and policy iteration produced the same obstacle-avoiding route in the stochastic grid world.
What I learned
Representing the robot as a finite body changed both the state space and the collision-checking problem; a valid point path was no longer enough.
Planner settings have geometric consequences. Faster expansion on one map does not guarantee better exploration or clearance on another.
RRT and dynamic programming address different layers of autonomy: one searches for feasible motion, while the other chooses actions from a known model.
Technical archive
Point-robot RRT notebook
Point-robot RRT implementation, single- and multi-obstacle paths, and the step-size runtime sweep.
L-shaped body RRT notebook
Configuration-space extension with (x, y, θ) nodes, vertex transforms, and a narrow-passage wall.
Value and policy iteration notebook
4 × 4 stochastic grid world with value iteration, policy iteration, and a greedy-path visualization.