Performs iterative deepening search over one unit of modular expansion (see below), i.e. search over one branch stops when it reaches a DEFAULT task. Each DEFAULT Task represents the frontier. The planner expands the search from the frontier with the lowest cost phi (A*-style search), which are logged into a priority queue. More...

#include <planner.h>

Inheritance diagram for HorizonStarPlanner:

[legend]

Collaboration diagram for HorizonStarPlanner:

[legend]

Public Member Functions
std::vector< vertexDescriptor >	plan (TransitionSystem &g, vertexDescriptor src, ExecutionInfo &info, bool *finished=NULL) override
	Implements custom algorithm to search transition system for a plan. More...

Protected Member Functions
void	path2add2 (std::vector< std::vector< vertexDescriptor >>::reverse_iterator &path, const std::vector< vertexDescriptor > &add, std::vector< std::vector< vertexDescriptor >> &paths, TransitionSystem &g)
	Finds the best path to add a frontier to (frontier found separately) More...

std::vector< vertexDescriptor >	best_path (const std::vector< std::vector< vertexDescriptor >> &paths, vertexDescriptor goal, vertexDescriptor cv, bool change, const TransitionSystem &g)
	Searches all paths for best path according to the lowest final cost phi. More...

std::vector< Frontier >	frontierVertices (vertexDescriptor v, TransitionSystem &g, ExecutionInfo &info)
	Performs iterative deepening search to find the frontier. More...

void	addToPriorityQueue (const Frontier &f, std::vector< Frontier > &queue, TransitionSystem &g, vertexDescriptor goal=TransitionSystem::null_vertex())
	Adds frontier to priority queue. More...

Protected Attributes
const Direction	frontier_direction =DEFAULT
	The depth-first search portion of iterative deepening will stop when it reaches a DEFAULT task.

Additional Inherited Members
Static Public Member Functions inherited from Planner
static float	evaluationFunction (EndedResult er, const vertexDescriptor &v, std::vector< vertexDescriptor > &p)
	calculates cumulative cost phi, add discount factor if in plan More...

static EndedResult	estimateCost (const State &state, b2Transform start, Direction d, Task &_goal)
	Estimates cost (phi) of a state as a measure of: past cost (gamma): the position relative to an obstacle, if present future cost heuristic (chi): the position relative to a goal, if present. More...

Detailed Description

Performs iterative deepening search over one unit of modular expansion (see below), i.e. search over one branch stops when it reaches a DEFAULT task. Each DEFAULT Task represents the frontier. The planner expands the search from the frontier with the lowest cost phi (A*-style search), which are logged into a priority queue.

NB: maximum amount of nodes traversed to find a DEFAULT task is three from the start node, including the DEFAULT task

                       EXAMPLE MODULE

             q2(LEFT)---q3(DEFAULT)
            /   
          q0 --- q1(DEFAULT)
            \
             q4(RIGHT)
                      \
                       q5(RIGHT)---q6(DEFAULT)      ->  maximum depth

Member Function Documentation

◆ addToPriorityQueue()

void HorizonStarPlanner::addToPriorityQueue	(	const Frontier &	f,
		std::vector< Frontier > &	queue,
		TransitionSystem &	g,
		vertexDescriptor	goal = `TransitionSystem::null_vertex()`
	)

protected

Adds frontier to priority queue.

Parameters

f	the frontier
queue	the priority queue
g	the transition system
goal	the vertex where the goal is reach

◆ best_path()

std::vector< vertexDescriptor > HorizonStarPlanner::best_path	(	const std::vector< std::vector< vertexDescriptor >> &	paths,
		vertexDescriptor	goal,
		vertexDescriptor	cv,
		bool	change,
		const TransitionSystem &	g
	)

protected

Searches all paths for best path according to the lowest final cost phi.

Parameters

paths	all the paths
goal	the goal vertex (if known)
cv	the current vertex
change	whether the task needs to be changed
g	the transition system

Returns: the plan!

◆ frontierVertices()

std::vector< Frontier > HorizonStarPlanner::frontierVertices	(	vertexDescriptor	v,
		TransitionSystem &	g,
		ExecutionInfo &	info
	)

protected

Performs iterative deepening search to find the frontier.

Parameters

v	source vertex: we find the frontier from here
g	the transitionSystem
d
info

Returns: std::vector <Frontier>

◆ path2add2()

void HorizonStarPlanner::path2add2	(	std::vector< std::vector< vertexDescriptor >>::reverse_iterator &	path,
		const std::vector< vertexDescriptor > &	add,
		std::vector< std::vector< vertexDescriptor >> &	paths,
		TransitionSystem &	g
	)

protected

Finds the best path to add a frontier to (frontier found separately)

Parameters

path	the path to add to
add	the frontier
paths	all the paths
g	the transition system

◆ plan()

std::vector< vertexDescriptor > HorizonStarPlanner::plan	(	TransitionSystem &	g,
		vertexDescriptor	src,
		ExecutionInfo &	info,
		bool *	finished = `NULL`
	)

overridevirtual

Implements custom algorithm to search transition system for a plan.

Parameters

g	the transitionSystem
src	vertex from which the planning start
info	execution info
finished	will return true if the planning process reaches the goal

Returns: std::vector<vertexDescriptor>

Implements Planner.

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

src/planner.h
src/planner.cpp

Public Member Functions

Protected Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ addToPriorityQueue()

◆ best_path()

◆ frontierVertices()

◆ path2add2()

◆ plan()