Research Article | Open Access
Xiwei Wu, Bing Xiao, Cihang Wu, Yiming Guo, "Centroidal Voronoi Tessellation and Model Predictive Control–Based Macro-Micro Trajectory Optimization of Microsatellite Swarm", Space: Science & Technology, vol. 2022, Article ID 9802195, 10 pages, 2022. https://doi.org/10.34133/2022/9802195
Centroidal Voronoi Tessellation and Model Predictive Control–Based Macro-Micro Trajectory Optimization of Microsatellite Swarm
Probabilistic swarm guidance enables autonomous microsatellites to generate their individual trajectories independently so that the entire swarm converges to the desired distribution shape. However, it is essential to avoid crowding for reducing the possibility of collisions between microsatellites. To determine the collision-free guidance trajectory of each microsatellite from the current position to the target space, a collision avoidance algorithm is necessary. A synthesis method is proposed that generate the collision avoidance trajectories. The idea is that the trajectory planning is divided into macro-planning and micro-planning; macro-planning guides where the microsatellites move step by step from the initial cube to the target cube by probabilistic swarm guidance with Centroidal Voronoi tessellation, while the micro-planning is to generate the optimal path for each step and finally reach the specified position in the target cube by model predictive control. Simulation results are presented for the collision-free guidance trajectory of microsatellites to verify the benefits of this planning scheme.
As an emerging multi-satellite cooperative flight mode, microsatellite swarm has become an important future research issue for distributed space systems due to their advantages of low cost, rapid response, and collaborative decision-making. Recently, reference  develops hundreds or thousands of small femtosatellites and establishes effective swarm GNC strategies for potential synthetic aperture applications. The problem of shaping a large swarm (104–105) of particles into a large reflective dish was addressed [2–3], with only a few (40) actuators in the boundary of the workspace. Due to their small size, the microsatellites have limited sensing, actuation, and computation capabilities, which require the guidance and control algorithms of the swarm to be both fuel and computationally efficient.
To address the coordination of swarms for autonomous agents, a probabilistic guidance approach was investigated [4–6], which contain sub-swarms with different mission objectives. The probabilistic guidance approach is based on designing a Markov chain such that its steady-state distribution corresponds to the desired swarm density. On the basis of the above method, a homogeneous Markov chain-based approach was presented for the probabilistic density control of swarm. The proposed approach specifies the time evolution of the probabilistic density distribution by using a Markov chain, which guides the swarm to a desired steady-state distribution, while satisfying the prescribed ergodicity, motion, and safety constraints [7–11]. Different from the above method based on homogeneous Markov chain is that a novel and generic distributed swarm guidance algorithm using inhomogeneous Markov chain that guarantees superior performance over existing homogeneous Markov chain based algorithms, when the feedback of the current swarm distribution is available [12–16]. In contrast with previous homogeneous or inhomogeneous Markov chain–based approaches, optimal transport based approach was presented which guarantees faster convergence, minimizes a given cost function, and reduces the number of transitions for achieving the desired formation [2, 3, 17]. Moreover, the optimal transport based approach was verified by the Robotarium platform , and Jet Propulsion Laboratory of NASA has developed a guidance algorithm for a swarm of assets deployed from the back shell of the Mars spacecraft for distributed science . All these cases indirectly show that the probabilistic guidance method can be applied to the practical swarm satellite mission.
The solution of the probabilistic guidance algorithm establishes the target bin for each agent. Collision avoidance algorithms are necessary for generating collision-free guidance trajectories from the present location to the target bin. The previous homogeneous or inhomogeneous Markov chain–based approaches adopt safety constraints to avoid collision, and the optimal transport–based approach adopts a distributed collision avoidance algorithm for multi agent path planning by modifying the coverage control algorithm. However, these collision avoidance algorithms are only macro-planning, thinking that the agent is a particle, without considering their micro-dynamics model. Therefore, it is difficult to guarantee that collision avoidance between microsatellites in physical space and that the trajectories may not be optimal and will waste fuel.
The main contribution of this paper is the integration of probabilistic swarm guidance with a macro-micro trajectory-planning algorithm. Model predictive control (MPC) has been a major research area in aerospace for over a decade . To save fuel consumption and improve computational efficiency, MPC has been used in applications similar to swarm guidance, such as spacecraft landing , spacecraft rendezvous , and reconfiguration of a satellite constellation . Additionally, some collision avoidance algorithms by using MPC for spacecraft swarm are proposed [23, 24]. The guidance trajectories obtained from PDGS can be implemented using sequential convex programming and model predictive control , and the experiment verified the feasibility of MPC in path planning for swarm.
In this paper, we propose a synthesis method that Centroidal Voronoi tessellation (CVT) [26–28] and model predictive control based macro-micro trajectory optimization of microsatellite swarm, and it is different from . The main contributions of this work are listed as follows: (1)Comparing with the existing swarm distribution guidance [4–17], the physical space over which the swarm agents are distributed from 2D to 3D, it is more suitable for the practical application of swarm(2)A synthesis method is proposed that generate the collision avoidance trajectories. The idea is that the trajectory planning is divided into macro-planning and micro-planning, macro-planning guides where the microsatellites move step by step from the initial cube to the target cube by probabilistic swarm guidance with CVT, while the micro-planning is to generate the optimal path for each step and finally reach the specified position in the target cube by MPC(3)Considering perturbation in the micro-modeling of microsatellite swarm, it is more corresponded to engineering practice
The remainder of this paper is organized as follows. The problem formulation is introduced in Section 2. The macro-planning of microsatellite swarm is presented in Section 3, and the micro-planning of microsatellites is presented in Section 4. The effectiveness of the proposed scheme is validated by using a numerical example in Section 5. Some conclusions and future work are given in Section 6.
2. Problem Formulation
2.1. Probabilistic Swarm Guidance
According to the probabilistic swarm guidance method described in literature , the agents can move in 2D plane. In this paper, we will investigate the transfer of swarm microsatellites in 3D space. The physical space over which the swarm microsatellites are distributed is denoted as ; it is assumed that the space is divided into a union of disjoint subspaces , that is, . For , . The subspaces are referred to as cubes.
Let be the position of a microsatellite at time index . Let be a probability vector so that is the probability of the event that the microsatellite will be in cube at time ,
Consider a swarm consisting of independently acting microsatellites so that (1) holds for independent events: where denotes the position of the -th microsatellite at time . Here, is called the swarm distribution.
The distribution guidance problem is defined as follows: Given any initial probability distribution, the swarm must be guided to a specified steady-state probability distribution :
Subject to motion constraints, specified by the adjacency matrix as
The idea behind probabilistic swarm guidance is to control the propagation of probability vectors rather than the individual micorsatellite positions .
The probability density vector over evolves as
2.2. Safety Analysis of Collision Avoidance
In the method of probabilistic swarm guidance, it is essential to avoid crowding for reducing the possibility of collisions between microsatellites. To determine the collision-free guidance trajectory of each microsatellite from the current position to the target space, a collision avoidance algorithm is needed. However, with high-level coordination that uses the macroscopic models, collision-free trajectories are very hard to generate. In this paper, a synthesis method was presented that the collision avoidance trajectories are generated. The idea is that the trajectory planning is divided into macro-planning and micro-planning, as shown in Figure 1, where macro-planning guides the microsatellites move step by step from the initial cube to the target cube, while the micro-planning is to generate the optimal path for each step and finally reach the specified position in the target cube.
Collision avoidance needs to be considered during trajectory generation. The minimum collision avoidance distance between all microsatellites is required, represented by . Collision avoidance analysis is based on finding the lower bound of the minimum distance between all microsatellites at any time. Suppose the distance between two microsatellites is , so the difference between it and the minimum safe distance is , then
therefore, , define
The positive invariance condition can be expressed as
When the distance between any microsatellites is less than the lower bound of , the time derivative of the distance function can maintain or increase the distance, so collision avoidance can be guaranteed.
3. Macro-Planning of Microsatellite Swarm
3.1. Voronoi Tessellation
For convex set , is defined as the set of distinct points in set . The Voronoi cell corresponding to the generation point is defined as follows: where denotes the Euclidean distance in . From the above definition, it can be seen that all points in whose Euclidean distance to the generation point is less than to the generation point and the points are included in the Voronoi cells . For , . Except for the boundary, all Voronoi cells are disjoint, and is true, that is, the set is a partition of the set .
3.2. Centroidal Voronoi Tessellation
When the function of the target space is set, its generation point is the centroid of each Voronoi cell (the density function is used to calculate the centroid); it is the Centroidal Voronoi tessellation.
Assuming that the density function of space is defined as , then the centroid of each Voronoi cell is positioned as
When the position of the generation point is the centroid, namely: is Centroidal Voronoi tessellation.
When the cost function is less than a certain threshold, it can be judged that the Centroidal Voronoi tessellation tends to be stable. Given the density function, the cost function is
The cost function estimates the error between the generation point and the centroid of the Voronoi tessellation by the density function of the space.
3.3. CVT-Based Trajectory Planning for Microsatellite Swarm
The target position of each microsatellite is determined by the centroid generated through CVT algorithm, and all microsatellites move to the corresponding centroid until the algorithm converges. In the present work, a code library of CVT based on the probabilistic Lloyd’s method is incorporated to produce the CVT generators. According to the location of the centroid, the final distribution of the microsatellite swarm in the space is obtained. The main algorithm step is as follows:
Determine 3D space , density function , and define integer microsatellites. (1)Select the points randomly as generated points, namely, the initial position of the microsatellites(2)The probabilistic guidance algorithm [4, 5] was executed to determine the cube where each microsatellite was located(3)Construct the corresponding Voronoi cells for each microsatellite(4)Calculate the centroid positions of Voronoi cells(5)These centroids form a new set of points; move the generate point to the centroid(6)If the new generation point satisfies convergence, the algorithm terminates. Otherwise return to Step 3
4. Micro-Planning of Microsatellites
4.1. The Orbital Dynamics Model Considering Perturbation
The reference frame is the local-vertical-local-horizontal (LVLH) denoted by . The origin of LVLH coordinate system is the centroid of the central microsatellite, the -axis points to the centroid of the central microsatellite from the center of the earth, the -axis is perpendicular to the orbital plane and points to the direction of the orbital angular momentum, and the -axis is perpendicular to the and axes and is determined by the right hand rule.
The relative dynamics equation of the microsatellite considering the perturbation is where is the position vector of the microsatellite in the LVLH coordinate system of the reference satellite, is the control torque imposed on microsatellite, is the mean orbital motion of the microsatellite, is geocentric distance, and is the Earth’s gravitational constant.
The orbital elements are described as , is semi-major axis, is eccentricity, is orbit inclination, is the right ascension of ascending node, is argument of perigee, and is true anomaly. is the perturbing acceleration caused by : where the coefficient , is the radius of the Earth, is the second zonal harmonic coefficient of the Earth, and is argument of latitude.
The relative dynamics model of microsatellite swarm is expressed in state space: where is the number of microsatellites, and the state of the -th microsatellite at time is , , and .
To satisfy the conditions of solving convex optimization problem, the dynamics model was discretized and obtained from the continuous dynamics model by zero-order equal interval sampling:
Then, the dynamics model of discretization is where
4.2. Convexification of Collision Avoidance Constraints
To avoid two members of microsatellite swarm moving to the same location at the same time, collision trajectory between members should be considered in the process of swarm reconfiguration. Then, the anti-collision avoidance constraint can be expressed as where , , , , and is the maximum communication distance.
Equation (21) is linearized at the discrete points corresponding to the two reference trajectories of microsatellite and , and the affine function about the state of the two adjacent microsatellites can be obtained, so as to realize the convexity of collision avoidance constraints between microsatellites: where is the nominal trajectory of each trajectory point. The accurate collision avoidance constraint requires only that the distance between two adjacent microsatellites is no less than the safe distance. However, after convexization, as shown in Figure 2, the constraint becomes that the two adjacent microsatellites cannot simultaneously be located in the belt region with width , which is perpendicular to the connection line of the discrete reference points of the two adjacent microsatellites, and the position of the space is not fixed, so it can move along the connection direction of the reference points.
4.3. MPC-Based Trajectory Optimization for Microsatellites
To implement real-time trajectory planning, model predictive control is introduced; the MPC implementation uses a receding horizon to update the optimal trajectories based on the current state information. Assuming that the prediction horizon and the control horizon are both , according to the principle of model predictive control, it can be obtained where is initial state, and
The cost function is defined as where , and are the weight matrix, is the predicted state, is the predicted terminal state, and are usually the diagonal matrix, and is the terminal cost weight matrix obtained by solving the algebraic Riccarti equation.
In the whole reconfiguration stage, it is assumed that microsatellite members of swarm have limited communication capacity, so the members can only communicate with their neighboring microsatellites, so each member microsatellite needs to consider anti-collision constraints. So the trajectory planning problem of microsatellite swarm considering collision constraints can be described as
In this section, numerical simulation is carried out to verify the proposed macro-micro trajectory planning method of microsatellite swarm. In this paper, a virtual central microsatellite is given, and a large-scale (300) microsatellite swarm is designed with an omnidirectional flight configuration. The initial orbital element of the central satellite is (7106.14 km, 0.05°, 98.3°, 270°, 0°, 0°). The earth’s gravitational constant is ; the radius of the earth is 6378.140 km. In LVLH coordinates, the position vectors of 300 microsatellites relative to the virtual center microsatellite are randomly generated, the azimuth angle is randomly selected, and the initial distance is randomly selected within 100 km.
In the micro-planning, we do not have a reference trajectory only a reference final position. Hence, a terminal constraint is added to the MPC. The state error cost is kept low because, we do not have a state trajectory to follow only the final destination. Meanwhile, the control cost is kept high to emphasize the optimization of fuel consumption to be minimum to the reference which is taken to be zero. The sampling time is 60s, the prediction horizon is 50. The is , is , and is .
The overall configuration transformation of microsatellite swarm is shown in Figures 3 and 4. The initial configuration generated is shown in Figures 3(a) and 3(d); the desired configuration design is of type “0”. Here, the numbers of microsatellites in each sub-swarm have been specifically chosen so that the final configuration is uniform over the shape of the “0”. With the increase of iteration times, microsatellite swarm gradually forms the desired configuration under the action of macro and micro trajectory planning. It can be seen that the desired configuration can be formed quickly. After the 10 iterations, the desired configuration is basically formed and maintained in a stable state; as shown in Figure 4, there is no significant change in distance scale. In the meanwhile, the total variation in Figure 5 indicates that convergence is achieved at roughly steps.
In this paper, we use the CVT algorithm to divide regions, and so as to determine the position of the microsatellites to be transferred at the next moment. As shown in Figure 6, we selected one of the cubes in the transfer process and perform CVT on it to determine the transfer position of the microsatellite. After 50 iterations, a stable configuration is obtained, and the position where the microsatellite moves at the next moment is determined.
Due to the large scale of the microsatellite swarm, the process of achieving the final configuration requires many transitions. To verify the proposed trajectory optimization based on model predictive control, one of the microsatellites is selected from the initial point to the next desired target point at a certain moment, as shown in Figure 7. The individual microsatellites can reach the desired point well. After the desired point is reached, the next iteration will be carried out, and due to the influence of orbital dynamics, the microsatellite may not remain the target point without control constraints. Therefore, the trajectory curve after s of the simulation in Figure 7 is not a reference. To make the mission of microsatellite swarm more practical, we used MPC in micro-planning to improve the performance of microsatellite swarm in terms of fuel consumption and resource utilization.
This paper developed a synthesis trajectory planning method for microsatellite swarm, which include macro-planning and micro-planning. The former used Centroidal Voronoi tessellation, while the latter adopted MPC to generate the optimal trajectories. The proposed method can not only realize collision avoidance of microsatellite swarm maneuvering at the macro-level, but also provide optimal trajectories for each microsatellite of swarm individuals at the micro-level. Macro-planning provides guidance for micro-planning, and micro-planning implements the commands of macro-planning; the proposed method accords well with engineering practice. Future work will focus on the extending the presented scheme to achieve a faster, more fuel-efficient trajectory optimization method. Moreover, the validation experiments will be carried out.
The simulation date and the program files in this paper cannot be shared with others as they are our basis for next research.
Conflicts of Interest
The authors declare that there is no conflict of interest regarding the publication of this article.
Xiwei Wu contributed to the writing of the manuscript and research design. Bing Xiao participated in the research design and review. Cihang Wu conducted simulation experiment. Yiming Guo and Cihang Wu performed statistical analysis.
This work was supported by the National Natural Science Foundation of China (No. 61873207), the National Science and Technology Major Project, China (No. J2019-I-0021-0020), the Natural Science Basic Research Program of Shaanxi, China (No. 2019JQ-344), the Science and Technology Program of Xi’an City, China (No. 2019218314GXRC019CG020-GXYD19.3), and the Innovation Foundation for Doctor Dissertation of Northwestern Polytechnical University, China (No. CX2021084).
- F. Y. Hadaegh, S. J. Chung, and H. M. Manohara, “On development of 100-gram-class spacecraft for swarm applications,” IEEE Systems Journal, vol. 10, no. 2, pp. 673–684, 2016.
- C. Sinigaglia, S. Bandyopadhyay, M. Quadrelli, and F. Braghin, “Optimal-transport-based control of particle swarms for orbiting rainbows concept,” Journal of Guidance, Control, and Dynamics, vol. 44, no. 11, pp. 2108–2117, 2021.
- S. Bandyopadhyay and M. Quadrelli, “Optimal Transport Based Control of Granular Imaging System in Space,” in 2017 International Workshop on Satellite Constellations and Formation Flying (IWSCFF), Boulder, Colorado, USA, June 2017.
- B. Açikmeşe and D. S. Bayard, “A markov chain approach to probabilistic swarm guidance,” in 2012 American Control Conference (ACC), pp. 6300–6307, Montreal, QC, Canada, June 2012.
- B. Açikmeşe and D. S. Bayard, “Probabilistic swarm guidance for collaborative autonomous agents,” in 2014 American Control Conference, pp. 477–482, Portland, OR, USA, June 2014.
- B. Açikmeşe and D. S. Bayard, “Markov chain approach to probabilistic guidance for swarms of autonomous agents,” Asian Journal of Control, vol. 17, no. 4, pp. 1105–1124, 2015.
- N. Demir, B. Açikmeşe, and M. W. Harris, “Convex optimization formulation of density upper bound constraints in markov chain synthesis,” in 2014 American control conference, pp. 483–488, Portland, OR, USA, June 2014.
- N. Demir, B. Açikmeşe, and C. Pehlivantürk, “Density control for decentralized autonomous agents with conflict avoidance,” IFAC Proceedings Volumes, vol. 47, no. 3, pp. 11715–11721, 2014.
- N. Demir and B. Açikmeşe, “Probabilistic density control for swarm of decentralized on-off agents with safety constraints,” in 2015 American Control Conference (ACC), pp. 5238–5244, Chicago, IL, USA, July 2015.
- N. Demir, U. Eren, and B. Açikmeşe, “Decentralized probabilistic density control of autonomous swarms with safety constraints,” Autonomous Robots, vol. 39, no. 4, pp. 537–554, 2015.
- N. Demirer, “Density control of multi-agent systems with safety constraints: a Markov chain approach,” Tech. Rep., Ph.D. dissertation, 2017.
- S. Bandyopadhyay, S.-J. Chung, and F. Y. Hadaegh, “Inhomogeneous Markov Chain Approach to Probabilistic Swarm Guidance Algorithm,” in 5th Int. Conf. Spacecraft Formation Flying Missions and Technologies, Munich, Germany, 2013.
- S. Bandyopadhyay, S.-J. Chung, and F. Y. Hadaegh, “Probabilistic swarm guidance using inhomogeneous markov chains,” IEEE Transactions on Control of Network Systems, 2014, http://arxiv.org/abs/1403.4134.
- S. Bandyopadhyay, S.-J. Chung, and F. Y. Hadaegh, “Feedback-based inhomogeneous markov chain approach to probabilistic swarm guidance,” in 2015 International Workshop on Satellite Constellations and Formation Flying (IWSCFF), Delft, Netherlands, June 2015.
- S. Bandyopadhyay, S.-J. Chung, and F. Y. Hadaegh, “A probabilistic Eulerian approach for motion planning of a large-scale swarm of robots,” in 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3822–3829, Daejeon, October 2016.
- S. Bandyopadhyay, S.-J. Chung, and F. Y. Hadaegh, “Probabilistic and distributed control of a large-scale swarm of autonomous agents,” IEEE Transactions on Robotics, vol. 33, no. 5, pp. 1103–1123, 2017.
- S. Bandyopadhyay, S.-J. Chung, and F. Y. Hadaegh, “Probabilistic swarm guidance using optimal transport,” in 2014 IEEE Conference on Control Applications (CCA), pp. 498–505, Juan Les Antibes, France, October 2014.
- S. Bandyopadhyay, J.-P. de la Croix, I. Nesnas, D. Bayard, S.-J. Chung, and F. Hadaegh, “Probabilistic guidance of a swarm deployed from the back shell of a mars spacecraft,” in 2019 International Astronautical Congress (IAC), Washington, D.C., USA, October 2019.
- U. Eren, A. Prach, B. B. Kocer, S. V. Raković, E. Kayacan, and B. Açikmeşe, “Model predictive control in aerospace systems: current state and opportunities,” Journal of Guidance, Control, and Dynamics, vol. 40, no. 7, pp. 1541–1566, 2017.
- J. Carson and A. Acikmese, “A model-predictive control technique with guaranteed resolvability and required thruster silent times for small-body proximity operations,” in AIAA guidance, Navigation, and Control Conference and Exhibit, p. 6780, Keystone, Colorado, August 2006.
- S. Di Cairano, H. Park, and I. Kolmanovsky, “Model predictive control approach for guidance of spacecraft rendezvous and proximity maneuvering,” International Journal of Robust and Nonlinear Control, vol. 22, no. 12, pp. 1398–1427, 2012.
- T. Pippia, V. Preda, S. Bennani, and T. Keviczky, “Reconfiguration of a satellite constellation in circular formation orbit with decentralized model predictive control,” 2022, https://arxiv.org/abs/2201.10399.
- D. Morgan, S.-J. Chung, and F. Y. Hadaegh, “Model predictive control of swarms of spacecraft using sequential convex programming,” Journal of Guidance, Control, and Dynamics, vol. 37, no. 6, pp. 1725–1740, 2014.
- R. Foust, S.-J. Chung, and F. Y. Hadaegh, “Optimal guidance and control with nonlinear dynamics using sequential convex programming,” Journal of Guidance, Control, and Dynamics, vol. 43, no. 4, pp. 633–644, 2020.
- D. Morgan, G. P. Subramanian, S. Bandyopadhyay, S.-J. Chung, and F. Y. Hadaegh, “Probabilistic guidance of distributed systems using sequential convex programming,” in 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3850–3857, Chicago, IL, USA, September 2014.
- J. Cortes, S. Martinez, T. Karatas, and F. Bullo, “Coverage control for mobile sensing networks,” IEEE Transactions on Robotics and Automation, vol. 20, no. 2, pp. 243–255, 2004.
- T. Chevet, C. S. Maniu, C. Vlad, and Y. Zhang, “Voronoi-based uavs formation deployment and reconfiguration using mpc techniques,” in 2018 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 9–14, Dallas, Texas, USA, 2018.
- A. Carron and M. N. Zeilinger, “Model predictive coverage control,” IFAC-PapersOnLine, vol. 53, no. 2, pp. 6107–6112, 2020.
Copyright © 2022 Xiwei Wu et al. Exclusive Licensee Beijing Institute of Technology Press. Distributed under a Creative Commons Attribution License (CC BY 4.0).