BiDirectional RRT

C++ module that explores a given environment area creating rapidly exploring random trees expanding towards each other and then determining a path to take while avoiding obstacles. This algorithm is used for a 2d environment. For determining the route, the robot will be treated as holonomic.

Random Object placement with no Optimizations example 1:

User Defined Object placement:

User Defined Object placement with path Optimizations:

Random Object placement with path Optimizations:

git clone https://github.com/JakeInit/RRT.git

Ensure all dependencies below are installed:

sudo apt-get update
sudo apt-get install lsb-release -y
sudo apt-get install -y \
  clang \
  g++ \
  doxygen \
  git \
  build-essential \
  linux-libc-dev \
  cmake \
  cmake-qt-gui \
  libusb-1.0-0-dev \
  libusb-dev \
  libudev-dev \
  libgtest-dev \
  freeglut3-dev \
  gcc \
  graphviz

json
sudo apt-get install libjsoncpp-dev

boost
sudo apt-get install libboost-all-dev

eigen3
sudo apt-get install libeigen3-dev

octomap
sudo apt-get install liboctomap-dev

libccd
git clone https://github.com/danfis/libccd.git
cd libccd
mkdir build && cd build
cmake -G "Unix Makefiles" ..
make
make install

fcl
git clone https://github.com/flexible-collision-library/fcl.git
cd fcl
mkdir build && cd build
cmake ..
make
make install

or on ubuntu
sudo apt-get install libfcl-dev

SFML
sudo apt-get install libopenal-dev
sudo apt-get install -y vorbis-tools
sudo apt-get install libvorbis-dev
sudo apt install libflac-dev

git clone https://github.com/SFML/SFML.git
cd SFML
mkdir build && cd build
cmake ..
make
make install

mkdir build && cd build
cmake ..
make
cd ..
./bin/rrtApplication

note: make can be run from the main repo directory. This will run cmake and make. <br />
Then just run ./bin/rrtApplication

1. loop_frequency_Hz: determines how fast the loop time of the application is run at
   
2. maxNodes: the max number of attempts to connect the trees
   
3. visualizerHeight_pix: visualizer window height in pixels,
   
4. visualizerWidth_pix: visualizer window width in pixels
   
5. stepDistance_m: max distance to expand the tree on each iteration
   
6. minStepDistance_m: min distance to expand the tree on goal iteration
   
7. boundaryHeight_m: the +/- max y values of the coordinate system
   
8. boundaryWidth_m: the +/- max x values of the coordinate system
   
9. maxObjects: max number of objects to be randomly generated in the map
   
10. minObjects: min number of objects to be randomly generated in the map
    
11. maxObjectSize_m: square objects are generated form 0.100m to a max size of this value
    
12. pathSmootherOn: attempts to smooth the path taken if enabled
    
13. UserDefinedObjectsOn Places user defined objects in graph instead of random placement
    
14. width_m: robot width
    
15. height_m: robot height
    
16. buffer_m: robot buffer for gap to leave betwen objects

The below is an example of user defined objects. The value "UserDefinedObjectsON" must be
set to true to use these. Otherwise random objects are created. Objects are defined by 2D
x, y coordinates. Any new object and any number can be added using the format below.

IMPORTANT: "User defined objects must be axis aligned for both x and y. Shapes must be square or rectangle.

"object_1": [
  [-2, -2],
  [-2, 2],
  [2, -2],
  [2, 2]
],
"object_2": [
  [-3, -3],
  [-2.5, -2.5],
  [-2.5, -3],
  [-3, -2.5]
]

1. User configurations exist in pathToRepo/RRT/json/config.json
2. Objects in visualizer will be white squares as well as borders
3. The robot in visualizer will be a blue square
4. The goal point in visualizer will be a red circle
5. The RRT in visualizer will made up of red line segments
6. The path taken in visualizer will be outlined in green
7. List of poses of path taken is written to pathToRepo/RRT/poses/poses.txt
8. Too many objects can make path impossible and impossible to place robot and goal point
9. Too large of objects can make path impossible and impossible to place robot and goal point