---

FDP Class Reference

A dynamic programming approach to nonholonomic planning, as proposed by Barraquand, Latombe, Algorithmica 10:6, pp. 121-155, 1993. More...

#include <fdp.h>

Inheritance diagram for FDP::

List of all members.

Public Methods
	FDP (Problem *problem)
	A constructor that initializes data members.
	~FDP ()
	Empty destructor.
virtual void	Reset ()
	Reset the planner.
virtual bool	Plan ()
	Attempt to solve an Initial-Goal query by growing an FDP tree.
Public Attributes
int	SatisfiedCount
	Number of times the collision checker has been called.
Protected Methods
virtual double	SearchCost (double initcost, MSLNode *&n, MSLNode *&nn)
virtual vector<int>	StateToIndices (const MSLVector &x)
virtual MSLVector	IndicesToState (const vector< int > &indices)
Protected Attributes
priority_queue<MSLNode*,vector< MSLNode*>,MSLNodeGreater>	Q
	Priority queue of nodes.
MultiArray<int>*	Grid
	A quantized state space.
vector<int>	GridDimensions
	Dimensions for the grid.
int	GridDefaultResolution
	Default size for each axis of the grid.
MSLVector	Quantization
	The quantized step size for each axis (computed automatically).

---

Detailed Description

A dynamic programming approach to nonholonomic planning, as proposed by Barraquand, Latombe, Algorithmica 10:6, pp. 121-155, 1993.

Forward Dynamic Programming, as proposed by Barraquand, Latombe, Algorithmica 10:6, pp. 121-155, 1993. The solutions should be optimized with respect to time, although problems can be caused by quantization errors.

When an instance is constructed, a grid is initialized and each element of checked for collision. The test point for collision is the center of the cell. The current version does not use distance computations; therefore, a large value for PlannerDeltaT might cause collisions to be missed.

Make sure that PlannerDeltaT is large enough to allow the state to move from one cell to another without in a single step. For example, if the quantization leads to a grid boundary every 2.0 units, then PlannerDeltaT could be set to cause the state to change by 3.0 units.

GridDimensions sets the resolution of the grid and can be read from a file. For high-dimensional problems an error message may occur due to a grid that is too large. To enable larger grids, set the MaxSize to a desirable size in the MultiArray class (in marray.C).

---

Constructor & Destructor Documentation

FDP::FDP ( Problem * problem )

A constructor that initializes data members.

FDP::~FDP ( ) [inline]

Empty destructor.

---

Member Function Documentation

virtual MSLVector FDP::IndicesToState ( const vector< int > & indices ) [protected, virtual]

bool FDP::Plan ( ) [virtual]

Attempt to solve an Initial-Goal query by growing an FDP tree. Reimplemented from Planner. Reimplemented in FDPBi.

void FDP::Reset ( ) [virtual]

Reset the planner. Reimplemented from Planner. Reimplemented in FDPBi.

virtual double FDP::SearchCost ( double initcost, MSLNode *& n, MSLNode *& nn ) [protected, virtual]

Reimplemented in FDPStar, and FDPBestFirst.

virtual vector<int> FDP::StateToIndices ( const MSLVector & x ) [protected, virtual]

---

Member Data Documentation

MultiArray< int > * FDP::Grid [protected]

A quantized state space.

int FDP::GridDefaultResolution [protected]

Default size for each axis of the grid.

vector< int > FDP::GridDimensions [protected]

Dimensions for the grid.

priority_queue< MSLNode *,vector< MSLNode *>,MSLNodeGreater > FDP::Q [protected]

Priority queue of nodes.

MSLVector FDP::Quantization [protected]

The quantized step size for each axis (computed automatically).

int FDP::SatisfiedCount

Number of times the collision checker has been called.

---

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

• fdp.h

---

Web page maintained by Steve LaValle
Partial support provided by NSF CAREER Award IRI-970228 (LaValle), Honda Research.
Contributors: Anna Atramentov, Peng Cheng, James Kuffner, Steve LaValle, and Libo Yang.