Sparse Hierarchical Non-Linear Programming for Inverse Kinematic Planning and Control with Autonomous Goal Selection

Kai Pfeiffer · 2024

Read Sparse Hierarchical Non-Linear Programming for Inverse Kinematic Planning and Control with Autonomous Goal Selection by Kai Pfeiffer (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01324.txt.

Introduction

Pfeiffer and colleagues present in twenty twenty-four a solver that fuses robot motion planning with the discrete choices planning usually handles apart. A robot arm may need to pick which handhold or target to use while shaping its whole-body motion, and mixing both in one nonlinear problem is heavy. Older routes split the choice from the motion maths or used blunt approximations.

Their sparse hierarchical solver exploits the problem's layered structure and a strict count of active joints, a tool rarely used in robotics. It handles cases like planning a reach while picking the best end point from many candidates, or choosing two-handed grasps on a turned box, in one pass. The authors claim speed, range, and accuracy gains over mixed-integer and split approaches.

Catalog record

CREATORKai Pfeiffer
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-01324

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sparse Hierarchical Non-Linear Programming for Inverse Kinematic Planning and Control with Autonomous Goal Selection Kai Pfeiffer Abstract Sparse programming is an important tool in robotics, for example in real-time sparse inverse kinematic control with a minimum number of active joints, or autonomous Cartesian goal selection. However, current approaches are limited to real-time control without consideration of the underlying non-linear problem. This prevents the application to non-linear problems like inverse kinematic planning while the robot simultaneously and autonomously chooses from a set of potential end-effector goal positions. Instead, kinematic reachability approximations are used while the robot’s whole body motion is considered separately. This can lead to infeasible goals. Furthermore, the sparse constraints are not prioritized for intuitive problem formulation. Lastly, the computational effort of standard sparse solvers is cubically dependent on the number of constraints which prevents real-time control in the presence of a large number of possible goals. In this work, we develop a non-linear solver for sparse hierarchical non-linear programming. Sparse non-linear constraints for autonomous goal selection can be formulated on any priority level, which enables hierarchical decision making capabilities. The solver scales linearly in the number of constraints. This facilitates efficient robot sparse hierarchical inverse kinematic planning and real-time control with simultaneous and autonomous goal selection from a high number of possible goal positions without any reachability approximations. I Introduction Sparse programming is an important tool in robotics due to the inherent redundancy both in the robot’s kinematics and motion planning. Robots typically possess more degrees of freedom than are necessary to fulfill a given kinematic task. Using sparsity enhancing solution methods in robot control leads to economic [ 1 ] and human looking motions [ 2 ] . At the same time, motion planning can involve several possible scenarios, for example if different sequences of Cartesian end-effector positions lead to the same desired goal configuration. Here, sparse methods enable selection and decision making capabilities [ 3 ] . In this work, we develop a non-linear solver for sparse hierarchical non-linear programming (SH-NLP) with sparse non-linear constraints on any priority level. This enables the application to robot sparse hierarchical inverse kinematic (SHIK) • planning (SHIK-P: directly solve non-linear SHIK) • control (SHIK-C: solve SHIK instantaneously) with simultaneous and autonomous Cartesian goal selection (AGS). This is in contrast to other approaches for example in footstep planning [ 4 ] where kinematic reachability approximations are used while the robot’s whole-body motion is considered separately. This comes with the inherent risk that the resulting goal is not actually feasible / reachable if the approximation is not chosen conservative enough. While we consider the full inverse kinematics, the solver is very efficient as its computations scale linearly (and not cubically as in [ 3 , 5 ] ) in the number of sparse constraints. This enables real-time SHIK-C of humanoid robots in the presence of a large number of possible goals. We evaluate our methods on hierarchies of test functions and robot SHIK-P and SHIK-C with AGS. The use of sparse programming finds its origin in statistical analysis like compressed sensing [ 6 ] or decision making like portfolio optimization [ 7 ] . Here, an unconstrained regression problem is solved to fit model parameters to measured data. By introducing sparsity enhancing regularization factors, the choice of parameters is biased towards a minimal set which is sufficient to explain the data. Sparsity refers to the minimum \ell_{0} -norm. The \ell_{0} -norm counts non-zero entries of a vector x and is a pseudo-norm, as for example the homogeneity condition \|\alpha x\|_{\ell_{0}}=|\alpha|\|x\|_{\ell_{0}} for \alpha\neq 0 is not fulfilled. Minimization in the \ell_{0} -norm requires a combinatorial search which is intractable for large problems. However, a suitable approximation effectively recasts \ell_{0} -norm into weighted \ell_{1} -norm minimization problems [ 6 ] which can be solved efficiently, for example by the interior-point method [ 8 ] . Here, we aim to exploit sparse programming for inverse kinematic planning and control with simultaneous and autonomous Cartesian goal selection. Robot planning and control typically involve non-linear constraints ensuring robot safety or physical stability. However, current approaches in sparse programming concern either linear optimization problems or unconstrained ones with a sparse regularization term. Constrained sparse programming has been addressed in [ 1 ] where the sparsity enhancing properties of the simplex method is leveraged to achieve sparse robot control via \ell_{1} -norm programming. This selects a minimal set of robot joints of the redundant robot to fulfill a given task. The approaches in [ 3 ] and [ 5 ] use mixed-integer linear programming for the sparse selection of contact forces and the sparse control regularization on the last level of a control hierarchy for SHIK-C, respectively. In all approaches, the sparsity enhancing term is only included on a single layer either as a linear cost or constraint of the optimization problem. However, robots are non-linear systems both in their kinematics and dynamics. The above approaches [ 1 , 3 , 5 ] are based on sequential programming where in each iteration a linearized sparse problem at the current working point is solved. However, non-linear solver elements like filters [ 9 ] are not implemented which prevents their application to non-linear SHIK-P or optimal control. Optimal costs with smooth approximations of \ell_{1} -norm regularization terms of the variable vector for sparse control has been addressed by differential dynamic programming [ 10 ] . However, the non-linear costs itself can not be sparse. The approach in [ 11 ] provides an optimization based point of view of non-linear constrained sparse programming. Non-linear but non-sparse constraints are restricted to equality constraints, while the sparse (linear) constraints are limited to the variable vector. In this work, we address some of the shortcomings of the above methods. We propose an efficient sequential sparse hierarchical quadratic programming solver (S-SHQP) for SH-NLP with the following attributes, which hold for all priority levels: • Hierarchical optimization with sparse non-linear equality and inequality constraints without feasiblity requirements. • Computations scale linearly in the number of sparse constraints. To the best of our knowledge, the first point is currently not addressed in the robotics or optimization literature and S-SHQP is the first to be able to solve such hierarchical decision making problems. This solver is an extension to the non-linear hierarchical least-squares programming (NL-HLSP, \ell_{2} instead of \ell_{0} programming) solver presented in previous works [ 12 , 13 ] . Hierarchical optimization enables an intuitive problem formulation without the need for weighting objectives and constraints. Such non-linear hierarchical problems can be solved by sequential hierarchical least-squares programming based on a hierarchical step-filter (HSF) and trust-region constraint [ 13 ] . Here, we introduce the necessary adaptations for application to \ell_{0} programming and AGS (see Sec. III and IV ). In its main computational step, S-SHQP iteratively solves sparse hierarchical quadratic programs (SHQP). This can be achieved by standard QP solvers like PIQP or MOSEK [ 14 , 15 ] , but they ignore the specific structure of SHQP. Our proposed SHQP solver \mathcal{N} QP exploits this for computational efficiency. This is useful for robot applications as it enables: • Robot SHIK-P and SHIK-C with simultaneous AGS. • Efficient AGS from large selection of goal positions without need for

Read the complete text