rrt_2d

rrt_2d

Overview

This is a basic graph based rapidly-exploring random tree (RRT) search implementation in C++17.
The graph structure was implemented using Boost Graph Library. Nodes and Edges are user defined structures. The graph was configured for bidirectional architecture. The terminal arguments parsing is done using Boost Program Option Library.

See the SAMPLE_RUNS.md file to see graph output of RRT search on environment defined by the obstacles file available in inputs. The output files of the search are saved in outputs.

There main search functions is defined in search.h. This functions implement the RRT search.

std::pair<int, bool>
    search(const Point2D &start, const GoalZone &goal, Graph &g, Workspace &w_space, const ObstacleVec &obs_vec,
           const std::function<bool(Point2D, Point2D, const CircleObstacle&)> &collision_func,
           const double eps = 1, const int iter_lim = 1e8, const int verbose = 0);

An example RRT search can be executed by compiling and running the rrt.cpp file. See the Run Instructions below for more details on building and running the project.

The code was written to allow a desired level of configurability. Run the code with -h/--help tag to know more.

./cmake-build-release/rrt_2d -h
Allowed options:
  -h [ --help ]                               Print the help message
                                              
  -s [ --start ] arg (=x: 0, y: 0 )           Start node coordinate as (x, y)
  -g [ --goal ] arg (=x: 40, y: 40 , r: 1 )   Goal node coordinate as (x, y, r)
  -b [ --bias ] arg (=0)                      The goal bias. Probability in range [0, 1]
  -e [ --epsilon ] arg (=1)                   The maximum distance covered by a new trajectory during exploration.
  -i [ --iter_lim ] arg (=100000000)          The maximum number of exploration iterations allowed.
  -r [ --rand_seed ] arg (=-1)                The seed for the random number generator. -1 would mean 
                                              non-deterministically random.
  -v [ --verbose ] [=arg(=1)] (=0)            Verbosity. Choose between 0, 1, 2 and 3
  -o [ --obs_fp ] arg (=obstacle.txt)         Relative/absolute path to the obstacle file
  -p [ --path_fp ] arg (=path_output.txt)     Relative/absolute path to the Path output file
  -t [ --search_fp ] arg (=search_output.txt) Relative/absolute path to the Search output file

Also, the program can be compiled to use a collision detection function from a list of collision detection functions defined in search.h. Some examples of collision detection function are: collision_check.

Run Instructions

For Ubuntu:
Option 1: (Execute the build_script.sh and run_script.sh)

# open this directory
cd <path to this directory>

# build the project
./build_script.sh

# run the a_star algorithm for some sample inputs
./run_script.sh

Option 2: (Build and run the project yourself)

# open this directory
cd <path to this directory>

# view the CMakeLists.txt file of the sub-project
cat ./CMakeLists.txt

# make sure proper directories are included in the CMakeLists.txt file.
<use code editor of your preference to edit CMakeLists.txt>

# create a build directory
mkdir build

# open the build directory
cd build

# cmake the project in the build directory
cmake .. 

# make the cmake project
make -j4

# execute the generated executible file
./<executible file>

For Windows: I would recommend using an IDE that uses CMake for build process. Use the contents of the provided CMakeLists_Windows.txt file in the CMakeLists.txt file of your project generated by the IDE.
Example IDE: CLion by Jetbrains, Visual Studio etc.

Sample Run

./cmake-build-release/rrt_2d -s '(45,-45)' -g '(-45,45,15)' -e 5 -o ./inputs/obstacles.txt -p ./outputs/path_output_3.txt -t ./outputs/search_output_3.txt -v -r 20
start: x: 45, y: -45 , goal: x: -45, y: 45 , r: 15 , bias: 0, seed: 20, epsilon: 5, verbose: 1, iter_lim: 100000000
obs_fp: ./inputs/obstacles.txt
path_fp: ./outputs/path_output_3.txt
search_fp: ./outputs/search_output_3.txt

Successfully opened the obstacle file: ./inputs/obstacles.txt
The obstacle file has 20 obstacles.
20 obstacles were added to obstacle vector.

The search was successful. It took 116 microseconds.
Start: x: 45, y: -45
Goal: x: -45, y: 45 , r: 15

Successfully opened the path file: ./outputs/path_output_3.txt
Successfully wrote path file: "./outputs/path_output_3.txt".

Successfully opened the graph file: ./outputs/search_output_3.txt
Successfully wrote graph file: "./outputs/search_output_3.txt".

This search was then visualized using search_viz.py

See the SAMPLE_RUNS.md file to see graph output of RRT search on environment defined by the obstacles file available in inputs. The output files of the search are saved in outputs.