Collocation methods for the synthesis of graceful robot motions

Abstract

(English) Graceful motion can be loosely defined as the one we observe in natural movements executed by animals and humans, which are characterized by being agile, efficient, and fluid. The generation of graceful robot motions is typically sought through the minimization of cost functions involving not only path length, but also aspects related to smoothness, like the time derivative of acceleration, called jerk, or that of the controls. A widely used approach to compute optimal trajectories is through direct collocation, a technique that converts the continuous-time optimal control problem into a finite-dimensional NLP problem. Collocation proceeds by discretizing the trajectory using so-called collocation points, and imposing the dynamics constraints at such points. The formulation of most collocation methods, however, assumes that the system is governed by a first order ODE, whereas robotic systems are typically described by second or higher order ODEs. As a result, the usual practice is to initially convert those ODEs into first order form via introducing new variables, and adding new equations that link these variables with their integral counterparts. An often overlooked effect of this transformation is that it generates inconsistencies between the trajectory of each variable and that of its time derivative. This is so because a collocation method only imposes the differential relationships at the collocation points, but not in between such points. A closer examination of this effect reveals that the dynamic equations, which should be satisfied in the collocation points, are actually violated in them, despite apparently having been enforced. This thesis introduces new collocation methods designed to overcome these problems. Specifically, we develop improved versions of the most popular piecewise and pseudospectral collocation schemes, including the trapezoidal and Hermite-Simpson methods, as well as the LG, LGR, and LGL methods. The new algorithms are able to treat differential equations of arbitrary order M ≥ 1 without having to convert them into first order form. In all of them, the trajectory obtained for each variable coincides exactly with the time derivative of its corresponding integral variable, and the dynamic constraints are satisfied accurately at the collocation points. These properties allow a drastic reduction of the dynamics error of the obtained trajectories in many cases, meaning that the governing equations are better respected along the continuous time horizon of the problem. Our methods also provide trajectories that are smoother than those of conventional ones, and easily treat variables such as jerk or the time derivative of the controls in the cost function. An hp adaptive refinement algorithm is also proposed to combine the benefits of our piecewise and pseudospectral methods so as to speed up convergence to the solutions.

(Català) Un moviment gràcil es pot definir informalment com el que observem en els moviments naturals executats per animals i humans, que es caracteritzen per ser àgils, eficients i fluids. La generació de moviments robòtics gràcils s’acostuma a realitzar mitjançant la minimització de funcions de cost que impliquen no només la longitud de la trajectòria, sinó també aspectes relacionats amb la suavitat, com ara la derivada temporal de l'acceleració, anomenada sobreacceleració (jerk en anglès), o la dels controls. Un enfocament molt utilitzat per calcular trajectòries òptimes és la col·locació directa, una tècnica que converteix el problema de control òptim en temps continu en un de programació no lineal de dimensió finita. La tècnica de col·locació consisteix a discretitzar la trajectòria utilitzant els anomenats punts de col·locació i imposant les restriccions de la dinàmica en aquests punts. No obstant això, la formulació de la majoria dels mètodes de col·locació assumeixen que el sistema es regeix per una EDO de primer ordre, mentre que els sistemes robòtics solen descriure's mitjançant EDOs de segon ordre o superior. En conseqüència, la pràctica habitual consisteix a convertir inicialment aquestes EDOs a la forma de primer ordre mitjançant la introducció de noves variables i l'addició de noves equacions que vinculen aquestes variables amb les seves homòlogues integrals. Un efecte d'aquesta transformació que sovint passa desapercebut és que genera inconsistències entre la trajectòria de cada variable i la de la seva derivada temporal. Això és així perquè un mètode de col·locació només imposa les relacions diferencials als punts de col·locació, però no entremig d’aquests punts. Una anàlisi més detallada d'aquest efecte revela que les equacions de la dinàmica, que s'haurien de satisfer en els punts de col·locació, en realitat s'hi incompleixen, tot i que aparentment s’hi hagin imposat. Aquesta tesi introdueix nous mètodes de col·locació directa dissenyats per resoldre aquests problemes. Específicament, desenvolupem versions millorades dels esquemes de col·locació per trams i pseudoespectrals més populars, incloent-hi els mètodes trapezoïdal i Hermite-Simpson, així com els mètodes LG, LGR i LGL. Els nous algorismes són capaços de tractar equacions diferencials d’ordre M ≥ 1 arbitrari sense necessitat de convertir-les a la forma de primer ordre. En tots ells, la trajectòria obtinguda per a cada variable coincideix exactament amb la derivada temporal de la corresponent variable integral, i les restriccions de la dinàmica se satisfan amb precisió als punts de col·locació. En molts casos, aquestes propietats permeten reduir dràsticament l'error dinàmic de les trajectòries obtingudes aconseguint, d’aquesta manera, que les equacions diferencials del sistema es respectin més acuradament al llarg de l'horitzó temporal del problema. Els nostres mètodes també proporcionen trajectòries més suaus que les dels mètodes convencionals, i permeten tractar fàcilment variables com la sobreacceleració o la derivada temporal dels controls a la funció de cost. La tesi també proposa un algorisme hp de refinament adaptatiu que combina els avantatges dels nous mètodes de col·locació per trams i pseudoespectrals, per tal d’accelerar la convergència cap a les solucions.

(Español) Un movimiento grácil puede definirse informalmente como el que observamos en los movimientos naturales ejecutados por animales y humanos, que se caracterizan por ser ágiles, eficientes y fluidos. La generación de movimientos robóticos gráciles suele acometerse mediante la minimización de funciones de coste que implican no sólo la longitud de la trayectoria, sino también aspectos relacionados con la suavidad, como la derivada temporal de la aceleración, denominada sobreaceleración (jerk en inglés), o la de los controles. Un enfoque muy utilizado para calcular trayectorias óptimas es la colocación directa, una técnica que convierte el problema de control óptimo en tiempo continuo en un problema de programación no lineal de dimensión finita. La técnica de colocación consiste en discretizar la trayectoria utilizando los denominados puntos de colocación e imponiendo las restricciones de la dinámica en dichos puntos. Sin embargo, la formulación de la mayoría de los métodos de colocación asumen que el sistema se rige por una EDO de primer orden, mientras que los sistemas robóticos suelen describirse mediante EDOs de segundo orden o superior. En consecuencia, la práctica habitual consiste en convertir inicialmente esas EDOs a la forma de primer orden mediante la introducción de nuevas variables y la adición de nuevas ecuaciones que vinculan esas variables con sus homólogas integrales. Un efecto de esta transformación que a menudo se pasa por alto es que genera incoherencias entre la trayectoria de cada variable y la de su derivada temporal. Esto es así porque un método de colocación sólo impone las relaciones diferenciales en los puntos de colocación, pero no entre dichos puntos. Un examen más detallado de este efecto revela que las ecuaciones de la dinámica, que deberían satisfacerse en los puntos de colocación, en realidad se incumplen en ellos, a pesar de que aparentemente hayan sido impuestas. Esta tesis introduce nuevos métodos de colocación diseñados para superar estos problemas. Específicamente, desarrollamos versiones mejoradas de los esquemas de colocación por tramos y pseudoespectrales más populares, incluyendo los métodos trapezoidal y Hermite-Simpson, así como los métodos LG, LGR y LGL. Los nuevos algoritmos son capaces de tratar ecuaciones diferenciales de orden M ≥ 1 arbitrario sin necesidad de convertirlas a la forma de primer orden. En todos ellos, la trayectoria obtenida para cada variable coincide exactamente con la derivada temporal de su correspondiente variable integral, y las restricciones de la dinámica se satisfacen con precisión en los puntos de colocación. En muchos casos, estas propiedades permiten reducir drásticamente el error dinámico de las trayectorias obtenidas lo que significa que las ecuaciones que gobiernan el sistema se respetan mejor a lo largo de todo el horizonte temporal del problema. Nuestros métodos también proporcionan trayectorias más suaves que las de los métodos convencionales, y permiten tratar fácilmente variables como la sobreaceleración o la derivada temporal de los controles en la función de coste. También se propone un algoritmo hp de refinamiento adaptativo para combinar las ventajas de nuestros métodos por tramos y pseudoespectrales con el fin de acelerar la convergencia hacia las soluciones.