Sequential And Physical Decomposition Methods For A Layout Design Problem Of Spacecraft

Spatial layout design of a spacecraft affects heavily its structure, performance, service life, and the length of its design cycle, the cost of its assembly and maintenance. It is one of the key issues in the global design of spacecraft, which is also known as a combinatorial optimization and NP-hard problem in mathematics, and a scheme design and complex system problem in engineering. Considerable challenges and difficulties exist in the solution of the layout design problem, which include the specification and formulation of the problem, and the formation of a competent problem-solving process that suffers from both the combinatorial explosion in mathematics and the complexity in engineering system, etc. Only limited-scale instances of layout design problems are studied and published, with lower complexity far from engineering practice. Existing layout design methods are lack of diversity in operating procedures, and few practical techniques and tools are available.This work focused on the decomposition and coordination methods for a kind of layout design problems of spacecraft, against the background of a project of Research and Development of a Software Platform for Layout Design of Spacecraft from a research institute of China Aerospace Science and Technology corporation (CAST). The layout problem herein aims to improve the global mass properties of a spacecraft by adjusting the locations and orientations of its components. Moreover, this work is supported by the National Nature Science Foundation of China.The main contributions of this work are as follows.Firstly, a heuristic named centripetal balancing method for assigning objects between subspaces and an Ant-Colony-Optimization (ACO) based layout improvement algorithm are presented. According to a set of heuristic rules and a relaxed objective function, the former uses to schedule components between different subspaces to improve the mass distribution primarily, and guides the subsequent detailed layout design. Based on an initial layout provided by GA, the latter, i.e. ACO, operates a quasi-TSP (Traveling Salesman Problem) model for layout optimization, and enhances the local search ability to accelerate the convergence. After the discretization of the exploring directions and the moving steps of each component, the layout optimization problem of improving the objective by adjusting the locations of each component is converted to a path optimization problem, named a quasi-TSP in this work. An ACO that is proved to be one of the most efficient algorithms for TSP is then adopted in the solution of the quasi-TSP. This optimization method combines the genetic algorithm for global real-space optimization and the ACO for combination optimization that enhances the local search capability in last search stage. The experimental results show that the proposed methods are feasible and effective.Secondly, a physical decomposition method is proposed to decompose a large-scale detailed layout design problem of a spacecraft into smaller parallel and coupled sub-problems, according to the characteristics of the physical structure of a spacecraft. A status vector of each subsystem is defined as well as their coupled relations. Subsequently, a two-level optimization framework is presented, in which a coordination problem is defined at the top level, as well as a set of detailed layout problems at the subsystem-level. The mathematicaloptimization models are given and corresponding optimization algorithms are developed. The proposed method differs from the collaborative optimization algorithm, target cascading algorithm and optimum response surface based local-global optimization architecture in the decomposition-coordination mechanism of the design problems at the subsystem-level. It decomposes the optimization objectives, design variables and constraints completely between sub-problems, and take the status vector of each subsystem as the links between the coordination problem at the top-level and the detailed layout design problems in each subsystem. It keeps the full autonomy of detailed layout design in each subspace and maintains the efficient coordination between different subsystems as the same time. The decomposition-coordination mechanism benefits the capability of improving the objective function continuously at the top level and follows the idea of target cascading in nature. The experimental results from two numerical examples show that the proposed methods are feasible for a kind of layout design problems of spacecraft and outperform the GA or GA-ACO on optimization ability, despite the fact that it takes a longer running time. Note that the proposed methods perform better on large-scale layout problems rather than on small-scale layout problems. Besides, this method not only benefits the solution of other layout problems with the same design objective and constraints as in this work, but also contributes to the study of the layout problems with the different in the broad sense.Lastly, an initial layout algorithm and a matching layout algorithm are presented, which are based on Multi-Agent System (MAS) and consider the embodiment requirements of layout of subsystems in physical (spatial) decomposition method. An initial layout algorithm is a basic sub-problem for detailed layout design of every sub-system, which only considers satisfying the spatial constrains, and does not consider satisfying the performance and optimization objective temporarily. And the matching layout problem is a main formulation for layout design of every sub-system, which takes a special layout status as an optimization objective with a prior condition that spatial constraints are satisfied. In these algorithms, a component to be located is regarded as an autonomous agent with local percipiency and special behaviors. This component's status attributes are defined, including volume interference, step size, static time, freedom, etc. Layout behaviors are also defined, including movement, jumpiness, rotation, etc. Moreover, a set of coordination rules and environment model are defined. Using the definition mentioned above, this paper gives a MAS-based design method for detailed layout, which is based on ideas from entity simulation, distributed storage and processing of information. In the matching layout algorithm, a probabilistic rule is adopted to evaluate the collision degree an agent suffering in different environment, instead of a classical penalty function method. This benefits the balance between the decrease of matching distance and the satisfaction of non-overlapping conditions. And the multi-restarting strategy helps to improve the matching ability of the system. The experimental results from numerical examples show that on initial layout problems the MAS-based layout algorithm runs in a more efficient way than the traditional genetic algorithm while achieving a superior or equal rate of successful runs. And on matching layout examples, the proposed algorithm for matching layout problems outperforms the genetic algorithm for matching layout problems on both efficiency and the probability of success while a feasible matching layout exists, and all runs of the proposed algorithms converge to a feasible layout that satisfies all spatial constraints andminimizes the matching distance.To draw a conclusion, this paper presents a centripetal balancing heuristic for scheduling components between subspaces, following the sequential decomposition strategy for complex design problems. Then, a quasi-TSP model based ACO algorithm is developed to accelerate local convergence in the later period of layout search. Moreover, spatial decomposition-coordination architecture for moderate and large-scale layout instances is investigated, which is primarily used to solve the large-scale layout problem. Finally, a MAS model based random layout algorithm and a matching layout algorithm are proposed. The experimental results preliminarily show the actual cases and potentiality of the MAS methodology in layout design problems. This work is expected to advance the theories of collaborative design for the complex system and layout design for spacecraft, and is also likely to benefit the research and development of practical methods and techniques for a layout design problem of spacecraft. Finally, the main contributions of this research are likely to be applied to the layout design of other spacecraft.