Algoritmos de cinemática inversa

Las clases inverseKinematics y generalizedInverseKinematics le dan acceso a los algoritmos de cinemática inversa (IK). Puede utilizar estos algoritmos para generar una configuración de robot que logre los objetivos y las restricciones especificados para el robot. Esta configuración del robot es una lista de posiciones de articulación que se encuentran dentro de los límites de posición del modelo de robot y no infringen ninguna restricción que tenga el robot.

Elegir un algoritmo

MATLAB® admite tres algoritmos para conseguir una solución de IK: el algoritmo de proyección BFGS, el algoritmo de Levenberg-Marquardt y el algoritmo de programación cuadrática secuencial (SQP) fmincon. Los tres algoritmos son métodos de optimización iterativos, basados en gradientes, que parten de una estimación inicial sobre la solución y tratan de minimizar una función de coste específica. Si cualquiera de los dos algoritmos converge en una configuración en la que el coste es cercano a cero dentro de una tolerancia especificada, ha encontrado una solución al problema de cinemática inversa. Sin embargo, para algunas combinaciones de estimaciones iniciales y poses deseadas del efector final, el algoritmo puede salir sin encontrar una configuración ideal del robot. Para hacer frente a esto, el algoritmo utiliza un mecanismo de reinicio aleatorio. Si está activado, el mecanismo de reinicio aleatorio reinicia la búsqueda iterativa a partir de una configuración aleatoria del robot siempre que esa búsqueda no encuentre una configuración que logre la pose deseada del efector final. Estos reinicios aleatorios continúan hasta que se encuentre una solución de IK que cumpla los requisitos, hasta que haya transcurrido el tiempo máximo o hasta que se alcance el límite de iteración.

El algoritmo SQP fmincon es especialmente apto para gestionar restricciones en el problema de optimización, que lo convierte en una elección sólida para escenarios de IK complejos con múltiples restricciones.

Para establecer el algoritmo, especifique la propiedad SolverAlgorithm como "BFGSGradientProjection", "LevenbergMarquardt" o "fminconsqp".

Proyección de gradiente BFGS

El algoritmo de proyección de gradiente Broyden-Fletcher-Goldfarb-Shanno (BFGS) es un método cuasi-Newton que utiliza los gradientes de la función de coste de las iteraciones anteriores para generar información aproximada de segunda derivada. El algoritmo utiliza esta información de segunda derivada para determinar el paso que debe darse en la iteración actual. Se utiliza un método de proyección de gradiente para tratar los límites de la función de coste que crean los límites de articulación del modelo del robot. La dirección calculada se modifica para que la dirección de búsqueda sea siempre válida.

Este método es el algoritmo predeterminado y es más sólido a la hora de encontrar soluciones que el método de Levenberg-Marquardt. Es más eficaz para las configuraciones cercanas a los límites de articulación o cuando la estimación inicial no se acerca a la solución. Si la estimación inicial está cerca de la solución y se necesita una solución más rápida, considere los métodos SQP fmincon o Levenberg-Marquardt.

Levenberg-Marquardt

La variante del algoritmo de Levenberg-Marquardt (LM) que se utiliza en la clase InverseKinematics es un método de mínimos cuadrados con amortiguación de errores. El factor de amortiguación de errores ayuda a evitar que el algoritmo escape de un mínimo local. El algoritmo de LM está optimizado para converger mucho más rápido si la estimación inicial está cerca de la solución. Sin embargo, el algoritmo no gestiona bien las estimaciones iniciales arbitrarias. Considere el uso de este algoritmo para encontrar soluciones de IK para una serie de poses a lo largo de una trayectoria deseada del efector final. Una vez que se ha encontrado una configuración del robot para una pose, esa configuración suele ser una buena estimación inicial de una solución de IK para la siguiente pose en la trayectoria. En esta situación, los algoritmos de LM o SQP fmincon pueden generar resultados más rápidos. De lo contrario, utilice el Proyección de gradiente BFGS en su lugar.

SQP fmincon

La variante del algoritmo fmincon utilizada para solvers de cinemática inversa es el método de programación cuadrática secuencial (SQP), que destaca en la resolución de funciones objetivo no lineales. Este método requiere menos iteraciones para converger en una solución que la proyección BFGS o el algoritmo de Levenberg-Marquardt, sin necesidad de reinicios aleatorios. Para obtener más información sobre el solver SQP fmincon, consulte la función fmincon (Optimization Toolbox).

Este algoritmo requiere Optimization Toolbox™.

Parámetros del solver

Cada algoritmo tiene parámetros específicos que se pueden regular para mejorar las soluciones. Esos parámetros se especifican en la propiedad SolverParameters del objeto.

Proyección de gradiente BFGS

La estructura de parámetros del solver para el algoritmo BFGS tiene estos campos:

  • MaxIterations: número máximo de iteraciones permitidas. El valor predeterminado es 1500.

  • GradientTolerance: umbral del gradiente de la función de coste. El algoritmo se detiene si la magnitud del gradiente cae por debajo de ese umbral. Debe ser un escalar positivo.

  • SolutionTolerance: umbral de la magnitud del error entre la pose del efector final generada a partir de la solución y la pose deseada. En este cálculo se incluyen las ponderaciones especificadas para cada componente de la pose en el objeto. Debe ser un escalar positivo.

  • EnforceJointLimits: indicador de si se consideran los límites de articulación en el cálculo de la solución. JointLimits es una propiedad del modelo de robot en rigidBodyTree. De forma predeterminada, se aplican los límites de articulación.

  • AllowRandomRestart: indicador de si se permiten los reinicios aleatorios, especificado como 1 (true) o 0 (false) lógico. Los reinicios aleatorios se activan cuando el algoritmo se acerca a una solución que no cumple las tolerancias. El solver de IK genera una estimación inicial utilizando los campos RandomStream y Seed, a la vez que sigue satisfaciendo los campos MaxIteration y MaxTime. De forma predeterminada, los reinicios aleatorios están activados.

  • RandomRestartParameters: parámetros para el reinicio aleatorio, especificados como estructura que contiene estos campos.

    • RandomStream: secuencia de números aleatorios utilizada por el solver de IK para reinicios aleatorios. El valor predeterminado es 'Global stream', que utiliza la secuencia aleatoria global de MATLAB con la que se pueden obtener resultados no repetibles, a menos que se establezca la semilla externamente con la función rng. Para obtener resultados repetibles, establezca RandomStream en 'mt19937ar with seed' para especificar semillas mediante el campo Seed.

    • Seed: valor de la semilla de números aleatorios, que especifica el punto de inicio para que el algoritmo genere números aleatorios. El campo RandomStream debe establecerse en 'mt19937ar with seed' para que el solver utilice el valor del campo Seed.

    El solver de cinemática inversa solo utiliza el campo RandomRestartParameters cuando AllowRandomRestarts es "on" y la propiedad Solver es "BFGSGradientProjection" o "LevenbergMarquardt".

  • StepTolerance: tamaño de paso mínimo permitido por el solver. Los tamaños de paso más pequeños suelen significar que la solución está cerca de la convergencia. El valor predeterminado es 1e–14.

  • MaxTime: número máximo de segundos durante los cuales se ejecuta el algoritmo antes de que se agote el tiempo. El valor predeterminado es 10.

Levenberg-Marquardt

La estructura de los parámetros del solver para el algoritmo de LM tiene estos campos adicionales, además de los que requiere el método Proyección de gradiente BFGS:

  • ErrorChangeTolerance: umbral del cambio de error de pose del efector final entre iteraciones. El algoritmo devuelve si los cambios en todos los elementos del error de pose son menores que este umbral. Debe ser un escalar positivo.

  • DampingBias: término constante de amortiguación. El algoritmo de LM tiene una característica de amortiguación controlada por esta constante que opera con la función de coste para controlar la tasa de convergencia. Para desactivar la amortiguación, utilice el parámetro UseErrorDamping.

  • UseErrorDamping: 1 (valor predeterminado), indicador de si se utiliza la amortiguación. Establezca este parámetro en false para desactivar la amortiguación.

SQP fmincon

La estructura de parámetros del solver para el algoritmo fmincon SQP tiene estos campos:

  • MaxIterations: número máximo de iteraciones permitidas. El valor predeterminado es 1500. Corresponde a la opción MaxIterations de la función fmincon.

  • SolutionTolerance: umbral de la magnitud del error entre la pose del efector final generada a partir de la solución y la pose deseada. Este cálculo incluye las ponderaciones especificadas para cada componente de la pose en el objeto. Especifique este valor como un escalar positivo. Corresponde a la opción ObjectiveLimit de la función fmincon.

  • StepTolerance: tamaño de paso mínimo permitido por el solver. Con tamaños de paso más pequeños se suele obtener una solución más cerca de la convergencia. El valor predeterminado es 1e–6. Corresponde a la opción StepTolerance de la función fmincon.

  • GradientTolerance: umbral del gradiente de la función de coste. El algoritmo se detiene si la magnitud del gradiente cae por debajo de ese umbral. Especifique este valor como un escalar positivo. Corresponde a la opción OptimalityTolerance de la función fmincon.

  • EnforceJointLimits: indica si se deben considerar los límites de articulación al calcular la solución. JointLimits es una propiedad de los modelos de robot rigidBodyTree. De forma predeterminada, el algoritmo aplica los límites de articulación. Corresponde a los argumentos lb (Optimization Toolbox) y ub (Optimization Toolbox) de la función fmincon.

  • ConstraintTolerance: umbral de las infracciones de las restricciones. Esto indica las infracciones permitidas por el solver en los límites de la posición de las articulaciones. El valor predeterminado es 1e-6 y debe ser un escalar numérico no negativo. Corresponde a la opción ConstraintTolerance de la función fmincon.

Para obtener más información sobre las opciones de fmincon a las que se asignan estos parámetros, consulte el argumento options (Optimization Toolbox) de la función fmincon.

Información de la solución

Al utilizar los algoritmos de cinemática inversa, cada llamada al objeto devuelve información de la solución sobre el rendimiento del algoritmo. La información de la solución se proporciona como una estructura con los siguientes campos:

  • Iterations: el número de iteraciones ejecutadas por el algoritmo.

  • NumRandomRestarts: el número de reinicios aleatorios debidos a que el algoritmo se ha quedado atascado en un mínimo local.

  • PoseErrorNorm: la magnitud de error de la pose de la solución comparada con la pose del efector final deseada.

  • ExitFlag: el código que proporciona más detalles sobre la ejecución del algoritmo y la causa de que sea devuelta. Para ver los indicadores de salida de los diferentes tipos de algoritmo, consulte Indicadores de salida.

  • Status: el vector de caracteres que describe si la solución se encuentra dentro de la tolerancia ('success') o la mejor solución posible que ha encontrado el algoritmo ('best available').

Indicadores de salida

En la información de la solución, los indicadores de salida aportan más detalles sobre la ejecución del algoritmo específico. Observe la propiedad Status del objeto para saber si el algoritmo ha resultado satisfactorio. Cada código de indicador de salida tiene una descripción definida.

Indicadores de salida del algoritmo de "BFGSGradientProjection":

  • 1: se ha encontrado un mínimo local.

  • 2: número máximo de iteraciones alcanzadas.

  • 3: el algoritmo se ha agotado durante la operación.

  • 4: tamaño de paso mínimo. El tamaño del paso está por debajo del campo StepToleranceSize de la propiedad SolverParameters.

  • 5: no existe un indicador de salida. Solo es relevante para el algoritmo "LevenbergMarquardt".

  • 6: dirección de búsqueda no válida.

  • 7: la hessiana no es semidefinida positiva.

Indicadores de salida del algoritmo de "LevenbergMarquardt":

  • 1: se ha encontrado un mínimo local.

  • 2: número máximo de iteraciones alcanzadas.

  • 3: el algoritmo se ha agotado durante la operación.

  • 4: tamaño de paso mínimo. El tamaño del paso está por debajo del campo StepToleranceSize de la propiedad SolverParameters.

  • 5: el cambio de error de pose del efector final está por debajo del campo ErrorChangeTolerance de la propiedad SolverParameters.

Indicadores de salida del algoritmo de "fminconsqp":

  • 1: la medida de optimalidad de primer orden es menor que GradientTolerance y la infracción de restricción máxima es menor que ConstraintTolerance.

  • 0: el número de iteraciones ha superado MaxIterations o el número de evaluaciones de la función ha superado el valor predeterminado máximo para MaxFunctionEvaluations (Optimization Toolbox).

  • -1: se ha detenido mediante una función de salida o de gráfica.

  • -2: no se ha encontrado ninguna solución factible.

  • -3: la función objetivo en la iteración actual ha descendido por debajo de SolutionTolerance y la infracción de restricción máxima era menor que ConstraintTolerance.

Consulte el argumento exitflag (Optimization Toolbox) de la función fmincon para obtener más información.

Referencias

[1] Badreddine, Hassan, Stefan Vandewalle, and Johan Meyers. "Sequential Quadratic Programming (SQP) for Optimal Control in Direct Numerical Simulation of Turbulent Flow." Journal of Computational Physics. 256 (2014): 1–16. doi:10.1016/j.jcp.2013.08.044.

[2] Bertsekas, Dimitri P. Nonlinear Programming. Belmont, MA: Athena Scientific, 1999.

[3] Goldfarb, Donald. "Extension of Davidon’s Variable Metric Method to Maximization Under Linear Inequality and Equality Constraints." SIAM Journal on Applied Mathematics. Vol. 17, No. 4 (1969): 739–64. doi:10.1137/0117067.

[4] Nocedal, Jorge, and Stephen Wright. Numerical Optimization. New York, NY: Springer, 2006.

[5] Sugihara, Tomomichi. "Solvability-Unconcerned Inverse Kinematics by the Levenberg–Marquardt Method." IEEE Transactions on Robotics Vol. 27, No. 5 (2011): 984–91. doi:10.1109/tro.2011.2148230.

[6] Zhao, Jianmin, and Norman I. Badler. "Inverse Kinematics Positioning Using Nonlinear Programming for Highly Articulated Figures." ACM Transactions on Graphics Vol. 13, No. 4 (1994): 313–36. doi:10.1145/195826.195827.

Consulte también

| |

Temas