This project was done by me during my Internship at Robotics Research Center(RRC)@ International Institute of Information Technology (IIIT) Hyderabad under the mentorship and supervision of Prof. Nagamanikandan Govind and Prof Madhav Krishna.
I have provided the link to the useful resources and project presentation slides here.
Link to Github repo (Have not got the permission to Upstream this part of the project yet)
Recommended Read -
- Trajectory Generation and Following by a Holonomic Drive Robot
🤔Introduction
Path optimization is a critical aspect in fields like robotics, autonomous navigation, and animation. One of the most effective techniques for achieving smooth and efficient paths is through the use of splines. Unlike straight-line paths, splines allow for the creation of continuous, curvilinear trajectories that optimize movement while avoiding abrupt changes in direction. Splines provide flexibility by adjusting curves through control points, enabling precise control over the path’s shape.
This technique minimizes energy consumption and ensures smoother transitions given that you have to reach point A→B through Multiple Way-Points in a given time frame, making it ideal for robotics and other motion-based applications.
Objective -
To Generate a trajectory through a given set of waypoints such that -
- The path generated is atleast velocity continuous.
- The path shall be smooth and shouldn’t stop at the waypoints to rotate towards the next waypoint.
- The path should pass through all the waypoints.
- The path must be Optimal In terms of smoothness and curvature.
Consideration and it’s result Summary-
Type of Spline | Notes | Pros | Cons | |
1. | Linear Spline | Piecewise linear segments connecting waypoints. | Simple to implement; low computational cost. | Produces sharp transitions at waypoints; lacks smoothness. |
2. | Quadratic Spline | Uses quadratic polynomials between waypoints, offering moderate smoothness. | Smoother than linear splines; computationally efficient. | Not as smooth as cubic splines; may lack control over curvature. |
3. | Bézier Spline | Defined by control points rather than waypoints, providing a flexible curve. | Good control over the shape of the curve; widely used in graphics and animation. | Requires more control points for complex paths; can be computationally expensive for higher-degree curves. |
4. | B-Spline | Generalization of Bézier splines, offering local control over curve segments without affecting the entire path. | Local control allows for easy modification; smooth curves; widely used in robotics and CAD applications. | Can be complex to implement; may require a high number of control points to achieve certain path shapes. |
5. | Catmull-Rom Spline | A type of interpolating spline that passes through each waypoint. | Automatically interpolates through waypoints; smooth transitions without overshooting. | Limited control over the tension of the curve; can produce undesirable oscillations with certain waypoint configurations. |
6. | Hermite Spline | Defined by endpoint positions and tangents at each waypoint, offering direct control over both the shape and slope of the curve. | Provides control over both position and velocity (or slope) at waypoints; smooth and versatile. | Requires specifying tangent vectors at each waypoint, which can add complexity; not ideal if tangents are difficult to estimate. |
Major Consideration and selection
After exploring various spline types, we decided to go ahead with Hermite, Cardinal and Catmull-Rom Spline for the testing of trajectory generation due to the specific advantages they offer in our use case.
Hermite Spline:
- Control Over Tangents: Hermite splines provide direct control over both the positions and tangents (slopes) at each waypoint, which is crucial when we need precise control over the velocity or direction of the path.
- Smooth Transitions: The ability to define tangents ensures that the transitions between waypoints are smooth and customizable, making Hermite splines ideal for applications where movement needs to be refined.
- Flexibility: The additional flexibility to adjust the shape of the curve makes splines suitable for complex trajectories that require precise maneuvering.
Cardinal Spline:
- Adjustable Tension: Cardinal splines are a generalization of Catmull-Rom splines with an additional tension parameter. This gives us more control over the shape of the curve, allowing us to adjust how tight or loose the path is between waypoints. By tuning the tension, we can achieve the desired balance between sharpness and smoothness in the trajectory.
- Smooth Interpolation: Like Catmull-Rom, cardinal splines also pass smoothly through all the waypoints, but the tension control adds flexibility, making it useful when different parts of the trajectory require varying degrees of smoothness.
- Balanced Control and Simplicity: While more flexible than Catmull-Rom, cardinal splines remain relatively simple to implement and offer a good trade-off between control and ease of use.
Catmull-Rom Spline:
It’s a cardinal Spline with a scale value(s) = 1/2
•Automatic Interpolation: Catmull-Rom splines automatically interpolate through all waypoints without the need to manually define tangents, making it easier to generate a smooth path that passes through all key positions.
•Simplicity: It provides smooth transitions without overshooting, making it a reliable option when a smooth, natural curve is required through multiple waypoints with minimal setup.
•Efficient for Waypoint-Based Paths: For applications where waypoints are already well-defined and smoothness is a priority, Catmull-Rom splines offer a quick and efficient way to generate a trajectory.
📈Further Optimization
For the optimization of our trajectory, we ultimately chose the Cardinal Spline as it met all of our criteria. This spline gave us the flexibility to control the tension between waypoints, allowing us to adjust the smoothness and sharpness of the path. Cardinal splines, being a generalization of Catmull-Rom splines, introduce a tension parameter (s) that controls the tightness of the curve. The value of this parameter significantly impacts the overall behavior of the trajectory.
🚦Flexibility in Control
The key advantage of using a Cardinal Spline is the ability to fine-tune the tension parameter. By adjusting s, we can control how sharp or smooth the path is between waypoints:
- Low tension (s closer to 0) results in looser, more flexible curves, ideal for gentle transitions.
- High tension (s closer to 1) tightens the curve, resulting in sharper, more precise turns.
For most of our test cases, s = 1/2 worked well as a general value, offering a balanced trade-off between sharpness and smoothness. However, for maximum optimization, we aimed to fine-tune this parameter further, specifically to minimize the overall cost of the path, which includes factors like trajectory smoothness, energy consumption, and execution time for robotic systems.
Cost Optimization Using Gradient Descent
To achieve the best possible path, we focused on reducing the cost function associated with our trajectory. The cost function takes into account:
- Path smoothness (minimizing sudden direction changes),
- Energy consumption (ensuring the robot moves efficiently),
- Time (minimizing unnecessary delays while maintaining smooth motion).
To optimize the tension parameter (s) in the Cardinal Spline, we used gradient descent. This is an iterative optimization algorithm that adjusts parameters to minimize the cost function. Here’s how it worked:
- Define the Cost Function: We formulated a cost function that includes terms for trajectory smoothness, energy efficiency, and sharpness penalties. This function quantifies how “good” a particular path is based on these factors.
- Initialize the Tension Parameter (s): We began with s = 1/2, which served as our initial guess. This value worked well in many cases, but it wasn’t optimal for all scenarios, so it required further fine-tuning.
- Calculate the Gradient: At each iteration, we computed the gradient of the cost function with respect to s. The gradient indicates the direction and rate of change in the cost function, helping us understand whether increasing or decreasing s will reduce the cost.
- Update the Tension Parameter (s): Using the gradient, we updated the value of s in the direction that minimizes the cost. This adjustment followed the equation:
where η is the learning rate, controlling how large each step is in the optimization process.
- Iterate Until Convergence: We repeated the process, continuously updating s until the cost function converged to its minimum. In most cases, this resulted in small tweaks to s that led to a significant reduction in the overall cost.
Conclusion :
- Optimal Tension Parameter: While s = 1/2 was a good starting point, gradient descent allowed us to find more precise values of s for specific trajectories, further reducing cost and improving path efficiency.
- Improved Smoothness and Efficiency: The optimized values of s resulted in smoother transitions between waypoints while minimizing unnecessary movements, which directly reduced the energy consumption and improved overall execution time.
- Flexibility and Control: By applying gradient descent, we achieved a level of control over the path that wouldn’t have been possible with a fixed tension parameter. The optimization process allowed us to dynamically adjust the smoothness and sharpness of the trajectory based on the specific requirements of the robot’s path.
In conclusion, using Cardinal Splines combined with gradient descent for parameter optimization allowed us to achieve a well-balanced, efficient, and smooth trajectory that met our optimization goals. The flexibility provided by the adjustable tension parameter and the cost-reduction benefits of gradient descent proved crucial in minimizing the path cost while maintaining high-performance motion.