Fawkes API
Fawkes Development Version
|
Graph-based path planner A* search state. More...
#include <>>
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::NavGraphNode & | node () |
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... | |
![]() | |
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 | |
![]() | |
AStarState * | parent |
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... | |
AStarState * | father_ |
The predecessor state. More... | |
int | past_cost_ |
The past cost. More... | |
int | total_cost_ |
The total cost. More... | |
Graph-based path planner A* search state.
Definition at line 38 of file search_state.h.
fawkes::NavGraphSearchState::NavGraphSearchState | ( | fawkes::NavGraphNode | node, |
fawkes::NavGraphNode | goal, | ||
fawkes::NavGraph * | map_graph, | ||
fawkes::NavGraphConstraintRepo * | constraint_repo = NULL |
||
) |
Constructor.
node | graph node this search state represents |
goal | graph node of the goal |
map_graph | map graph |
constraint_repo | constraint 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().
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.
node | graph node this search state represents |
goal | graph node of the goal |
map_graph | map graph |
estimate_func | function 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_func | function 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_repo | constraint 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.
fawkes::NavGraphSearchState::~NavGraphSearchState | ( | ) |
Destructor.
Definition at line 138 of file search_state.cpp.
|
virtual |
Estimate the heuristic cost to the goal.
Implements fawkes::AStarState.
Definition at line 154 of file search_state.cpp.
Referenced by key(), and NavGraphSearchState().
|
inlinestatic |
Determine euclidean cost between two nodes.
Note that the given notes are assumed to be adjacent nodes.
from | originating node |
to | destination node |
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().
|
virtual |
Check, wether we reached a goal or not.
Implements fawkes::AStarState.
Definition at line 161 of file search_state.cpp.
References fawkes::NavGraphConstraintRepo::blocks(), fawkes::NavGraphConstraintRepo::increases_cost(), fawkes::NavGraphNode::name(), NavGraphSearchState(), fawkes::NavGraph::node(), fawkes::AStarState::path_cost, and fawkes::NavGraphNode::reachable_nodes().
Referenced by key().
|
inlinevirtual |
Generates a unique key for this state.
There has to be a unique key for each state (fast closed list -> bottleneck!)
Implements fawkes::AStarState.
Definition at line 55 of file search_state.h.
References estimate(), and is_goal().
fawkes::NavGraphNode & fawkes::NavGraphSearchState::node | ( | ) |
Get graph node corresponding to this search state.
Definition at line 147 of file search_state.cpp.
Referenced by NavGraphSearchState().
|
inlinestatic |
Determine straight line estimate between two nodes.
node | node to query heuristic value for |
goal | goal node to get estimate for |
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().