Project Evaluation

My project goal was to produce a procedural walk for a biped model, using inverse kinematics to maintain natural human motion.
While I did not effectively complete this milestone, I believe my development progress demonstrates that I have acquired an understanding of the necessary functionality in order to meet my goal.
Having completed multiple IK implementations, step trajectories and logic systems to enact locomotion logic I am impressed with the amount I have learnt through research and prototyping into an area I was previously unfamiliar with and consider the project a success.

Simulating Balance: Contact Wrench Cones to Remove Limitations of ZMP

Contact Wrench Cone 

Continued reading into approaches to maintain biped stability revealed some limitations of ZMP concept.

As discussed by Dai, H. and Tedrake, R. (Planning robust walking motion on uneven terrain via convex optimization, 2016) The ZMP approach relies on the assumption that the ground contact plane is perfectly flat and even, otherwise the calculation of the support polygon can quickly become highly complex and produces poorly defined areas.

Dai, H. and Tedrake, R. continue to explain that ZMP always considers the contact surface to have theoretically infinite friction to keep the leg limbs from slipping on the surface. This is an issue in real-world robotics as it means that even if the ZMP lies within the support polygon, the leg limb can still slide along the surface and unbalance the system.
In real-world robotics, slipping is a necessary consideration. For my simulation I would be able to adjust the friction of any surface to be sufficient to guarantee no leg-slip, though expanding the solution to assess friction would allow for more believable interactions with external objects as the previous proposed blog improvement would allow.

The stability of the biped systems stance on surfaces of varying friction and tilt can be assessed with the concept of a contact wrench cone.

“The contact wrench cone (CWC) is the admissible set of the total contact wrench, which is computed by summing up the individual contact wrenches at each contact location.” (Dai, H. and Tedrake, R., 2016, P. 580), where a wrench is the concatenation of force and torque.

Simulating Balance: ZMP and Support Polygon

As briefly visited in an earlier blog, when considering the natural motion of a biped’s joints through gait phases I was able to make use of a simple inverted pendulum which I discovered through research into Zero Movement Points.

“ZMP is defined as the point on the ground where the net moment of the inertial forces and the gravity forces has no component along the horizontal axes” (Goswami, 2009, p. 9).

My solution was not produced to account for gravity on the biped, due to the time constraints of the project - though if it were to be expanded, while significantly increasing the systems complexity would produce more realistic behaviours as the biped system adapts its speed and posture with the goal of remaining balanced.

This would allow more realistic behaviours when traversing different terrain types and also from interactions from external forces.

To define the ZMP of a legged system, a single point is approximated by evaluating the ZMP as a function of the systems centre of mass position and centre of mass acceleration as discussed by Danilov et al. (2016, pp. 3-4).

Improving Footstep Placement

Orienting the foot to the supporting surface is comparatively simple compared to the selection of foot placement during locomotion.

Kanoun, Laumond and Yoshida suggest using a model where “Two successive footprints are viewed as two virtual rigidbodies joined by two prismatic joints and one revolute joint around the vertical” (2010, p. 478).

The defined distance between the feet assists with balancing the ZMP within the support polygon. This approach also means that the location of every previous step can be stored in memory – allowing the biped to backtrack if necessary.

Figure 1: Foot step locations with separation determined by two prismatic and a revolute joint (Kanoun, Laumond and Yoshida, 2010, p. 478)

The Footbase - Improving Foot Constraints

In addition to correctly restraining the joint angles during motion, for added realism a model’s feet should match the surface angle of the terrain. Currently only the heel joint is used to check the contact with the floor, which may cause the rest of the foot to clip through the ground/obstacles during the support phase.

Johansen (2009) explains that simply using a single joint/point on the foot is insufficient to orient the joints of the feet to the surface appropriately, as shown in figure 1.

Figure 1: Foot clipping with environment when single joint used to compare ground plane (Johansen, 2009)

Johansen (2009) presents a solution to this issue – the footbase.

3D Procedural Walk

With the exception of the IK algorithm joint constraints, the prerequisite behaviours are now in place to attempt a 3D procedural walk.

As per my milestones, to demonstrate the procedural capability of the solution, I created a script to take basic input from the user: accelerate, decelerate, pivot (about y-axis).
The values in this script are then converted using inverse lerp to give proportional values which are used to define how far ahead of the biped the next foot marker is place and how fast the hips will rotate over the supporting foot.

Bézier Trajectory - 3D Bubbles of Free Space

3D Limb Bones Intersection Problem 

My previous trajectory plotter checked for intersections linearly between the Bézier curve resolution points to determine whether the was an obstacle, and whether the respective obstruction was ‘walkable’.

This approach was suitable for the 2D biped walker, as the model only had to account for the travel space of a point (the centre of the end effector).
Using a 3D model, the foot object (from ankle joint to toe-end joint) must be considered as it moves through space.

To obtain a trajectory that guarantees not to pass through another object, Zhao (2015, pp. 52-58) proposes creating a path of connected ‘bubbles’ as shown in figure 1.
"the concept of bubbles of free configuration space ... is an exact collision checking by attempting to cover the path with collision-free neighborhoods"(Zhao, 2015, p. 54)

Figure 1: Overlapping bubbles of free space to create a clear path (Zhao, 2015, p. 55)

CCD - Joint Rotation Constraints (2nd Attempt)

While I have struggled to find IK sources which describe this problem or solutions to it, further reading and involvement in robotics/maths forums did indicate some potential solutions.

Using these prompts and research from recent weeks I have made multiple more attempts to rewrite my constraint method and CCD script itself to keep the CCD function, while allowing joints to rotate within their defined boundaries.

Alternate Attempts 

CCD - Joint Rotation Constraints, Further Research

Euler Angles 

Euler angles describe the orientation of rigid body in a within a static coordinate system.
“Any orientation can be decomposed into three elemental rotations”: x (yaw), y (pitch) and z (roll). These three elemental angles can then be concatenated to yield the desired orientation" (Kenwright, 2013, p. 4).
Because each angle is decomposed into elemental axis rotations, using Euler angles within an IK solution would make limiting specific joints degrees-of-freedom to explicit rotations straightforward.
In a 2D IK solution this would provide results as intended, though in a 3D IK solutions gimbal lock would have significant negative impact on the functionality of the algorithm.

Figure 1: no aligned axis, no Gimbal lock (Wikipedia Contributors, 2019)

Figure 2: aligned axis, Gimbal lock (Wikipedia Contributors, 2019)

CCD - Joint Rotation Constraints (1st Attempt)

My current solution does nothing to prevent overextension of joints, nor tight configurations of joint angles which “cause the chain to form a loop, intersecting itself” (Mukundan, 2009, p. 304).

Figure 1: Common drawbacks of CCD, including chain intersection (Mukundan, 2009, p. 304)

The problems this creates are clear - an example is demonstrated in figure 2:

Figure 2: Unconstrained solution allows intersections and overextension of joints

The animations my solutions produce must preserve the natural limits of the human body. Limiting the range of each joints’ rotation, coupled with the comparatively low degree of freedom of human limbs and my controllable trajectory plotter, should prevent the above problems.

CCD - Multi-End Structures

During my research for joint bias, I came across the concept of multi-ended kinematic structures. While this was not in my initial development plan, it should provide more natural reaching behaviour and with my current functionality should be a simple to implement in addition to constraining rotation of chain joints this week.

Kenwright (2013, pp. 63-64) discusses how the typical CCD algorithm can be applied to multiple hierarchy structures with separate end effectors.

“It work inwards from the end-effectors and bias the constrain update order towards the starting end-effector (i.e., by bouncing back to the start each time a joint moves), we can avoid joint ownership fighting. In such situations, however, the last updated sequence of joints for an end-effector will get priority on the final orientation (or length) of joints.” (Kenwright, 2013, pp. 63-64)

CCD - Joint Bias and Rotation Damping

Joint Bias 

As discussed by Bouckley (2018) the seeking action of CCD through a kinematic chain does not effectively mimic the natural motion of a human. A human will choose to move there limbs as little as possible to reach their goal, only moving their spine if it becomes necessary, whereas my solution will update every link in the chain each iteration.

To simulate more organic movement of the chain, Kenwright (2013, pp. 59-64) and Bouckley (2018) suggest giving joints closer to the end effector a higher bias, which will cause the joint order to “bounce back towards the start end and updates earlier joints” (Kenwright, 2013, p. 60) each time a joint is corrected, before progressing to the subsequent joint in the chain.

Figure 1: Joint bias

This favouring one chain end for joint correction more closely mirrors the natural joint accommodation behaviour of humans.

Cyclic Coordinate Descent - Implementation

Accommodating Chains of Greater Degrees of Freedom 

“When the number of links in a joint chain becomes greater than three, analytical methods usually become complex and difficult to implement.” (Mukundan, 2009, p. 1)

The function of a Cyclic Coordinate Descent (CCD) algorithm allows for control of highly articulated systems, well beyond 3 degrees of freedom which my current analytical solution limits me to.

As explored in my earlier inverse kinematics approaches blog, a heuristic iterative search aims to place the end effector as close to the target position as possible by performing a series of one-bone corrections in turn, along the length of the limb.

Progress Presentation Feedback

Feedback received from the progress presentation indicates tutors are pleased with my progress and agree that my updated milestones from the initial project proposal have become more accurate and remain appropriate for completion of the project.

During the question period following the presentation I discussed including true physics interactions with the biped, simulating gravity and balance with a true inverted pendulum and support plane.
Lecturers were quick to point out that the scope of this addition is significant, and they expect it to be far too large for a stretch goal. I agree with their assessment and unless I manage to complete the MVP with substantial time remaining, will focus instead on polishing the existing functionality.

Project Milestone Adjustment, 2

Now I have produced a procedural walk for a 2D biped it is an appropriate time to review the remainder of my project – especially with a progress presentation due shortly. Adjusting now will enable me to present a more accurate plan to tutors.

The goals put in place at my last milestone would have achieved the absolute minimum functionality needed to create the 2D procedural gait. While I encountered some issues and had to invest more development time to solve them, I also chose to deviate slightly from my plan to explore, compare and understand the functionality behind the behaviours.
I’m pleased I made this decision as I’m confident I’m in a stronger position to implement the 3D end goal as a result.

Procedural 2D Biped Walk Gait

Now all the prerequisite behaviours have been implemented, they can be combined to procedurally animate locomotion of a 2D biped.

Locomotion Logic 

My earlier gait analysis research has provided the basis for controlling the gait cycle, identifying gait phases which can be used to structure all necessary behaviour:

• Initial contact
• Double support
• Rear foot lift
• Single support/Swing

These phases will be an enum, used by both leg limbs states remain asymmetrical to each other during the gait cycle.

Inverted Pendulum, Hip Motion During Gait

Application In Robotics 

In robotics the “Zero moment point (ZMP) is a mathematical formulation to find a point that causes equilibrium of action and reaction momentum (momentum equal to zero) … ZMP can be approached using Single Linear Inverted Pendulum Model (SLIPM).” (Pristovani et al., 2017, p. 1)

A SLIPM can therefore be used to determine whether the biped is balanced, and corrective limb placement to reach the ZMP.

To achieve this, the model has two main considerations: the position of the centre of mass and the linear acceleration of the object.

Considering Piecewise Curves to Preserve Continuity Over Complex Pathways

While I don’t foresee my trajectory pathways requiring more complexity than can be produced with four control points in a single cubic spline, I have considered how to accommodate more precise pathways if the need arises.

One solution is to simply raise the number of control points used to form the curve, though as the number of control points rises overfitting will become more noticeable. Global control benefits my solution over a short range, maintaining a natural arc, though over longer more intricate paths global control across many more control points may unfavourably alter the path defined by others elsewhere in the curve.

A better method is to join a series of cubic curves together to form a piecewise cubic curve.
While each control point has global control within its cubic curve, it will have no influence over the curve during any other cubic section. This will lessen overfitting while offering suitable control to create complicated pathways.

Bézier Curve, Constant Velocity Throughout Dynamic Ellipses

I have noticed that when control points are manually moved to extreme positions, the speed at which an object moves along the curve is inconsistent.

Figure 1: Difference in segment section lengths when control points positioned outside of natural gait proportion

This is because the length of each segment between two control points in normalised (they are always represented between 0 and 1).

Trajectory Plotting Within Solution

Moving Along Curve 

To give my leg limb end effector an appropriate target to follow during its swing phase, the target must interpolate along the plotted trajectory.

Initially I approached this problem incorrectly; attempting to ‘grow’ the curve by simultaneously expanding each curve section over time, starting from the first control point.
As figure 1 shows, this places the final curve resolution point at the sum interpolation value of all sections – interpolating it along the Bezier curve.
This would allow the target position to be set equal to the final resolution point each frame.

Figure 1: Simultaneously interpolation each curve section over time

Bézier and Catmull-Rom Implementation Comparison

Having implemented functional Bézier and Catmull-Rom curves has been more revealing than expected.

Figure 1: 2D comparison of curves

Figure 2: 3D comparison of curves

The two curves are compared above in 2D (figure 1) and 3D (figure 2). The Bézier curve is shown with spheres at its resolution points and the Catmull-Rom with cubes.