Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “combinatorial”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 55 records · Page 3

Dissolving variables in connectionist combinatory logic

A connectionist system which can represent and execute combinator expressions to elegantly solve the variable binding problem in connectionist networks is presented. This system is a graph reduction machine utilizing graph representations and traversal mechanisms similar to ones described in the BoltzCONS system of Touretzky (1986). It is shown that, as combinators eliminate variables by introducing special functions, these functions can be connectionistically implemented without reintroducing variable binding. This approach 'dissolves' an important part of the variable binding problem, in that a connectionist system still has to manipulate complex data structures, but those structures and their manipulations are rendered more uniform.

Barnden, John↗

On well-partial-order theory and its application to combinatorial problems of VLSI design

We nonconstructively prove the existence of decision algorithms with low-degree polynomial running times for a number of well-studied graph layout, placement, and routing problems. Some were not previously known to be in p at all; others were only known to be in p by way of brute force or dynamic programming formulations with unboundedly high-degree polynomial running times. Our methods include the application of the recent Robertson-Seymour theorems on the well-partial-ordering of graphs under both the minor and immersion orders. We also briefly address the complexity of search versions of these problems.

Fellows, M.↗

Quantum Adiabatic Optimization and Combinatorial Landscapes

In this paper we analyze the performance of the Quantum Adiabatic Evolution (QAE) algorithm on a variant of Satisfiability problem for an ensemble of random graphs parametrized by the ratio of clauses to variables, gamma = M / N. We introduce a set of macroscopic parameters (landscapes) and put forward an ansatz of universality for random bit flips. We then formulate the problem of finding the smallest eigenvalue and the excitation gap as a statistical mechanics problem. We use the so-called annealing approximation with a refinement that a finite set of macroscopic variables (verses only energy) is used, and are able to show the existence of a dynamic threshold gamma = gammad, beyond which QAE should take an exponentially long time to find a solution. We compare the results for extended and simplified sets of landscapes and provide numerical evidence in support of our universality ansatz.

Smelyanskiy, V. N.↗

Combinatorial Generation of Test Suites

Testgen is a computer program that generates suites of input and configuration vectors for testing other software or software/hardware systems. As systems become ever more complex, often, there is not enough time to test systems against all possible combinations of inputs and configurations, so test engineers need to be selective in formulating test plans. Testgen helps to satisfy this need: In response to a test-suite-requirement-specification model, it generates a minimal set of test vectors that satisfies all the requirements.

Dvorak, Daniel L.↗

Precise delay measurement through combinatorial logic

A high resolution circuit and method for facilitating precise measurement of on-chip delays for FPGAs for reliability studies. The circuit embeds a pulse generator on an FPGA chip having one or more groups of LUTS (the "LUT delay chain"), also on-chip. The circuit also embeds a pulse width measurement circuit on-chip, and measures the duration of the generated pulse through the delay chain. The pulse width of the output pulse represents the delay through the delay chain without any I/O delay. The pulse width measurement circuit uses an additional asynchronous clock autonomous from the main clock and the FPGA propagation delay can be displayed on a hex display continuously for testing purposes.

Burke, Gary R.↗

Combinatorial Multidomain Mesoporous Chips and a Method for Fractionation, Stabilization, and Storage of Biomolecules

A new fractionation device shows desirable features for exploratory screening and biomarker discovery. The constituent MSCs may be tailored for desired pore sizes and surface properties and for the sequestration and enrichment of extremely low abundant protein and peptides in desired ranges of the mass/charge spectrum. The MSCs are effective in yielding reproducible extracts from complex biological samples as small as 10 microliter in a time as short as 30 minutes. They are inexpensive to manufacture, and allow for scaled up production to attain the simultaneous processing of a large number of samples. The MSCs are multiplexed, label-free diagnostic tools with the potential of biological recognition moiety modification for enhanced specificity. The MSCs may store, protect and stabilize biological fluids, enabling the simplified and cost-effective collection and transportation of clinical samples. The MSC-based device may serve as a diagnostic tool to complement histopathology, imaging, and other conventional clinical techniques. The MSCs mediated identification of disease-specific protein signatures may help in the selection of personalized therapeutic combinations, in the real-time assessment of therapeutic efficacy and toxicity, and in the rational modulation of therapy based on the changes in the protein networks associated with the prognosis and the drug resistance of the disease.

Ferrari, Mauro↗

Plasma and Brain Cytokine Responses to Single and Combinatorial Spaceflight Stressors in Male and Female Mice

Spaceflight involves exposure to multiple environmental stressors, including Ionizing Radiation (IR), microgravity, and social isolation. We hypothesize that spaceflight stressors combine synergistically to trigger an oxidative stress response that, in turn, alters immune homeostasis, brain structure/function, and neurobehavioral/cognitive performance. Here, we report plasma and brain cytokine findings from two studies of crew age-matched (24-week-old) male and female mice exposed to simulated 5-Ion GCRsim at the NASA Space Radiation Laboratory (NSRL). In Study 1, mice were exposed to 0, 5, 15, or 50cGy 5-ion GCRsim. Immune and brain measures were acquired either at ‘Acute’ (within 3 days post-irradiation; IR), ‘Intermediate’ (IR+14 days) or ‘Delayed’ (IR+125 days) timepoints. In Study 2, mice were exposed singly and in combination to 15cGy 5-ion GCRsim, simulated microgravity via continuous head-down tilt/hindlimb unloading (HU), and social isolation. Plasma and brain cytokine cytokine profiling revealed sex-specific as well as sex-common responses. Notably, plasma granulocyte colony stimulating factor (GCSF) levels showed significant regulation compared to a single stressor alone, suggesting a potential biomarker responder. Increased GCSF was correlated with corresponding increased blood neutrophil populations. Futhermore, our study provides evidence for robust effects of HU relative to IR alone. This project addresses NASA’s efforts to characterize risks in both women and men in anticipation of future space missions beyond low earth orbit (BLEO). Ensuring crew health and performance during extended transits to the moon and beyond necessitates that sensorimotor and cognitive abilities remain strong to avoid potentially catastrophic health and safety outcomes.

mouse radiation hindlimb unloading spaceflight↗

Technological and Medical Human Health and Well-Being Options in Deep Space

Zeroth order, maintenance of human health requires supportive protection from the hazards of space, including supplying breathable air, comfortable temperatures, a supportive diet/nutrition, radiation protection, and sufficient gravity to avoid the combinatorial impacts of such effecting human operability and health. Spacecraft operability must be “fail-safe” to ensure these basic human life support conditions are maintained throughout the mission and the mission(s) must be affordable. There are known effects and unknowns effects regarding aspects of human health for Mars duration missions. Mars has the order of a third g. We have no data regarding the health impacts of this on humans or the combinatorial effects associated with 45% GCR on the Martian surface over time. There is a suspicion that if humans survive such conditions over long times they will evolve to living at reduced g and become “Martians”. Cascading failures and subcritical degradations in systems of systems causing an overall unrecoverable failure are a potential issue. There are two exremely complex systems associated with humans-Mars missions: the technical, engineering, and architectural system of systems that enable the mission and the humans. Both need to be mutually configured and operated to mitigate the overall risks and hazards of the mission. Regarding the humans that mitigation includes both the mission risks and supporting-to-increasing the human immune and other concomitant physiological systems. This report will summarize the risks, current mitigation approaches, and putative approaches including lifestyle, nutrition, and “wellness” approaches to possibly improve the human capacity to withstand the large number of combinatorial human physiological rigors of the missions. The wellness observations also apply to and are derived from Earth terrestrial applicable research.

Dennis M Bushnell↗

Minimizing distortion and internal forces in truss structures by simulated annealing

Inaccuracies in the length of members and the diameters of joints of large truss reflector backup structures may produce unacceptable levels of surface distortion and member forces. However, if the member lengths and joint diameters can be measured accurately it is possible to configure the members and joints so that root-mean-square (rms) surface error and/or rms member forces is minimized. Following Greene and Haftka (1989) it is assumed that the force vector f is linearly proportional to the member length errors e(sub M) of dimension NMEMB (the number of members) and joint errors e(sub J) of dimension NJOINT (the number of joints), and that the best-fit displacement vector d is a linear function of f. Let NNODES denote the number of positions on the surface of the truss where error influences are measured. The solution of the problem is discussed. To classify, this problem was compared to a similar combinatorial optimization problem. In particular, when only the member length errors are considered, minimizing d(sup 2)(sub rms) is equivalent to the quadratic assignment problem. The quadratic assignment problem is a well known NP-complete problem in operations research literature. Hence minimizing d(sup 2)(sub rms) is is also an NP-complete problem. The focus of the research is the development of a simulated annealing algorithm to reduce d(sup 2)(sub rms). The plausibility of this technique is its recent success on a variety of NP-complete combinatorial optimization problems including the quadratic assignment problem. A physical analogy for simulated annealing is the way liquids freeze and crystallize. All computational experiments were done on a MicroVAX. The two interchange heuristic is very fast but produces widely varying results. The two and three interchange heuristic provides less variability in the final objective function values but runs much more slowly. Simulated annealing produced the best objective function values for every starting configuration and was faster than the two and three interchange heuristic.

Kincaid, Rex K.↗

Optimal actuator placement on an active reflector using a modified simulated annealing technique

The development of a lightweight actuation system for maintaining the surface accuracy of a composite honeycomb panel using piezoelectric actuators is discussed. A modified simulated annealing technique is used to optimize the problem with both combinatorial and continuous criteria and with inequality constraints. Near optimal solutions for the location of the actuators, using combinatorial optimization, and for the required actuator forces, employing continuous optimization, are sought by means of the modified simulated annealing technique. The actuator locations are determined by first seeking a near optimum solution using the modified simulated annealing technique. The final actuator configuration consists of an arrangement wherein the piezoelectric actuators are placed along six radial lines. Numerical results showing the achievable surface correction by means of this configuration are presented.

Kuo, Chin-Po↗

Passive MMW camera for low visibility landings

A passive, millimeter wave imaging sensor for aircraft landing in low or poor visibility conditions is described. The sensor can be incorporated in a camera for future enhanced/synthetic vision systems. Contrast is provided by differences in material reflectivities, temperature, and sky illumination of the scene being imaged. Photographic images of the system's fog penetration capabilities are presented. A combinatorial geometry technique is used to construct the scene geometries. This technique uses eight basic geometric shapes which are used as building blocks for 3-D complex-shaped objects. The building blocks are then combined via union, intersection and exclusion operations to form 3-D scene objects and the combinatorial geometry package determines ray intercepts with scene objects, providing the specific surfaces and propagation distance for the scene.

Shoucri, Merit↗

Auctioning Airport Slots?

The current allocation of slots on congested European airports constitutes an obstacle to the effective liberalisation of air transportation undertaken in Europe. With a view to favouring effluent slot utilisation and competition, as is the goal of the Euopean commission, we propose to use a market mechanism, based on temporary" utilisation licences. In order to allocate those licences, we propose and describe an iterated combinatorial auction mechanism where a percentage of licences would be reallocated each season. A secondary market would also be set up in order to reallocate slots during a season. Since a combinatorial auction involve a complex optimisation procedure, we describe how it can be made to work in the case of auctions.

Gruyer, Nicolas↗

Analyses Made to Order: Using Transformation to Rapidly Configure a Multidisciplinary Environment

Aerospace problems are highly multidisciplinary. Four or more major disciplines are involved in analyzing any particular vehicle. Moreover, the choice of implementation technology of various subsystems can lead to a change of leading domain or reformation of the driving equations. An excellent example is the change of expertise required to consider aircraft built from composite or metallic structures, or those propelled by chemical or electrical thrusters. Another example is in the major reconfiguration of handling and stability equations with different control surface configuration (e.g., canards, t-tail v four-post tail). Combinatorial problems are also commonplace anytime that a major system is to be designed. If there are only 5 attributes of a design to consider with 4 different options, this is already 1024 options. Adding just 5 more dimensions to the study explodes the space to over one million. Even generous assumptions like the idea that only 10% of the combinations are physically feasible can only contain the problem for so long. To make matters worse, the simple number of combinations is only the beginning. Combining the issue of trade space size with the need to reformulate the design problem for many of the possibilities makes life exponentially more difficult. Advances in software modeling approaches have led to the development of model-driven architecture. This approach uses the transformation of models into inferred models (e.g. inferred execution traces from state machines) or the skeletons for code generation. When the emphasis on transformation is applied to aerospace, it becomes possible to exploit redundancy in the information specified in multiple domain models into a unified system model. F1urther, it becomes possible to overcome the combinatorial nature of specifying integrated system behavior by manually combining the equations governing a given component technology. Transformations from a system specification combined with a system-analysis mapping specification enable one-click combination of domain analyses. This is a flexibility that has been missing from many engineering codes, which often entangle design specification and physical examination much more than is required to conduct the analysis. This capability has been investigated and cultivated within the DARPA F6 program by a team of JPL and Phoenix Integration engineers building the Adapatable Systems Design and Analysis (ASDA) framework. By embracing system modeling with SysML and the Query-View-Transformation (QVT) language, the ASDA team has been able to build a flexible, easily reconfigurable framework for building up and solving large tradespaces. Examples of application and lessons learned in building the framework will be described in this paper. In addition, the motivation will be laid for various tool vendors to develop open model description standards while being able to maintain competitive advantage through proprietary algorithms and approaches. These standards will also be compared to the underpinnings of model-driven architecture and the OMG standards of the Meta-Object Facility (MOF), SysML, and QVT.

Cole, Bjorn↗

Solar Proton Transport Within an ICRU Sphere Surrounded by a Complex Shield: Ray-trace Geometry

A computationally efficient 3DHZETRN code with enhanced neutron and light ion (Z is less than or equal to 2) propagation was recently developed for complex, inhomogeneous shield geometry described by combinatorial objects. Comparisons were made between 3DHZETRN results and Monte Carlo (MC) simulations at locations within the combinatorial geometry, and it was shown that 3DHZETRN agrees with the MC codes to the extent they agree with each other. In the present report, the 3DHZETRN code is extended to enable analysis in ray-trace geometry. This latest extension enables the code to be used within current engineering design practices utilizing fully detailed vehicle and habitat geometries. Through convergence testing, it is shown that fidelity in an actual shield geometry can be maintained in the discrete ray-trace description by systematically increasing the number of discrete rays used. It is also shown that this fidelity is carried into transport procedures and resulting exposure quantities without sacrificing computational efficiency.

Slaba, Tony C.↗

Disruptive Technologies and Their Putative Impacts Upon Society and Aerospace- Entering The Virtual Age

Developments in technology over the recent decades have been extraordinary. They include the IT, bio, nano, and now quantum and energetics technology arenas and their many combinatorial interactions and impacts. In the main, these are at the frontiers of the small and in a combinational, synergistic feeding frenzy with each other. They fall under the broad category of Disruptive Technologies and have greatly altered society. The outlook for the runout of these and other technology developments augers mid-term to later alterations in components of the human existence theorem, including the requirement to work for our living and our physiological makeup and longevity (Ref 1). The IT revolution began in the 1950s with the development of solid-state electronics. The biologics revolution began later in the 1960s and 1970s with DNA and genomics, and the nano revolution in the 1990s with self-forming nano systems and carbon nanotubes. Quantum technology is now developing rapidly, aided by enabling nano systems, and the energetics revolution is providing ever more efficient and less expensive renewable energy sources. The IT revolution has produced improvements of an astounding eleven orders of magnitude in computing speed since the late 1950s. As we shift from silicon to biological, optical, nano, molecular, and atomic computing, improvements of some 4 orders of magnitude are evidently possible from either optical or DNA computing [Refs 2and 3], then there are combinatorials. Then there is quantum computing, under development worldwide for an increasing number of applications and proffering phenomenal capabilities. The current fastest computers are considerably beyond human brain speed. Machine intelligence is developing well after decades of inadequate machine capability, now no longer the case, and a detour into expert systems. Researchers in machine intelligence are now pursuing deep learning approaches using neural nets, which are proving to be extremely useful. Some believe the frontier of potential human-level machine intelligence may be found in biomimetics and brain-emulation approaches. There is even a possibility of “emergence”—i.e., when the machine intelligence is complex enough that it “wakes up,” as when human intelligence emerged via evolution during the million-plus years of the hunter-gatherer epoch [ Ref 4]. In fact, some posit that human intelligence can be improved upon and is only a cul-de-sac of what is conceivable. The IT revolution has produced massive changes in human society and economics—from the Internet, enabling the rapid expansion of knowledgeability (and even what is knowable), to an increasingly pervasive trend of “tele-everything.” The extraordinary compilation, storage, and availability of truly massive amounts of information could, when combined with AI and under the mantra of “big data,” greatly improve many of our technical and commercial processes and their content including elucidating new heuristic governing laws.

Dennis M. Bushnell↗

SatNet: A Benchmark for Satellite Scheduling Optimization

Satellites provide essential services such as networking and weather tracking, and the number of near-earth and deep space satellites are expected to grow rapidly in the coming years. Communications with terrestrial ground stations is one of the critical functionalities of any space mission. Satellite scheduling is a problem that has been scientifically investigated since the 1970s. A central aspect of this problem is the need to consider resource contention and satellite visibility constraints as they require line of sight. Due to the combinatorial nature of the problem, prior solutions such as linear programs and evolutionary algorithms require extensive compute capabilities to output a feasible schedule for each scenario. Machine learning based scheduling can provide an alternative solution by training a model with historical data and generating a schedule quickly with model inference. We present SatNet, a benchmark for satellite scheduling optimization based on historical data from the NASA Deep Space Network. We propose formulation of the satellite scheduling problem as a Markov Decision Process and use reinforcement learning (RL) policies to generate schedules. The nature of constraints imposed by SatNet differ from other combinatorial optimization problems such as vehicle routing studied in prior literature. Our initial results indicate that RL is an alternative optimization approach that can generate candidate solutions of comparable quality to existing state-of-the-practice results. However, we also find that RL policies overfit to the training dataset and do not generalize well to new data, thereby necessitating continued research on reusable and generalizable agents.

Wilson, Brian↗