Robot Motion Planning Algorithms

A collection of 4 different motion planning methods for a differential drive on a 2D maze example.

This is a motion planning repo adopted from HW5 of CSE276C Mathematics in Robotics (FA22) at UCSD. Following motion planning algorithms are involved:

  • Dijkstra’s algorithm
  • Voronoi diagram path planning
  • Probabilistic roadmap (PRM) path planning
  • Rapidly exploring random tree (RRT)

GitHub repo here (Note: the project repo is NOT permently public. It could be set to private as required for academic intergrity. This page demostrates some main results from my project.)

Shortest Path

The shortest path found by Dijkstra's algorithm. The figure on the top shows the shortest path in the configuration space when robot facing east, west, south, or north. The figure on the bottom shows the shortest path in the configuration space when robot facing northeast, northwest, southeast, southwest.

Safest Path

The safest path found by using Voronoi diagram.

Probabilistic Road-Map (PRM)

The path found by using PRM with 100 samples.

Rapidly-Exploring Random Trees (RRT)

The path found by using RRT with the step size (extension length to put the new node) equals to 5 and the probability of sampling the goal-point equals to 5%.