SEARCH · Search NASA

Results for “heuristic algorithm”

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.

SourceResearch connectionFrom yearThrough year

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

At least 181 records · Page 10

All sources NASA NTRS DOE OSTI

NASA NTRS1996

Soft-output decoding algorithms in iterative decoding of turbo codes

In this article, we present two versions of a simplified maximum a posteriori decoding algorithm. The algorithms work in a sliding window form, like the Viterbi algorithm, and can thus be used to decode continuously transmitted sequences obtained by parallel concatenated codes, without requiring code trellis termination. A heuristic explanation is also given of how to embed the maximum a posteriori algorithms into the iterative decoding of parallel concatenated codes (turbo codes). The performances of the two algorithms are compared on the basis of a powerful rate 1/3 parallel concatenated code. Basic circuits to implement the simplified a posteriori decoding algorithm using lookup tables, and two further approximations (linear and threshold), with a very small penalty, to eliminate the need for lookup tables are proposed.

Benedetto, S.↗

NASA NTRS1996

Soft-Output Decoding Algorithms in Iterative Decoding of Turbo Codes

Benedetto, S.↗

NASA NTRS1984

An on-line equivalent system identification scheme for adaptive control

A prime obstacle to the widespread use of adaptive control is the degradation of performance and possible instability resulting from the presence of unmodeled dynamics. The approach taken is to explicitly include the unstructured model uncertainty in the output error identification algorithm. The order of the compensator is successively increased by including identified modes. During this model building stage, heuristic rules are used to test for convergence prior to designing compensators. Additionally, the recursive identification algorithm as extended to multi-input, multi-output systems. Enhancements were also made to reduce the computational burden of an algorithm for obtaining minimal state space realizations from the inexact, multivariate transfer functions which result from the identification process. A number of potential adaptive control applications for this approach are illustrated using computer simulations. Results indicated that when speed of adaptation and plant stability are not critical, the proposed schemes converge to enhance system performance.

Sliwa, S. M.↗

DOE OSTI2025

Faster solutions to the interdiction defense problem using suboptimal solutions

The interdiction defense (ID) problem solves a defender-attacker-defender model where the defender and attacker share the same set of components to harden and target. Here, we build upon the best response intersection (BRI) algorithm by developing the BRI with suboptimal solutions (BRI-SS) algorithm to solve the ID problem. The BRI-SS algorithm utilizes off-the-shelf optimization solvers that return suboptimal solutions at no additional computation cost. We derive novel cuts from suboptimal solutions, reducing the number of iterations required for the algorithm to converge while maintaining optimality guarantees. We also present a heuristic that utilizes all obtained suboptimal solutions to select the next defense to evaluate at each iteration. We perform computational experiments applied to power grid interdiction on standard test cases. Our results demonstrate that the BRI-SS algorithm consistently outperforms the BRI algorithm across all test cases.

Computer science↗

NASA NTRS1974

Global parallel unification for large question-answering systems

An efficient means of storing data in a first-order predicate calculus theorem-proving system is described. The data structure is oriented for large scale question-answering (QA) systems. An algorithm is outlined which uses the data structure to unify a given literal in parallel against all literals in all clauses in the data base. The data structure permits a compact representation of data within a QA system. Some suggestions are made for heuristics which can be used to speed-up the unification algorithm in systems.

Auguston, J. G.↗

NASA NTRS2005

At-Least Version of the Generalized Minimum Spanning Tree Problem: Optimization Through Ant Colony System and Genetic Algorithms

The At-Least version of the Generalized Minimum Spanning Tree Problem (L-GMST) is a problem in which the optimal solution connects all defined clusters of nodes in a given network at a minimum cost. The L-GMST is NPHard; therefore, metaheuristic algorithms have been used to find reasonable solutions to the problem as opposed to computationally feasible exact algorithms, which many believe do not exist for such a problem. One such metaheuristic uses a swarm-intelligent Ant Colony System (ACS) algorithm, in which agents converge on a solution through the weighing of local heuristics, such as the shortest available path and the number of agents that recently used a given path. However, in a network using a solution derived from the ACS algorithm, some nodes may move around to different clusters and cause small changes in the network makeup. Rerunning the algorithm from the start would be somewhat inefficient due to the significance of the changes, so a genetic algorithm based on the top few solutions found in the ACS algorithm is proposed to quickly and efficiently adapt the network to these small changes.

Janich, Karl W.↗

DOE OSTI2024

OpenFacadeControl: enabling integration of automated facades with other building systems

Automated facades are, for the most part, still considered as separate from other building systems throughout the design, installation, commissioning, operation, and maintenance cycle. This takes place despite the fact that their energy and comfort performance are deeply interlinked with the operation of lighting and HVAC systems. Over the last two decades, research has shown that there are significant advantages from operating facades as an integrated system with the rest of the building. Nevertheless, significant barriers prevent this type of integration becoming more common. One of them is the lack of a platform that is inexpensive to implement and that easily allows the practical implementation of integrated control algorithms across fenestration and other building systems, using a variety of communications protocols. This is particularly challenging when automated facades are installed in existing buildings, where interaction with legacy building systems that were installed over the past lifetime of the building can require a high degree of interoperability. OpenFacadeControl (OFC) is an open-source controls framework aimed at unified control of facades and other building systems, including the sharing of third-party sensor information. Through leveraging the Volttron controls platform, it allows the integration of systems and sensors that are manufactured by different companies and that use different communications protocols into an ensemble that functions as a single system. OFC is designed to enable integrated control algorithms of varying degrees of complexity, ranging from simple, heuristic controls to more sophisticated approaches like model-predictive control. Use of a research version to test advanced lighting and shading strategies in a full-scale experimental testbed has demonstrated the ease of deploying advanced control solutions using OpenFacadeControl. This paper presents the structure of OpenFacadeControl and a demonstration case showing the use of OFC in laboratory tests of advanced lighting and fenestration controls that coordinated motorized shades communicating via the BACnet building communications standard and lights communicating via internet-protocol-based application programming interface (API), based on the readings of a shared light level sensor communicating via a different API.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

NASA NTRS1980

A viable suboptimal controller for robotic manipulators

A simple algebraic solution is obtained to an optimal control problem in joint space for a general robotic manipulator. Open loop and closed loop control laws are obtained. The resulting control algorithm is similar in form to a commonly used heuristic controller using cubic polynomial trajectories.

Turner, T. L.↗

NASA NTRS1987

Automatic routing module

Automatic Routing Module (ARM) is a tool to partially automate Air Launched Cruise Missile (ALCM) routing. For any accessible launch point or target pair, ARM creates flyable routes that, within the fidelity of the models, are optimal in terms of threat avoidance, clobber avoidance, and adherence to vehicle and planning constraints. Although highly algorithmic, ARM is an expert system. Because of the heuristics applied, ARM generated routes closely resemble manually generated routes in routine cases. In more complex cases, ARM's ability to accumulate and assess threat danger in three dimensions and trade that danger off with the probability of ground clobber results in the safest path around or through difficult areas. The tools available prior to ARM did not provide the planner with enough information or present it in such a way that ensured he would select the safest path.

Malin, Janice A.↗

NASA NTRS1999

Experiments on Evolving Software Models of Analog Circuits

Analog circuits are of great importance in electronic system design since the world is fundamentally analog in nature. While the amount of digital design activity far outpaces that of analog design, most digital systems require analog modules for interfacing with the external world. It was recently estimated that approximately 60% of digital application- specific integrated circuit designs incorporated analog circuits. With challenging analog circuit design problems and few analog design engineers, there are economic reasons for automating the analog design process, especially time-to-market considerations. Techniques for analog circuit design automation began appearing about two decades ago. These methods incorporated heuristics [6], knowledge bases [1], simulated annealing [5], and other algorithms. Efforts using techniques from evolutionary computation began appearing over the last few years. These include the use of genetic algorithms to select electronic component values (for example, the resistance value of a resistor), to select circuit topologies, and to design amplifiers using a limited set of canned topologies [4]. A genetic programming-based analog circuit design system has been demonstrated in which the circuit sizes, component values, and the circuit topologies are determined automatically [3]. The genetic-algorithm systems typically represent circuit structures as vectors of parameters encoded in binary strings, while the genetic programming system manipulates tree data structures.

Lohn, Jason D.↗

NASA NTRS1986

On orbital allotments for geostationary satellites

The following satellite synthesis problem is addressed: communication satellites are to be allotted positions on the geostationary arc so that interference does not exceed a given acceptable level by enforcing conservative pairwise satellite separation. A desired location is specified for each satellite, and the objective is to minimize the sum of the deviations between the satellites' prescribed and desired locations. Two mixed integer programming models for the satellite synthesis problem are presented. Four solution strategies, branch-and-bound, Benders' decomposition, linear programming with restricted basis entry, and a switching heuristic, are used to find solutions to example synthesis problems. Computational results indicate the switching algorithm yields solutions of good quality in reasonable execution times when compared to the other solution methods. It is demonstrated that the switching algorithm can be applied to synthesis problems with the objective of minimizing the largest deviation between a prescribed location and the corresponding desired location. Furthermore, it is shown that the switching heuristic can use no conservative, location-dependent satellite separations in order to satisfy interference criteria.

Gonsalvez, David J. A.↗

DOE OSTI2025

Clifford Circuit-Based Heuristic Optimization of Fermion-To-Qubit Mappings

Simulation of interacting Fermionic Hamiltonians is one of the most promising applications of quantum computers. However, the feasibility of analyzing Fermionic systems with a quantum computer hinges on the efficiency of Fermion-to-qubit mappings that encode nonlocal Fermionic degrees of freedom in local qubit degrees of freedom. While recent studies have highlighted the importance of designing Fermion-to-qubit mappings that are tailored to specific problem Hamiltonians, the methods proposed so far either are restricted to a narrow class of mappings or they use computationally expensive and unscalable brute-force search algorithms. Here, in this work, we address this challenge by designing a heuristic numerical optimization framework for Fermion-to-qubit mappings. To this end, we first translate the Fermion-to-qubit mapping problem to a Clifford circuit optimization problem and then use simulated annealing to optimize the average Pauli weight of the problem Hamiltonian. For all Fermionic Hamiltonians we have considered, the numerically optimized mappings outperform their conventional counterparts, including ternary-tree-based mappings that are known to be optimal for single creation and annihilation operators. We find that our optimized mappings yield between 15% and 40% improvements on the average Pauli weight when the simulation Hamiltonian has an intermediate level of complexity. Most remarkably, the optimized mappings improve the average Pauli weight for 6 × 6 nearest-neighbor hopping and Hubbard models by more than 40% and 20%, respectively. Surprisingly, we also find specific interaction Hamiltonians for which the optimized mapping outperforms any ternary-tree-based mapping. Our results establish heuristic numerical optimization as an effective method for obtaining mappings tailored for specific Fermionic Hamiltonian.

Hamiltonians↗

NASA NTRS2012

Mixed Integer Programming and Heuristic Scheduling for Space Communication Networks

In this paper, we propose to solve the constrained optimization problem in two phases. The first phase uses heuristic methods such as the ant colony method, particle swarming optimization, and genetic algorithm to seek a near optimal solution among a list of feasible initial populations. The final optimal solution can be found by using the solution of the first phase as the initial condition to the SQP algorithm. We demonstrate the above problem formulation and optimization schemes with a large-scale network that includes the DSN ground stations and a number of spacecraft of deep space missions.

Communication Network Scheduling↗

NASA NTRS1990

EDNA: Expert fault digraph analysis using CLIPS

Traditionally fault models are represented by trees. Recently, digraph models have been proposed (Sack). Digraph models closely imitate the real system dependencies and hence are easy to develop, validate and maintain. However, they can also contain directed cycles and analysis algorithms are hard to find. Available algorithms tend to be complicated and slow. On the other hand, the tree analysis (VGRH, Tayl) is well understood and rooted in vast research effort and analytical techniques. The tree analysis algorithms are sophisticated and orders of magnitude faster. Transformation of a digraph (cyclic) into trees (CLP, LP) is a viable approach to blend the advantages of the representations. Neither the digraphs nor the trees provide the ability to handle heuristic knowledge. An expert system, to capture the engineering knowledge, is essential. We propose an approach here, namely, expert network analysis. We combine the digraph representation and tree algorithms. The models are augmented by probabilistic and heuristic knowledge. CLIPS, an expert system shell from NASA-JSC will be used to develop a tool. The technique provides the ability to handle probabilities and heuristic knowledge. Mixed analysis, some nodes with probabilities, is possible. The tool provides graphics interface for input, query, and update. With the combined approach it is expected to be a valuable tool in the design process as well in the capture of final design knowledge.

Dixit, Vishweshwar V.↗

NASA NTRS1973

Digital processing of stereoscopic image pairs.

The problem under consideration is concerned with scene analysis during robot navigation on the surface of Mars. In this mode, the world model of the robot must be continuously updated to include sightings of new obstacles and scientific samples. In order to describe the content of a particular scene, it is first necessary to segment it into known objects. One technique for accomplishing this segmentation is by analyzing the pair of images produced by the stereoscopic cameras mounted on the robot. A heuristic method is presented for determining the range for each point in the two-dimensional scene under consideration. The method is conceptually based on a comparison of corresponding points in the left and right images of the stereo pair. However, various heuristics which are adaptive in nature are used to make the algorithm both efficient and accurate. Examples are given of the use of this so-called range picture for the purpose of scene segmentation.

Levine, M. D.↗

NASA NTRS2019

Utilizing Convolutional Neural Networks for Global Seagrass Habitat Mapping

Convolutional neural networks (CNNs) are becoming an increasingly prevalent machine learning algorithm due to their high accuracy and lack of reliance on heuristic processes. One of the major drawbacks of convolutional neural networks is their reliance on large amounts of training data in order to generate sensible results. This talk will cover how our team has utilized the strengths and overcome the weaknesses of convolutional neural networks as they apply to seagrass habitat mapping. We will share our technical CNN results over time, detail the requirements and challenges that our team overcame and explore how other teams can better incorporate a stronger seagrass component into their machine learning projects.

Convolutional↗

DOE OSTI2024

Adiabatic quantum imaginary time evolution

We introduce an adiabatic state preparation protocol which implements quantum imaginary time evolution under the Hamiltonian of the system. Unlike the original quantum imaginary time evolution algorithm, adiabatic quantum imaginary time evolution does not require quantum state tomography during its runtime and, unlike standard adiabatic state preparation, the final Hamiltonian is not the system Hamiltonian. Instead, the algorithm obtains the adiabatic Hamiltonian by integrating a classical differential equation that ensures that one follows the imaginary time evolution state trajectory. We introduce some heuristics that allow this protocol to be implemented on quantum architectures with limited resources. We explore the performance of this algorithm via classical simulations in a one-dimensional spin model and highlight essential features that determine its cost, performance, and implementability for longer times, and compare to the original quantum imaginary time evolution for ground-state preparation. More generally, our algorithm expands the range of states accessible to adiabatic state preparation methods beyond those that are expressed as ground states of simple explicit Hamiltonians. Published by the American Physical Society 2024

Hejazi, Kasra (ORCID:000000032349478X)↗

NASA NTRS1990

Empirical comparison of heuristic load distribution in point-to-point multicomputer networks

The study compared several load placement algorithms using instrumented programs and synthetic program models. Salient characteristics of these program traces (total computation time, total number of messages sent, and average message time) span two orders of magnitude. Load distribution algorithms determine the initial placement for processes, a precursor to the more general problem of load redistribution. It is found that desirable workload distribution strategies will place new processes globally, rather than locally, to spread processes rapidly, but that local information should be used to refine global placement.

Grunwald, Dirk C.↗