Spline Optimization : Spline optimization using genetic algorithm in AGV system
Männikkö, Viljami (2019)
2019
Teknis-luonnontieteellinen DI-ohjelma - Degree Programme in Science and Engineering
Tekniikan ja luonnontieteiden tiedekunta - Faculty of Engineering and Natural Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2019-10-23
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tuni-201910183950
https://urn.fi/URN:NBN:fi:tuni-201910183950
Tiivistelmä
Splines are polynomial curves. They are used for example to model complicated shapes in computer programs and science. They can be also used to construct planes. Those planes can be used to easily model complicated surfaces. Splines are widely used also in 3D modeling, where models surfaces are defined with splines. In this work, we use splines to model automated guided vehicles’ (AGV) routes. By combining splines, we can easily construct complex route networks to all sorts of vehicles.
Splines can be constructed in multiple ways. No matter of construction method, splines’ shape is always defined by using control points. In this work, splines are constructed by using knot vector and so-called basis functions. If splines are constructed in this way, they are called basis splines (B-splines). Any spline can be defined by a linear combination of B-splines and that’s why Bsplines are practically some sort of basis for splines. B-spline basis functions are constructed by using the Cox de Boor recursion algorithm.
This work’s purpose is to study spline properties from a spline modification point of view. Our goal is to develop an algorithm that modifies the spline route to be faster to drive with an automated guided vehicle in a specified system. Optimization is made by using genetic algorithm properties. In route optimization, we need to take into account different kinds of systems’ restrictions. Splines model AGV routes in the warehouse, which adds more restrictions to the optimization. In optimization, we need to take into account at least AGV maximum acceleration, maximum deceleration, wheel maximum rotation angle, maximum centripetal and maximum velocity. The route has to also be possible to drive, so we have to check during the route that AGV doesn’t hit the obstacles. The goal is to modify route such that AGV start and end velocity, startand endpoint and start and end angle doesn’t change during the optimization. In the work, we will also go through other possible approaches to the optimization, such as the so-called resilient backpropagation method.
Splines can be constructed in multiple ways. No matter of construction method, splines’ shape is always defined by using control points. In this work, splines are constructed by using knot vector and so-called basis functions. If splines are constructed in this way, they are called basis splines (B-splines). Any spline can be defined by a linear combination of B-splines and that’s why Bsplines are practically some sort of basis for splines. B-spline basis functions are constructed by using the Cox de Boor recursion algorithm.
This work’s purpose is to study spline properties from a spline modification point of view. Our goal is to develop an algorithm that modifies the spline route to be faster to drive with an automated guided vehicle in a specified system. Optimization is made by using genetic algorithm properties. In route optimization, we need to take into account different kinds of systems’ restrictions. Splines model AGV routes in the warehouse, which adds more restrictions to the optimization. In optimization, we need to take into account at least AGV maximum acceleration, maximum deceleration, wheel maximum rotation angle, maximum centripetal and maximum velocity. The route has to also be possible to drive, so we have to check during the route that AGV doesn’t hit the obstacles. The goal is to modify route such that AGV start and end velocity, startand endpoint and start and end angle doesn’t change during the optimization. In the work, we will also go through other possible approaches to the optimization, such as the so-called resilient backpropagation method.