estar::Algorithm Class Reference

#include <Algorithm.hpp>

List of all members.

---

Detailed Description

Medium-level layer for controlling E*.

It uses the underlying C-space graph etc for implementing E*. End-users will probably prefer Facade, which provides higher level access.

Public Member Functions
	Algorithm (boost::shared_ptr< BaseCSpace > cspace, bool check_upwind, bool check_local_consistency, bool check_queue_key, bool auto_reset, bool auto_flush)
void	AddVertex (vertex_t vertex, const Kernel &kernel)
	For telling the algorithm that a vertex has been added to C-space (after the algorithm has started running).
void	AddGoal (vertex_t vertex, double value)
	Declare a node to be a goal vertex, and fix its value.
void	RemoveGoal (vertex_t vertex)
	Declare that a node is not a goal anymore.
void	RemoveAllGoals ()
	Flag all goal nodes as "normal" again, and request a Reset() for the next ComputeOne().
void	Reset ()
	Reset the algorithm, preserving only goal information.
bool	IsGoal (vertex_t vertex) const
	Returns: True if the node is part of the goal set.
void	SetMeta (vertex_t vertex, double meta, const Kernel &kernel)
void	ComputeOne (const Kernel &kernel, double slack)
	Perform an elementary propagation (or "expansion") step.
bool	HaveWork () const
	Returns: True if there is something to do, such as expanding a node or re-initializing the algorithm after a goal removal.
boost::shared_ptr< BaseCSpace const >	GetCSpace () const
	Read-only access to C-space.
const cspace_t &	GetCSpaceGraph () const
	Read-only access to the C-space graph.
const value_map_t &	GetValueMap () const
	Read-only access to the values of all C-space nodes.
const meta_map_t &	GetMetaMap () const
	Read-only access to the meta information of all C-space nodes.
const rhs_map_t &	GetRhsMap () const
	Read-only access to the rhs-value of all C-space nodes.
const flag_map_t &	GetFlagMap () const
	Read-only access to the flags (flag_t) of all C-space nodes.
const vertexid_map_t &	GetVertexIdMap () const
	Read-only access to the vertex ID of all C-space nodes, useful for adding user-defined data to nodes.
const Queue &	GetQueue () const
	Read-only access to the wavefront queue.
const Upwind &	GetUpwind () const
	Read-only access to the upwind graph, which traces on which neighbor's a node's value depends.
Queue &	GetQueue ()
	Write-access to the upwind queue.
size_t	GetStep () const
	Returns: The number of times that ComputeOne() has actually done something.
double	GetLastComputedValue () const
	Returns: The last value that was used in ComputeOne().
vertex_t	GetLastComputedVertex () const
	Returns: The ID of the vertex that was last touched by ComputeOne().
double	GetLastPoppedKey () const
	Returns: The queue key of the vertex that was last expanded by ComputeOne().
Private Types
typedef std::set< vertex_t >	goalset_t
Private Member Functions
void	UpdateVertex (vertex_t vertex, const Kernel &kernel)
void	DoComputeOne (const Kernel &kernel, double slack)
Private Attributes
boost::shared_ptr< BaseCSpace >	m_cspace
Queue	m_queue
Upwind	m_upwind
goalset_t	m_goalset
size_t	m_step
double	m_last_computed_value
vertex_t	m_last_computed_vertex
double	m_last_popped_key
bool	m_pending_reset
bool	m_auto_reset
bool	m_auto_flush
cspace_t &	m_cspace_graph
value_map_t &	m_value
meta_map_t &	m_meta
rhs_map_t &	m_rhs
flag_map_t &	m_flag
boost::scoped_ptr< PropagatorFactory >	m_propfactory

---

Member Typedef Documentation

typedef std::set<vertex_t> estar::Algorithm::goalset_t [private]

---

Constructor & Destructor Documentation

estar::Algorithm::Algorithm	(	boost::shared_ptr< BaseCSpace >	cspace,
		bool	check_upwind,
		bool	check_local_consistency,
		bool	check_queue_key,
		bool	auto_reset,
		bool	auto_flush
	)

Parameters:

cspace	The object that represents the planning space.
check_upwind	Whether to check the upwind structure when computing the propagator set of a node. Use false to mimic old behavior.
check_local_consistency	Whether to check for local consistency (rhs==value) when computing the propagator set of a node. Use false to mimic old behavior.
check_queue_key	Whether to check if a neighbor lies below the wavefront when computing the propagator set of a node. Use false to mimic old behavior
auto_reset	Whether to automatically reset the whole E* computations when meta information changes. This is usually not needed.
auto_flush	Whether to automatically propagate until the entire queue has been emptied each time you call ComputeOne(). This is usually a waste of resources.

---

Member Function Documentation

void estar::Algorithm::AddVertex	(	vertex_t	vertex,
		const Kernel &	kernel
	)

For telling the algorithm that a vertex has been added to C-space (after the algorithm has started running).

The new node's value, rhs, and flag properties are properly initialized, but the meta will not be touched. The vertex is put on the wavefront queue if appropriate (one of its neighbors lies below the wavefront). Before calling this method, the new vertex must already be properly inserted into the C-space structure, particularly its neighbors must already be defined.

Note:

We assume that any vertices added after the algorithm started will be inserted with infinite value. This makes it OK to subsequently add edges between existing vertices and new vertices without reconsidering the value (and queueing) of the existing vertex, as no new information could flow from the new to the old node.

void estar::Algorithm::AddGoal	(	vertex_t	vertex,
		double	value
	)

Declare a node to be a goal vertex, and fix its value.

This only works as expected if the goal vertex is already connected to its neighbors. Specifying a value is useful for seeding the interpolation with a range of smoothly varying "true distance" values along the edges of an extended goal Region.

If the vertex is already a goal, this method still checks if the value is different, and queues it if necessary. If the vertex is not yet a goal but the value happens to be the same, this method essentially "freezes" the vertex such that subsequent sweeps of the wavefront will not affect it.

void estar::Algorithm::RemoveGoal

(

vertex_t

vertex

)

Declare that a node is not a goal anymore.

This causes the whole Algorithm to Reset() the next time you call ComputeOne(). If the vertex was not a goal to begin with, however, this expensive operation is not performed.

void estar::Algorithm::RemoveAllGoals

(

)

Flag all goal nodes as "normal" again, and request a Reset() for the next ComputeOne().

Note, however, that ComputeOne() will only do something useful if there is at least one goal node.

void estar::Algorithm::Reset

(

)

Reset the algorithm, preserving only goal information.

This means:

• clear the wavefront queue
• set all values to infinity
• set non-goal rhs values to infinity
• clear non-goal flags
• requeue goal cells (remember, their rhs values were preserved, which will make the original goal values reappear as soon as they have been popped off the queue and expanded)

Note:

Automatically called from ComputeOne() if necessary (ie after goal removal).

bool estar::Algorithm::IsGoal

(

vertex_t

vertex

)

const

Returns:

True if the node is part of the goal set.

void estar::Algorithm::SetMeta	(	vertex_t	vertex,
		double	meta,
		const Kernel &	kernel
	)

Unlike InitMeta() which should only be used during initialisation, this method also performs the correct updates by estimating the new one-step-lookahead rhs-value, entering the vertex into the Queue, and updating the upwind graph accordingly.

The interpretation of the meta information, which encodes traversability information, depends on the Kernel. For example, the LSMKernel uses meta=0 for obstacles and meta=1 for freespace. In order to manage the meta information more or less generically, you can use Kernel::GetFreespaceMeta(), Kernel::GetObstacleMeta(), Kernel::ChangeWouldRaise(), or one of the RiskMap subclasses to translate from the general notion of "collision risk" to the Kernel-dependent meta interpretation.

void estar::Algorithm::ComputeOne	(	const Kernel &	kernel,
		double	slack
	)

Perform an elementary propagation (or "expansion") step.

This is a no-op if the queue is empty. If there is a pending Reset(), such as after RemoveGoal() or any meta modification with an enabled m_auto_reset option, the reset is performed first. If m_auto_flush is set, the computation is iterated until the queue is empty.

Node expansion means:

1. Take the top vertex from the Queue.
2. Check if it is "different enough" to warrant computations. This is controlled by the "slack" parameter, which should be significantly smaller than the smallest meaningful increment of value between two neighbors. For example, if you're using a grid with a certain "scale" (the distance between two neighboring nodes), then slack should be something like scale/10000.
3. If the node's value gets decreased, update all neighbors as they might in turn get lowered.
4. Otherwise, if the value gets raised, set this node to infinity, update all its downwind neighbors (whose value was computed using the just-raised node), and re-queue the node such that it may be lowered on its next turn

Todo:

Wasn't "slack" a bit of a hack at one point? Should test if we can take it out now, and just use epsilon as everywhere else...

Parameters:

slack

Value changes smaller than this are ignored. Slack should be significantly smaller than the smallest expected useful increment of value between two neighboring nodes. For example, if you're using a Grid instance, it is suggested to use slack=scale/10000 or so.

bool estar::Algorithm::HaveWork

(

)

const

Returns:

True if there is something to do, such as expanding a node or re-initializing the algorithm after a goal removal.

boost::shared_ptr<BaseCSpace const> estar::Algorithm::GetCSpace

(

)

const [inline]

Read-only access to C-space.

const cspace_t& estar::Algorithm::GetCSpaceGraph

(

)

const [inline]

Read-only access to the C-space graph.

const value_map_t& estar::Algorithm::GetValueMap

(

)

const [inline]

Read-only access to the values of all C-space nodes.

const meta_map_t& estar::Algorithm::GetMetaMap

(

)

const [inline]

Read-only access to the meta information of all C-space nodes.

const rhs_map_t& estar::Algorithm::GetRhsMap

(

)

const [inline]

Read-only access to the rhs-value of all C-space nodes.

const flag_map_t& estar::Algorithm::GetFlagMap

(

)

const [inline]

Read-only access to the flags (flag_t) of all C-space nodes.

const vertexid_map_t& estar::Algorithm::GetVertexIdMap

(

)

const [inline]

Read-only access to the vertex ID of all C-space nodes, useful for adding user-defined data to nodes.

Note:

Check out the CustomCSpace template.

const Queue& estar::Algorithm::GetQueue

(

)

const [inline]

Read-only access to the wavefront queue.

const Upwind& estar::Algorithm::GetUpwind

(

)

const [inline]

Read-only access to the upwind graph, which traces on which neighbor's a node's value depends.

Queue& estar::Algorithm::GetQueue

(

)

[inline]

Write-access to the upwind queue.

Should not be required anymore, unless you're developing some new features that should probably go into the Algorithm class when you're done.

size_t estar::Algorithm::GetStep

(

)

const [inline]

Returns:

The number of times that ComputeOne() has actually done something.

double estar::Algorithm::GetLastComputedValue

(

)

const [inline]

Returns:

The last value that was used in ComputeOne().

vertex_t estar::Algorithm::GetLastComputedVertex

(

)

const [inline]

Returns:

The ID of the vertex that was last touched by ComputeOne().

double estar::Algorithm::GetLastPoppedKey

(

)

const [inline]

Returns:

The queue key of the vertex that was last expanded by ComputeOne().

void estar::Algorithm::UpdateVertex	(	vertex_t	vertex,
		const Kernel &	kernel
	)			[private]

void estar::Algorithm::DoComputeOne	(	const Kernel &	kernel,
		double	slack
	)			[private]

---

Member Data Documentation

boost::shared_ptr<BaseCSpace> estar::Algorithm::m_cspace [private]

Queue estar::Algorithm::m_queue [private]

Upwind estar::Algorithm::m_upwind [private]

goalset_t estar::Algorithm::m_goalset [private]

size_t estar::Algorithm::m_step [private]

double estar::Algorithm::m_last_computed_value [private]

vertex_t estar::Algorithm::m_last_computed_vertex [private]

double estar::Algorithm::m_last_popped_key [private]

bool estar::Algorithm::m_pending_reset [private]

bool estar::Algorithm::m_auto_reset [private]

bool estar::Algorithm::m_auto_flush [private]

cspace_t& estar::Algorithm::m_cspace_graph [private]

value_map_t& estar::Algorithm::m_value [private]

meta_map_t& estar::Algorithm::m_meta [private]

rhs_map_t& estar::Algorithm::m_rhs [private]

flag_map_t& estar::Algorithm::m_flag [private]

boost::scoped_ptr<PropagatorFactory> estar::Algorithm::m_propfactory [private]

---

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

• estar/Algorithm.hpp
• estar/Algorithm.cpp

---

E* Interpolated Graph Replanner Wed Dec 12 18:55:49 2007