moveit2
The MoveIt Motion Planning Framework for ROS 2.
GreedyKCenters.h
Go to the documentation of this file.
1 /*********************************************************************
2  * Software License Agreement (BSD License)
3  *
4  * Copyright (c) 2011, Rice University
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 Rice University 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 OWNER 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 
35 /* Author: Mark Moll */
36 
37 // This file is a slightly modified version of <ompl/datastructures/GreedyKCenters.h>
38 
39 #pragma once
40 
41 #include <functional>
42 #include <random>
43 #include <eigen3/Eigen/Core>
44 
46 {
50 template <typename _T>
52 {
53 public:
55  using DistanceFunction = std::function<double(const _T&, const _T&)>;
57  using Matrix = Eigen::MatrixXd;
58 
59  GreedyKCenters() = default;
60  GreedyKCenters(const GreedyKCenters&) = default;
62  GreedyKCenters& operator=(const GreedyKCenters&) = default;
63  GreedyKCenters& operator=(GreedyKCenters&&) noexcept = default;
64  virtual ~GreedyKCenters() = default;
65 
68  {
69  distFun_ = distFun;
70  }
71 
74  {
75  return distFun_;
76  }
77 
86  void kcenters(const std::vector<_T>& data, unsigned int k, std::vector<unsigned int>& centers, Matrix& dists)
87  {
88  // array containing the minimum distance between each data point
89  // and the centers computed so far
90  std::vector<double> min_dist(data.size(), std::numeric_limits<double>::infinity());
91 
92  centers.clear();
93  centers.reserve(k);
94  if (((long unsigned int)dists.rows()) < data.size() || ((long unsigned int)dists.cols()) < k)
95  dists.resize(std::max(2 * ((long unsigned int)dists.rows()) + 1, data.size()), k);
96  // first center is picked randomly
97  centers.push_back(std::uniform_int_distribution<size_t>{ 0, data.size() - 1 }(generator_));
98  for (unsigned i = 1; i < k; ++i)
99  {
100  unsigned ind = 0;
101  const _T& center = data[centers[i - 1]];
102  double max_dist = -std::numeric_limits<double>::infinity();
103  for (unsigned j = 0; j < data.size(); ++j)
104  {
105  if ((dists(j, i - 1) = distFun_(data[j], center)) < min_dist[j])
106  min_dist[j] = dists(j, i - 1);
107  // the j-th center is the one furthest away from center 0,..,j-1
108  if (min_dist[j] > max_dist)
109  {
110  ind = j;
111  max_dist = min_dist[j];
112  }
113  }
114  // no more centers available
115  if (max_dist < std::numeric_limits<double>::epsilon())
116  break;
117  centers.push_back(ind);
118  }
119 
120  const _T& center = data[centers.back()];
121  unsigned i = centers.size() - 1;
122  for (unsigned j = 0; j < data.size(); ++j)
123  dists(j, i) = distFun_(data[j], center);
124  }
125 
126 protected:
129 
131  std::mt19937 generator_{ std::random_device{}() };
132 };
133 } // namespace cached_ik_kinematics_plugin
An instance of this class can be used to greedily select a given number of representatives from a set...
const DistanceFunction & getDistanceFunction() const
Get the distance function used.
GreedyKCenters(const GreedyKCenters &)=default
void kcenters(const std::vector< _T > &data, unsigned int k, std::vector< unsigned int > &centers, Matrix &dists)
Greedy algorithm for selecting k centers.
void setDistanceFunction(const DistanceFunction &distFun)
Set the distance function to use.
Eigen::MatrixXd Matrix
A matrix type for storing distances between points and centers.
std::function< double(const _T &, const _T &)> DistanceFunction
The definition of a distance function.
DistanceFunction distFun_
The used distance function.
GreedyKCenters(GreedyKCenters &&) noexcept=default