-# 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.
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.
+/*! \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
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<double> log_path_cost_;
/*! \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 {
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 {
void reset();
};
-/*! \brief Different `steer` procedures.
+/* \brief Different `steer` procedures.
Use sampling in control input for `steer1`. Use R&S steering for `steer2`.
*/
bool next();
};
-/*! \brief Goal Zone.
+/* \brief Goal Zone.
*/
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:
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.
std::vector<RRTNode *> 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 {
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.
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.
std::vector<RRTNode *> 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:
}
};
-/*! \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_;
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);
};
projects / hubacji1 / rrts.git / commitdiff