M.Sc Thesis

M.Sc StudentSidorov Ariel Eric
SubjectLyapunov Based Estimation of the Basin of Attraction of
Poincare Maps with Applications to Limit Cycle
DepartmentDepartment of Mechanical Engineering
Supervisor PROF. Miriam Zacksenhouse
Full Thesis textFull thesis text - English Version


Limit cycle Walking, a common paradigm in robotic dynamic locomotion, views walking gaits as stable limit cycles. Orbital stability of limit cycles is commonly studied by analyzing the stability of a discretization of the systems dynamics known as the Poincare map. Local stability can be assessed by examining the eigenvalues of the linearized Poincare map. However, when studying highly nonlinear systems, such as dynamic walkers, local stability might not be sufficient, since it may be valid only for very small perturbations. In order to study the robustness of the limit cycle to larger perturbations one might be interested in its Basin of Attraction (BA), the set of all initial conditions from which the system converge to the limit cycle.

The most direct and common method to estimate BAs is by exhaustive simulation methods such as cell mapping. However those methods are computationally intensive with complexity increasing exponentially with the dimension of the state-space. A different class of methods utilize Lyapunov's direct method to characterize invariant subsets of the BA by means of sub-level sets of a Lyapunov function.

In this Thesis, I used sub-level sets of a quadratic Lyapunov function to obtain ellipsoidal inner  estimates of BAs of fixed points of polynomial discrete time systems. We present an algorithm that finds the "best" Lyapunov function, in terms of the largest provable subset of the BA. The algorithm is based on a polynomial optimization technique known as Sums of Squares Programming.

The proposed method was demonstrated on a simple biped walking model under different modes of actuation. For each mode of actuation, a polynomial function was fitted to the Poincare map using a small number of simulations, and used to estimate the BA. Each estimated BA was contained in the corresponding BA computed using the computationally intensive cell-to cell mapping method, and captured well its shape,   while reducing the computation time from hours to minutes. Comparing the BAs achieved by the different modes of actuation we demonstrate that the BA of a passive biped model can be enlarged using minimalistic event-driven actuation, and that this relationship is also apparent from the estimated inner bounds of the Bas.