Global trajectory optimisation: can we prune the solution space when considering deep space manoeuvres?

This document contains a report on the work done under the ESA/Ariadna study 06/4101 on the global optimization of space trajectories with multiple gravity assist (GA) and deep space manoeuvres (DSM). The study was performed by a joint team of scientists from the University of Reading and the University of Glasgow.

Search space pruning and global optimization of multiple gravity assist trajectories with deep space manoeuvres

This paper deals with the design of optimal multiple gravity assist trajectories with deep space manoeuvres. A pruning method which considers the sequential nature of the problem is presented. The method locates feasible vectors using local optimization and applies a clustering algorithm to find reduced bounding boxes which can be used in a subsequent optimization step. Since multiple local minima remain within the pruned search space, the use of a global optimization method, such as Differential Evolution, is suggested for finding solutions which are likely to be close to the global optimum. Two case studies are presented.

Stabilizing swarm intelligence search via positive feedback resource allocation

A novel Swarm Intelligence method for best-fit search, Stochastic Diffusion Search, is presented capable of rapid location of the optimal solution in the search space. Population based search mechanisms employed by Swarm Intelligence methods can suffer lack of convergence resulting in ill defined stopping criteria and loss of the best solution. Conversely, as a result of its resource allocation mechanism, the solutions SDS discovers enjoy excellent stability.

Distributed space-time block coding for 3 and 4 relay nodes: Imperfect synchronisation and a solution

Most research on distributed space time block coding (STBC) has so far focused on the case of 2 relay nodes and assumed that the relay nodes are perfectly synchronised at the symbol level. By applying STBC to 3-or 4-relay node systems, this paper shows that imperfect synchronisation causes significant performance degradation to the conventional detector. To this end, we propose a new STBC detection solution based on the principle of parallel interference cancellation (PIC). The PIC detector is moderate in computational complexity but is very effective in suppressing the impact of imperfect synchronisation.

Search space pruning and global optimisation of Multiple Gravity Assist spacecraft trajectories

We introduce and describe the Multiple Gravity Assist problem, a global optimisation problem that is of great interest in the design of spacecraft and their trajectories. We discuss its formalization and we show, in one particular problem instance, the performance of selected state of the art heuristic global optimisation algorithms. A deterministic search space pruning algorithm is then developed and its polynomial time and space complexity derived. The algorithm is shown to achieve search space reductions of greater than six orders of magnitude, thus reducing significantly the complexity of the subsequent optimisation.

Resource allocation analysis of the stochastic diffusion search

The Stochastic Diffusion Search (SDS) was developed as a solution to the best-fit search problem. Thus, as a special case it is capable of solving the transform invariant pattern recognition problem. SDS is efficient and, although inherently probabilistic, produces very reliable solutions in widely ranging search conditions. However, to date a systematic formal investigation of its properties has not been carried out. This thesis addresses this problem. The thesis reports results pertaining to the global convergence of SDS as well as characterising its time complexity. However, the main emphasis of the work, reports on the resource allocation aspect of the Stochastic Diffusion Search operations. The thesis introduces a novel model of the algorithm, generalising an Ehrenfest Urn Model from statistical physics. This approach makes it possible to obtain a thorough characterisation of the response of the algorithm in terms of the parameters describing the search conditions in case of a unique best-fit pattern in the search space. This model is further generalised in order to account for different search conditions: two solutions in the search space and search for a unique solution in a noisy search space. Also an approximate solution in the case of two alternative solutions is proposed and compared with predictions of the extended Ehrenfest Urn model. The analysis performed enabled a quantitative characterisation of the Stochastic Diffusion Search in terms of exploration and exploitation of the search space. It appeared that SDS is biased towards the latter mode of operation. This novel perspective on the Stochastic Diffusion Search lead to an investigation of extensions of the standard SDS, which would strike a different balance between these two modes of search space processing. Thus, two novel algorithms were derived from the standard Stochastic Diffusion Search, ‘context-free’ and ‘context-sensitive’ SDS, and their properties were analysed with respect to resource allocation. It appeared that they shared some of the desired features of their predecessor but also possessed some properties not present in the classic SDS. The theory developed in the thesis was illustrated throughout with carefully chosen simulations of a best-fit search for a string pattern, a simple but representative domain, enabling careful control of search conditions.

Consistent Dirichlet Boundary Conditions for Numerical Solution of Moving Boundary Problems

We consider the imposition of Dirichlet boundary conditions in the finite element modelling of moving boundary problems in one and two dimensions for which the total mass is prescribed. A modification of the standard linear finite element test space allows the boundary conditions to be imposed strongly whilst simultaneously conserving a discrete mass. The validity of the technique is assessed for a specific moving mesh finite element method, although the approach is more general. Numerical comparisons are carried out for mass-conserving solutions of the porous medium equation with Dirichlet boundary conditions and for a moving boundary problem with a source term and time-varying mass.

Synthesis, structure and solution chemistry of a family of dinuclear hydrazonato-vanadium(V) complexes with [OV(mu-O)VO](4+) core

Dinuclear trioxidic [{VOL}(2)mu-O] (1-4) complexes were synthesized from the reaction of [(VO)-O-IV(acac)(2)] with an equimolar amount of H2L [H2L is the general abbreviation of hydrazone ligands (H2L1-4) derived from the condensation of benzoyl hydrazine with either 2-hydroxyacetophenone or its para substituted derivatives] in acetone or CH2Cl2 or acetonitrile. These V2O3L2 complexes were also obtained from the reaction of VOSO4 with H2L in the presence of two equivalents sodium acetate in aqueous-methanolic (50% V/V) medium and also from the decomposition of [(VO)-O-IV(L)(bipy/phen)] complexes in CH2Cl2 Solution. Black monoclinic crystals of 2 and 4 with C2/c space group were obtained from the reaction of [(VO)-O-IV(acac)(2)], respectively, with H2L2 and H2L4 in acetone in which the respective ligands are bonded meridionally to vanadium in their fully deprotonated enol forms. The V-O bond lengths follow the order: V-O(oxo) < V-O(oxo-bridged) < V-O(phenolate) < V-O(enolate). Complexes (1-4) are diamagnetic exhibiting LMCT transition band near 380 nm in CH2Cl2 solution and they are electroactive displaying a quasi-reversible reduction peak in the 0.14-0.30 V versus SCE region. The and the reduction peak potential (E-p(c)) values show linear relationships with the Hammett constant (sigma) of the substituents in the hydrazone ligands. These dinuclear complexes are converted to the corresponding mononuclear cis dioxo complexes K(H2O)(+)[(VO2)-O-V(L)](-) (5-8) and mixed-ligand [(VO)-O-V(L)(hq)] complexes on reaction, respectively, with two equivalents KOH in methanol and two equivalents 8-hydroxyquinoline (Hhq) in CHCl3. Ascorbic acid reduces the dioxovanadium(V) complexes reversibly under aerobic condition. (C) 2008 Elsevier Ltd. All rights reserved.

Synthesis of heterosulfamates. Search for structure-taste relationships

Thirty one new sodium heterosulfamates, RNHSO3Na, where the R portion contains mainly thiazole, benzothiazole, thiadiazole and pyridine ring structures, have been synthesized and their taste portfolios have been assessed. A database of 132 heterosulfamates ( both open-chain and cyclic) has been formed by combining these new compounds with an existing set of 101 heterosulfamates which were previously synthesized and for which taste data are available. Simple descriptors have been obtained using (i) measurements with Corey-Pauling-Koltun (CPK) space- filling models giving x, y and z dimensions and a volume VCPK, (ii) calculated first order molecular connectivities ((1)chi(v)) and (iii) the calculated Spartan program parameters to obtain HOMO, LUMO energies, the solvation energy E-solv and V-SPART AN. The techniques of linear (LDA) and quadratic (QDA) discriminant analysis and Tree analysis have then been employed to develop structure-taste relationships (SARs) that classify the sweet (S) and non-sweet (N) compounds into separate categories. In the LDA analysis 70% of the compounds were correctly classified ( this compares with 65% when the smaller data set of 101 compounds was used) and in the QDA analysis 68% were correctly classified ( compared to 80% previously). TheTree analysis correctly classified 81% ( compared to 86% previously). An alternative Tree analysis derived using the Cerius2 program and a set of physicochemical descriptors correctly classified only 54% of the compounds.

Minimum stable convergence criteria for stochastic diffusion search

An analysis of Stochastic Diffusion Search (SDS), a novel and efficient optimisation and search algorithm, is presented, resulting in a derivation of the minimum acceptable match resulting in a stable convergence within a noisy search space. The applicability of SDS can therefore be assessed for a given problem.

Space partitioning for scalable K-means

K-Means is a popular clustering algorithm which adopts an iterative refinement procedure to determine data partitions and to compute their associated centres of mass, called centroids. The straightforward implementation of the algorithm is often referred to as `brute force' since it computes a proximity measure from each data point to each centroid at every iteration of the K-Means process. Efficient implementations of the K-Means algorithm have been predominantly based on multi-dimensional binary search trees (KD-Trees). A combination of an efficient data structure and geometrical constraints allow to reduce the number of distance computations required at each iteration. In this work we present a general space partitioning approach for improving the efficiency and the scalability of the K-Means algorithm. We propose to adopt approximate hierarchical clustering methods to generate binary space partitioning trees in contrast to KD-Trees. In the experimental analysis, we have tested the performance of the proposed Binary Space Partitioning K-Means (BSP-KM) when a divisive clustering algorithm is used. We have carried out extensive experimental tests to compare the proposed approach to the one based on KD-Trees (KD-KM) in a wide range of the parameters space. BSP-KM is more scalable than KDKM, while keeping the deterministic nature of the `brute force' algorithm. In particular, the proposed space partitioning approach has shown to overcome the well-known limitation of KD-Trees in high-dimensional spaces and can also be adopted to improve the efficiency of other algorithms in which KD-Trees have been used.

Optimal piecewise locally linear modeling

Associative memory networks such as Radial Basis Functions, Neurofuzzy and Fuzzy Logic used for modelling nonlinear processes suffer from the curse of dimensionality (COD), in that as the input dimension increases the parameterization, computation cost, training data requirements, etc. increase exponentially. Here a new algorithm is introduced for the construction of a Delaunay input space partitioned optimal piecewise locally linear models to overcome the COD as well as generate locally linear models directly amenable to linear control and estimation algorithms. The training of the model is configured as a new mixture of experts network with a new fast decision rule derived using convex set theory. A very fast simulated reannealing (VFSR) algorithm is utilized to search a global optimal solution of the Delaunay input space partition. A benchmark non-linear time series is used to demonstrate the new approach.