As explored in my last blog entry, forward kinematics is concerned with identifying the position and rotation of the kinematic chain’s end effector, while inverse kinematics aims to position the kinematic chain so that it can accommodate the position of the end effector.
This relationship between the two operations is described in figure 1.
 |
| Figure 1: Relationship between forward and inverse kinematics (Kucuk and Bingul, 2006, p. 118) |
Forward kinematics assesses the local position and rotation of each joint to determine the end effector rotation and position in global space. Inverse kinematics uses this global position and adjusts the local rotation of each joint so that the end effector reaches the target position.
My solution will rely on an IK implementation to affect the rotations on joints in the biped limbs to reach towards target positions while applying constraints which maintain realistic human joint rotation limits.
There are 3 categories of IK solution which encompass more specific techniques:
- Analytical
- Heuristic Iterative Search
- Jacobian
Analytical
Analytical techniques frequently yield the fastest solutions to IK errors “because they reduce the IK problem to a mathematical equation that need only be evaluated in a single step to produce a result” (Meredith and Maddock, 2004, p. 1).As kinematic chain length increases beyond 3 joints, this approach becomes less optimal as a number of issues become more likely. While it is still possible to use an analytical solution with longer kinematic chains it is inadvisable as the problem becomes exponentially more complex as it increases in length – the more complex the algorithm becomes the more likely it is to encounter ambiguity and difficulty being able to produce a set of equations for the systems constraints (if one even exists).
Kenwright (2013, pp. 44-54) discusses further potential issues of analytical solutions; analytical algorithms do not handle prioritised constraints, nor do they contain accurate behaviours for out of reach targets.
For my solution these issues may be problematic later in development as I attempt to create more natural motions. Not being able to prioritise joints due to the solution being found in a single step may cause inhuman movements.
While out of reach targets will need to be solved with a ‘best guess’ posture, this can be minimised to give suitably accurate joint angles.
While the restriction to kinematic chains of 2 joints or less is not viable for the later stages of the project, for a basic 2D biped an analytical approach is the “ideal solution for single-degree of freedom hinge joints, such as character knee or elbow joint” (Kenwright, 2013, p. 52).
Heuristic Iterative Search
These techniques consider the IK problem as a series of single bone errors by “attempts to minimize position and orientation errors by transforming one joint variable at a time” (Aristidou et al., 2017, p. 8).The algorithm will iterate over the kinematic chain, correcting the rotation at each joint to reach toward the target location, gradually moving towards a solution.
Unlike analytical solutions, this approach means that the algorithm is easily scalable and could be used to correct the posture of a kinematic chain of any desired length.
Approaches are computationally fast and yield the corrective posture quickly, which as Kenwright (2013, p. 55) mentions, makes them ideal for IK solutions within games.
The nature of iterative corrections along the chain, however, means there is no guarantee that the end effector will be able to precisely reach the target position. As noted by Zucconi (2017) threshold checks could be added to allow the IK solution to break the corrective function if the target has not been reached to prevent the solution adjusting the chain joint angles indefinitely.
As the solution treats the IK error as a series of single-bone problems, the corrective joint rotation applied may also not appear smooth – with some joints having to snap between rotation values to accommodate a moving target position. This will need to be addressed to replicate natural biped locomotion.
As discussed by Mukundan (2009, p. 350), as with an analytical solution, singularities will persist as many possible configurations may solve the IK problem.
My research has shown two promising Heuristic Iterative Search algorithms: Cyclic Coordinate Descent (CCD) and Forwards And Backwards Reaching Inverse Kinematics (FABRIK).
-
CCD: “the purpose of the CCD is to minimize the function that relates the current position of the robot's end effector and the desired position to reach under a certain precision, by moving the robot joints in succession.” (Martín, Barrientos and del Cerro, 2018, p. 4)
As the calculation of CCD corrections requires “only a dot and cross product … it has low computational cost per iteration.” (Aristidou et al., 2017, p. 8).
-
FABRIK: is an IK “solver that gains effi-ciency by finding each joint position by locating a point on a line between the new and old position of the end effector, instead of using angle rotations.” (Ramachandran and John, 2013, p.2).
As shown by (Aristidou et al., 2017) FABRIK frequently outperforms CCD – though the underlying calculations used to generate the corrective posture are more complex.
Both techniques show that their algorithms can be adjusted to constrain joint rotation, prioritise joint rotation, adjust the method in which rotation is applied and be expanded to control connected joint chains.
Jacobian
Jacobian solutions attempt to solve the problem at a global level by minimising each joint error to a corresponding equation to solve how each individual joint can be corrected to accommodate all chain joints while placing the end effector at the target position.This gives accurate corrective postures and eliminates multiple possibilities by only ever defining a single posture.
This implementation is commonly used in robotics to define limb positions periodically. To meet my requirements, the solution would need to be run in Unity’s Update function. The calculations which defines the joint corrections of this approach are by far the most complex of the IK solution categories, which is a concern as Meredith and Maddock (2004, p. 4) point out: “The computational demand of the algorithm is relatively high over a number of iterations” – making its application less suited to that of a game project.
Conclusion and Next Objectives
I have concerns over the performance of a Jacobian solution in comparison to the other techniques. For my goal, while the unwarranted mathematical complexity of the algorithm has potential to impact my ability to meet project milestones.A Heuristic approach offers increased performance, though admittedly has greater potential to yield less ‘natural’ joint configurations when compared to the global calculations carried out by a Jacobian solution. However, as discussed above the constraints, checks and behaviour that can be included within an iterative algorithm seem to be able to correct these unwanted traits in the applied postures.
Analytical approaches are the most performant and simplest to implement, though would effectively limit the scope of implementation to two or fewer joints.
I believe the best plan for my project’s development is to begin my exploration by developing an analytical solution for a 2D biped with arm/leg chains each consisting of two joints and an end effector.
Once successful I will progress onto a heuristic iterative search algorithm which will allow me to transition into longer, 3D kinematic chains as will be required for the project.
I expect that completing a 2D analytical solution first will give me a greater understanding of issues shared by analytical and iterative solutions (singularities, out of range targets, less desirable methods of applying rotation) before I then attempt the more complex iterative algorithms.
When I reach the stage where I am ready to begin producing an iterative search, I will begin with CCD for largely the same reason I have chosen not to produce a Jacobian solution. If I am successful with this implementation and there is suitable remaining time I will produce a FABRIK solution so my application can be made more efficient.
References
Aristidou, A., Lasenby, J., Chrysanthou, Y. and Shamir, A. (2017). Inverse Kinematics Techniques in Computer Graphics: A Survey. Computer Graphics Forum, [online] 37(6), pp.35-58. Available at: http://www.andreasaristidou.com/publications/papers/IK_survey.pdf [Accessed 10 Nov. 2018].
Kenwright, B. (2013). Game inverse kinematics. [Place of publication not identified]: CreatSpace, pp.8-10, 39-87, 89-96.
Kucuk, S. and Bingul, Z. (2006). Robot Kinematics: Forward and Inverse Kinematics. Industrial-Robotics-Theory-Modelling-Control, [online] pp.117-148. Available at: https://pdfs.semanticscholar.org/d2ff/f0043238ad6b525ed22839e813e3e85b5511.pdf [Accessed 14 Nov. 2018].
Martín, A., Barrientos, A. and del Cerro, J. (2018). The Natural-CCD Algorithm, a Novel Method to Solve the Inverse Kinematics of Hyper-redundant and Soft Robots. Soft Robotics, [online] 5(3), pp.242-257. Available at: https://www.liebertpub.com/doi/full/10.1089/soro.2017.0009 [Accessed 1 Nov. 2018].
Meredith, M. and Maddock, S. (2004). Real-Time Inverse Kinematics: The Return of the Jacobian. [online] pp.1-5, 9-13. Available at: https://staffwww.dcs.shef.ac.uk/people/S.Maddock/publications/MeredithMaddock2004_CS0406.pdf [Accessed 16 Nov. 2018].
Mukundan, R. (2009). A robust inverse kinematics algorithm for animating a joint chain. International Journal of Computer Applications in Technology, 34(4), p.303.
Ramachandran, S. and John, N. (2013). A Fast Inverse Kinematics Solver using Intersection of Circles. [online] pp.1-5. Available at: https://www.academia.edu/29770733/A_Fast_Inverse_Kinematics_Solver_using_Intersection_of_Circles [Accessed 15 Nov. 2018].
Zucconi, A. (2017). The Mathematics of Forward Kinematics - Alan Zucconi. [online] Alan Zucconi. Available at: https://www.alanzucconi.com/2017/04/06/forward-kinematics/ [Accessed 11 Nov. 2018].
Bibliography
Gürbüzbalaban, M., Ozdaglar, A., Parrilo, P. and Denizcan Vanli, N. (2017). When Cyclic Coordinate Descent OutperformsRandomized Coordinate Descent. 31st Conference on Neural Information Processing Systems (NIPS 2017, [online] pp.1-3, 7-8. Available at: https://papers.nips.cc/paper/7275-when-cyclic-coordinate-descent-outperforms-randomized-coordinate-descent.pdf [Accessed 16 Nov. 2018].
Singh, G. and Claassens, J. (2010). An analytical solution for the inverse kinematics of a redundant 7DoF Manipulator with link offsets. 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, [online] pp.1-7. Available at: https://www.researchgate.net/publication/224199136_An_analytical_solution_for_the_inverse_kinematics_of_a_redundant_7DoF_Manipulator_with_link_offsets [Accessed 16 Nov. 2018].
