rsLQR
0.1
|
Data Structures | |
struct | UnitRange |
Represents a range of consecutive integers. More... | |
struct | BinaryNode_s |
struct | OrderedBinaryTree |
The binary tree for the rsLQR solver. More... | |
struct | NdLqrCholeskyFactors |
Stores a list of CholeskyInfo structs for the rsLQR solver. More... | |
struct | NdFactor |
A chunk of memory for a single time step. More... | |
struct | NdData |
Core storage container for the rsLQR solver. More... | |
struct | NdLqrProfile |
A struct describing how long each part of the solve took, in milliseconds. More... | |
struct | NdLqrSolver |
Main solver for rsLQR. More... | |
Typedefs | |
typedef struct BinaryNode_s | BinaryNode |
One of the nodes in the binary tree for the rsLQR solver. More... | |
Functions | |
OrderedBinaryTree | ndlqr_BuildTree (int N) |
Construct a new binary tree for a horizon of length N . More... | |
int | ndlqr_FreeTree (OrderedBinaryTree *tree) |
Frees the data in tree . More... | |
int | ndlqr_GetIndexFromLeaf (const OrderedBinaryTree *tree, int leaf, int level) |
Get the knot point index given the leaf index at a given level. More... | |
int | ndlqr_GetIndexLevel (const OrderedBinaryTree *tree, int index) |
Get the level for a given knot point index. More... | |
int | ndlqr_GetIndexAtLevel (const OrderedBinaryTree *tree, int index, int level) |
Get the index in level that corresponds to index . More... | |
NdLqrCholeskyFactors * | ndlqr_NewCholeskyFactors (int depth, int nhorizon) |
Initialize a new NdLqrCholeskyFactors object. More... | |
int | ndlqr_FreeCholeskyFactors (NdLqrCholeskyFactors *cholfacts) |
Free the memory of a CholeskyFactors object. More... | |
int | ndlqr_GetQFactorizon (NdLqrCholeskyFactors *cholfacts, int index, CholeskyInfo **cholfact) |
Get the CholeskyInfo for the matrix Q at index index . More... | |
int | ndlqr_GetRFactorizon (NdLqrCholeskyFactors *cholfacts, int index, CholeskyInfo **cholfact) |
Get the CholeskyInfo for the matrix R at index index . More... | |
int | ndlqr_GetSFactorization (NdLqrCholeskyFactors *cholfacts, int leaf, int level, CholeskyInfo **cholfact) |
Get the CholeskyInfo for the output of ndlqr_SolveCholeskyFactor(). More... | |
Matrix | ndlqr_GetLambdaFactor (NdFactor *factor) |
Matrix | ndlqr_GetStateFactor (NdFactor *factor) |
Matrix | ndlqr_GetInputFactor (NdFactor *factor) |
NdData * | ndlqr_NewNdData (int nstates, int ninputs, int nhorizon, int width) |
Initialize the NdData structure. More... | |
int | ndlqr_FreeNdData (NdData *nddata) |
Frees the memory allocated in an NdData structure. More... | |
int | ndlqr_GetNdFactor (NdData *nddata, int index, int level, NdFactor **factor) |
Retrieve an individual NdFactor out of the NdData. More... | |
void | ndlqr_ResetNdData (NdData *nddata) |
Resets all of the memory for an NdData to zero. More... | |
int | ndlqr_SolveLeaf (NdLqrSolver *solver, int index) |
Solve all the equations for the lowest-level diagonal blocks, by timestep. More... | |
int | ndlqr_SolveLeaves (NdLqrSolver *solver) |
int | ndlqr_FactorInnerProduct (NdData *data, NdData *fact, int index, int data_level, int fact_level) |
Calculates one of the inner products needed at level data_level . More... | |
int | ndlqr_SolveCholeskyFactor (NdData *fact, CholeskyInfo *cholinfo, int index, int level, int upper_level) |
Use the precomputed Cholesky factorization to solve for y at each parent level. More... | |
bool | ndlqr_ShouldCalcLambda (OrderedBinaryTree *tree, int index, int i) |
Determines if the \( \Lambda \) should be updated during ndlqr_UpdateSchurFactor() More... | |
int | ndlqr_UpdateShurFactor (NdData *fact, NdData *soln, int index, int i, int level, int upper_level, bool calc_lambda) |
Calculates \( x \) and \( z \) to complete the factorization at the current level. More... | |
int | ndlqr_ComputeShurCompliment (NdLqrSolver *solver, int index, int level, int upper_level) |
int | ndlqr_Solve (NdLqrSolver *solver) |
Solve an LQR problem using rsLQR. More... | |
Matrix | ndlqr_GetSolution (NdLqrSolver *solver) |
Return the solution vector. More... | |
int | ndlqr_CopySolution (NdLqrSolver *solver, double *soln) |
Copies the solution vector to a user-supplied array. More... | |
NdLqrProfile | ndlqr_NewNdLqrProfile () |
Create a profile initialized with zeros. | |
void | ndlqr_ResetProfile (NdLqrProfile *prof) |
Reset the profile to its initialized state. More... | |
void | ndlqr_CopyProfile (NdLqrProfile *dest, NdLqrProfile *src) |
Copy the profile information to a new profile. More... | |
void | ndlqr_PrintProfile (NdLqrProfile *profile) |
Print a summary fo the profile. More... | |
void | ndlqr_CompareProfile (NdLqrProfile *base, NdLqrProfile *prof) |
Compare two profiles, printing the comparison to stdout. More... | |
NdLqrSolver * | ndlqr_NewNdLqrSolver (int nstates, int ninputs, int nhorizon) |
Create a new solver, allocating all the required memory. More... | |
int | ndlqr_FreeNdLqrSolver (NdLqrSolver *solver) |
Deallocates the memory for the solver. More... | |
int | ndlqr_InitializeWithLQRProblem (const LQRProblem *lqrprob, NdLqrSolver *solver) |
Initialize the solver with data from an LQR Problem. More... | |
void | ndlqr_ResetSolver (NdLqrSolver *solver) |
Resets the rsLQR solver. More... | |
void | ndlqr_PrintSolveSummary (NdLqrSolver *solver) |
Prints a summary of the solve. More... | |
int | ndlqr_GetNumVars (NdLqrSolver *solver) |
Gets the total number of decision variables for the problem. More... | |
int | ndlqr_SetNumThreads (NdLqrSolver *solver, int num_threads) |
Set the number of threads to be used during the solve. More... | |
int | ndlqr_GetNumThreads (NdLqrSolver *solver) |
Get the number of threads used during the rsLQR solve. More... | |
int | ndlqr_PrintSolveProfile (NdLqrSolver *solver) |
Prints a summary of how long individual components took. More... | |
NdLqrProfile | ndlqr_GetProfile (NdLqrSolver *solver) |
Ge the internal profile data from a solve. More... | |
typedef struct BinaryNode_s BinaryNode |
One of the nodes in the binary tree for the rsLQR solver.
OrderedBinaryTree ndlqr_BuildTree | ( | int | N | ) |
Construct a new binary tree for a horizon of length N
.
Must be paired with a corresponding call to ndlqr_FreeTree().
N | horizon length. Must be a power of 2. |
void ndlqr_CompareProfile | ( | NdLqrProfile * | base, |
NdLqrProfile * | prof | ||
) |
Compare two profiles, printing the comparison to stdout.
base | The baseline profile |
prof | The "new" profile |
void ndlqr_CopyProfile | ( | NdLqrProfile * | dest, |
NdLqrProfile * | src | ||
) |
Copy the profile information to a new profile.
dest | New location for data. Existing data will be overwritten. |
src | Data to be copied. |
int ndlqr_CopySolution | ( | NdLqrSolver * | solver, |
double * | soln | ||
) |
Copies the solution vector to a user-supplied array.
See ndlqr_GetSolution() for variable order.
solver | The solver with the solution. |
soln | Output location for the solution vector. Should have length at least equal to the output of ndlqr_GetNumVars(). |
int ndlqr_FactorInnerProduct | ( | NdData * | data, |
NdData * | fact, | ||
int | index, | ||
int | data_level, | ||
int | fact_level | ||
) |
Calculates one of the inner products needed at level data_level
.
Calculates the following:
\[ \bar{\Lambda_{k+1}^{(p)}} = \bar{\Lambda_k^{(p)}}S + \langle X_k^{(j)}, \bar{X}_k^{(p)} \rangle + \langle U_k^{(j)}, \bar{U}_k^{(p)} \rangle + \langle X_{k+1}^{(j)}, \bar{X}_{k+1}^{(p)} \rangle + \langle U_{k+1}^{(j)}, \bar{U}_{k+1}^{(p)} \rangle \]
where \( j \) is data_level
, \( p \) is fact_level
, and \( k \) is index
.
data | The data for the original KKT matrix |
fact | The current data for the factorization |
index | Knot point index |
data_level | Level index for the original data, or equivalently the current level being processed by the outer solve |
fact_level | Level index for the factorization data, or equivalently the parent or upper level. fact_level >= data_level . |
int ndlqr_FreeCholeskyFactors | ( | NdLqrCholeskyFactors * | cholfacts | ) |
Free the memory of a CholeskyFactors object.
cholfacts | An initialized NdLqrCholeskyFactors object |
int ndlqr_FreeNdData | ( | NdData * | nddata | ) |
int ndlqr_FreeNdLqrSolver | ( | NdLqrSolver * | solver | ) |
Deallocates the memory for the solver.
solver | An initialized solver. |
int ndlqr_FreeTree | ( | OrderedBinaryTree * | tree | ) |
Frees the data in tree
.
tree | An initialized binary tree |
int ndlqr_GetIndexAtLevel | ( | const OrderedBinaryTree * | tree, |
int | index, | ||
int | level | ||
) |
Get the index in level
that corresponds to index
.
If the level is higher than the level of the given index, it's simply the parent at that level. If it's lower, then it's the index that's closest to the given one, with ties broken by choosing the left (or smaller) of the two.
tree | Precomputed binary tree |
index | Start index of the search. The result will be the index closest to this index. |
level | The level in which the returned index should belong to. |
int ndlqr_GetIndexFromLeaf | ( | const OrderedBinaryTree * | tree, |
int | leaf, | ||
int | level | ||
) |
Get the knot point index given the leaf index at a given level.
tree | An initialized binary tree for the problem horizon |
leaf | Leaf index |
level | Level of tree from which to get the index |
int ndlqr_GetIndexLevel | ( | const OrderedBinaryTree * | tree, |
int | index | ||
) |
Get the level for a given knot point index.
tree | An initialized binary tree for the problem horizon |
index | Knot point index |
Retrieve an individual NdFactor out of the NdData.
Retrieves a block of memory out of NdData, stored as an NdFactor. Typical usage will look like:
nddata | Storage location for the desired block of memory |
index | Time step of the factor to extract |
level | Level (or column in the NdData) of the desired factor |
factor | Storage location for the factor. |
int ndlqr_GetNumThreads | ( | NdLqrSolver * | solver | ) |
Get the number of threads used during the rsLQR solve.
solver | A solver which has already been initialized and solved |
int ndlqr_GetNumVars | ( | NdLqrSolver * | solver | ) |
Gets the total number of decision variables for the problem.
solver |
NdLqrProfile ndlqr_GetProfile | ( | NdLqrSolver * | solver | ) |
Ge the internal profile data from a solve.
solver | A solver which has already been initialized and solved |
int ndlqr_GetQFactorizon | ( | NdLqrCholeskyFactors * | cholfacts, |
int | index, | ||
CholeskyInfo ** | cholfact | ||
) |
Get the CholeskyInfo for the matrix Q at index index
.
[in] | cholfacts | All the stored info for the Cholesky solves |
[in] | index | Knot point index |
[out] | cholfact | Location for the retrieved CholeskyInfo |
int ndlqr_GetRFactorizon | ( | NdLqrCholeskyFactors * | cholfacts, |
int | index, | ||
CholeskyInfo ** | cholfact | ||
) |
Get the CholeskyInfo for the matrix R at index index
.
[in] | cholfacts | All the stored info for the Cholesky solves |
[in] | index | Knot point index |
[out] | cholfact | Location for the retrieved CholeskyInfo |
int ndlqr_GetSFactorization | ( | NdLqrCholeskyFactors * | cholfacts, |
int | leaf, | ||
int | level, | ||
CholeskyInfo ** | cholfact | ||
) |
Get the CholeskyInfo for the output of ndlqr_SolveCholeskyFactor().
Gets the CholeskyInfo for \( \bar{B}_i^{(j)} \).
[in] | cholfacts | All the stored info for the Cholesky solves |
[in] | leaf | The leaf index for the desired factor |
[in] | level | The level of the binary tree for the factor |
[out] | cholfact | Location for the retrieved CholeskyInfo |
Matrix ndlqr_GetSolution | ( | NdLqrSolver * | solver | ) |
Return the solution vector.
Returns the solution vector as a Matrix object, which is a simple wrapper around a raw pointer which points to the data actually stored by the solver. The user must not free the data, as it is owned by the solver. To get a solution vector owned by the caller, use ndlqr_CopySolution() instead.
The variables are ordered in the solution vector as follows:
\[ \begin{bmatrix} \lambda_1^T & x_1^T & u_1^T & \lambda_2^T & \dots & x_{N-1}^T & u_{N-1}^T & \lambda_N^T & x_N^T \end{bmatrix}^T \]
solver |
int ndlqr_InitializeWithLQRProblem | ( | const LQRProblem * | lqrprob, |
NdLqrSolver * | solver | ||
) |
Initialize the solver with data from an LQR Problem.
lqrprob | An initialized LQR problem with the data to be be solved. |
solver | An initialized solver. |
NdLqrCholeskyFactors* ndlqr_NewCholeskyFactors | ( | int | depth, |
int | nhorizon | ||
) |
Initialize a new NdLqrCholeskyFactors object.
Must be paired with a call to ndlqr_FreeCholeskyFactors().
depth | Depth of the binary tree |
nhorizon | Length of the time horizon. log2 (@depth) = nhorizon . |
NdData* ndlqr_NewNdData | ( | int | nstates, |
int | ninputs, | ||
int | nhorizon, | ||
int | width | ||
) |
Initialize the NdData structure.
Note this allocates a large block of memory. This should be followed by a single call to ndlqr_FreeNdData().
nstates | Number of variables in the state vector |
ninputs | Number of control inputs |
nhorizon | Length of the time horizon |
width | With of each factor. Should be nstates for KKT matrix data, or 1 for the right-hand side vector. |
NdLqrSolver* ndlqr_NewNdLqrSolver | ( | int | nstates, |
int | ninputs, | ||
int | nhorizon | ||
) |
Create a new solver, allocating all the required memory.
Must be followed by a later call to ndlqr_FreeNdLqrSolver().
nstates | Number of elements in the state vector |
ninputs | Number of control inputs |
nhorizon | Length of the time horizon. Must be a power of 2. |
void ndlqr_PrintProfile | ( | NdLqrProfile * | profile | ) |
Print a summary fo the profile.
profile |
int ndlqr_PrintSolveProfile | ( | NdLqrSolver * | solver | ) |
Prints a summary of how long individual components took.
solver | A solver which has already been initialized and solved |
void ndlqr_PrintSolveSummary | ( | NdLqrSolver * | solver | ) |
Prints a summary of the solve.
Prints solve time, the residual norm, and the number of theads.
solver |
void ndlqr_ResetNdData | ( | NdData * | nddata | ) |
void ndlqr_ResetProfile | ( | NdLqrProfile * | prof | ) |
Reset the profile to its initialized state.
prof | A profile |
void ndlqr_ResetSolver | ( | NdLqrSolver * | solver | ) |
Resets the rsLQR solver.
Resets all of the data in the solver to how it was when it was first initialized.
solver |
int ndlqr_SetNumThreads | ( | NdLqrSolver * | solver, |
int | num_threads | ||
) |
Set the number of threads to be used during the solve.
Does not guarantee that the specified number of threads will be used. To query the actual number of threads used during the solve, use the ndlqr_GetNumThreads() function after the solve.
solver | rsLQR solver |
num_threads | requested number of threads |
bool ndlqr_ShouldCalcLambda | ( | OrderedBinaryTree * | tree, |
int | index, | ||
int | i | ||
) |
Determines if the \( \Lambda \) should be updated during ndlqr_UpdateSchurFactor()
Basically checks to see if the \( \Lambda \) for the given index is a $B_i^{(p)}$ for any level greater than or equal to the current level.
tree | Binary tree with cached information about the structure of the problem |
index | Knot point index calculated using ndlqr_GetIndexAtLevel() |
i | Knot point index being processed |
int ndlqr_Solve | ( | NdLqrSolver * | solver | ) |
Solve an LQR problem using rsLQR.
This is the main method of the package. Using the data already allocated in the solver, this first calculates the factorization of the matrix data and then solves for solution vector. Note that calling this method twice will not result in the same data since it replaces the original right-hand-side data with the solution vector.
The solution can be retrieved after the solve by calling either ndlqr_GetSolution() or ndlqr_CopySolution().
If you want to call this method multiple times on the same data (e.g. when benchmarking solve times), use ndlqr_ResetNdData() between solves to reset the factorization data. Then re-initialize the solver with the problem data via ndlqr_InitializeWithLQRProblem().
solver | An nsLQR solver that has been initialized with the desired problem data. |
int ndlqr_SolveCholeskyFactor | ( | NdData * | fact, |
CholeskyInfo * | cholinfo, | ||
int | index, | ||
int | level, | ||
int | upper_level | ||
) |
Use the precomputed Cholesky factorization to solve for y at each parent level.
Solve the following linear system of equations, overwriting the right-hand-side.
\[ \bar{\Lambda}_{k+1}^{(j)} y = \bar{\Lambda}_{k+1}^{(p)} \]
where \( j \) is level
, \( p \) is upper_level
, and \( k \) is index
.
This is the same as solving
\[ -\bar{B}_i^{(j)} y_i^{(j,p)} = \bar{b}_i^{(j,p)} \]
using the notation from the paper.
fact | Data for the factorization |
cholinfo | Cached Cholesky factorization for \( \bar{\Lambda}_{k+1}^{(j)} \). |
index | Knot point index. Should be calculated using ndlqr_GetIndexFromLeaf(). |
level | Level index for the level currently being processed by the upper-level solve. |
upper_level | Level index for the right-hand-side. upper_level > level . |
int ndlqr_SolveLeaf | ( | NdLqrSolver * | solver, |
int | index | ||
) |
Solve all the equations for the lowest-level diagonal blocks, by timestep.
Called at the beginning of the solve, this method calculates the initial pieces of the factorization needed to start the recursion up through the rest of the levels. For and LQR problem, it calculates
\[ Q_k^{-1} A_k^T Q_k^{-1} q_k R_k^{-1} B_k^T R_k^{-1} r_k \]
for each index \( k \), with special-casing applied to the first and last indices.
solver | An initialized rsLQR solver |
index | Knotpoint index |
int ndlqr_UpdateShurFactor | ( | NdData * | fact, |
NdData * | soln, | ||
int | index, | ||
int | i, | ||
int | level, | ||
int | upper_level, | ||
bool | calc_lambda | ||
) |
Calculates \( x \) and \( z \) to complete the factorization at the current level.
Calculates the following
\[ \bar{\Lambda}_k^{(p)} = \bar{\Lambda}_k^{(p)} - \bar{\Lambda}_k^{(j)} \bar{\Lambda}_{k_\text{sep}}^{(p)} \bar{X}_k^{(p)} = \bar{X}_k^{(p)} - \bar{X}_k^{(j)} \bar{\Lambda}_{k_\text{sep}}^{(p)} \bar{U}_k^{(p)} = \bar{U}_k^{(p)} - \bar{U}_k^{(j)} \bar{\Lambda}_{k_\text{sep}}^{(p)} \]
where \( \bar{\Lambda}_{k_\text{sep}}^{(p)} \) is equivalent to $y_i^{(j,p)}$ from the paper and is the result of the ndlqr_SolveCholeskyFactor() for index
, level
, and upper_level
.
fact | NdData for the factorization data |
soln | NdData for the factorization data or solution vector |
index | Knot point index of the "separator" at level level . Should be calculated using ndlqr_GetIndexAtlevel(). |
i | Knot point index to be processed |
level | Level index for the level currently being processed |
upper_level | Level index of the upper level. upper_level > level |
calc_lambda | Whether the \( \Lambda \) factor should be updated. This should be calculated using ndlqr_ShouldCalcLambda(). |