Determining the basis of a Lie algebra may be a long and tedious process. The combinations of Lie brackets in Example 15.17 were given; however, it is not known in advance which ones will produce independent vector fields. Numerous Lie brackets may be needed, including some that are nested, such as . The maximum depth of nested Lie bracket operations is not known a priori. Therefore, a systematic search must be performed (this can in fact be modeled as a discrete planning problem) by starting with , , and iteratively generating new, independent vector fields using Lie brackets.
One popular approach is to generate the Philip Hall basis (or P. Hall basis) of the Lie algebra . The construction of the basis essentially follows breadth-first search, in which the search depth is defined to be the number of nested levels of bracket operations. The order (or depth) of a Lie product is defined recursively as follows. For the base case, let for any of the system vector fields. For any Lie product , let
In addition to standard breadth-first search, pruning should be automatically performed to ensure that the skew symmetry and Jacobi identities are always utilized to eliminate redundancy. A P. Hall basis is a sequence, , , , of Lie products for which:
When does the sequence terminate? Recall that can be no greater than , because . In other words, at every state , the number of possible independent velocity vectors is no more than the dimension of the tangent space at . Therefore, can be terminated once independent vector fields are obtained because there is no possibility of finding more. For some systems, there may be a depth after which all Lie brackets are zero. Such systems are called nilpotent of order . This occurs, for example, if all components of all vector fields are polynomials. If the system is not nilpotent, then achieving termination may be difficult. It may be the case that is strictly less than , but this is usually not known in advance. It is difficult to determine whether more Lie brackets are needed to increase the dimension or the limit has already been reached.
Steven M LaValle 2012-04-20