Browsing by Subject "Tree search"
Now showing 1 - 4 of 4
- Results Per Page
- Sort Options
Item Automated assembly sequence generation using a novel search scheme for handling parallel sub-assemblies(2013-05) Poladi, Ranjith; Campbell, Matthew I.; Kutanoglu, ErhanThe Assembly sequencing problem (ASP) is part of the assembly planning process. The ASP is basically a large scale, combinatorial problem which is highly constrianed. The aim of this thesis is to automatically generate assembly sequence(s) for mechanical products. In this thesis, the CAD model of an assembly is represented or modeled as a label-rich graph. The assembly sequences are generated using graph grammar rules that are applied on the graph. The sequences are stored in a search tree and to find an optimal sequence multiple evaluation criteria like time, subassembly stability and accessibility measures are used. This research implements a novel tree search algorithm called "Ordered Depth First Search" (ODFS) to find an optimal assembly sequence in very low processing time. The software has successfully generated an optimized assembly sequence for an assembly with 14 parts.Item Preliminary design of spacecraft trajectories for missions to outer planets and small bodies(2015-08) Lantukh, Demyan Vasilyevich; Russell, Ryan Paul, 1976-; Fowler, Wallace; Bettadpur, Srinivas; Guo, Yanping; Broschart, StephenMultiple gravity assist (MGA) spacecraft trajectories can be difficult to find, an intractable problem to solve completely. However, these trajectories have enormous benefits for missions to challenging destinations such as outer planets and primitive bodies. Techniques are presented to aid in solving this problem with a global search tool and additional investigation into one particular proximity operations option is discussed. Explore is a global grid-search MGA trajectory pathsolving tool. An efficient sequential tree search eliminates v∞ discontinuities and prunes trajectories. Performance indices may be applied to further prune the search, with multiple objectives handled by allowing these indices to change between trajectory segments and by pruning with a Pareto-optimality ranking. The MGA search is extended to include deep space maneuvers (DSM), v∞ leveraging transfers (VILT) and low-thrust (LT) transfers. In addition, rendezvous or nπ sequences can patch the transfers together, enabling automatic augmentation of the MGA sequence. Details of VILT segments and nπ sequences are presented: A boundaryvalue problem (BVP) VILT formulation using a one-dimensional root-solve enables inclusion of an efficient class of maneuvers with runtime comparable to solving ballistic transfers. Importantly, the BVP VILT also allows the calculation of velocity-aligned apsidal maneuvers (VAM), including inter-body transfers and orbit insertion maneuvers. A method for automated inclusion of nπ transfers such as resonant returns and back-flip trajectories is introduced: a BVP is posed on the v∞ sphere and solved with one or more nπ transfers – which may additionally fulfill specified science objectives. The nπ sequence BVP is implemented within the broader search, combining nπ and other transfers in the same trajectory. To aid proximity operations around small bodies, analytical methods are used to investigate stability regions in the presence of significant solar radiation pressure (SRP) and body oblateness perturbations. The interactions of these perturbations allow for heliotropic orbits, a stable family of low-altitude orbits investigated in detail. A novel constrained double-averaging technique analytically determines inclined heliotropic orbits. This type of knowledge is uniquely valuable for small body missions where SRP and irregular body shape are very important and where target selection is often a part of the mission design.Item Rule based stochastic tree search(2011-12) Kumar, Mukund; Campbell, Matthew I.; Crawford, RichardThis work presents an enhancement of a search process that is suited for a problem that can be solved using a graph grammar based generative tree. Generative grammar can be used to generate a vast number of design alternatives by using a seed graph of the problem and a set of transformation rules. The problem is to find the best solution among this space by doing the least number of evaluations possible. In a previous paper, an interactive algorithm for searching in a graph grammar representation was presented. The process was demonstrated for a problem of tying a necktie and the work here builds on top of this process to be useful for solving engineering problem. To test the search process, two problems, a photovoltaic array topology optimization problem and an electromechanical product redesign problem, are chosen. It is shown this search process converges in finding the best solution within a few hundred evaluations which is a manageable number compared to the large solution space of millions of candidates. Further optimization and tweaks are done on the process to control exploration vs. exploitation and find the parameters for fastest convergence and the best solution.Item A tabu search methodology for spacecraft tour trajectory optimization(2014-12) Johnson, Gregory Phillip; Ocampo, CesarA spacecraft tour trajectory is a trajectory in which a spacecraft visits a number of objects in sequence. The target objects may consist of satellites, moons, planets or any other body in orbit, and the spacecraft may visit these in a variety of ways, for example flying by or rendezvousing with them. The key characteristic is the target object sequence which can be represented as a discrete set of decisions that must be made along the trajectory. When this sequence is free to be chosen, the result is a hybrid discrete-continuous optimization problem that combines the challenges of discrete and combinatorial optimization with continuous optimization. The problem can be viewed as a generalization of the traveling salesman problem; such problems are NP-hard and their computational complexity grows exponentially with the problem size. The focus of this dissertation is the development of a novel methodology for the solution of spacecraft tour trajectory optimization problems. A general model for spacecraft tour trajectories is first developed which defines the parameterization and decision variables for use in the rest of the work. A global search methodology based on the tabu search metaheuristic is then developed. The tabu search approach is extended to operate on a tree-based solution representation and neighborhood structure, which is shown to be especially efficient for problems with expensive solution evaluations. Concepts of tabu search including recency-based tabu memory and strategic intensification and diversification are then applied to ensure a diverse exploration of the search space. The result is an automated, adaptive and efficient search algorithm for spacecraft tour trajectory optimization problems. The algorithm is deterministic, and results in a diverse population of feasible solutions upon termination. A novel numerical search space pruning approach is then developed, based on computing upper bounds to the reachable domain of the spacecraft, to accelerate the search. Finally, the overall methodology is applied to the fourth annual Global Trajectory Optimization Competition (GTOC4), resulting in previously unknown solutions to the problem, including one exceeding the best known in the literature.