grid_astar_model_3dof.cpp
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2019-2020, the neonavigation authors
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are met:
7  *
8  * * Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  * * Redistributions in binary form must reproduce the above copyright
11  * notice, this list of conditions and the following disclaimer in the
12  * documentation and/or other materials provided with the distribution.
13  * * Neither the name of the copyright holder nor the names of its
14  * contributors may be used to endorse or promote products derived from
15  * this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
18  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
21  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
22  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
23  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
25  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
27  * POSSIBILITY OF SUCH DAMAGE.
28  */
29 
30 #include <cmath>
31 #include <limits>
32 #include <utility>
33 #include <vector>
34 
35 #include <ros/ros.h>
36 
37 #include <costmap_cspace_msgs/MapMetaData3D.h>
38 
45 
46 namespace planner_cspace
47 {
48 namespace planner_3d
49 {
51  const costmap_cspace_msgs::MapMetaData3D& map_info,
52  const Vecf& euclid_cost_coef,
53  const int local_range,
54  BlockMemGridmapBase<float, 3, 2>& cost_estim_cache,
58  const CostCoeff& cc,
59  const int range)
60  : hysteresis_(false)
61  , map_info_(map_info)
62  , euclid_cost_coef_(euclid_cost_coef)
63  , resolution_(
64  1.0f / map_info.linear_resolution,
65  1.0f / map_info.linear_resolution,
66  1.0f / map_info.angular_resolution)
67  , local_range_(local_range)
68  , cost_estim_cache_(cost_estim_cache)
69  , cm_(cm)
70  , cm_hyst_(cm_hyst)
71  , cm_rough_(cm_rough)
72  , cc_(cc)
73  , range_(range)
74 {
75  rot_cache_.reset(map_info_.linear_resolution, map_info_.angular_resolution, range_);
76 
77  costmap_cspace_msgs::MapMetaData3D map_info_linear(map_info_);
78  map_info_linear.angle = 1;
79 
81  map_info_linear.linear_resolution,
82  map_info_linear.angular_resolution,
83  range_,
86  map_info_.linear_resolution,
87  map_info_.angular_resolution,
88  range_,
89  cm_.getAddressor());
90 
91  // Make boundary check threshold
94  Vec(static_cast<int>(map_info_.width),
95  static_cast<int>(map_info_.height),
96  static_cast<int>(map_info_.angle)) -
98  ROS_INFO("x:%d, y:%d grids around the boundary is ignored on path search", min_boundary_[0], min_boundary_[1]);
99 
101 
103  search_list_rough_.clear();
104  Vec d;
105  for (d[0] = -range_; d[0] <= range_; d[0]++)
106  {
107  for (d[1] = -range_; d[1] <= range_; d[1]++)
108  {
109  if (d.sqlen() > range_ * range_)
110  continue;
111  d[2] = 0;
112  search_list_rough_.push_back(d);
113  }
114  }
115  path_interpolator_.reset(map_info_.angular_resolution, range_);
116 }
117 
118 void GridAstarModel3D::enableHysteresis(const bool enable)
119 {
120  hysteresis_ = enable;
121 }
123 {
124  for (int rootsum = 0;
125  rootsum < static_cast<int>(euclid_cost_lin_cache_.size()); ++rootsum)
126  {
127  euclid_cost_lin_cache_[rootsum] = std::sqrt(rootsum) * euclid_cost_coef_[0];
128  }
129 }
130 float GridAstarModel3D::euclidCost(const Vec& v) const
131 {
132  float cost = euclidCostRough(v);
133 
134  int angle = v[2];
135  while (angle > static_cast<int>(map_info_.angle) / 2)
136  angle -= static_cast<int>(map_info_.angle);
137  while (angle < -static_cast<int>(map_info_.angle) / 2)
138  angle += static_cast<int>(map_info_.angle);
139  cost += std::abs(euclid_cost_coef_[2] * angle);
140  return cost;
141 }
143 {
144  int rootsum = 0;
145  for (int i = 0; i < 2; ++i)
146  rootsum += v[i] * v[i];
147 
148  if (rootsum < static_cast<int>(euclid_cost_lin_cache_.size()))
149  return euclid_cost_lin_cache_[rootsum];
150 
151  return std::sqrt(rootsum) * euclid_cost_coef_[0];
152 }
154  const Vec& cur, const Vec& next, const std::vector<VecWithCost>& start, const Vec& goal) const
155 {
156  Vec d_raw = next - cur;
157  d_raw.cycle(map_info_.angle);
158  const Vec d = d_raw;
159  float cost = euclidCost(d);
160 
161  if (d[0] == 0 && d[1] == 0)
162  {
163  // In-place turn
164  int sum = 0;
165  const int dir = d[2] < 0 ? -1 : 1;
166  Vec pos = cur;
167  for (int i = 0; i < std::abs(d[2]); i++)
168  {
169  pos[2] += dir;
170  if (pos[2] < 0)
171  pos[2] += map_info_.angle;
172  else if (pos[2] >= static_cast<int>(map_info_.angle))
173  pos[2] -= map_info_.angle;
174  const auto c = cm_[pos];
175  if (c > 99)
176  return -1;
177  sum += c;
178  }
179 
180  cost +=
181  sum * map_info_.angular_resolution * euclid_cost_coef_[2] / euclid_cost_coef_[0] +
182  sum * map_info_.angular_resolution * cc_.weight_costmap_turn_ / 100.0;
183  // simplified from sum * map_info_.angular_resolution * abs(d[2]) * cc_.weight_costmap_turn_ / (100.0 * abs(d[2]))
184  return cc_.in_place_turn_ + cost;
185  }
186 
187  const Vec d2(d[0] + range_, d[1] + range_, next[2]);
188  const Vecf motion = rot_cache_.getMotion(cur[2], d2);
189  const float dist = motion.len();
190 
191  if (motion[0] < 0)
192  {
193  // Going backward
194  cost *= 1.0 + cc_.weight_backward_;
195  }
196 
197  if (d[2] == 0)
198  {
199  const float aspect = motion[0] / motion[1];
200  cost += euclid_cost_coef_[2] * std::abs(1.0 / aspect) * map_info_.angular_resolution / (M_PI * 2.0);
201 
202  // Go-straight
203  int sum = 0, sum_hyst = 0;
204  Vec d_index(d[0], d[1], next[2]);
205  d_index.cycleUnsigned(map_info_.angle);
206 
207  const auto cache_page = motion_cache_.find(cur[2], d_index);
208  if (cache_page == motion_cache_.end(cur[2]))
209  return -1;
210  const int num = cache_page->second.getMotion().size();
211  for (const auto& pos_diff : cache_page->second.getMotion())
212  {
213  const Vec pos(
214  cur[0] + pos_diff[0], cur[1] + pos_diff[1], pos_diff[2]);
215  const auto c = cm_[pos];
216  if (c > 99)
217  return -1;
218  sum += c;
219 
220  if (hysteresis_)
221  sum_hyst += cm_hyst_[pos];
222  }
223  const float distf = cache_page->second.getDistance();
224  cost += sum * map_info_.linear_resolution * distf * cc_.weight_costmap_ / (100.0 * num);
225  cost += sum_hyst * map_info_.linear_resolution * distf * cc_.weight_hysteresis_ / (100.0 * num);
226  }
227  else
228  {
229  const std::pair<float, float>& radiuses = rot_cache_.getRadiuses(cur[2], d2);
230  const float r1 = radiuses.first;
231  const float r2 = radiuses.second;
232  const float curv_radius = (r1 + r2) / 2;
233 
234  // Ignore boundary
235  if (cur[0] < min_boundary_[0] || cur[1] < min_boundary_[1] ||
236  cur[0] >= max_boundary_[0] || cur[1] >= max_boundary_[1])
237  return -1;
238 
239  if (std::abs(cc_.max_vel_ / r1) > cc_.max_ang_vel_)
240  {
241  const float vel = std::abs(curv_radius) * cc_.max_ang_vel_;
242  // Curve deceleration penalty
243  cost += dist * std::abs(vel / cc_.max_vel_) * cc_.weight_decel_;
244  }
245 
246  {
247  int sum = 0, sum_hyst = 0;
248  Vec d_index(d[0], d[1], next[2]);
249  d_index.cycleUnsigned(map_info_.angle);
250 
251  const auto cache_page = motion_cache_.find(cur[2], d_index);
252  if (cache_page == motion_cache_.end(cur[2]))
253  return -1;
254  const int num = cache_page->second.getMotion().size();
255  for (const auto& pos_diff : cache_page->second.getMotion())
256  {
257  const Vec pos(
258  cur[0] + pos_diff[0], cur[1] + pos_diff[1], pos_diff[2]);
259  const auto c = cm_[pos];
260  if (c > 99)
261  return -1;
262  sum += c;
263 
264  if (hysteresis_)
265  sum_hyst += cm_hyst_[pos];
266  }
267  const float distf = cache_page->second.getDistance();
268  cost += sum * map_info_.linear_resolution * distf * cc_.weight_costmap_ / (100.0 * num);
269  cost += sum * map_info_.angular_resolution * std::abs(d[2]) * cc_.weight_costmap_turn_ / (100.0 * num);
270  cost += sum_hyst * map_info_.linear_resolution * distf * cc_.weight_hysteresis_ / (100.0 * num);
271  }
272  }
273 
274  return cost;
275 }
277  const Vec& cur, const Vec& goal) const
278 {
279  Vec s2(cur[0], cur[1], 0);
280  float cost = cost_estim_cache_[s2];
281  if (cost == std::numeric_limits<float>::max())
282  return std::numeric_limits<float>::max();
283 
284  int diff = cur[2] - goal[2];
285  while (diff > static_cast<int>(map_info_.angle) / 2)
286  diff -= static_cast<int>(map_info_.angle);
287  while (diff < -static_cast<int>(map_info_.angle) / 2)
288  diff += static_cast<int>(map_info_.angle);
289 
290  cost += euclid_cost_coef_[2] * std::abs(diff);
291 
292  return cost;
293 }
294 const std::vector<GridAstarModel3D::Vec>& GridAstarModel3D::searchGrids(
295  const Vec& p,
296  const std::vector<VecWithCost>& ss,
297  const Vec& es) const
298 {
299  const float local_range_sq = local_range_ * local_range_;
300  for (const VecWithCost& s : ss)
301  {
302  const Vec ds = s.v_ - p;
303 
304  if (ds.sqlen() < local_range_sq)
305  {
306  return motion_primitives_[p[2]];
307  }
308  }
309  return search_list_rough_;
310 }
311 
313  const Vec& cur, const Vec& next, const std::vector<VecWithCost>& start, const Vec& goal) const
314 {
315  Vec d = next - cur;
316  d[2] = 0;
317  float cost = base_->euclidCostRough(d);
318 
319  int sum = 0;
320  const auto cache_page = base_->motion_cache_linear_.find(0, d);
321  if (cache_page == base_->motion_cache_linear_.end(0))
322  return -1;
323  const int num = cache_page->second.getMotion().size();
324  for (const auto& pos_diff : cache_page->second.getMotion())
325  {
326  const Vec pos(cur[0] + pos_diff[0], cur[1] + pos_diff[1], 0);
327  const auto c = base_->cm_rough_[pos];
328  if (c > 99)
329  return -1;
330  sum += c;
331  }
332  const float distf = cache_page->second.getDistance();
333  cost += sum * base_->map_info_.linear_resolution *
334  distf * base_->cc_.weight_costmap_ / (100.0 * num);
335 
336  return cost;
337 }
339  const Vec& cur, const Vec& goal) const
340 {
341  const Vec d = goal - cur;
342  const float cost = base_->euclidCostRough(d);
343 
344  return cost;
345 }
346 const std::vector<GridAstarModel3D::Vec>& GridAstarModel2D::searchGrids(
347  const Vec& cur, const std::vector<VecWithCost>& start, const Vec& goal) const
348 {
349  return base_->search_list_rough_;
350 }
351 } // namespace planner_3d
352 } // namespace planner_cspace
d
Chain d2()
void cycle(const int res, const ArgList &...rest)
Definition: cyclic_vec.h:282
float cost(const Vec &cur, const Vec &next, const std::vector< VecWithCost > &start, const Vec &goal) const final
float costEstim(const Vec &cur, const Vec &goal) const final
const std::vector< Vec > & searchGrids(const Vec &p, const std::vector< VecWithCost > &ss, const Vec &es) const override
f
const Cache::const_iterator end(const int start_yaw) const
Definition: motion_cache.h:79
const CyclicVecInt< 3, 2 > & getMaxRange() const
Definition: motion_cache.h:88
XmlRpcServer s
virtual std::function< void(CyclicVecInt< DIM, NONCYCLIC >, size_t &, size_t &)> getAddressor() const =0
void cycleUnsigned(const int res, const ArgList &...rest)
Definition: cyclic_vec.h:289
IMETHOD Vector diff(const Vector &p_w_a, const Vector &p_w_b, double dt=1)
std::vector< std::vector< Vec > > motion_primitives_
GridAstarModel3D(const costmap_cspace_msgs::MapMetaData3D &map_info, const Vecf &euclid_cost_coef, const int local_range, BlockMemGridmapBase< float, 3, 2 > &cost_estim_cache, BlockMemGridmapBase< char, 3, 2 > &cm, BlockMemGridmapBase< char, 3, 2 > &cm_hyst, BlockMemGridmapBase< char, 3, 2 > &cm_rough, const CostCoeff &cc, const int range)
TFSIMD_FORCE_INLINE tfScalar angle(const Quaternion &q1, const Quaternion &q2)
BlockMemGridmapBase< float, 3, 2 > & cost_estim_cache_
const CyclicVecFloat< 3, 2 > & getMotion(const int start_angle, const CyclicVecInt< 3, 2 > &end) const
void reset(const float linear_resolution, const float angular_resolution, const int range, const std::function< void(CyclicVecInt< 3, 2 >, size_t &, size_t &)> gm_addr)
void reset(const float linear_resolution, const float angular_resolution, const int range)
#define ROS_INFO(...)
float cost(const Vec &cur, const Vec &next, const std::vector< VecWithCost > &start, const Vec &goal) const override
float costEstim(const Vec &cur, const Vec &goal) const override
const std::vector< Vec > & searchGrids(const Vec &cur, const std::vector< VecWithCost > &start, const Vec &goal) const final
void reset(const float angular_resolution, const int range)
const std::pair< float, float > & getRadiuses(const int start_angle, const CyclicVecInt< 3, 2 > &end) const
static std::vector< std::vector< Vec > > build(const costmap_cspace_msgs::MapMetaData3D &map_info, const CostCoeff &cc, const int range)
const Cache::const_iterator find(const int start_yaw, const CyclicVecInt< 3, 2 > &goal) const
Definition: motion_cache.h:70


planner_cspace
Author(s): Atsushi Watanabe
autogenerated on Wed May 12 2021 02:20:42