README.md

   1 # RRT\* algorithm
   2 RRTS is a C++ library with implementation of RRT\* planning algorithm.
   3
   4 # License
   5 The project is published under [GNU GPLv3][1].
   6
   7 [1]: ./LICENSE
   8
   9 # Build
  10 To build the project run the following commands:
  11 ```
  12 mkdir build
  13 cd build
  14 cmake ../
  15 make
  16 ```
  17
  18 To build with ninja:
  19 ```
  20 mkdir build
  21 cd build
  22 cmake -DCMAKE_BUILD_TYPE=Release -G Ninja ../
  23 ninja -v
  24 ```
  25
  26 ## Dependencies
  27 - `libbcar`
  28 - `libjsoncpp-dev`
  29
  30 # RRT Extensions
  31 There is basic RRT\* algorithm in `rrts.cc` file. To test different approaches
  32 and upgrades to RRT, *extensions* are declared in `rrtext.h` and implemented in
  33 `rrtextX.cc`, where `X` is the number of an extension.
  34
  35 ## Implemented extensions
  36 There is a list of implemented extensions and what they include. The extension
  37 number accomply to file `src/rrtextN.cc` where `N` is:
  38
  39 1.  "cost" RS-M -- Reeds & Shepp (build), Matej's heur. (search).
  40 2.  "collision" [cute c2][] for collision detection,
  41 3.  "path optimization" Dijkstra algorithm,
  42 4.  "nn" 2D grid for nodes storage,
  43 5.  "cost" RS-E -- Reeds & Shepp (build), Euclidean (search),
  44 6.  "cost" RS-RS -- Reeds & Shepp (build), Reeds & Shepp (search),
  45 7.  "nn" 2D [K-d tree][] for nodes storage,
  46 8.  "nn" 3D [K-d tree][] for nodes storage,
  47 9.  "nn" 3D grid for nodes storage,
  48 10. "cost" RS-H -- Reeds & Shepp (build), B-Spline paper (search)
  49 11. "goal zone" gz -- Use drivable of libbcar to check if goal found.
  50 12. "steer" -- Use random control input for `steer1`, use R&S for `steer2`.
  51 13. "path optimization" -- Dijkstra algorithm, goal zone for interesting nodes.
  52 14. "sampling" -- uniform sampling in circle between init, goal (rad = edist)
  53
  54 [cute c2]: https://github.com/RandyGaul/cute_headers/blob/master/cute_c2.h
  55 [K-d tree]: https://en.wikipedia.org/wiki/K-d_tree
  56
  57 ## Compound extensions
  58 There is a list of classes with reference to extensions used. The extensio
  59 number accomply to class `RRTCEn` where `n` is:
  60
  61 1.  cute, gz, Dijkstra, RS-M.
  62 2.  cute, gz, Dijkstra, RS-E.
  63 3.  cute, gz, Dijkstra, RS-RS.
  64 4.  RS-M, cute, 2D grid.
  65 5.  cute, 2D grid, RS-E.
  66 6.  cute, 2D grid, RS-RS.
  67 7.  cute, Dijkstra, 2D grid, RS-E.
  68 8.  cute, Dijkstra, 2D grid, RS-RS.
  69 9.  cute, Dijkstra, 2D grid, RS-M.
  70 10. cute, Dijkstra, 2D tree, RS-RS.
  71 11. cute, Dijkstra, 2D tree, RS-E.
  72 12. cute, Dijkstra, 2D tree, RS-M.
  73 13. cute, Dijkstra, 3D tree, RS-RS.
  74 14. cute, Dijkstra, 3D tree, RS-M.
  75 15. cute, Dijkstra, 3D grid, RS-RS.
  76 16. cute, Dijkstra, 3D grid, RS-M.
  77 17. cute, gz, Dijkstra, RS-H.
  78
  79 18. cute, gz, Dijkstra, 2D grid, RS-RS
  80 19. cute, gz, Dijkstra, 2D grid, RS-E
  81 20. cute, gz, Dijkstra, 2D grid, RS-M
  82 21. cute, gz, Dijkstra, 2D grid, RS-H
  83
  84 22. cute, gz, Dijkstra, 2D tree, RS-RS
  85 23. cute, gz, Dijkstra, 2D tree, RS-E
  86 24. cute, gz, Dijkstra, 2D tree, RS-M
  87 25. cute, gz, Dijkstra, 2D tree, RS-H
  88
  89 26. cute, gz, Dijkstra, 3D grid, RS-RS
  90 27. cute, gz, Dijkstra, 3D grid, RS-E
  91 28. cute, gz, Dijkstra, 3D grid, RS-M
  92 29. cute, gz, Dijkstra, 3D grid, RS-H
  93
  94 30. cute, gz, Dijkstra, 3D tree, RS-RS
  95 31. cute, gz, Dijkstra, 3D tree, RS-E
  96 32. cute, gz, Dijkstra, 3D tree, RS-M
  97 33. cute, gz, Dijkstra, 3D tree, RS-H
  98
  99 34. cute, gz, Dijkstra, 3D tree, RS-H, diff. steer
 100
 101 # Contribute
 102 Use [OneFlow][3] branching model and keep the [changelog][4].
 103
 104 Write [great git commit messages][5]:
 105 1. Separate subject from body with a blank line.
 106 2. Limit the subject line to 50 characters.
 107 3. Capitalize the subject line.
 108 4. Do not end the subject line with a period.
 109 5. Use the imperative mood in the subject line.
 110 6. Wrap the body at 72 characters.
 111 7. Use the body to explain what and why vs. how.
 112
 113 When adding feature or hotfix, use [Test-driven development (TDD)][2]:
 114 1. Add tests to `ut` folder, add methods declaration, basic structure.
 115 2. Run tests (just `make` in `build` folder), check that tests *fail*.
 116 3. Implement functionality.
 117 4. Run tests, check that tests *pass*.
 118 5. Refactor.
 119
 120 [2]: https://en.wikipedia.org/wiki/Test-driven_development
 121 [3]: https://www.endoflineblog.com/oneflow-a-git-branching-model-and-workflow
 122 [4]: ./CHANGELOG.md
 123 [5]: https://chris.beams.io/posts/git-commit/
 124
 125 # Documentation
 126 The documentation is generated by Doxygen, at least version `1.8.15` is needed.
 127 Just run `doxygen` in the project root directory.