Autonomous Onboard Mission Planning for Multiple Satellite Systems

Zixuan Zheng

Research output: ThesisDissertation (TU Delft)

488 Downloads (Pure)

Abstract

With the rising demands from customers and users and the development of ever advanced technologies, many space missions nowadays require more than one satellite to fulfill their mission objectives. Although replacing single satellite systems (SSSs) by multiple satellite systems (MSSs) offers advantages, such as enhanced spatial and temporal coverage as well as high robustness and multifunctional purposes, it also introduces new challenges. There is no doubt that as the number of satellites in a mission grows, the complexity and operation cost of controlling and coordinating these satellites only by human (or ground based) operators will increase dramatically. In addition, for some deep space missions or complex operational tasks, due to the long signal transmission time between the spacecraft and ground-based antennas or short communication windows, there will not be enough time or resources for operators to sufficiently and efficiently control all of the required onboard functions from mission control centers. Therefore, to enhance the efficiency of operating an MSS, and to reduce the cost of human resources and ground infrastructure, an onboard autonomous system (OAS) for MSS is a promising solution. For specific missions, the use of an OAS may even be a mission enabler. One important function of an OAS is to provide planning and re-planning services based on different mission requirements. The objective of this research is to develop and characterize onboard autonomous mission planning and re-planning approaches for MSSs. Traditional planning approaches have been reviewed and proven to be inappropriate and inefficient for complex planning problems in the harsh space environment when severe system constraints are enforced and a large number of vehicles constitutes the MSS. % Artificial intelligence (AI) approaches, in contrast, are more suitable for complex problems due to their broad adaptability and their ability to cope with large-scale variables. To overcome these deficiencies, engineers and researchers have started to develop OAS with the help of Artificial Intelligence (AI) techniques to allow for more complex space missions. Based on the relevance of this problem, the following research questions (RQs) have been formulated and will be answered in this thesis. % and a review of the state-of-the-art scientific literature \textbf{RQ1: What are the strengths of using AI in space missions? How to use a centralized AI algorithm in a multi-satellite system to decompose mission objectives and perform mission planning for the entire system?} \textbf{RQ2: How to define emergency situations which may occur during mission operations? How to use AI algorithms to handle mission re-planning and re-scheduling problems?} \textbf{RQ3: How to design cooperation and negotiation approaches for an MSS to reach an agreement? How to improve AI algorithms for distributed onboard mission planning problems?} To define potential scenarios, a reference mission is introduced in this thesis, called \textit{Discovering the Sky at the Longest Wavelength (DSL)}. The mission is assumed to comprise one Mother Satellite (MS) and eight Daughter Satellites (DSs) in a lunar orbit. Its scientific objective is to observe the universe in the hitherto-unexplored very low frequency (below 30 MHz) electromagnetic spectrum. The DSs collect scientific data only in those parts of the orbit which is shielded from radio frequencies emitted by the Earth. These DSs can only transmit collected data to the MS when they are outside of this shielded orbit sections, to prevent interferences caused by communication. % The DSs collect scientific data and transmit those to the MS with the constraints what scientific data collection may only occur in the part of the orbit. This part of the orbit is shielded from radio frequencies emitted by the Earth and no other DSs are transmitting data to the MS. This renders mission operations of DSL very complex. The existing body of knowledge on mission planning problems for multi-satellite systems is reviewed. It comprises three categories: classical approaches, heuristic approaches, and advanced techniques (e.g., team negotiation mechanisms, evaluation algorithms). Targeting the complexity of foreseeable DSL planning problems, nine representative optimization algorithms are applied to fourteen test functions. The results indicate that Evolutionary Algorithms (EAs) have a broader adaptability than classical approaches. They are also more efficient than other heuristic approaches. Therefore, EAs family is selected as suitable candidate for the reference MSS. % fourteen test functions are used to test nine representative algorithms to provide a preliminary selection for the reference MSS.=-098 % The fourteen test functions we used contain different types of objective functions and constraints to guarantee the diversity of the preliminary selection. % The goal of this selection is to identify a suitable approach for an MSS to handle different types of optimization problems. Eight constrained and six unconstrained test functions are employed as benchmarks. The operations concept of the DSL mission foresees that the initial mission planning is performed by the MS, while the eight DSs are preliminary executing data collection and transmission tasks. % Considering the scientific design of the DSL mission, the initial mission planning procedures are all performed by the Mother Satellite (MS), while the rest eight Daughter Satellites (DSs) are just participating satellites which response for gathering and transmitting data. During this phase, the MSS implements a centralized architecture and the MS conducts a centralized planning approach. By comparing basic Genetic Algorithm (GA) with several state-of-the-art improved GAs, its weaknesses are revealed. In this thesis, to overcome early and slow convergence problems, the need to develop a new mutation strategy for GA is motivated. % By revealing the weaknesses of the basic Genetic Algorithm (GA), along with a comparison with several other improved GAs, The proposed novel mutation strategy is called Hybrid Dynamic Mutation (HDM), which contains a standard mutation operator and an escape mutation operator. While the standard mutation operator uses a small mutation rate for approaching the global optimum, the escape mutation operator uses a larger mutation rate to allow an escape from local optima. The simulation results indicate that the proposed HDM can improve the basic GA (which turns into the HDMGA) leading to a superior performance on correctness and effectiveness as compared to alternative GAs. Based on these findings, AI related methods are considered a promising category as compared to classical methods due to their flexibility and effectiveness to support the onboard planning for an MSS. In addition, the proposed HDMGA also provides a satisfying result for the considered initial mission planning problems. Internal or external causes, e.g. an actuator failure or the challenging space environment, can lead to a satellite malfunction during mission operations. This thesis considers the two most important behaviors of the DSL mission, observation and communication, and proposes potential emergency scenarios to handle possible system failures on DSs. Two re-planning methods, one called the Cyclically Re-planning Method (CRM), the other one the Near Real-time Re-planning Method (NRRM), are established and compared. The CRM performs re-planning at the beginning of each orbit and only re-plans for one orbit. The NRRM performs re-planning in a near real-time setting when the emergency occurs. Its re-planning covers for the rest of the mission. Three simulation study cases are formulated based on assumed emergency scenarios. % Each case is designed to represent a different level of failures on multiple DSs. The proposed two methods are compared on three aspects: the total number of data observed from all DSs within a certain time frame, the total number of data the MS received from all DSs within a certain time frame, and the average computation time needed for re-planning. The results indicate that: (1) The NRRM allows to observe and transmit more data than the CRM within a specific operational lifetime. (2) The NRRM requires more computational time than the CRM for emergency situations, while it requires less time than the CRM for nominal situations. % For emergency situations, the CRM can therefore provide re-planning sequences faster than the NRRM, while for nominal operations, the NRRM is much faster than the CRM. This research also covers a much more severe scenario, namely that the MS becomes fully non-functional in an emergency situation. This would render the MS unable to provide mission planning and re-planning services for the MSS. Without its main controller on the MS, all DSs now need to cooperate to jointly solve the mission planning problems. Due to the loss of the MS, both distributed and decentralized architectures, which the MSS could then use are introduced. In a distributed architecture, each DS is connected with all other DSs directly or through DS which acts as retranslator. In a decentralized architecture, each DS can only communicate with its neighbors. Considering that the mission allocation problems in different organizational architectures are similar to information games in game theory, a game-theoretical model of the Multi-Satellite Mission Allocation (MSMA) problem is formulated. % Three new negotiation mechanisms are introduced, compared and analyzed in theoretical terms. The Utility-based Regret Play (URP) negotiation mechanism is proposed for an MSMA problem using a distributed architecture. It inherits the ability to evaluate individual utility at each negotiation step from the Utility-based Fictitious Play, and the ability to regret the current choice and for not proposing particular choices in the past negotiation steps from the Regret Matching Play. The Smoke Signal Play (SSP) and Broadcast-based Play (BBP) are developed for a decentralized architecture instead. The SSP is inspired by an old communication method called \textit{Smoke Signal}, where each satellite is considered as a smoke tower, passing information of utility to its succeeding neighbor. The BBP uses broadcasting as the communication method, where each satellite can transmit information to all its neighbors. The simulation results show that the URP can outperform the other three state-of-the-art mechanisms (Action-based Fictitious Play, Utility-based Fictitious Play, and Regret Matching Play) with studied cases. For the decentralized architecture, the results reveal that both SSP and BBP can provide valid solutions for mission allocation problems. The BBP mechanism shows a superior performance on computation time as compared to SSP and a state-of-the-art approach called Market-based Auction. The SSP mechanism, on the other hand, shows the best performance with respect to power consumption. To solve complex optimization problems in distributed mission planning scenarios, an approach, named Hybrid Distributed GA (HDGA) is proposed. This approach contains two modules: the Local Constraint Satisfaction module (LCS) and the Globally Distributed Optimization module (GDO). In the LCS module, the greedy best-first search algorithm is employed as the local search heuristic for helping each DS to find suitable solutions which can satisfy individual constraints. This module is designed to generate multiple solutions to form local populations for the GDO. The GDO module employs the HDMGA as the core optimization algorithm, while the individual populations are formed through the local populations exchange procedure between one participant and all other participants. For a standard planning case, the results indicate that HDGA can reduce the computation time while ensuring a higher success rate compared to the HDMGA. Comparing the HDGA with two other state-of-the-art distributed optimization algorithms, the Distributed Ant Colony Optimization (DACO) and the Coevolutionary Particle Swarm Optimization (CPSO), the statistical results reveal that HDGA is more stable and accurate to handle large-scale planning problems. The HDGA also shows the best performance on computation time among all tested distributed approaches. With the rising demands from customers and users and the development of ever advanced technologies, many space missions nowadays require more than one satellite to fulfill their mission objectives. Although replacing single satellite systems (SSSs) by multiple satellite systems (MSSs) offers advantages, such as enhanced spatial and temporal coverage as well as high robustness and multifunctional purposes, it also introduces new challenges. There is no doubt that as the number of satellites in a mission grows, the complexity and operation cost of controlling and coordinating these satellites only by human (or ground based) operators will increase dramatically. In addition, for some deep space missions or complex operational tasks, due to the long signal transmission time between the spacecraft and ground-based antennas or short communication windows, there will not be enough time or resources for operators to sufficiently and efficiently control all of the required onboard functions from mission control centers. Therefore, to enhance the efficiency of operating an MSS, and to reduce the cost of human resources and ground infrastructure, an onboard autonomous system (OAS) for MSS is a promising solution. For specific missions, the use of an OAS may even be a mission enabler. One important function of an OAS is to provide planning and re-planning services based on different mission requirements. The objective of this research is to develop and characterize onboard autonomous mission planning and re-planning approaches for MSSs. Traditional planning approaches have been reviewed and proven to be inappropriate and inefficient for complex planning problems in the harsh space environment when severe system constraints are enforced and a large number of vehicles constitutes the MSS. % Artificial intelligence (AI) approaches, in contrast, are more suitable for complex problems due to their broad adaptability and their ability to cope with large-scale variables. To overcome these deficiencies, engineers and researchers have started to develop OAS with the help of Artificial Intelligence (AI) techniques to allow for more complex space missions. Based on the relevance of this problem, the following research questions (RQs) have been formulated and will be answered in this thesis. % and a review of the state-of-the-art scientific literature \textbf{RQ1: What are the strengths of using AI in space missions? How to use a centralized AI algorithm in a multi-satellite system to decompose mission objectives and perform mission planning for the entire system?} \textbf{RQ2: How to define emergency situations which may occur during mission operations? How to use AI algorithms to handle mission re-planning and re-scheduling problems?} \textbf{RQ3: How to design cooperation and negotiation approaches for an MSS to reach an agreement? How to improve AI algorithms for distributed onboard mission planning problems?} To define potential scenarios, a reference mission is introduced in this thesis, called \textit{Discovering the Sky at the Longest Wavelength (DSL)}. The mission is assumed to comprise one Mother Satellite (MS) and eight Daughter Satellites (DSs) in a lunar orbit. Its scientific objective is to observe the universe in the hitherto-unexplored very low frequency (below 30 MHz) electromagnetic spectrum. The DSs collect scientific data only in those parts of the orbit which is shielded from radio frequencies emitted by the Earth. These DSs can only transmit collected data to the MS when they are outside of this shielded orbit sections, to prevent interferences caused by communication. % The DSs collect scientific data and transmit those to the MS with the constraints what scientific data collection may only occur in the part of the orbit. This part of the orbit is shielded from radio frequencies emitted by the Earth and no other DSs are transmitting data to the MS. This renders mission operations of DSL very complex. The existing body of knowledge on mission planning problems for multi-satellite systems is reviewed. It comprises three categories: classical approaches, heuristic approaches, and advanced techniques (e.g., team negotiation mechanisms, evaluation algorithms). Targeting the complexity of foreseeable DSL planning problems, nine representative optimization algorithms are applied to fourteen test functions. The results indicate that Evolutionary Algorithms (EAs) have a broader adaptability than classical approaches. They are also more efficient than other heuristic approaches. Therefore, EAs family is selected as suitable candidate for the reference MSS. % fourteen test functions are used to test nine representative algorithms to provide a preliminary selection for the reference MSS.=-098 % The fourteen test functions we used contain different types of objective functions and constraints to guarantee the diversity of the preliminary selection. % The goal of this selection is to identify a suitable approach for an MSS to handle different types of optimization problems. Eight constrained and six unconstrained test functions are employed as benchmarks. The operations concept of the DSL mission foresees that the initial mission planning is performed by the MS, while the eight DSs are preliminary executing data collection and transmission tasks. % Considering the scientific design of the DSL mission, the initial mission planning procedures are all performed by the Mother Satellite (MS), while the rest eight Daughter Satellites (DSs) are just participating satellites which response for gathering and transmitting data. During this phase, the MSS implements a centralized architecture and the MS conducts a centralized planning approach. By comparing basic Genetic Algorithm (GA) with several state-of-the-art improved GAs, its weaknesses are revealed. In this thesis, to overcome early and slow convergence problems, the need to develop a new mutation strategy for GA is motivated. % By revealing the weaknesses of the basic Genetic Algorithm (GA), along with a comparison with several other improved GAs, The proposed novel mutation strategy is called Hybrid Dynamic Mutation (HDM), which contains a standard mutation operator and an escape mutation operator. While the standard mutation operator uses a small mutation rate for approaching the global optimum, the escape mutation operator uses a larger mutation rate to allow an escape from local optima. The simulation results indicate that the proposed HDM can improve the basic GA (which turns into the HDMGA) leading to a superior performance on correctness and effectiveness as compared to alternative GAs. Based on these findings, AI related methods are considered a promising category as compared to classical methods due to their flexibility and effectiveness to support the onboard planning for an MSS. In addition, the proposed HDMGA also provides a satisfying result for the considered initial mission planning problems. Internal or external causes, e.g. an actuator failure or the challenging space environment, can lead to a satellite malfunction during mission operations. This thesis considers the two most important behaviors of the DSL mission, observation and communication, and proposes potential emergency scenarios to handle possible system failures on DSs. Two re-planning methods, one called the Cyclically Re-planning Method (CRM), the other one the Near Real-time Re-planning Method (NRRM), are established and compared. The CRM performs re-planning at the beginning of each orbit and only re-plans for one orbit. The NRRM performs re-planning in a near real-time setting when the emergency occurs. Its re-planning covers for the rest of the mission. Three simulation study cases are formulated based on assumed emergency scenarios. % Each case is designed to represent a different level of failures on multiple DSs. The proposed two methods are compared on three aspects: the total number of data observed from all DSs within a certain time frame, the total number of data the MS received from all DSs within a certain time frame, and the average computation time needed for re-planning. The results indicate that: (1) The NRRM allows to observe and transmit more data than the CRM within a specific operational lifetime. (2) The NRRM requires more computational time than the CRM for emergency situations, while it requires less time than the CRM for nominal situations. % For emergency situations, the CRM can therefore provide re-planning sequences faster than the NRRM, while for nominal operations, the NRRM is much faster than the CRM. This research also covers a much more severe scenario, namely that the MS becomes fully non-functional in an emergency situation. This would render the MS unable to provide mission planning and re-planning services for the MSS. Without its main controller on the MS, all DSs now need to cooperate to jointly solve the mission planning problems. Due to the loss of the MS, both distributed and decentralized architectures, which the MSS could then use are introduced. In a distributed architecture, each DS is connected with all other DSs directly or through DS which acts as retranslator. In a decentralized architecture, each DS can only communicate with its neighbors. Considering that the mission allocation problems in different organizational architectures are similar to information games in game theory, a game-theoretical model of the Multi-Satellite Mission Allocation (MSMA) problem is formulated. % Three new negotiation mechanisms are introduced, compared and analyzed in theoretical terms. The Utility-based Regret Play (URP) negotiation mechanism is proposed for an MSMA problem using a distributed architecture. It inherits the ability to evaluate individual utility at each negotiation step from the Utility-based Fictitious Play, and the ability to regret the current choice and for not proposing particular choices in the past negotiation steps from the Regret Matching Play. The Smoke Signal Play (SSP) and Broadcast-based Play (BBP) are developed for a decentralized architecture instead. The SSP is inspired by an old communication method called \textit{Smoke Signal}, where each satellite is considered as a smoke tower, passing information of utility to its succeeding neighbor. The BBP uses broadcasting as the communication method, where each satellite can transmit information to all its neighbors. The simulation results show that the URP can outperform the other three state-of-the-art mechanisms (Action-based Fictitious Play, Utility-based Fictitious Play, and Regret Matching Play) with studied cases. For the decentralized architecture, the results reveal that both SSP and BBP can provide valid solutions for mission allocation problems. The BBP mechanism shows a superior performance on computation time as compared to SSP and a state-of-the-art approach called Market-based Auction. The SSP mechanism, on the other hand, shows the best performance with respect to power consumption. To solve complex optimization problems in distributed mission planning scenarios, an approach, named Hybrid Distributed GA (HDGA) is proposed. This approach contains two modules: the Local Constraint Satisfaction module (LCS) and the Globally Distributed Optimization module (GDO). In the LCS module, the greedy best-first search algorithm is employed as the local search heuristic for helping each DS to find suitable solutions which can satisfy individual constraints. This module is designed to generate multiple solutions to form local populations for the GDO. The GDO module employs the HDMGA as the core optimization algorithm, while the individual populations are formed through the local populations exchange procedure between one participant and all other participants. For a standard planning case, the results indicate that HDGA can reduce the computation time while ensuring a higher success rate compared to the HDMGA. Comparing the HDGA with two other state-of-the-art distributed optimization algorithms, the Distributed Ant Colony Optimization (DACO) and the Coevolutionary Particle Swarm Optimization (CPSO), the statistical results reveal that HDGA is more stable and accurate to handle large-scale planning problems. The HDGA also shows the best performance on computation time among all tested distributed approaches.
Original languageEnglish
QualificationDoctor of Philosophy
Awarding Institution
  • Delft University of Technology
Supervisors/Advisors
  • Guo, J., Supervisor
  • Gill, E.K.A., Supervisor
Thesis sponsors
Award date3 May 2019
Publisher
Print ISBNs978-94-028-1480-4
Electronic ISBNs978-94-028-1480-4
DOIs
Publication statusPublished - 3 May 2019

Keywords

  • Artificial Intelligence
  • Onboard Autonomy
  • Mission Planning
  • Multiple Satellite Systems
  • Team Negotiation Mechanisms
  • Centralized and Distributed optimization

Fingerprint

Dive into the research topics of 'Autonomous Onboard Mission Planning for Multiple Satellite Systems'. Together they form a unique fingerprint.

Cite this