graph_search.h

Go to the documentation of this file.

/*********************************************************************
 *
 * Software License Agreement (BSD License)
 *
 *  Copyright (c) 2017,
 *  TU Dortmund - Institute of Control Theory and Systems Engineering.
 *  All rights reserved.
 *
 *  Redistribution and use in source and binary forms, with or without
 *  modification, are permitted provided that the following conditions
 *  are met:
 *
 *   * Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 *   * Redistributions in binary form must reproduce the above
 *     copyright notice, this list of conditions and the following
 *     disclaimer in the documentation and/or other materials provided
 *     with the distribution.
 *   * Neither the name of the institute nor the names of its
 *     contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *
 *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 *  POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Christoph Rösmann, Franz Albers
 *********************************************************************/
 
#ifndef GRAPH_SEARCH_INTERFACE_H
#define GRAPH_SEARCH_INTERFACE_H
 
#ifdef BOOST_NO_CXX11_DEFAULTED_FUNCTIONS
  #include <boost/graph/adjacency_list.hpp>
#else
  // Workaround for a bug in boost graph library (concerning directed graphs), boost version 1.48:
  // boost::add_vertex requires a move constructor/assignment operator in one of the underlying boost objects if C++11 is activated,
  // but they are missing. The compiler fails due to an implicit deletion. We just deactivate C++11 default functions for now.
  #define BOOST_NO_CXX11_DEFAULTED_FUNCTIONS
  #include <boost/graph/adjacency_list.hpp>
  #undef BOOST_NO_CXX11_DEFAULTED_FUNCTIONS
#endif
 
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/utility.hpp>
#include <boost/random.hpp>
 
#include <Eigen/Core>
 
#include <geometry_msgs/Twist.h>
 
#include <teb_local_planner/equivalence_relations.h>
#include <teb_local_planner/pose_se2.h>
#include <teb_local_planner/teb_config.h>
 
namespace teb_local_planner
{
 
class HomotopyClassPlanner; // Forward declaration
 
struct HcGraphVertex
{
public:
  Eigen::Vector2d pos; // position of vertices in the map
  EIGEN_MAKE_ALIGNED_OPERATOR_NEW
};
 
typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS, HcGraphVertex, boost::no_property > HcGraph;
typedef boost::graph_traits<HcGraph>::vertex_descriptor HcGraphVertexType;
typedef boost::graph_traits<HcGraph>::edge_descriptor HcGraphEdgeType;
typedef boost::graph_traits<HcGraph>::vertex_iterator HcGraphVertexIterator;
typedef boost::graph_traits<HcGraph>::edge_iterator HcGraphEdgeIterator;
typedef boost::graph_traits<HcGraph>::adjacency_iterator HcGraphAdjecencyIterator;
 
inline std::complex<long double> getCplxFromHcGraph(HcGraphVertexType vert_descriptor, const HcGraph& graph)
{
  return std::complex<long double>(graph[vert_descriptor].pos.x(), graph[vert_descriptor].pos.y());
}
 
inline const Eigen::Vector2d& getVector2dFromHcGraph(HcGraphVertexType vert_descriptor, const HcGraph& graph)
{
  return graph[vert_descriptor].pos;
}
 
class GraphSearchInterface
{
public:
 
  virtual void createGraph(const PoseSE2& start, const PoseSE2& goal, double dist_to_obst, double obstacle_heading_threshold, const geometry_msgs::Twist* start_velocity, bool free_goal_vel = false) = 0;
 
  void clearGraph() {graph_.clear();}
 
  // HcGraph graph() const {return graph_;}
  // Workaround. graph_ is public for now, beacuse otherwise the compilation fails with the same boost bug mentioned above.
  HcGraph graph_; 
 
protected:
  GraphSearchInterface(const TebConfig& cfg, HomotopyClassPlanner* hcp) : cfg_(&cfg), hcp_(hcp){}
 
  void DepthFirst(HcGraph& g, std::vector<HcGraphVertexType>& visited, const HcGraphVertexType& goal, double start_orientation, double goal_orientation, const geometry_msgs::Twist* start_velocity, bool free_goal_vel = false);
 
 
protected:
    const TebConfig* cfg_; 
    HomotopyClassPlanner* const hcp_; 
 
public:
  EIGEN_MAKE_ALIGNED_OPERATOR_NEW
};
 
 
 
class lrKeyPointGraph : public GraphSearchInterface
{
public:
  lrKeyPointGraph(const TebConfig& cfg, HomotopyClassPlanner* hcp) : GraphSearchInterface(cfg, hcp){}
 
  virtual ~lrKeyPointGraph(){}
 
  virtual void createGraph(const PoseSE2& start, const PoseSE2& goal, double dist_to_obst, double obstacle_heading_threshold, const geometry_msgs::Twist* start_velocity, bool free_goal_vel = false);
};
 
 
 
 
class ProbRoadmapGraph : public GraphSearchInterface
{
public:
  ProbRoadmapGraph(const TebConfig& cfg, HomotopyClassPlanner* hcp) : GraphSearchInterface(cfg, hcp){}
 
  virtual ~ProbRoadmapGraph(){}
 
 
  virtual void createGraph(const PoseSE2& start, const PoseSE2& goal, double dist_to_obst, double obstacle_heading_threshold, const geometry_msgs::Twist* start_velocity, bool free_goal_vel = false);
 
private:
    boost::random::mt19937 rnd_generator_; 
};
} // end namespace
 
#endif // GRAPH_SEARCH_INTERFACE_H