From 9e8169cc420b08423d579617e2c7d0e94794df9e Mon Sep 17 00:00:00 2001 From: Jiri Vlasak Date: Fri, 23 Jul 2021 13:13:03 +0200 Subject: [PATCH] Update documentation --- README.md | 149 +++++++++++++++---------------------------------- incl/rrtext.hh | 87 +++++++++++++++++++++-------- incl/rrts.hh | 5 +- 3 files changed, 112 insertions(+), 129 deletions(-) diff --git a/README.md b/README.md index 13e581d..0d4b315 100644 --- a/README.md +++ b/README.md @@ -1,108 +1,43 @@ -# RRT\* algorithm +RRT\* algorithm +=============== + RRTS is a C++ library with implementation of RRT\* planning algorithm. -# License +License +------- + The project is published under [GNU GPLv3][1]. [1]: ./LICENSE -# Build +Dependencies +------------ + +- `libbcar` (as submodule) +- `libjsoncpp-dev` + +Build +----- + To build the project run the following commands: -``` -mkdir build -cd build -cmake ../ -make -``` + + mkdir build + cd build + cmake ../ + make To build with ninja: -``` -mkdir build -cd build -cmake -DCMAKE_BUILD_TYPE=Release -G Ninja ../ -ninja -v -``` - -## Dependencies -- `libbcar` -- `libjsoncpp-dev` -# RRT Extensions -There is basic RRT\* algorithm in `rrts.cc` file. To test different approaches -and upgrades to RRT, *extensions* are declared in `rrtext.h` and implemented in -`rrtextX.cc`, where `X` is the number of an extension. - -## Implemented extensions -There is a list of implemented extensions and what they include. The extension -number accomply to file `src/rrtextN.cc` where `N` is: - -1. "cost" RS-M -- Reeds & Shepp (build), Matej's heur. (search). -2. "collision" [cute c2][] for collision detection, -3. "path optimization" Dijkstra algorithm, -4. "nn" 2D grid for nodes storage, -5. "cost" RS-E -- Reeds & Shepp (build), Euclidean (search), -6. "cost" RS-RS -- Reeds & Shepp (build), Reeds & Shepp (search), -7. "nn" 2D [K-d tree][] for nodes storage, -8. "nn" 3D [K-d tree][] for nodes storage, -9. "nn" 3D grid for nodes storage, -10. "cost" RS-H -- Reeds & Shepp (build), B-Spline paper (search) -11. "goal zone" gz -- Use drivable of libbcar to check if goal found. -12. "steer" -- Use random control input for `steer1`, use R&S for `steer2`. -13. "path optimization" -- Dijkstra algorithm, goal zone for interesting nodes. -14. "sampling" -- uniform sampling in circle between init, goal (rad = edist) -15. "log" -- log goal cc each iteration. - -[cute c2]: https://github.com/RandyGaul/cute_headers/blob/master/cute_c2.h -[K-d tree]: https://en.wikipedia.org/wiki/K-d_tree - -## Compound extensions -There is a list of classes with reference to extensions used. The extensio -number accomply to class `RRTCEn` where `n` is: - -1. cute, gz, Dijkstra, RS-M. -2. cute, gz, Dijkstra, RS-E. -3. cute, gz, Dijkstra, RS-RS. -4. RS-M, cute, 2D grid. -5. cute, 2D grid, RS-E. -6. cute, 2D grid, RS-RS. -7. cute, Dijkstra, 2D grid, RS-E. -8. cute, Dijkstra, 2D grid, RS-RS. -9. cute, Dijkstra, 2D grid, RS-M. -10. cute, Dijkstra, 2D tree, RS-RS. -11. cute, Dijkstra, 2D tree, RS-E. -12. cute, Dijkstra, 2D tree, RS-M. -13. cute, Dijkstra, 3D tree, RS-RS. -14. cute, Dijkstra, 3D tree, RS-M. -15. cute, Dijkstra, 3D grid, RS-RS. -16. cute, Dijkstra, 3D grid, RS-M. -17. cute, gz, Dijkstra, RS-H. - -18. cute, gz, Dijkstra, 2D grid, RS-RS -19. cute, gz, Dijkstra, 2D grid, RS-E -20. cute, gz, Dijkstra, 2D grid, RS-M -21. cute, gz, Dijkstra, 2D grid, RS-H - -22. cute, gz, Dijkstra, 2D tree, RS-RS -23. cute, gz, Dijkstra, 2D tree, RS-E -24. cute, gz, Dijkstra, 2D tree, RS-M -25. cute, gz, Dijkstra, 2D tree, RS-H - -26. cute, gz, Dijkstra, 3D grid, RS-RS -27. cute, gz, Dijkstra, 3D grid, RS-E -28. cute, gz, Dijkstra, 3D grid, RS-M -29. cute, gz, Dijkstra, 3D grid, RS-H - -30. cute, gz, Dijkstra, 3D tree, RS-RS -31. cute, gz, Dijkstra, 3D tree, RS-E -32. cute, gz, Dijkstra, 3D tree, RS-M -33. cute, gz, Dijkstra, 3D tree, RS-H - -34. cute, gz, Dijkstra, 3D tree, RS-H, diff. steer - -# Contribute -Use [OneFlow][3] branching model and keep the [changelog][4]. + mkdir build + cd build + cmake -DCMAKE_BUILD_TYPE=Release -G Ninja ../ + ninja -v + +Contribute +---------- Write [great git commit messages][5]: + 1. Separate subject from body with a blank line. 2. Limit the subject line to 50 characters. 3. Capitalize the subject line. @@ -111,18 +46,24 @@ Write [great git commit messages][5]: 6. Wrap the body at 72 characters. 7. Use the body to explain what and why vs. how. -When adding feature or hotfix, use [Test-driven development (TDD)][2]: -1. Add tests to `ut` folder, add methods declaration, basic structure. -2. Run tests (just `make` in `build` folder), check that tests *fail*. -3. Implement functionality. -4. Run tests, check that tests *pass*. -5. Refactor. - -[2]: https://en.wikipedia.org/wiki/Test-driven_development -[3]: https://www.endoflineblog.com/oneflow-a-git-branching-model-and-workflow -[4]: ./CHANGELOG.md [5]: https://chris.beams.io/posts/git-commit/ -# Documentation +Documentation +------------- + The documentation is generated by Doxygen, at least version `1.8.15` is needed. Just run `doxygen` in the project root directory. + + +RRT Extensions +============== + +There is basic RRT\* algorithm in `rrts.cc` file. To test different approaches +and upgrades to RRT, _extensions_ are declared in `rrtext.hh` and implemented in +`src/rrtextN.cc`, where `N` is the number of an extension. + +For more information, see the `incl/rrtext.hh` header file or the generated +documentation. + +RRT extensions are not to be used as the final planner. Instead, the _RRT* +planners_ declared in `incl/rrtsp.hh` are to be used as the final planner. diff --git a/incl/rrtext.hh b/incl/rrtext.hh index b09f1c4..69f9175 100644 --- a/incl/rrtext.hh +++ b/incl/rrtext.hh @@ -1,3 +1,17 @@ +/*! \brief RRT* extensions. + * + * The extensions are used to implement or change the default behavior of the + * RRT* algorithm. + * + * \file + * \defgroup ext-col Collision detection extensions + * \defgroup ext-store Node storage and searching tree extensions + * \defgroup ext-cost Cost extensions + * \defgroup ext-opt Path optimization extensions + * \defgroup ext-sampl Random sampling extensions + * \defgroup ext-steer Steering procedure extensions + * \defgroup ext-aux Auxilliary extensions + */ #ifndef RRTS_RRTEXT_H #define RRTS_RRTEXT_H @@ -18,21 +32,37 @@ namespace rrts { +/*! \brief Finish when more than 1000 iterations. + * + * \ingroup ext-aux + */ class RRTExt18 : public virtual RRTS { private: bool should_finish() const; }; +/*! \brief Finish when goal found or more than 1000 iterations. + * + * \ingroup ext-aux + */ class RRTExt17 : public virtual RRTS { private: bool should_finish() const; }; +/*! \brief Use Reeds & Shepp steering procedure. + * + * \ingroup ext-steer + */ class RRTExt16 : public virtual RRTS { private: void steer(RRTNode const& f, RRTNode const& t); }; +/*! \brief Log goal's cumulative cost each iteration. + * + * \ingroup ext-aux + */ class RRTExt15 : public virtual RRTS { private: std::vector log_path_cost_; @@ -44,6 +74,7 @@ public: /*! \brief Random sampling in the circuit between root and goal. * + * \ingroup ext-sampl * \see https://stackoverflow.com/questions/5837572/generate-a-random-point-within-a-circle-uniformly/50746409#50746409 */ class RRTExt14 : public virtual RRTS { @@ -59,7 +90,13 @@ public: void reset(); }; -/*! Use Dijkstra-based path optimization, goal zone for interesting nodes. */ +/*! \brief Use Dijkstra algorithm to find path between interesting nodes. + * + * The search for interesting nodes starts at root, the last drivable nodes is + * added to interesting nodes until goal is reached. + * + * \ingroup ext-opt + */ class RRTExt13 : public virtual RRTS { private: class DijkstraNode { @@ -89,7 +126,7 @@ public: void reset(); }; -/*! \brief Different `steer` procedures. +/* \brief Different `steer` procedures. Use sampling in control input for `steer1`. Use R&S steering for `steer2`. */ @@ -101,7 +138,7 @@ class RRTExt12 : public virtual RRTS { bool next(); }; -/*! \brief Goal Zone. +/* \brief Goal Zone. */ class RRTExt11 : public virtual RRTS { @@ -109,13 +146,13 @@ class RRTExt11 : public virtual RRTS { bool goal_found(RRTNode &f); }; -/*! \brief Different costs extension. +/*! \brief Reeds & Shepp (build) and Euclidean + abs angle (search). + * + * Use Reeds & Shepp path length for building tree data structure and Euclidean + * distance plus (abs) heading difference for searching it. * - * Use different cost for bulding tree data structure and searching in the - * structure. The cost function is from Elbanhawi, Mohamed, Milan Simic, and - * Reza Jazar. “Randomized Bidirectional B-Spline Parameterization Motion - * Planning.” IEEE Transactions on Intelligent Transportation Systems 17, no. 2 - * (February 2016): 406–19. https://doi.org/10.1109/TITS.2015.2477355. + * \ingroup ext-cost + * \see https://doi.org/10.1109/TITS.2015.2477355 */ class RRTExt10 : public virtual RRTS { protected: @@ -123,7 +160,7 @@ protected: double cost_search(RRTNode const& f, RRTNode const& t) const; }; -/*! \brief Use grid data structure to store RRT nodes. +/* \brief Use grid data structure to store RRT nodes. This approach speeds up the search process for the nearest neighbor and the near vertices procedures. @@ -169,11 +206,12 @@ class RRTExt9 : public virtual RRTS { std::vector nv(RRTNode &t); }; -/*! \brief Use k-d tree data structure to store RRT nodes. +/*! \brief Use 3D k-d tree data structure to store RRT nodes. * * This approach speeds up the search process for the nearest neighbor and the * near vertices procedures. This extension implements 3D K-d tree. * + * \ingroup ext-store * \see https://en.wikipedia.org/wiki/K-d_tree */ class RRTExt8 : public virtual RRTS { @@ -198,7 +236,7 @@ public: void find_nv(RRTNode const& t); }; -/*! \brief Use k-d tree data structure to store RRT nodes. +/* \brief Use k-d tree data structure to store RRT nodes. This approach speeds up the search process for the nearest neighbor and the near vertices procedures. This extension implements 2D K-d tree. @@ -244,22 +282,22 @@ private: double cost_search(RRTNode const& f, RRTNode const& t) const; }; -/*! \brief Different costs extension. +/* \brief Different costs extension. Use different cost for bulding tree data structure and searching in the structure. This one is complementary to `rrtext1.cc`. */ class RRTExt5 : public virtual RRTS { public: - /*! \brief Reeds and Shepp path length. + /* \brief Reeds and Shepp path length. */ double cost_build(RRTNode &f, RRTNode &t); - /*! \brief Euclidean distance. + /* \brief Euclidean distance. */ double cost_search(RRTNode &f, RRTNode &t); }; -/*! \brief Use grid data structure to store RRT nodes. +/* \brief Use grid data structure to store RRT nodes. This approach speeds up the search process for the nearest neighbor and the near vertices procedures. @@ -302,7 +340,7 @@ class RRTExt4 : public virtual RRTS { std::vector nv(RRTNode &t); }; -/*! \brief Use Dijkstra algorithm to find the shorter path. +/* \brief Use Dijkstra algorithm to find the shorter path. */ class RRTExt3 : public virtual RRTS { private: @@ -337,10 +375,11 @@ class RRTExt3 : public virtual RRTS { } }; -/*! \brief Use cute_c2 for collision detection. - -\see https://github.com/RandyGaul/cute_headers/blob/master/cute_c2.h -*/ +/*! \brief Use cute_c2 library for collision detection. + * + * \ingroup ext-col + * \see https://github.com/RandyGaul/cute_headers/blob/master/cute_c2.h + */ class RRTExt2 : public virtual RRTS { private: c2Poly c2_bc_; @@ -354,17 +393,17 @@ public: void json(Json::Value jvi); }; -/*! \brief Different costs extension. +/* \brief Different costs extension. Use different cost for bulding tree data structure and searching in the structure. */ class RRTExt1 : public virtual RRTS { public: - /*! \brief Reeds and Shepp path length. + /* \brief Reeds and Shepp path length. */ double cost_build(RRTNode &f, RRTNode &t); - /*! \brief Matej's heuristics. + /* \brief Matej's heuristics. */ double cost_search(RRTNode &f, RRTNode &t); }; diff --git a/incl/rrts.hh b/incl/rrts.hh index f2c8962..0e12a5c 100644 --- a/incl/rrts.hh +++ b/incl/rrts.hh @@ -1,4 +1,7 @@ -/*! \file */ +/*! \brief RRT* structure and default procedures. + * + * \file + */ #ifndef RRTS_RRTS_H #define RRTS_RRTS_H -- 2.39.2