Planning and Decision-Making
in Robotics
Planning and Decision Making in Robotics
(16-782) Homework Assignments at CMU
CATCHING A MOVING TARGET
Language: C++
The goal of this assignment was to catch a moving target in an 8-connected grid world. Each cell in the grid world had a cost associated with visiting it. Ideally, the goal was to minimize this cost, but the main priority is to catch the target. The target moved one step on a known predefined trajectory once every real world second. This constrained our planner, as it was called every time the robot took one step. Because of this, part of my strategy was to minimize the runtime of my planner, since if it took more than 1 second to run each time, it would make it very hard for the robot to catch up with the target. When the target reached the end of its trajectory, it disappeared and was unable to be caught.
​
To prioritize the ability of the robot to reach the target, the planner first checked if the robot is on the future trajectory of the target. If it was, then the robot moved backwards along the target trajectory, ensuring that the target will be caught. During this step of checking all the future trajectory points, the planner also flags if there is a reachable place on the trajectory as early as possible. This coordinate is saved as possX, possY for later usage.
If the robot is not on the future trajectory of the target, a first call to A* is made to find the least cost path to the final target position, assuming the cost of all traversable cells is 1. This step checked if the final target position was reachable within the timeframe of the trajectory. If the length of the trajectory found by this call to A* plus some buffer value is longer than the amount of time left, then the robot would follow this trajectory to ensure the target is able to be reached. This trajectory is also followed if the amount of time for the planner to run up to this step has exceeded a certain threshold.
​
Otherwise, the planner uses A* to find a trajectory to the possX, possY coordinate pair saved from earlier. Then the robot follows this trajectory instead.
​
Below are some examples showing results of the planner. The pink is the target trajectory, and the green is the robot trajectory. The legend on the right of each map shows the cost of cells being traversed.
​
​
In all three examples above, my robot reaches the target. In the first two images, though it cannot be seen here, the robot reaches the target well before the end of the target's trajectory. In the last picture, the target does not move, but stays in place for a number of seconds before disappearing. There is not enough time for the robot to go completely around the high cost area. However, the robot still tries to take a path that both successfully reaches the target and minimizes the amount of time spent traversing high cost cells.
PLANNING FOR AN N-DOF ARM
Language: C++
In this assignment, the goal was to implement four different probabilistically complete planners for an N-DOF robotic arm. Given a configuration space, starting joint angles, and goal joint angles, our planners had to navigate the arm to the goal without intersecting obstacles.
​
The four planners I implemented were RRT, RRT-Connect, RRT*, and PRM. Each of these planners were run 4 times each on 5 different sets of start/goal points. Thus, each planner was run 20 times each, and their results were compiled into a chart, as seen below, displaying the averages.
​
​
For PRM, I kept generating new random nodes for the tree until I reached a hyper-parameter of N valid vertices. I then used A* to find the final path between start and end nodes.
​
Note, that by changing hyper-parameters, such as epsilon, these results can change.
​
Each of these algorithms have their advantages. The RRT varieties are of better use when doing one shot planning. That is, when the configuration space of a robot may change between each plan, and the robot needs to create a new valid graph for planning each time. PRM is more useful when multiple paths need to be computed that reuse the same configuration space. RRT-Connect is clearly the most successful at generating a solution faster. However, the cost of the path is greater than using something like RRT*.
SYMBOLIC PLANNING WITH STRIPS
Language: C++
In this assignment, I implemented a generic planner that is capable of solving any planning problem that can be represented with STRIPS (Stanford Research Institute Problem Solver), without knowledge of the environment. Given a set of STRIPS defined symbols, action names, action preconditions, action effects, start conditions, and goal conditions my planner was able to successfully return a set of valid actions that would take the environment from the start conditions to the goal conditions.
​
To solve this assignment, I used an A* search with an implicitly defined graph. My planner was tested on multiple environments, such as a basic Blocks World and a more complicated Blocks and Triangles World. Blocks and Triangles is the same as Blocks World, but there is the additional component of triangles where items cannot be placed on top of these triangle pieces.
​
For A*, I compared 3 different heuristics: the 0 heuristic, the basic heuristic, and the empty-delete-list heuristic. The basic heuristic for a state is defined as h(s) = # of literals not yet satisfied between the current condition and the goal condition. The empty-delete-list heuristic defines h(s) by solving a simplified sub-problem between the current conditions and the goal conditions.
​
​
​
​
​
In theory, the empty-delete-list heuristic is good because it has the chance of decreasing the amount of time it takes to find the plan. It is admissible too, so it guarantees that the path returned will be optimal. We can even see that it does help to expand fewer states. However, because it has to solve so many sub problems to calculate the heuristics, it may take longer depending on the environment. On the other hand, the basic heuristic does not guarantee optimality, because it is not admissible. However, it is still complete -- it will find a solution if one exists, and in these particular cases, it is much faster, despite having to expand a more states.