1.3.1 Different type of optimization algorithms
Historically, several types of optimization algorithms have been used based on their strengths and weaknesses; however, all optimization algo-rithms can be categorized into calculus-based methods, enumerative meth-ods, and random methods.
Calculus-based methods have been by far the most explored and stud-ied optimization methods. They rely on solving linear or nonlinear sets of equations by computing the gradient of the functions to search where the function gradient becomes null, which indicates a local maxima or minima. The problems with these methods are apparent. They are very powerful tools to obtain the extrema of a known function; however, they might breakdown when the problem becomes difficult to express from a mathematical point of view. Further, the obtained results might be only local extrema and not global ones.
The second method is a very human-like approach to solving the prob-lem of enumeration. As the name implies, the process is to enumerate every single possible solution of the problem to assess their quality. This straightforwardness can seem attractive; however, as expected, in the case of complex system analysis, it is simply a widely inefficient method because of the number of useless answers obtained in the process.
The final optimization method, which has attracted the most attention in recent years, is the random method. Within this method, we found several nature-inspired optimization algorithms such as GA [71, 72], par-ticle swarm optimization (PSO) [73], artificial bee colony (ABC) [74, 75], and adaptive firefly algorithm (AFA) [76]. The most popular and widely used would be GA because they can solve multiobjective problems with relatively simple algorithms involving a minimal amount of mathematics.
The tradeoff is the birth of deceptive results if the problem is not tackled
wisely and the uncertainty of computational time.
In our case, we adapt the optimization of the mechanical design using exponential coordinates to GA because exponential parameters are flexible, describe the robotic system in an independent manner, and are easy to code into binary strings.
1.3.2 Overview on genetic algorithms
First, we provide a quick reminder on GA. The GA is a type of op-timization algorithm based on natural selection, first proposed by John Holland in the 1970s. Similar to the natural process, GAs observe the evo-lution of a given population at a given time. First, we define the several parts of GAs to clarify their components:
• The total number of samples in a study are referred as the population of the study and the size of the population is given by N.
• A structure orgenotype in an artificial genetic system is one member of the population. They represent a parameter set in the solution space and are referred to as Si.
• A string or chromosome is the coding of one parameter within the parameter set. In the simplest cases (when parameter sets are only composed of one parameter), the structure and string are the same entity. We refer to the strings as si
• These chromosomes are composed of genes that are the elementary brick of the parameter coding within the set and are denoted as bi. These genes contain two pieces of information: their position in the chromosome, which we will call the locus, and their value, which we will call alleles.
• The function value or fitness of a structure or string defines its apti-tude to compel to the objective of the optimization, the aim being the maximization of the average fitness of a population, which will mean that we are closer to achieving the objective.
For simplicity, we show an example to explain GAs by representing the population as a string of Boolean characters representing numbers. The set of Boolean is defined as B = {b|b ∈ {0,1}}. A string is a vector with members in B; for instance,
s =
b1 · · · bn
∈ Bns. (1.61)
However, these strings cannot be used in their Boolean form most of the time because they do not carry the information (or parameter value)
explicitly. To extract the information from those strings, we decode them to obtain a value in the natural number set such that the natural equivalent defined in N is given by
s ≡ b1 ×20 +· · ·+b1 ×2n−1. (1.62) Once the population is defined, we must observe their evolution over time and generate successive populations that will hopefully improve over time. To achieve evolution, the three main operators of genetic algorithms—
Reproduction, Crossover and Mutation—are used.
Reproduction is the process of copying existing strings or structures based on their fitness. Since the fitness of these structures are a direct measure of their utility or goodness that we want to maximize, it is only natural to attach higher importance to the structure possessing a high fitness. As such, the reproduction process will first aim to classify each structure in the current population according to their fitness, attributing to every structure a percentage of the total fitness. When this percentage is attributed, we will build a roulette wheel representing the different struc-tures according to their fitness, and we reproduce the structure attached to them where the marble ends up in the wheel. This operator simply repre-sents the concept of the survival of the fittest, because higher the fitness of one structure, the larger is their portion in the wheel, and thus, the higher is the probability that the marble will fall out in their position. We spin the wheel n times to end up with the same number of structures as we had in the beginning.
Crossover is the process of mixing two structures information to form a new one containing part of both parent structure information. The crossover process can be divided into two steps. The first step is to decide where we will “cut” the string or structures to mate them together. The second step is to select two structures at random within the population to ensure that mating occurs. This operator mimics the natural mating process between two subjects of a population.
Finally, mutation is a process that transforms information possessed by one structure at random. Mutation is the operator that is completely random in a genetic algorithm and thus keeps the algorithms from stag-nating for too long in a dead end if their initial population is biased or if the population structures are similar but still fail to achieve the objective.
The several operations are shown on Fig. 1.5.
The overall process has, however, proven to be a very effective method to achieve optimization, especially when we do not have numerical equations fully describing a system, or when the number of optimization parame-ters is too high to attempt enumeration optimization methods. Therefore, the main challenge for the design optimization is to code the system pa-rameters in binary for the GA process, as shown in Eq. (1.62). In our exponential formulation, the parameters we need to code into the strings are the exponential parameters {vi, ωi, qi} and the chain matrix {Ch}. The length of the links li is defined from the positions of the joints qi, and it is not a design parameter.
Generation N Generation N+1
0100 0010 ...
1011
String Fitness
1011 0100 ...
1011
String Fitness
4 2 ..
11
11 4 ..
11
(a) Reproduction process
Generation N Generation N+1
String String
(b) Crossover process
(c) Mutation process
Generation N Generation N+1
String String
0100 0110
01 00 00 10
0000 0110
Figure 1.5: Basic operations of genetic algorithms
Chapter 2
Kinematics, Dynamics, and control
of tree-type systems
2.1 Purpose of this chapter
In this chapter, we will focus on the derivation of the kinematics and dy-namics of tree-type systems grasping an object, propose control strategies to apply for those systems and illustrate our theories with a well-known example: an arm-hand system.
We will start by describing the properties of tree-type systems. Those systems possess branching in the kinematic path, which we will describe by separating every path from the base to one extremity of the system in an entity which we will call a chain. We then propose a matrix regrouping the joints in the system and distributing them within the chains of the system. We will call this matrix the chain matrix, and it will describe the connection between the joints to understand the architecture of a tree-type system. Using this matrix, we will then propose a unified closed form of the kinematics and dynamics of those systems based solely on the exponential parameters q, v, ω, their transformations ξ and eξθ and the chain matrix Ch, allowing for an automated design process.
Next, we will focus on the grasping part, deriving the object equation of motion and the constraint linking the manipulator and the object in terms of exponential coordinates. When the whole system equations have been defined, we will observe that such systems often contains redundancy on the manipulator part. There, we will propose control strategies adapted to such situations, summarize the hole automated design process and conclude with an example.