von_neumann_path.cpp
Go to the documentation of this file.
1 /*
2  * Software License Agreement (BSD License)
3  *
4  * Copyright (c) 2018, Locus Robotics
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  * notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above
14  * copyright notice, this list of conditions and the following
15  * disclaimer in the documentation and/or other materials provided
16  * with the distribution.
17  * * Neither the name of the copyright holder nor the names of its
18  * contributors may be used to endorse or promote products derived
19  * from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  */
34 
37 #include <nav_core2/exceptions.h>
38 #include <limits>
40 
42 
43 namespace dlux_plugins
44 {
45 nav_2d_msgs::Path2D VonNeumannPath::getPath(const dlux_global_planner::PotentialGrid& potential_grid,
46  const geometry_msgs::Pose2D& start, const geometry_msgs::Pose2D& goal,
47  double& path_cost)
48 {
49  nav_2d_msgs::Path2D path;
50  path_cost = 0.0;
51 
52  unsigned int current_x = 0, current_y = 0;
53  worldToGridBounded(potential_grid.getInfo(), start.x, start.y, current_x, current_y);
54 
55  // Add 0.5 to represent center of the cell
56  geometry_msgs::Pose2D current;
57  current.x = current_x + 0.5;
58  current.y = current_y + 0.5;
59  path.poses.push_back(current);
60  path_cost += cost_interpreter_->getCost(current_x, current_y);
61 
62  unsigned int goal_index = potential_grid.getIndex(goal.x, goal.y);
63 
64  // Main Loop
65  while (potential_grid.getIndex(current_x, current_y) != goal_index)
66  {
67  float min_val = std::numeric_limits<float>::max();
68  unsigned int min_x = 0, min_y = 0;
69  unsigned int x, y;
70  int index;
71 
72  // Check the four neighbors
73  if (current_x > 0)
74  {
75  x = current_x - 1;
76  y = current_y;
77  index = potential_grid.getIndex(x, y);
78  if (potential_grid[index] < min_val)
79  {
80  min_val = potential_grid[index];
81  min_x = x;
82  min_y = y;
83  }
84  }
85  if (current_x < potential_grid.getWidth() - 1)
86  {
87  x = current_x + 1;
88  y = current_y;
89  index = potential_grid.getIndex(x, y);
90  if (potential_grid[index] < min_val)
91  {
92  min_val = potential_grid[index];
93  min_x = x;
94  min_y = y;
95  }
96  }
97  if (current_y > 0)
98  {
99  x = current_x;
100  y = current_y - 1;
101  index = potential_grid.getIndex(x, y);
102  if (potential_grid[index] < min_val)
103  {
104  min_val = potential_grid[index];
105  min_x = x;
106  min_y = y;
107  }
108  }
109  if (current_y < potential_grid.getHeight() - 1)
110  {
111  x = current_x;
112  y = current_y + 1;
113  index = potential_grid.getIndex(x, y);
114  if (potential_grid[index] < min_val)
115  {
116  min_val = potential_grid[index];
117  min_x = x;
118  min_y = y;
119  }
120  }
121 
122  if (min_val == std::numeric_limits<float>::max())
123  throw nav_core2::PlannerException("Reached dead end in traceback.");
124 
125  // Move to the Min Neighbor
126  current_x = min_x;
127  current_y = min_y;
128 
129  // Add 0.5 to represent center of the cell
130  current.x = current_x + 0.5;
131  current.y = current_y + 0.5;
132  path.poses.push_back(current);
133  path_cost += cost_interpreter_->getCost(current_x, current_y);
134  }
135  return mapPathToWorldPath(path, potential_grid.getInfo());
136 }
137 
138 } // namespace dlux_plugins
Traceback function that moves from cell to cell using only the four neighbors.
unsigned int getIndex(unsigned int mx, unsigned int my) const
TFSIMD_FORCE_INLINE const tfScalar & y() const
unsigned int getHeight() const
TFSIMD_FORCE_INLINE const tfScalar & x() const
unsigned int getWidth() const
NavGridInfo getInfo() const
#define PLUGINLIB_EXPORT_CLASS(class_type, base_class_type)
bool worldToGridBounded(const NavGridInfo &info, double wx, double wy, unsigned int &mx, unsigned int &my)


dlux_plugins
Author(s):
autogenerated on Wed Jun 26 2019 20:06:32