---

DStar Class Reference

A Modified D* Algorithm. (in work). More...

#include <dstar.h>

Inheritance diagram for DStar:

Public Member Functions
	DStar (OGrid *grid)
	First time search.
bool	search (motion_chain &path, motion start, motion goal)
	Incremental searches.
bool	research (motion_chain &path, motion start, node_chain &changed_nodes)
void	update_nodes (node_chain &changed_nodes)
	incrementally updates all nodes whose cost has changed.
bool	valid ()
	returns false if path is now blocked and needed to be recalculated via research.
void	dump (void)
uint8	cost (int i, int j)
	return cost of location x,y
int	cost (int x, int y, CELL_STATE ctype, node_chain *shadow_nodes=NULL)
Node *	node (uint8 x, uint8 y)
void	InitStar (void)
void	path_flag (motion_chain &path)
	Mark all segments in motion chain as within path.
Protected Member Functions
	DStar (void)
void	GetChildren (Node *n, Node *child[EDGES+1])
void	mark (int x, int y)
Protected Attributes
Node	_field [MAX_STAR_NODES]
OGrid *	_ogrid
Private Member Functions
void	Update_Keys (Node *)
void	update_succ (int)
void	Initialize ()
Priority	CalculateKey (Node *)
bool	ComputeShortestPath ()
void	UpdateVertex (Node *)
Node *	MinSucc (Node *s, int &G)
void	GetPred (Node *u, Node *child[EDGES+1])
void	GetSucc (Node *u, Node *child[EDGES+1])
Node *	Min (Node *s)
int	MinSuccCost (Node *s)
bool	GetPath (motion_chain &)
void	InitDstar (void)
Private Attributes
PriorityQueue	U
int	K_m
Node *	start
Node *	goal
Friends
class	PriorityQueue

---

Detailed Description

A Modified D* Algorithm. (in work).

Original code was based upon Sven Koenig's "Improved Fast Replanning for Robot Navigation in Unknown Terrain" (2002). I started with the optimized, but couldn't get it to work; switched to basic, and still couldn't get it to work. ARRRGGGGHHHHH!!!!!!!!!!!!! Of course a single search works fine.

Note:

The original D* Lite is said to be similar to LPA*, but I noticed LPA* (by comparing the web page app) evaluated many more nodes than it needs. For example, with straight line from start to goal distance =10, LPA* evaluates about 61 nodes. This one evaluates about 11 nodes. The advantage to this is you are more efficient the first time; the disavdavntage, is you possibly have to re-evaluate more often as its more likely a nearby node will change who you haven't already evaluated. The confusion is it's suppose to be similar to LPA*, ins't it?

Most D* algorithms assumes if you have 1 node (u) centered around 4 nodes (a,b,c,d), then you have a cost between every node: c(u,a), c(u,b), c(u,c), c(u,d). Whereas I simply treat node costs like a terrain cost--thus node--not edge giving the result c(u,a) = c(u,b) = c(u,c) = c(u,d). Thus, other Dstar implementation had cost[EDGES] whereas I only have cost. Finally, the consequence of this is that any reference to c(u,v) in psuedocode can be replace with c(u). This has one other suspicious consequence in line {44} rhs(u) = min(rhs(u),c(u,v) + g(v)). Indeed, is this equalvalentto rhs(u) = min(rhs(u),c(u)+g(u)) since there is no edge involved? Remarks Order of operation to do incremental search

• search(...);
• if (valid(...)) to check to see if path is blocked as needed.
• update_nodes(...) at least one before research and after all nodes have changed.
• research(...);

---

Constructor & Destructor Documentation

DStar (  OGrid *  grid  )

First time search.

DStar (  void   )  [protected]

---

Member Function Documentation

Priority CalculateKey (  Node *   )  [private]

bool ComputeShortestPath (   )  [private]

int cost (  int  x, int  y, CELL_STATE  ctype, node_chain *  shadow_nodes = NULL )  [inherited]

set cost of node location x,y. incrementally updates all nodes whose cost has changed.

uint8 cost (  int  i, int  j )  [inherited]

return cost of location x,y

void dump (  void   )

void GetChildren (  Node *  n, Node *  child[EDGES+1] )  [protected, inherited]

bool GetPath (  motion_chain &   )  [private]

void GetPred (  Node *  u, Node *  child[EDGES+1] )  [private]

void GetSucc (  Node *  u, Node *  child[EDGES+1] )  [private]

void InitDstar (  void   )  [private]

void Initialize (   )  [private]

void InitStar (  void   )  [inherited]

cost has range 0..255; 0 is clear, and 255 is "absolute" obstacle (whatever that means). Can recommend areas not to take by setting cell to a value less than the MINIMUM_OBSTACLE value. Once the value exceeds MINIMUM_OBSTACLE, then the cell will not be evaluated in the A* algorithm.

void mark (  int  x, int  y )  [protected, inherited]

Node* Min (  Node *  s  )  [private]

Node* MinSucc (  Node *  s, int &  G )  [private]

int MinSuccCost (  Node *  s  )  [private]

Node* node (  uint8  x, uint8  y )  [inherited]

Return Node at location x,y. (I forget why I needed this). Fills in a node with Terrain type specified.

void path_flag (  motion_chain &  path  )  [inherited]

Mark all segments in motion chain as within path.

bool research (  motion_chain &  path, motion  start, node_chain &  changed_nodes )

bool search (  motion_chain &  path, motion  start, motion  goal )

Incremental searches.

void Update_Keys (  Node *   )  [private]

void update_nodes (  node_chain &  changed_nodes  )

incrementally updates all nodes whose cost has changed. this is done this way because the node_chain is only so big, so this allows nodes to be updated incrementally. Reimplemented from Star.

void update_succ (  int   )  [private]

void UpdateVertex (  Node *   )  [private]

bool valid (   )

returns false if path is now blocked and needed to be recalculated via research.

---

Friends And Related Function Documentation

friend class PriorityQueue [friend]

---

Field Documentation

Node _field[MAX_STAR_NODES] [protected, inherited]

OGrid* _ogrid [protected, inherited]

Node* goal [private]

int K_m [private]

Node* start [private]

PriorityQueue U [private]

---