Fawkes API  Fawkes Development Version
fawkes::NavGraphSearchState Class Reference

Graph-based path planner A* search state. More...

#include <>>

Inheritance diagram for fawkes::NavGraphSearchState:

Public Member Functions

 NavGraphSearchState (fawkes::NavGraphNode node, fawkes::NavGraphNode goal, fawkes::NavGraph *map_graph, fawkes::NavGraphConstraintRepo *constraint_repo=NULL)
 Constructor. More...
 
 NavGraphSearchState (fawkes::NavGraphNode node, fawkes::NavGraphNode goal, fawkes::NavGraph *map_graph, navgraph::EstimateFunction estimate_func, navgraph::CostFunction cost_func=NavGraphSearchState::euclidean_cost, fawkes::NavGraphConstraintRepo *constraint_repo=NULL)
 Constructor. More...
 
 ~NavGraphSearchState ()
 Destructor. More...
 
fawkes::NavGraphNodenode ()
 Get graph node corresponding to this search state. More...
 
virtual size_t key ()
 Generates a unique key for this state. More...
 
virtual float estimate ()
 Estimate the heuristic cost to the goal. More...
 
virtual bool is_goal ()
 Check, wether we reached a goal or not. More...
 
- Public Member Functions inherited from fawkes::AStarState
 AStarState (float cost_sofar, AStarState *parent)
 Constructor. More...
 
virtual ~AStarState ()
 Destructor. More...
 
 AStarState ()
 This is the standard constructor. More...
 
 AStarState (int x, int y, int past_cost, AStarState *father)
 This is another standard constuctor, this time parametrized. More...
 

Static Public Member Functions

static float euclidean_cost (const fawkes::NavGraphNode &from, const fawkes::NavGraphNode &to)
 Determine euclidean cost between two nodes. More...
 
static float straight_line_estimate (const fawkes::NavGraphNode &node, const fawkes::NavGraphNode &goal)
 Determine straight line estimate between two nodes. More...
 

Additional Inherited Members

- Public Attributes inherited from fawkes::AStarState
AStarStateparent
 Predecessor. More...
 
float path_cost
 Cost of path leading to this search state. More...
 
float total_estimated_cost
 Total estimated cost. More...
 
int x_
 x coordinate of the state More...
 
int y_
 y coordinate of the state More...
 
AStarStatefather_
 The predecessor state. More...
 
int past_cost_
 The past cost. More...
 
int total_cost_
 The total cost. More...
 

Detailed Description

Graph-based path planner A* search state.

Author
Tim Niemueller

Definition at line 38 of file search_state.h.

Constructor & Destructor Documentation

◆ NavGraphSearchState() [1/2]

fawkes::NavGraphSearchState::NavGraphSearchState ( fawkes::NavGraphNode  node,
fawkes::NavGraphNode  goal,
fawkes::NavGraph map_graph,
fawkes::NavGraphConstraintRepo constraint_repo = NULL 
)

Constructor.

Parameters
nodegraph node this search state represents
goalgraph node of the goal
map_graphmap graph
constraint_repoconstraint repository, null to plan only without constraints

Definition at line 81 of file search_state.cpp.

References estimate(), euclidean_cost(), fawkes::NavGraphNode::name(), node(), fawkes::AStarState::path_cost, straight_line_estimate(), and fawkes::AStarState::total_estimated_cost.

Referenced by is_goal(), and straight_line_estimate().

◆ NavGraphSearchState() [2/2]

fawkes::NavGraphSearchState::NavGraphSearchState ( fawkes::NavGraphNode  node,
fawkes::NavGraphNode  goal,
fawkes::NavGraph map_graph,
navgraph::EstimateFunction  estimate_func,
navgraph::CostFunction  cost_func = NavGraphSearchState::euclidean_cost,
fawkes::NavGraphConstraintRepo constraint_repo = NULL 
)

Constructor.

Parameters
nodegraph node this search state represents
goalgraph node of the goal
map_graphmap graph
estimate_funcfunction to estimate the cost from any node to the goal. Note that the estimate function must be admissible for optimal A* search. That means that for no query may the calculated estimate be higher than the actual cost.
cost_funcfunction to calculate the cost from a node to another adjacent node. Note that the cost function is directly related to the estimate function. For example, the cost can be calculated in terms of distance between nodes, or in time that it takes to travel from one node to the other. The estimate function must match the cost function to be admissible.
constraint_repoconstraint repository, null to plan only without constraints

Definition at line 117 of file search_state.cpp.

References estimate(), fawkes::NavGraphNode::name(), node(), fawkes::AStarState::path_cost, and fawkes::AStarState::total_estimated_cost.

◆ ~NavGraphSearchState()

fawkes::NavGraphSearchState::~NavGraphSearchState ( )

Destructor.

Definition at line 138 of file search_state.cpp.

Member Function Documentation

◆ estimate()

float fawkes::NavGraphSearchState::estimate ( )
virtual

Estimate the heuristic cost to the goal.

Returns
estimated cost

Implements fawkes::AStarState.

Definition at line 154 of file search_state.cpp.

Referenced by key(), and NavGraphSearchState().

◆ euclidean_cost()

static float fawkes::NavGraphSearchState::euclidean_cost ( const fawkes::NavGraphNode from,
const fawkes::NavGraphNode to 
)
inlinestatic

Determine euclidean cost between two nodes.

Note that the given notes are assumed to be adjacent nodes.

Parameters
fromoriginating node
todestination node
Returns
cost from from to to.

Definition at line 66 of file search_state.h.

References fawkes::NavGraphNode::x(), and fawkes::NavGraphNode::y().

Referenced by fawkes::NavGraph::NavGraph(), NavGraphSearchState(), and fawkes::NavGraph::unset_search_funcs().

◆ is_goal()

bool fawkes::NavGraphSearchState::is_goal ( )
virtual

◆ key()

virtual size_t fawkes::NavGraphSearchState::key ( )
inlinevirtual

Generates a unique key for this state.

There has to be a unique key for each state (fast closed list -> bottleneck!)

Returns
unique key

Implements fawkes::AStarState.

Definition at line 55 of file search_state.h.

References estimate(), and is_goal().

◆ node()

fawkes::NavGraphNode & fawkes::NavGraphSearchState::node ( )

Get graph node corresponding to this search state.

Returns
graph node corresponding to this search state

Definition at line 147 of file search_state.cpp.

Referenced by NavGraphSearchState().

◆ straight_line_estimate()

static float fawkes::NavGraphSearchState::straight_line_estimate ( const fawkes::NavGraphNode node,
const fawkes::NavGraphNode goal 
)
inlinestatic

Determine straight line estimate between two nodes.

Parameters
nodenode to query heuristic value for
goalgoal node to get estimate for
Returns
estimate of cost from node to goal.

Definition at line 79 of file search_state.h.

References NavGraphSearchState(), fawkes::NavGraphNode::x(), and fawkes::NavGraphNode::y().

Referenced by fawkes::NavGraph::NavGraph(), NavGraphSearchState(), and fawkes::NavGraph::unset_search_funcs().


The documentation for this class was generated from the following files: