# Path Planning for a Space-Based Manipulator System Based on Quantum Genetic Algorithm

Authors: Zhengcang Chen; Weijia Zhou
Journal: Journal of Robotics
 (2017)

---

## Abstract

In this study, by considering a space-based,n-joint manipulator system as research object, a kinematic and a dynamic model are constructed and the system’s nonholonomic property is discussed. In light of the nonholonomic property unique to space-based systems, a path planning method is introduced to ensure that when an end-effector moves to the desired position, a floating base achieves the expected pose. The trajectories of the joints are first parameterized using sinusoidal polynomial functions, and cost functions are defined by the pose deviation of the base and the positional error of the end-effector. At this stage, the path planning problem is converted into a target optimization problem, where the target is a function of the joints. We then adopt a quantum genetic algorithm (QGA) to solve this objective optimization problem to attain the optimized trajectories of the joints and then execute nonholonomic path planning. To test the proposed method, we carried out a simulation on a six-degree-of-freedom (DOF) space-based manipulator system (SBMS). The results showed that, compared to traditional genetic optimization algorithms, the QGA converges more rapidly and has a more accurate output.


---

## Body

## 1. Introduction

During space missions, astronauts face a harsh and life-threatening environment in space, especially in the course of extravehicular activities. A growing number of researchers think it inevitable that space manipulators will be used, autonomously or semiautonomously, in future missions to perform tasks either completely or incompletely [1–3]. With the rapid development of space technologies, a number of tasks can be implemented by space manipulator systems. At present, some manipulators are installed on a base whose position or attitude is controlled by reaction wheels or thrusters, taking a satellite-manipulator system, for instance. This kind of system has the following disadvantages: (1) the position and pose control system (PACS) consumes fuel, which shortens the lifespan of the entire space mission. (2) Gas emitted by the thruster might negatively impact the surrounding objects. (3) When the PACS is used, a transient response appears that may impact the dynamic performance of the system. (4) The pose control system can easily attain a saturated state.In order to solve this problem, many researchers use space-based systems to replace the ones whose base is installed with PACS. However, there exists a highly dynamic coupling phenomenon between a floating base and a manipulator in a space-based system, especially when both have a similar mass. This affects the control precision of the end-effector of the manipulator because the space-based manipulator system (SBMS) is nonholonomic. This study focuses on using the nonholonomic property to plan the path of joints such that the end-effector and the floating base simultaneously arrive at the desired state.Unlike fixed systems, the position and pose of the end-effector of a manipulator in space-based systems are dependent not only on the given joint angles, but also on the joint paths. In other words, for the same joint configuration, different joint paths correspond to different poses. The authors of [4, 5] studied the course of the development and the status of nonholonomic systems as well as their principles of dynamics and control methods. Rathee and Pathak [6] present path planning of dual arm free flying space robot using smooth functions of time. Results of their works demonstrate that if the base mass and inertia are increased to a certain limit keeping in mind the singularities, then base disturbance can be decreased and the end effectors follow the required circular path. Zeng et al. [7] present a subsection algorithm for obstacle avoidance path planning of free-floating space manipulator for orbit observation. The approach could guarantee that the end-effector reaches the desired point and realize the obstacle avoidance. Kaigom et al. [8] propose a Constrained Particle Swarm Optimization algorithm to steer the end-effector to a target pose with minimized base disturbance. This approach is based on Reaction Null-Space concept. And its simulation results demonstrate the effectiveness of the planning method. Liu et al. [9] analyze the path planning of redundant, free-floating space manipulators with revolute joints, and 7 degrees of freedom. They provide a tractable planning method to avoid the pseudo-inverse of the Jacobian matrix. Nenchev [10] summarizes results based on the application of Reaction Null-Space approach. Via the null-space and pseudo-inverse mapping of the coupling inertia, the joint space is decomposed into two complementary orthogonal subspaces which is useful for motion analysis and control of various unfixed-base systems. Jia et al. [11] present a novel path planning method to avoid obstacle based on A∗ algorithm for space manipulators. In this article, a concept of “collision-free workspace” of a space manipulator is provided. Shi et al. [12] propose a nonholonomic motion planning methodology for free-floating space robot (FFSR) using swarm optimization algorithm. Also, an optimal control technique is applied for FFSR trajectory planning. Zhang [13] proposed a path planning method for a free-floating space robot in Cartesian space. Shi [14] proposed a quantum particle swarm optimization method to plan path for space robots, and Jia et al. [15] developed a straight-line trajectory optimization method for a redundant robot with nine degrees of freedom (DOF).In this study, based on an analysis of nonholonomic properties, we first determine the coupling relationship between a base and a manipulator. We consider the pose of the base and the position of the end-effector as the optimized targets. We then parameterize the joint trajectories using sinusoidal polynomial functions, set ranges of value for the joint angles, rate, and acceleration, and convert the path planning problem into a target optimization problem. Finally, we make use of a QGA to resolve and obtain the optimal parameters as well as an expression of the joint trajectory. To test the effectiveness of the proposed method, we conducted a forward simulation to solve for the optimal target.


## 2. Kinematic Model of a Space-Based Manipulator System

According to the modeling theory of unrooted multibody systems, with respect to coordinate transformation, a new modeling approach is proposed.


### 2.1. Description of SBMS

An SBMS consists of ann-joints manipulator and a floating base. Its simplified schematic diagram is shown in Figure 1:(1)
Each component of the system is rigid and numbered from 0 toN starting from the base.(2)
For simplicity, each joint between linki and link i+1 has one DOF.(3)
The entire system is in microgravity without an external force exerting on it.(4)
The system has a tree topology.(5)
Σi and ΣI are, respectively, the body-fixed reference frame and the inertial reference frame. In general, the origin of the inertial reference frame and the center of mass of the SBMS overlap to some extent in the initial state, and the direction of Σ0 coincides with that of ΣI.(6)
ai represents the position vector relating jointi to the CM of link i, and bi represents that relating the CM of linkito the next joint.Figure 1
Structure diagram of a space-based manipulator system.The selection of coordinate systems is a precondition of modeling. A mixed coordinate system consisting of related and reference coordinates is chosen in this study. In particular,x0∈R3 and θ∈R3 represent the position and pose of the base, and ϕ∈Rn represents the joint angles here.


### 2.2. Kinematic Modeling

We define dependent coordinatesYci=[xiT,θiT]T, i=0,…,n (called the positional screw), mixed independent coordinates yp=[x0T,θ0T,ϕT]T, and the dependent velocity screw as Y˙i=[viT,ωiT]T.The constraint equation of ann-joint open-loop serial rigid body system is written as(1)ΦYc=0∈Rm,where Yc=Yc0T,…,YcnTT∈R6n+6 andm represents the number of constraint equations. The velocity screw is not just a differential of positional screw. It is(2)Y˙c=UYcY˙.When a different reference frame is selected, the expression ofU also differs: see [16].We differentiate (1) and substitute (2) into it:(3)ΦYY˙=0,where ΦY=∂Φ/∂Y∈Rm×6n+6 represents the Jacobian of the constraint equations.Since the DOF of a system is equal to the difference between the number of dependent coordinates and that of the constraint equations—that is,f=(6n+6)-m—the kernel of ΦY is spanned by f linearly independent column vectors. The basic solutions of this vector space are defined as {S1,…,Sf}. Hence, the dependent velocity screw can be expressed as(4)Y˙=S1t1+S2t2+…+Sftf,where S=S1,…,Sf∈R(6n+6)×(n+6) is called the basic solution matrix. Let y˙=t=[t1,…,tn+6]T, which is an independent velocity vector. The velocity screw of the nth link can be written as(5)Y˙n=Bn,0Y˙0+Jnϕ˙.Since the system is in free-floating state, momentum is conserved and is assumed to be zero:(6)Y˙0=JTbϕJRbϕ=-JTωw+r~g0TIs-1Im-Is-1Imϕ.˙Connecting (5) and (6), the velocity-level differential equation is written as(7)Y˙n=J∗ϕϕ˙,where J∗ represents the generalized Jacobian matrix, the concrete representation of which is (8)J∗=E3r~Tn,00E3-JTωw-r~g0TIs-1Im-Is-1Im+Jn,Ji=JTiJRi=Bi,1η1⋯Bi,i-1ηi-1ηi0⋯0∈R6×n,Bi,j=E3r~Ti,j0E3,ηi=ki×aiki,JTω=∑i=1nmiJTi,ri,j=ri-rj,Im=∑i=1nIiJRi-mir~iTJTi-r~gJTω,Is=I0+∑i=1nIi+mir~ir~i0T-wr~gr~0gT.During nonholonomic path planning, the integral and iterative processes based on (6) and (7) can implement path following a floating base.


### 2.3. Analysis of Nonholonomic Properties

In order to better understand the coupling phenomenon between a floating base and a manipulator installed on it, an SBMS is here demonstrated as being nonholonomic [17].Definition 1.
A linear subspace spanned by one or moren-dimensional unsteady vectors is called a distribution.Definition 2.
If the result of a Lee bracket operation between two random vectors belonging to a distribution also belongs to it, the distribution is deemed involutive.Frobenius’ Theorem.The necessary and sufficient condition for the integrality of the Pfaffian constraint equations is that their solution space is an involutive distribution.The state variables are defined as the angle velocity of the base and the joint angle velocity of the manipulator; that is,x˙z=[ω0T,ϕ˙T]T. The input value is defined as u=ϕ˙. From (2) and (6), (9)x˙z=Ku,where the coefficient matrix K can be written as K=U-1θ0JRbϕEn and θ0 represents the pose angle.A generalized velocity distributionΔ consists ofn columns of K; that is, Δ=span⁡(K1,…,Kn), where Ki=(k1i,k2i,k3i,eiT)T and eiT represents the standard unit vector. The result of the Lee bracket between Ki and Kj is(10)Ki,Kj=k1ij,k2ij,k3ij,0TT∉Δ.Hence,Δ is not involutive. According to the Frobenius theorem, SBMS has been shown to be a nonholonomic system.


## 2.1. Description of SBMS

An SBMS consists of ann-joints manipulator and a floating base. Its simplified schematic diagram is shown in Figure 1:(1)
Each component of the system is rigid and numbered from 0 toN starting from the base.(2)
For simplicity, each joint between linki and link i+1 has one DOF.(3)
The entire system is in microgravity without an external force exerting on it.(4)
The system has a tree topology.(5)
Σi and ΣI are, respectively, the body-fixed reference frame and the inertial reference frame. In general, the origin of the inertial reference frame and the center of mass of the SBMS overlap to some extent in the initial state, and the direction of Σ0 coincides with that of ΣI.(6)
ai represents the position vector relating jointi to the CM of link i, and bi represents that relating the CM of linkito the next joint.Figure 1
Structure diagram of a space-based manipulator system.The selection of coordinate systems is a precondition of modeling. A mixed coordinate system consisting of related and reference coordinates is chosen in this study. In particular,x0∈R3 and θ∈R3 represent the position and pose of the base, and ϕ∈Rn represents the joint angles here.


## 2.2. Kinematic Modeling

We define dependent coordinatesYci=[xiT,θiT]T, i=0,…,n (called the positional screw), mixed independent coordinates yp=[x0T,θ0T,ϕT]T, and the dependent velocity screw as Y˙i=[viT,ωiT]T.The constraint equation of ann-joint open-loop serial rigid body system is written as(1)ΦYc=0∈Rm,where Yc=Yc0T,…,YcnTT∈R6n+6 andm represents the number of constraint equations. The velocity screw is not just a differential of positional screw. It is(2)Y˙c=UYcY˙.When a different reference frame is selected, the expression ofU also differs: see [16].We differentiate (1) and substitute (2) into it:(3)ΦYY˙=0,where ΦY=∂Φ/∂Y∈Rm×6n+6 represents the Jacobian of the constraint equations.Since the DOF of a system is equal to the difference between the number of dependent coordinates and that of the constraint equations—that is,f=(6n+6)-m—the kernel of ΦY is spanned by f linearly independent column vectors. The basic solutions of this vector space are defined as {S1,…,Sf}. Hence, the dependent velocity screw can be expressed as(4)Y˙=S1t1+S2t2+…+Sftf,where S=S1,…,Sf∈R(6n+6)×(n+6) is called the basic solution matrix. Let y˙=t=[t1,…,tn+6]T, which is an independent velocity vector. The velocity screw of the nth link can be written as(5)Y˙n=Bn,0Y˙0+Jnϕ˙.Since the system is in free-floating state, momentum is conserved and is assumed to be zero:(6)Y˙0=JTbϕJRbϕ=-JTωw+r~g0TIs-1Im-Is-1Imϕ.˙Connecting (5) and (6), the velocity-level differential equation is written as(7)Y˙n=J∗ϕϕ˙,where J∗ represents the generalized Jacobian matrix, the concrete representation of which is (8)J∗=E3r~Tn,00E3-JTωw-r~g0TIs-1Im-Is-1Im+Jn,Ji=JTiJRi=Bi,1η1⋯Bi,i-1ηi-1ηi0⋯0∈R6×n,Bi,j=E3r~Ti,j0E3,ηi=ki×aiki,JTω=∑i=1nmiJTi,ri,j=ri-rj,Im=∑i=1nIiJRi-mir~iTJTi-r~gJTω,Is=I0+∑i=1nIi+mir~ir~i0T-wr~gr~0gT.During nonholonomic path planning, the integral and iterative processes based on (6) and (7) can implement path following a floating base.


## 2.3. Analysis of Nonholonomic Properties

In order to better understand the coupling phenomenon between a floating base and a manipulator installed on it, an SBMS is here demonstrated as being nonholonomic [17].Definition 1.
A linear subspace spanned by one or moren-dimensional unsteady vectors is called a distribution.Definition 2.
If the result of a Lee bracket operation between two random vectors belonging to a distribution also belongs to it, the distribution is deemed involutive.Frobenius’ Theorem.The necessary and sufficient condition for the integrality of the Pfaffian constraint equations is that their solution space is an involutive distribution.The state variables are defined as the angle velocity of the base and the joint angle velocity of the manipulator; that is,x˙z=[ω0T,ϕ˙T]T. The input value is defined as u=ϕ˙. From (2) and (6), (9)x˙z=Ku,where the coefficient matrix K can be written as K=U-1θ0JRbϕEn and θ0 represents the pose angle.A generalized velocity distributionΔ consists ofn columns of K; that is, Δ=span⁡(K1,…,Kn), where Ki=(k1i,k2i,k3i,eiT)T and eiT represents the standard unit vector. The result of the Lee bracket between Ki and Kj is(10)Ki,Kj=k1ij,k2ij,k3ij,0TT∉Δ.Hence,Δ is not involutive. According to the Frobenius theorem, SBMS has been shown to be a nonholonomic system.


## 3. Transformation of Path Planning Problem to Objective Optimization Problem

### 3.1. Solving the Objective Function

As we know, the whole system is composed of a floating base, a macroarm, and a dexterous robotic hand. During objective capturing process, the macroarm and dexterous hand are fixed together. The main topic of this text is to make the dexterous hand (or a special point of the macroarm) arrive a desired position by planning the joint path of the macroarm. As for how and with what attitude to capture an objective by the dexterous hand, it is not included in the topics. Also, attitude of the floating base has an important influence on communication quality and solar conversion efficiency. So, the focus of this study is to plan joint trajectory in order to enable the posture of the base and the position of the end-effector arrive at their desirable states simultaneously. The relevant variables include the quaternion of the base and the position vector of the end link, which are written asX=[QbT,PeT]T∈R6. X0, Xd, and Xf are, respectively, the initial state, the desired state, and the final state.Steps of path planning are as follows:(1)
Transformation of state variables (X→X′=QbT,ϕTT). End-effector positional vector with respect to the base-linked reference frame is only dependent on joint angles vector ϕ; that is, PeT0=f1(ϕ), while the homogenous transformation matrix from inertial reference frame to base-linked one is related to attitude of the base and the base’s positional vector rb; that is, AI0=f2(QbT,rb). Assume that rb=rb0 (a constant) at t=0. According to momentum conservation law, vector rb is related to history of joint angles; that is, rb=rb(ϕ). So state variable is transformed by PeT=AI0·P0eT=f3(QbT,ϕ).(2)
Parameterized joint trajectory using sinusoidal polynomial functions.(3)
Design of objective function based on the deviation between the final state and the desire state.The destination of path planning is as follows: the planned joint trajectoryϕ(t) can render true the condition whereby the final state variables can infinitely approach the desired variables; that is, X′d-X′f→0.


### 3.2. Parameterization of Joint Angles

Using the sinusoidal function to parameterize the joint angles can better constrain their scope. To ensure that the velocity and acceleration curves are smooth, we define(11)ϕit=aisin⁡bi7t7+⋯+bi1t+bi0+ci.There are six constraint conditions:ϕi0=ϕ0, ϕi0=0, ϕ¨i0=0, ϕi(tf)=ϕid, ϕitf=0, and ϕ¨itf=0. The range of ϕi is ϕi∈[ϕi∣ϕimin<ϕi<ϕimax].So,ai=(ϕimax-ϕimin)/2 and ci=(ϕimax+ϕimin)/2.Then, joint angle velocity and acceleration can be written as(12)ϕ˙it=aicos⁡bi7t7+⋯+bi1t+bi0·7bi7t6+⋯+bi1,ϕ¨it=-aisin⁡bi7t7+⋯+bi1t+bi0·7bi7t6+⋯+bi12+aicos⁡bi7t7+⋯+bi1t+bi0·42bi7t5+⋯+2bi2.Equation (11) contains eight unknown parameters: bi0~bi7. With six constraint conditions, six of the eight unknowns can be eliminated. Let bi=[bi7,bi6] and b=[b1,…,bn]. The deviation of the state variables can be written as(13)ΔX′=X′d-X′f=ΔQbT,ΔϕTT.Then, the objective function is defined as(14)fb=normΔQbTKQ+normΔQbTKϕ.At this time, the path planning problem in SBMS has been transformed into an optimization problem of nonlinear functionf(b). We choose the QGA to solve it.


## 3.1. Solving the Objective Function

As we know, the whole system is composed of a floating base, a macroarm, and a dexterous robotic hand. During objective capturing process, the macroarm and dexterous hand are fixed together. The main topic of this text is to make the dexterous hand (or a special point of the macroarm) arrive a desired position by planning the joint path of the macroarm. As for how and with what attitude to capture an objective by the dexterous hand, it is not included in the topics. Also, attitude of the floating base has an important influence on communication quality and solar conversion efficiency. So, the focus of this study is to plan joint trajectory in order to enable the posture of the base and the position of the end-effector arrive at their desirable states simultaneously. The relevant variables include the quaternion of the base and the position vector of the end link, which are written asX=[QbT,PeT]T∈R6. X0, Xd, and Xf are, respectively, the initial state, the desired state, and the final state.Steps of path planning are as follows:(1)
Transformation of state variables (X→X′=QbT,ϕTT). End-effector positional vector with respect to the base-linked reference frame is only dependent on joint angles vector ϕ; that is, PeT0=f1(ϕ), while the homogenous transformation matrix from inertial reference frame to base-linked one is related to attitude of the base and the base’s positional vector rb; that is, AI0=f2(QbT,rb). Assume that rb=rb0 (a constant) at t=0. According to momentum conservation law, vector rb is related to history of joint angles; that is, rb=rb(ϕ). So state variable is transformed by PeT=AI0·P0eT=f3(QbT,ϕ).(2)
Parameterized joint trajectory using sinusoidal polynomial functions.(3)
Design of objective function based on the deviation between the final state and the desire state.The destination of path planning is as follows: the planned joint trajectoryϕ(t) can render true the condition whereby the final state variables can infinitely approach the desired variables; that is, X′d-X′f→0.


## 3.2. Parameterization of Joint Angles

Using the sinusoidal function to parameterize the joint angles can better constrain their scope. To ensure that the velocity and acceleration curves are smooth, we define(11)ϕit=aisin⁡bi7t7+⋯+bi1t+bi0+ci.There are six constraint conditions:ϕi0=ϕ0, ϕi0=0, ϕ¨i0=0, ϕi(tf)=ϕid, ϕitf=0, and ϕ¨itf=0. The range of ϕi is ϕi∈[ϕi∣ϕimin<ϕi<ϕimax].So,ai=(ϕimax-ϕimin)/2 and ci=(ϕimax+ϕimin)/2.Then, joint angle velocity and acceleration can be written as(12)ϕ˙it=aicos⁡bi7t7+⋯+bi1t+bi0·7bi7t6+⋯+bi1,ϕ¨it=-aisin⁡bi7t7+⋯+bi1t+bi0·7bi7t6+⋯+bi12+aicos⁡bi7t7+⋯+bi1t+bi0·42bi7t5+⋯+2bi2.Equation (11) contains eight unknown parameters: bi0~bi7. With six constraint conditions, six of the eight unknowns can be eliminated. Let bi=[bi7,bi6] and b=[b1,…,bn]. The deviation of the state variables can be written as(13)ΔX′=X′d-X′f=ΔQbT,ΔϕTT.Then, the objective function is defined as(14)fb=normΔQbTKQ+normΔQbTKϕ.At this time, the path planning problem in SBMS has been transformed into an optimization problem of nonlinear functionf(b). We choose the QGA to solve it.


## 4. Using QGA to Solve Optimization Problem

The quantum genetic algorithm [18] is a method that combines quantum computation and a genetic algorithm, which is a probabilistic evolutionary algorithm.


### 4.1. Theory of QGA

The genetic algorithm is a common method to solve complicated optimization problems. In 1998, Dr. Bagley proposed the concept of the “genetic algorithm” in his doctoral dissertation and developed a self-adaptation genetic algorithm [19]. The basic idea underlying this algorithm is to learn the jungle law in biological evolution and selection, as well as the crossover or mutation of chromosomes. It is robust and has a wide range of applicability. However, its iterations is much, its convergent rate is low, and it is easily caught in a local optimum.On the contrary, quantum computation involves solving an NP problem in classical computation using superposition, entanglement, and the interference of quantum-state information units. In 1994, Shor first proposed the quantum algorithm [20].The QGA is a genetic algorithm based on the expression of a quantum-state vector. The probability amplitude expression of the quantum bit is applied to a chromosome’s encoding process, because of which the chromosome can be expressed through the superposition of quantum states whose update process is conducted by means of a quantum rotate gate. Target optimization is thus completed.The quantum bit is a two-state system in a superposed state, such asφ=α0β1, where (α,β) is a set of amplitude constants that satisfies α2+β2=1. States 0 and 1, respectively, represent the spin-up and spin-down states. That is, a quantum bit contains information concerning States 0 and 1.The QGA is updated through the quantum rotate gate, which is expressed asUθi=cos⁡θi-sin⁡θisin⁡θicos⁡θi. The principle of update is αiβiupdate=Uθiαiβi, where αi,βiT and αi,βiupdateT represent probability amplitudes before and after the update, respectively, and θi represents the spin angle.Thus, the key differences between the quantum genetic algorithm and traditional genetic algorithm are that the former has more abundant population diversity and better parallel calculating abilities with larger search range and convergence rate. This is why its adaptation and efficiency is much higher.


### 4.2. Brief Introduction to QGA Performance

(1)
Compared to the genetic algorithm, QGA has several new features.
(2)
It uses the global searching method, which enlarges the search scope and increases search efficiency.
(3)
It effectively resists premature phenomena and has better convergence and precision.
(4)
With increase in the number of iterations, the global search capability decreases and local search ability increases, which can cause the system to converge to the global optimum.
(5)
The quantum system is a complex nonlinear system that can adapt to practical issues.


### 4.3. Path Planning Based on QGA

The path planning process of an SBMS based on the QGA is as follows:(1)
Set known parameters, such as mass, inertia, length, and the bound range of the joint angles. Input the initial state variable, the desired state variable, and the planning time.(2)
Parameterize the joint trajectory, and determine the type and number of parameters.(3)
Solve the final state variable. Compute the difference between the final state and the desired state.(4)
Define parameters mentioned in (2) as chromosomes, and initialize them randomly to obtain a population composed of n quantum bits.(5)
Measure the population and encode it.(6)
Design the objective function based on state difference.(7)
Solve the fitness of each individual and record the results.(8)
Judge whether the iterative process has end. The basis is the fitness constraint condition and the maximum number of iterations.(9)
Update individuals by quantum rotate gate, and perform the circuit operation along (5)~(8) until it jumps from the loop.The corresponding flowchart is shown in Figure2.Figure 2
Flowchart of QGA.


## 4.1. Theory of QGA

The genetic algorithm is a common method to solve complicated optimization problems. In 1998, Dr. Bagley proposed the concept of the “genetic algorithm” in his doctoral dissertation and developed a self-adaptation genetic algorithm [19]. The basic idea underlying this algorithm is to learn the jungle law in biological evolution and selection, as well as the crossover or mutation of chromosomes. It is robust and has a wide range of applicability. However, its iterations is much, its convergent rate is low, and it is easily caught in a local optimum.On the contrary, quantum computation involves solving an NP problem in classical computation using superposition, entanglement, and the interference of quantum-state information units. In 1994, Shor first proposed the quantum algorithm [20].The QGA is a genetic algorithm based on the expression of a quantum-state vector. The probability amplitude expression of the quantum bit is applied to a chromosome’s encoding process, because of which the chromosome can be expressed through the superposition of quantum states whose update process is conducted by means of a quantum rotate gate. Target optimization is thus completed.The quantum bit is a two-state system in a superposed state, such asφ=α0β1, where (α,β) is a set of amplitude constants that satisfies α2+β2=1. States 0 and 1, respectively, represent the spin-up and spin-down states. That is, a quantum bit contains information concerning States 0 and 1.The QGA is updated through the quantum rotate gate, which is expressed asUθi=cos⁡θi-sin⁡θisin⁡θicos⁡θi. The principle of update is αiβiupdate=Uθiαiβi, where αi,βiT and αi,βiupdateT represent probability amplitudes before and after the update, respectively, and θi represents the spin angle.Thus, the key differences between the quantum genetic algorithm and traditional genetic algorithm are that the former has more abundant population diversity and better parallel calculating abilities with larger search range and convergence rate. This is why its adaptation and efficiency is much higher.


## 4.2. Brief Introduction to QGA Performance

(1)
Compared to the genetic algorithm, QGA has several new features.
(2)
It uses the global searching method, which enlarges the search scope and increases search efficiency.
(3)
It effectively resists premature phenomena and has better convergence and precision.
(4)
With increase in the number of iterations, the global search capability decreases and local search ability increases, which can cause the system to converge to the global optimum.
(5)
The quantum system is a complex nonlinear system that can adapt to practical issues.


## 4.3. Path Planning Based on QGA

The path planning process of an SBMS based on the QGA is as follows:(1)
Set known parameters, such as mass, inertia, length, and the bound range of the joint angles. Input the initial state variable, the desired state variable, and the planning time.(2)
Parameterize the joint trajectory, and determine the type and number of parameters.(3)
Solve the final state variable. Compute the difference between the final state and the desired state.(4)
Define parameters mentioned in (2) as chromosomes, and initialize them randomly to obtain a population composed of n quantum bits.(5)
Measure the population and encode it.(6)
Design the objective function based on state difference.(7)
Solve the fitness of each individual and record the results.(8)
Judge whether the iterative process has end. The basis is the fitness constraint condition and the maximum number of iterations.(9)
Update individuals by quantum rotate gate, and perform the circuit operation along (5)~(8) until it jumps from the loop.The corresponding flowchart is shown in Figure2.Figure 2
Flowchart of QGA.


## 5. Simulation Test

In this section, we consider a 6-DOF SBMS as an example, the 3D model of which is shown in Figure3, for a simulation test to test the proposed path planning method. We also compared it with the traditional genetic algorithm.Figure 3
A space-based, 6-DOF manipulator system.The geometrical and inertial parameters of the system are shown in Figure3 and Table 1. The D-H model is shown in Figure 4: it depicts the deployable state, also called the zero state. The D-H parameters are shown in Table 2. The initial and desired poses of the base are represented by the quaternion as follows:(15)Qb0T=1,0,0,0,QbdT=0.9727,-0.1877,0.0782,0.112.Table 1
Geometrical and inertial parameters of a system.
Number
Mass/kg
Length/m
Inertia tensor/kg∗m2
I
x
x
I
y
y
I
z
z
I
x
y
I
y
z
I
x
z
0
100.2
—
—
10.12
10.05
9.88
0
0
0
b
0
1.3
1
10.1
a
1
0.554
1.012
0.099
0.102
0
0
0
b
1
0.554
2
10.3
a
2
0.554
1.012
0.099
0.102
0
0
0
b
2
0.554
3
9.5
a
3
0.554
1.012
0.099
0.102
0
0
0
b
3
0.554
4
9.8
a
4
0.554
1.012
0.099
0.102
0
0
0
b
4
0.554
5
9.9
a
5
0.489
1.01
0.110
0.103
0
0
0
b
5
0.489
6
7.5
a
6
0.412
0.808
0.1
0.099
0
0
0
b
6
0.412Table 2
D-H parameters of a space-based manipulator system.
Link number
θ
i/rad
α
i/rad
a
i/m
d
i/m
0
0
0
1.3
0
1
π
/
2
0
1.02
0.433
2
-
π
/
2
0
1.02
0.433
3
π
0
1.02
0.433
4
-
π
0
1.02
0.433
5
0
124/180∗π
0.81
0.548
6
0
0
0.808
0Figure 4
D-H frames of space-based systems.The initial and desired positions of the end-effector are(16)Pe0T=5.5,1.05,0,PedT=4.936,2.7622,-0.1242.According to the two preconditions above, we transformed them into another form that incorporated joint configuration. Based on the requests (positional error of end-effectorkpe≤0.05 m and attitude error of the base krb≤5°) of positional precision of the floating base and the attitude precision of the end-effector, we then defined the positional coefficient k1=0.4, kpe=0.02, and attitude coefficient k2=0.0175. According to formula (12) and the boundary values of it, the value ranges for each parameter were set as(17)bi7∈-3×10-3,3×10-3,bi6∈-3×10-3,3×10-3.The optimization of the objective functions was executed by the QGA and the genetic algorithm. The results, including the objective values and optimal parameters, are given below.Results of the Genetic Algorithm. The optimized parameters were bGA=[0.448,1.973,2.309,-1.274,2.327,1.887,-0.215,0.855,0.786,0.518,-1.888,0.714]×10-4. The corresponding objective value was JGA=0.385.Figure5 shows that the simulation process converged after 152 iterations.Figure 5
Fitness curve of global optimal points for GA.Results of QGA. The optimized parameters were bQGA=[-1.9319,-1.7996,-2.0789,1.6905,0.46052,-2.1949,1.3569,-0.42342,0.98057,-0.28985,1.877,-0.4173]×10-4. The corresponding objective value was JQGA=-2.2×10-4.Figure6 shows that the simulation converged after 80 iterations. Compared to the GA, the QGA converged much more rapidly with higher precision. Moreover, step width of ladder-shaped curve shown in Figure 5 is larger than that shown in Figure 6. This implies that the genetic algorithm can easily fall into a local optimum. Hence, the QGA is superior to the genetic algorithm.Figure 6
Fitness curve of global optimal points of QGA.We then solved the optimized joint trajectory according to the parameters obtained from the QGA, as shown in Figure7. Finally, we used the joint trajectories in Figure 7 as inputs to the motion of the control joint and observed whether the base and the end-effector arrived at the desired state simultaneously. Figure 8 shows the RPY angle curves of the floating base. Positional curves of the floating base and the end-effector are, respectively, described in Figures 9 and 10. Figure 11 shows the distance between the actual and desired positions of the end-effector. The deviation as 2.78×10-2, which was acceptable. From Figure 7, we see that the curves are smooth, and this is satisfactory for the control of the joints.Figure 7
Optimal joint curves.Figure 8
Pose error curves of the floating base.Figure 9
Positional curves of the floating base.Figure 10
Positional curves of the end-effector in inertial reference frame.Figure 11
Position error curve of end feature point.


## 6. Conclusion

In this study, we built a kinematical model for a SBMS and analyzed its nonholonomic properties. Moreover, we also parameterized the joint trajectory and the design objective function and hence transformed the path planning problem into a nonlinear objective optimization problem. We used the genetic algorithm and the QGA to solve above problem. The results showed that the proposed method can obtain a superior solution compared to prevalent systems and converges much more rapidly.We also obtained joint trajectories based on the optimized parameters and drew pose curves of the base and the position curve of the end-effector. The results indicated that the proposed method can arrive at the desired state.Our method can efficiently reduce the energy consumption and time in a coordinated control process between a floating base and a manipulator.



---

*Source: 3207950-2017-03-09.xml*