Path Planning

Plan for today

• Learn about our path planning system
• Download, compile, and run our RRT repository

High Level Overview

What is Path Planning

• Our robots need to know how to get from a start point to an end point
• Our path-planning algorithm of choice is the RRT (Rapidly-Exploring Random Tree)

How the RRT works

1. Start building our tree by placing a root node at the destination
2. Randomly select some coordinate in the position space
3. Identify existing node in the tree that is nearest to that coordinate
4. Add new node in tree branching from nearest node to random coordinate
5. Repeat 2-4 until a node is created at our destination. The series of connected nodes from root to destination forms the path that the robot will follow
6. Smooth out path with overlaid Bézier curve

Sounds really inefficient

• Why waste computation time branching out in random directions?
• What advantages could there be in random branching?
• Why not use a less computationally intense algorithm like A*?

Advantages of RRT

• Specialized for continuous configuration spaces
• Can handle kinodynamic constraints
• Algorithm can be modified for various needs and preferences

Repository Code

• rrt-viewer
• rrt

rrt-viewer

• Displays window for running RRT
• Uses QT for graphics

rrt

• Contains RRT implementation
• Defines state space
• Bi-RRT
  • We execute two RRTs, one rooted at the start node and the other at the end node

Download RRT

• Our rrt repository is located at http://github.com/RoboJackets/rrt
• On your terminal, type in:

git clone http://github.com/RoboJackets/rrt rrt

• DO NOT execute this command in your robocup repository

Compile and run RRT

cd rrt
git clone http://github.com/RoboJackets/rrt rrt
make
./build/rrt-viewer

How to use RRT

• Drag start and end points to desired locations
• Drag around the plane space to draw and remove obstacles
• Click "run" to run until the rrt finds a valid path, or "step" to execute a single rrt iteration
• Click "reset" once to delete the tree, twice to delete the previously calculated path

Tweaking parameters

Biases

• Increasing Goal Bias
  • Random branching has tendency to branch directly towards goal instead
• Increasing Waypoint Bias
  • Random branching has tendency to branch towards Bézier curve waypoints of previous paths
• Goal Bias + Waypoing Bias must sum to at most 1.0

Adaptive Stepsize Control

• Stepsize now dynamically changes based on whether there are obstacles nearby
• Requires extra computation time to locate nearby obstacles
• Having larger stepsizes when possible reduces total iteration count, which reduces computation time
• Obstacle-light environments benefit the most from this enhancement

Any questions?