6 #include <jsoncpp/json/json.h>
11 #define ETA 1.0 // for steer, nv
12 #define GAMMA(cV) ({ \
13 __typeof__ (cV) _cV = (cV); \
14 pow(log(_cV) / _cV, 1.0 / 3.0); \
17 /*! \brief Possible type of RRT node.
19 \param cusp The node that is cusp (change in direction).
20 \param connected The node that branches generated steered path.
24 static const unsigned int cusp = 1 << 0;
25 static const unsigned int connected = 1 << 1;
28 /*! \brief RRT node basic class.
30 \param c Cumulative cost from RRT data structure root.
31 \param p Pointer to parent RRT node.
32 \param t Type of the RRT node (RRTNodeType).
34 \param x Horizontal coordinate of rear axle center.
35 \param y Vertical coordinate of rear axle center.
36 \param h Heading of the car in the interval [-pi,+pi] radians.
37 \param sp Speed of the car.
38 \param st Steering of the car.
43 RRTNode *p_ = nullptr;
55 double c() const { return this->c_; }
56 void c(double c) { this->c_ = c; }
58 RRTNode *p() const { return this->p_; }
59 void p(RRTNode *p) { this->p_ = p; }
61 bool t(unsigned int flag) { return this->t_ & flag; }
62 void set_t(unsigned int flag) { this->t_ |= flag; }
63 void clear_t(unsigned int flag) { this->t_ &= ~flag; }
67 double x() const { return this->x_; }
68 void x(double x) { this->x_ = x; }
70 double y() const { return this->y_; }
71 void y(double y) { this->y_ = y; }
73 double h() const { return this->h_; }
83 double sp() const { return this->sp_; }
84 void sp(double sp) { this->sp_ = sp; }
86 double st() const { return this->st_; }
87 void st(double st) { this->st_ = st; }
90 RRTNode(const BicycleCar &bc);
91 bool operator==(const RRTNode& n);
94 /*! \brief Polygon obstacle basic class.
96 \param poly Border polygon of the obstacle.
100 std::vector<std::tuple<double, double>> poly_;
103 std::vector<std::tuple<double, double>> &poly()
111 /*! \brief RRT* algorithm basic class.
113 \param icnt RRT algorithm iterations counter.
114 \param goals The vector of goal nodes.
115 \param nodes The vector of all nodes in RRT data structure.
116 \param samples The vector of all samples of RRT algorithm.
117 \param sample_dist_type Random distribution type for sampling function (0 -
122 unsigned int icnt_ = 0;
123 std::chrono::high_resolution_clock::time_point tstart_;
127 int sample_dist_type_ = 0;
129 std::vector<RRTNode> goals_;
130 std::vector<RRTNode> nodes_;
131 std::vector<Obstacle> obstacles_;
132 std::vector<RRTNode> samples_;
133 std::vector<RRTNode> steered_;
135 /*! \brief Update and return elapsed time.
138 /*! \brief Set normal distribution for sampling.
140 void set_sample_normal(
141 double x1, double x2,
142 double y1, double y2,
145 /*! \brief Set uniform distribution for sampling.
147 void set_sample_uniform(
148 double x1, double x2,
149 double y1, double y2,
154 /*! \brief Store RRT node to tree data structure.
156 virtual void store_node(RRTNode n);
159 std::tuple<bool, unsigned int, unsigned int>
160 collide(std::vector<std::tuple<double, double>> &poly);
161 virtual std::tuple<bool, unsigned int, unsigned int>
162 collide_steered_from(RRTNode &f);
163 virtual std::tuple<bool, unsigned int, unsigned int>
164 collide_two_nodes(RRTNode &f, RRTNode &t);
166 std::default_random_engine gen_;
167 std::normal_distribution<double> ndx_;
168 std::normal_distribution<double> ndy_;
169 std::normal_distribution<double> ndh_;
170 std::uniform_real_distribution<double> udx_;
171 std::uniform_real_distribution<double> udy_;
172 std::uniform_real_distribution<double> udh_;
173 virtual RRTNode *nn(RRTNode &t);
174 virtual std::vector<RRTNode *> nv(RRTNode &t);
175 void steer(RRTNode &f, RRTNode &t);
176 /*! \brief Join steered nodes to RRT data structure
178 \param f RRT node to join steered nodes to.
180 void join_steered(RRTNode *f);
181 virtual bool goal_found(RRTNode &f);
186 /*! \brief Initialize RRT algorithm if needed.
189 /*! \brief Deinitialize RRT algorithm if needed.
191 virtual void deinit();
192 /*! \brief Return path found by RRT*.
194 virtual std::vector<RRTNode *> path();
195 /*! \brief Return ``true`` if algorithm should stop.
197 Update counters (iteration, seconds, ...) and return if
198 the current iteration should be the last one.
201 /*! \brief Return ``true`` if the algorithm should finish.
203 Finish means that the algorithm will not be resumed.
205 bool should_finish();
206 /*! \brief Return ``true`` if the algorithm shoud break.
208 Break means that the algorithm can be resumed.
211 /*! \brief Return ``true`` if algorithm should continue.
213 `pcnt_` is set to `scnt_`, so the difference is 0 and it can
214 start from scratch. After the `should_continue` is called,
215 there must be `while (rrts.next()) {}` loop.
217 bool should_continue();
218 /*! \brief Run next RRT* iteration.
221 /*! \brief Set sampling info.
223 Based on `sample_dist_type`, set proper distribution
224 parameters. The distribution parameters are relative to `front`
225 node in `nodes` (init).
228 \param x1 Mean x value.
229 \param x2 Standard deviation of x.
230 \param y1 Mean y value.
231 \param y2 Standard deviation of y.
232 \param h1 Mean h value.
233 \param h2 Standard deviation of h.
235 For uniform sampling:
236 \param x1 Minimum x value.
237 \param x2 Maximum x value.
238 \param y1 Minimum y value.
239 \param y2 Maximum y value.
240 \param h1 Minimum h value.
241 \param h2 Maximum h value.
244 double x1, double x2,
245 double y1, double y2,
248 /*! \brief Generate JSON output.
251 /*! \brief Load JSON input.
253 void json(Json::Value jvi);
256 virtual double cost_build(RRTNode &f, RRTNode &t);
257 virtual double cost_search(RRTNode &f, RRTNode &t);
260 unsigned int icnt() const { return this->icnt_; }
261 double scnt() const { return this->scnt_; }
262 bool gf() const { return this->gf_; }
263 void gf(bool f) { this->gf_ = f; }
264 int sample_dist_type() const { return this->sample_dist_type_;}
265 void sample_dist_type(int t) { this->sample_dist_type_ = t; }
266 std::vector<RRTNode> &goals() { return this->goals_; }
267 std::vector<RRTNode> &nodes() { return this->nodes_; }
268 std::vector<Obstacle> &obstacles() { return this->obstacles_; }
269 std::vector<RRTNode> &samples() { return this->samples_; }
270 std::vector<RRTNode> &steered() { return this->steered_; }
275 /*! \brief Compute cumulative cost of RRT node.
277 \param t RRT node to compute cumulative cost to.
279 double cc(RRTNode &t);