Planning and Decision-making in Robotics
Skills: C++, Python, Planning
In the Fall 2022 semester I took 16-782: Planning and Decision-making in Robotics at CMU. This course focused on developing a foundation in planning algorithms and their variations.
​
Over the course of the semester I coded several planning algorithms primarily in C++ for assignments in the course.
Assignment 1: Catch Me if You Can
Algorithms Implemented: Dijkstra's Algorithm, A* Search Algorithm, Weighted A* Search Algorithm
Description: For this assignment, we were provided with known maps of varied cost per pixel. The goal was to, given a point target with a known trajectory over time and a point robot with a starting position, implement a grid based planning algorithm that allows the robot to catch the target in the time it takes for the robot to plan the path and traverse it in simulation. Otherwise, if the robot is unable to do so, then robot should report that it is unable to catch the target. I implemented Dijkstra's Algorithm to generate a heuristics map from the target trajectory across the map, then used that heuristics map alongside time as a heuristic for weighted A* Search to find a desired trajectory for the robot to follow.
On the right are samples of my implementation running on several 2D maps. The light green "R" represents the robot while the pink "T" represents the target as they both move along their respective trajectories. The cost of each pixel varies from dark blue (cost of 1) to red (cost of 100).
​
Maps 1 through 4 demonstrate the success of my algorithm on maps of with different levels of complexity, starting with smaller maps with minimum and maximum cost cells only as well as an identical map but with varied costs, then once more with an increasingly complex map space.
​
Map 5 demonstrates my algorithm taking a slightly higher cost path in order to catch the target in time, while Map 6 demonstrates my algorithm taking a detour path to incur lower cost.
Map 1
Assignment 2: Planning for a High DoF Robot Arm
Algorithms Implemented: RRT, RRT-Connect, RRT*, PRM
Description: For this assignment, we are given a robot arm of varied degrees of freedom (DoF) in a configuration space with defined obstacles. The goal was to plan a path in the configuration space of the robot's joint angles in order to reach a desired ending joint angle configuration from any starting configuration, or to otherwise report if a path is impossible to find. In this assignment, I implemented Rapidly-exploring Random Trees (RRTs), variations of RRT such as RRT-Connect and RRT*, and Probabilistic RoadMaps (PRMs) in order to compare and contrast the performance between RRT variations as well as the difference between algorithms suited for one shot planning (RRT) and repeated map planning (PRMs).
​
Below are visualizations of the robot arm running from a start to end joint configuration using plans from my implementation, with cost calculated as the euclidean difference between joint angles in the joint angle space. RRT-Connect yielded the fastest solution from my implementation while incurring a slightly higher cost, RRT gave a slightly slower solution with varied cost across different runs, while RRT* resulted in an even slightly slower solution but with the lowest cost of the three. PRM took the longest time given that it had to construct the entire road map in joint angle space but, due to the large number of nodes generated, I was able to use A* Search on the road map to yield the lowest cost path across all of the algorithms.
RRT
RRT-Connect
RRT*
PRM
Assignment 3: Symbolic Planning
Algorithms Implemented: A*, Weighted A*, STRIPS Representation
Description: For this assignment, we are provided with a Stanford Research Institute Problem Solver (STRIPS) representation of several environments, such as a standard Blocks World. Each environment has an initial configuration and desired goal configuration, as well as sets of action preconditions with respect to and associated effects on the state of the environment. I implemented a generic symbolic planner which, provided any environment with associated conditions and actions, outputs the full sequence of actions to get from the initial configuration to the goal configuration. In addition, I applied a weighted heuristic and an empty-delete list heuristic to increase the performance of my planner, successfully reducing the run time, number of expanded search states, or both metrics simultaneously across all environments.