A Status Graph Based Control Allocation Algorithm of Digital Micro-Thruster Array for Micro/Nano-Satellites Orbit Control Application

ZHANG Dandan，ZHANG Yunyi，DONG Ke，LI Haiwang，WANG Shaoping

1. School of Energy and Power Engineering，Beihang University，Beijing 100191，P. R. China；

2. School of Automation Science and Electrical Engineering，Beihang University，Beijing 100191，P. R. China

（Received 11 Februry，2018；revised 9 April，2018；accepted 9 May，2018）

Abstract: Digital micro-thruster arrays can be used for special missions of micro/nano-satellites with the requirements of high precision and small impulse. This paper presents a novel control allocation algorithm for the digital micro -thruster array，namely status graph based control allocation（SGBCA）algorithm，which aims at finding the optimal micro thrusters combination scheme to realize the sequential control synthesis for micro/nano-satellite during real-time orbit control tasks. A mathematical model is set up for the control allocation of this multivariate over-actuated system.Through dividing thrusters into disjoint segments by offline calculation and combining segments dynamically online to provide a sequence of the required impulse for the micro/nano-satellite，the time complexity of the control allocation algorithm decreases significantly. All levels of impulse can be generated by the digital micro thruster arrays and the service life of the arrays can be extended using the segment converting strategy proposed in this paper. The simulation indicates that the algorithm can satisfy the requirements of real-time orbit control for micro/nano-satellites.

Key words: control allocation; digital micro-thruster array; micro/nano-satellite; orbit control

0 Introduction

The maturation of micro-propulsion technology has led to their widespread adoption for various micro/nano - satellites［1-4］. Based on the idea of digital micro - propulsion concept proposed two decades ago［5］，compact micro thruster arrays with numerous individual micro thrusters were designed and fabricated［6］，which are capable of delivering the impulse necessary for micro/nano-satellites attitude adjustment， gravitation compensation， and position maintenance. The thrust levels can be controlled by firing a different number of micro thrusters on the thruster array.

Solid propellant micro thruster utilizes the thermally - driven decomposition of a chemical blowing agent to provide impulse，which can serve as a type of micro - propulsion system for micro/nano - satellites［7］. However，as a kind of one-shot micro-thruster，multiple thrusters should be formed as an array to implement the concept of digital micro-propulsion by overcoming the drawback of its single-use characteristic［8-16］.

Structures and fabrication methods of solid propellant thrusters array are demonstrated in Refs.［17-18］，calculation models and micro -propulsion tests are conducted in Refs.［19-20］，and attitude control of low earth orbiting CubeSat using micro pulsed plasma thrusters as well as the design of attitude determination and control system for small satellites are described in Refs.［21 - 22］. However，the control allocation strategy for MEMS - based solid propellant micro thruster arrays during the orbit control task has not been fully explored. To generate the targeted level of thrust required during an orbit control mission， the combination scheme of the micro -thrusters for propulsion should be determined.Therefore，it is worthwhile to develop a feasible control allocation algorithm for this over - actuated system.

There are several challenges to this new problem. First，all levels of impulse should be able to be generated. During orbit maneuver or gravity compensation task，the impulse required in the next moment cannot be known beforehand. An efficient strategy for control allocation is required for this stochastic process. Second，the calculation scale of the algorithm should be small enough. Unlike traditional propulsion systems（cold gas propulsion system）with few control variables， some of the digital thruster arrays have millions of thrusters. For example，the thruster array with 512×512 thrusters fabricated by the Honeywell Center of Princeton University indicates 512×512 control variables［11］. The calculation scale of this kind of array is too large for the traditional methods，like pseudo inverse，linear programming， optimal look-up table， to solve［23-25］.Thus new approaches are needed. The online calculation should be able to be reduced to reach the realtime control requirement. Pretreatment work should be performed offline to reduce the calculation time for online control allocation. Furthermore，the combination scheme of the ignition of thrusters should be determined as soon as possible according to the control commands. Finally，the service life of the micro thruster array should be guaranteed for the fulfillment of the online orbit control task. Since micro thrusters are disposable，the mutual influence between different thruster segments should be eliminated.

In this paper，we try to fill the blank of the control allocation algorithm of solid propellant thruster array for micro/nano - satellite orbit control application. A status graph based control allocation（SGBCA）algorithm is proposed to determine the strategy of generating different levels of impulse. For the sake of real-time control，offline calculation is used to reduce the online computational burden. To extend the service life of the micro thruster array and deal with extreme conditions，segment converting strategy is proposed.

1 Problem Formulation

1. 1 Ignition model of a micro thruster

The structure parameters of the micro - thruster，the stored chemistry energy and the storage rank pressurization can influence the micro-propulsion properties of the thruster array. Modeling tools have been developed to predict the micro thruster performances［22］. For simplification，an equivalent rectangular pulse model can be used to represent the approximate thrust output generated by an individual thrust unit（Fig.1）. Suppose that the impulse-bit of each micro thruster is Iu. Faveis the equivalent average thrust provided by an individual micro thruster；Tavethe time for the duration of combustion. Their relationship is shown as

Fig. 1 The equivalent force and working time for a single micro thruster

1. 2 Principles of algorithm design

When we get the optimal solution of the total number of thrusters that we need for generating an impulse to realize the satellite trajectory tracking control，it is important to decide the combination scheme of specific micro thrusters in the arrays that should be fired. Many existing papers have already aimed at the calculation of the required impulse for optimal satellite trajectory control［25］. However，little research focuses on the control allocation for the micro thruster arrays.

This paper focuses on how to segment the thrusters’array into disjoint segments that can generate the corresponding impulses. Suppose that the number of thrusters to be ignited on each thrusters’ array V ( k )=[Vx(k)，Vy( k )，Vz(k) ] is derived.For thrusters’array perpendicular to the x-axis，the output of the proposed algorithm will be the position of the selected thrusters in a combination scheme to fire Vx(k) number of thrusters without generating extra moment. An optimal approach should be found to fire the thrusters symmetrically while maximizing the flexibility of the unused thrusters within the array regarding their accessible thrust states.

The control strategy can be applied to Vy( k )，Vz( k ) and constitute V ( k ). Assume r is the time horizon for a thruster array to generate thrust in an orbit control task，k ∈{ 1，2，...，r }. n represents the row and m the column；n × m the scale of a thruster array；x*and y*are the serial number of the row and the column to represent a thruster in a thruster array， respectively， and x*∈{1，2，…，n}，y*∈{1，2，…，m}.

After the one time decision matrix is calculated， the corresponding micro thrusters should be ignited.

At time t，sx*，y*，t= 1 represents that the thruster located at x*row and y*column is chosen to be ignited，otherwise，sx*，y*，t= 0. The one time decision matrix should satisfy the following constraint

Generally，for a pragmatic control allocation algorithm，the following three principles should be satisfied.

Principle 1Thrusters’arrays should provide required thrust without generating moment. During an orbit control task，propulsion system should deliver impulses to the micro/nano satellite to provide velocity increment but satellite’s attitude should remain. If the thruster arrays generate thrust and synthesis moment at the same time，the attitude of the satellite may change，which is not expected for the orbit control task.

Principle 2Ignition should maintain the possibility of delivering all kinds of thrusters for future use. Each micro thruster can only be used once. Random choice of thrusters to be ignited may severely decrease the possibility of future ignition. An efficient way should be found to select proper combination scheme of micro thrusters. This is also important for the thruster array to fulfill the requirement of the control task in every time step.

Principle 3Computation time for choosing suitable thrusters to be ignited should be short enough. Time for deciding which thrusters to be ignited should be short enough，especially for real -time control to make the micro thruster array practical for the orbit control task. The offline calculation is necessary to find out the reliable combination scheme to generate specific thrust without extra moment.

1. 3 Mathematical model for partition

Several assumptions for the mathematical model are provided before constructing the mathematical model .

Assumption 1Details of ignition process can be ignored.

Assumption 2Each micro-thruster in the thruster array provides the same impulse when being fired .

Assumption 3Thrusters’mutual influence can be ignored. That is to say，a micro thruster will not be ignited due to heat transfer provided by adjacent pixels.

Assumption 4Projections of satellite’s centroid on each surface coincides with the center of thruster arrays.

Theorem 1Suppose at time t，Vx(t) (Vx(t) ≥2，Vx(t) ∈N+) thrusters are required to be fired. There exist several combinations of integers ax(t)，bx(t) that satisfy

According to Theorem 1，for the positive integer Vx(t)，there are several combinations of ax(t)and bx(t)（related to line segments and triangle segments，see Definition 1）.

Thus， dividing thruster array into line segments and triangle segments strictly based on Principle 1 and then combining them to generate target thrust is an effective method.

Definition 1Line segment & Triangle segment

Line segment Lj{( xj1，yj1)，( xj2，yj2) } represents two thrusters whose midpoint is coincided with the origin point of the thruster array. As for Lj{( xj1，yj1)，( xj2，yj2) }

Triangle segment Ti{( xi1，yi1)，( xi2，yi2)，( xi3，yi3) } represents three thrusters whose barycenter is coincided with the origin point of the thruster array.As for Ti{( xi1，yi1)，( xi2，yi2)，( xi3，yi3) }

Triangle segments sets

Line segments set

They can be combined to synthesize any integer units of impulses. Coordination system is established before formulation. The origin point of the coordinate system is set at the center of the array，and the axes are parallel to the edges of the array. Suppose thrusters in a segment has coordinates( xi，yj)( i = 1，2，…，n ；j = 1，2，…，m )，thus igniting these thrusters will not generate moments as long as coordinates satisfyxi= 0 andyj= 0.

2 Status Graph Based Control Allocation Algorithm

2. 1 Basic ideas of divide and conquer method

SGBCA algorithm is developed based on the basic idea of divide and conquer method，which aims at dividing a thruster array into several disjoint segments.

The reason why we emphasize that segments should be disjoint is to avoid segments being destroyed. According to Principle 2，thrusters cannot be used twice. Thus， suppose two triangle segments Γ1，Γ2contain the same thruster P. After ignition of Γ1，P cannot be reused and Γ2is broken as a result. On the other hand，if Γ1，Γ2are disjoint，ignition of Γ1does not affect Γ2. Therefore，finding disjoint triangle segments is important. Obviously，it is easy to find line segments，but not so easy to find the triangle segments. Thus，triangle segments should be found first.

Definition 2Triangle segment couple

It is not easy to convert line segments into triangle segments. However，two central symmetric triangles can be easily converted to disjoint line segments. Since triangle couple is of great flexibility，we should find as many disjoint triangle segment couples as possible during partitioning process.

2. 2 Status graph based control allocation algorithm

Definition 3Status graph

Status graph G (U，V ) is a graph whose node set U is made up of all possible triangle segment couples and edge set V satisfies the following rule：i，j ∈U are linked if corresponding triangle segment couples i and j have at least one shared thrusters.

Definition 4Centrality of a triangle segment couple

The centrality of a triangle segment couple Ciis defined as the degree deg(i) of the corresponding node in the status graph，Cen ( i )= deg( i ).

If a triangle segment couple in the thruster array is ignited，triangle segment couples which have common thrusters with this couple will be destroyed and abandoned. In the status graph，it means deleting the ignited triangle segment couple’s corresponding node and its neighbors. Selecting a node with the smallest centrality means to delete the fewest nodes on the status graph，which results in maintaining more triangle segment couples before next ignition. Thus，the key of this algorithm is to find triangle segment couples with the least centrality and to delete the corresponding nodes of this couple and its neighbors. Table 1 presents a brief description of SGBCA algorithm.

Table 1 Status graph based control allocation algorithm

Fig. 2（a） demonstrates the status graph of a 5 × 5 thruster array. In a 5 × 5 thruster array，there are totally 43 triangle segment couples and each of them is represented by a node（from D0 to D42）in the status graph. Triangle segment couple D19 has the least centrality in the initial status.Cen (19 )= 23. D19’s neighbors are marked with red color in Fig. 2（a）. The operation is to delete D19 and D19’s neighbors from nodes set U and to delete the edges which link D19’s neighbors and the remaining nodes.

Fig. 2（b） shows the remaining nodes of the graph after once deletion. Calculation shows that D29 is with the least centrality. Cen ( 29 )= 11.D29’s neighbors are marked with red color in Fig.2（b）. The second deletion is to delete D29 and D29’s neighbors from nodes set U and to delete the edges which link D29’s neighbors and the remaining nodes. The algorithm keeps repeating to find and delete nodes and edges until U = ∅.

Fig.2 Process of the operation of SGBCA algorithm

Above all，three parts are included in the SGBCA algorithm. The first part is to find all possible triangle segment couples，whose time complexity is O ( n2m2). The second part is to construct a status graph，whose time complexity is O ( n4m4). The final part is to search the triangle segment couples with minimal centrality and renew the status graph，whose time complexity is O ( n6m6). Overall，the complexity of this algorithm is O ( n6m6). Comparing with traditional algorithms of exponential complexity like enumeration and dynamic programming，our algorithm can significantly reduce the computation time.

2. 3 Implementation of the online calculation process

Segment converting strategy is designed for the online calculation to maintain a balance between line segments set and triangle segment set as well as converting triangle segment couples to line segments dynamically，as shown in Fig.3.

Fig.3 Transform between line segments and triangle segments

After offline calculation，i.e. segment distribution algorithm partitioning the thrusters’array into disjoint elements，the thrusters’array is partitioned into several disjoint segments and the coordinates of each segment are stored in a queue in the satellite’s memory for future use. There are three operations for a queue，including insertion of new segments，popping segments from the head and converting triangle segment couples to line segments or triangle segments.

Insertion means to push segments to the back of the queue，as Fig. 4（a）demonstrates. Each element in the queue contains coordinates of thrusters and the serial number of the element. By iterative inserting elements to the back of the queue，segments can be stored in the satellite’s memory. After deciding the number of line segments and triangle segments to be ignited according to Theorem 1，we should pop segments from the head of line segment list and triangle couple list，as Fig.4（b）does. Since each thruster can be ignited only once，segments should be deleted from the list after ignition.

Fig.4 Storing and operating segments of a 5 × 5 thrusters’array during ignition processes

It is possible that line segments are used up while there remain some triangle couples and vice versa. When line segments are not sufficient，we can pop triangle couples and convert them into line segments.

For delivering odd units of impulses，we can partition triangle couple segments into two triangle segments，ignite one part and store the other part for further usage. With these four online operations，we can easily choose segments to ignite when specific impulses are needed to provide. Also，since triangle couples can be converted into line segments，it is better to ignite line segments rather than triangle couples to generate impulses. As shown in Fig. 5，using segment converting strategy can extend the service life of the micro thruster array significantly.

3 Simulation

In this section，we will demonstrate SGBCA algorithm for partitioning a 7 × 7 thrusters’array as well as choosing segments in an orbit control mission which includes several ignitions. Furthermore，online simulation is demonstrated in this section.

Fig.5 Transform between line segments and triangle segments

3. 1 Simulation for SGBCA algorithm

Fig.6 demonstrates each step of SGBCA algorithm in partitioning thrusters’array. As shown in the Fig.6，nearly all thrusters in the array except for the central thruster have been allotted to triangle segment couples. Besides，there are no apparent laws for the algorithm to choose thrusters to form segment couples. SGBCA algorithm is suitable for generating a significant number of triangle segment couples.

3. 2 Simulation for online application

In this part，the ignition process of a 9 × 9 digital thrusters’array in an orbit control task is simulated. During the mission，a sequence of impulses is required to be delivered at specific time and extra moments should not be generated.

Fig.6 Each step for SGBCA algorithm to partition a 7 × 7 thrusters’array into disjoint triangle couples

According to Ref.［18］，we suppose that a thruster delivers average thrusts in 350 ms，thus creating total impulses 0.005 25 N. s during ignition.Table 2 shows the impulses needed to be delivered in the orbit control task and the number of thrusters that needed to be fired in each time step. Fifty-nine thrusters are used in the task，and the number of the remaining thrusters are 22. A solution of { -Sn×m，t}can be illustrated in Fig.7 intuitively.

Table 2 Impulses needed to be delivered in the orbit control task and variable in each time step

Fig.7 Status of thrusters’array at specific time

4 Conclusions

This paper established the SGBCA algorithm to solve the problem of control allocation for microthruster array in delivering impulses without generating moments. The algorithms realize the control allocation by dividing thrusters’array into line segments and triangle segment couples，and choose the suitable combination for orbit control algorithm. Operations such as insertion，deletion and conversion of segments in the segments’lists are helpful for making full use of segments in the list.

Compared with traditional 0-1 programming algorithms，the SGBCA algorithm is of lower time complexity and moderate storage space. The simulation verified that the proposed algorithm is suitable for the online control allocation for micro-thruster array to fulfill the orbit adjustment task.

Practical issues such as the imbalance of impulses generated due to the deviations of the performance of single micro thruster and the potential failure of ignition process during control should be considered. Accumulative errors should be avoided，while compensation mechanism should be explored in the future.