Engineering Papers⌕ Search

SEARCH · Engineering Papers

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.

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

At least 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS1990

Real-time adaptive aircraft scheduling

One of the most important functions of any air traffic management system is the assignment of ground-holding times to flights, i.e., the determination of whether and by how much the take-off of a particular aircraft headed for a congested part of the air traffic control (ATC) system should be postponed in order to reduce the likelihood and extent of airborne delays. An analysis is presented for the fundamental case in which flights from many destinations must be scheduled for arrival at a single congested airport; the formulation is also useful in scheduling the landing of airborne flights within the extended terminal area. A set of approaches is described for addressing a deterministic and a probabilistic version of this problem. For the deterministic case, where airport capacities are known and fixed, several models were developed with associated low-order polynomial-time algorithms. For general delay cost functions, these algorithms find an optimal solution. Under a particular natural assumption regarding the delay cost function, an extremely fast (O(n ln n)) algorithm was developed. For the probabilistic case, using an estimated probability distribution of airport capacities, a model was developed with an associated low-order polynomial-time heuristic algorithm with useful properties.

Kolitz, Stephan E.↗
NASA NTRS2011

Meta-RaPS Algorithm for the Aerial Refueling Scheduling Problem

The Aerial Refueling Scheduling Problem (ARSP) can be defined as determining the refueling completion times for each fighter aircraft (job) on multiple tankers (machines). ARSP assumes that jobs have different release times and due dates, The total weighted tardiness is used to evaluate schedule's quality. Therefore, ARSP can be modeled as a parallel machine scheduling with release limes and due dates to minimize the total weighted tardiness. Since ARSP is NP-hard, it will be more appropriate to develop a ppro~imate or heuristic algorithm to obtain solutions in reasonable computation limes. In this paper, Meta-Raps-ATC algorithm is implemented to create high quality solutions. Meta-RaPS (Meta-heuristic for Randomized Priority Search) is a recent and promising meta heuristic that is applied by introducing randomness to a construction heuristic. The Apparent Tardiness Rule (ATC), which is a good rule for scheduling problems with tardiness objective, is used to construct initial solutions which are improved by an exchanging operation. Results are presented for generated instances.

Kaplan, Sezgin↗
NASA NTRS1991

Parallel algorithms for placement and routing in VLSI design

The computational requirements for high quality synthesis, analysis, and verification of very large scale integration (VLSI) designs have rapidly increased with the fast growing complexity of these designs. Research in the past has focused on the development of heuristic algorithms, special purpose hardware accelerators, or parallel algorithms for the numerous design tasks to decrease the time required for solution. Two new parallel algorithms are proposed for two VLSI synthesis tasks, standard cell placement and global routing. The first algorithm, a parallel algorithm for global routing, uses hierarchical techniques to decompose the routing problem into independent routing subproblems that are solved in parallel. Results are then presented which compare the routing quality to the results of other published global routers and which evaluate the speedups attained. The second algorithm, a parallel algorithm for cell placement and global routing, hierarchically integrates a quadrisection placement algorithm, a bisection placement algorithm, and the previous global routing algorithm. Unique partitioning techniques are used to decompose the various stages of the algorithm into independent tasks which can be evaluated in parallel. Finally, results are presented which evaluate the various algorithm alternatives and compare the algorithm performance to other placement programs. Measurements are presented on the parallel speedups available.

Brouwer, Randall Jay↗
NASA NTRS1988

A parallel row-based algorithm with error control for standard-cell replacement on a hypercube multiprocessor

A new row-based parallel algorithm for standard-cell placement targeted for execution on a hypercube multiprocessor is presented. Key features of this implementation include a dynamic simulated-annealing schedule, row-partitioning of the VLSI chip image, and two novel new approaches to controlling error in parallel cell-placement algorithms; Heuristic Cell-Coloring and Adaptive (Parallel Move) Sequence Control. Heuristic Cell-Coloring identifies sets of noninteracting cells that can be moved repeatedly, and in parallel, with no buildup of error in the placement cost. Adaptive Sequence Control allows multiple parallel cell moves to take place between global cell-position updates. This feedback mechanism is based on an error bound derived analytically from the traditional annealing move-acceptance profile. Placement results are presented for real industry circuits and the performance is summarized of an implementation on the Intel iPSC/2 Hypercube. The runtime of this algorithm is 5 to 16 times faster than a previous program developed for the Hypercube, while producing equivalent quality placement. An integrated place and route program for the Intel iPSC/2 Hypercube is currently being developed.

Sargent, Jeff Scott↗
NASA NTRS1989

Characterization of robotics parallel algorithms and mapping onto a reconfigurable SIMD machine

The kinematics, dynamics, Jacobian, and their corresponding inverse computations are six essential problems in the control of robot manipulators. Efficient parallel algorithms for these computations are discussed and analyzed. Their characteristics are identified and a scheme on the mapping of these algorithms to a reconfigurable parallel architecture is presented. Based on the characteristics including type of parallelism, degree of parallelism, uniformity of the operations, fundamental operations, data dependencies, and communication requirement, it is shown that most of the algorithms for robotic computations possess highly regular properties and some common structures, especially the linear recursive structure. Moreover, they are well-suited to be implemented on a single-instruction-stream multiple-data-stream (SIMD) computer with reconfigurable interconnection network. The model of a reconfigurable dual network SIMD machine with internal direct feedback is introduced. A systematic procedure internal direct feedback is introduced. A systematic procedure to map these computations to the proposed machine is presented. A new scheduling problem for SIMD machines is investigated and a heuristic algorithm, called neighborhood scheduling, that reorders the processing sequence of subtasks to reduce the communication time is described. Mapping results of a benchmark algorithm are illustrated and discussed.

Lee, C. S. G.↗
DOE OSTI2026

A Hierarchical Optimization Method for Electric Vertical Takeoff and Landing Aircraft Network Design

Electric vertical takeoff and landing aircraft (eVTOLs) are expected to serve urban air mobility in a station-to-station configuration, which makes the optimal network design of eVTOL stations a critical question to explore. Existing approaches often face limitations, such as the inability to interact station locations with demand or difficulty in finding the optimal solution for large study regions. Here, this paper first proposes a mathematical model to generate optimal eVTOL station locations while considering associated potential eVTOL demand, and then proposes a heuristic algorithm, Hierarchical Optimization MEthod (HOME), to efficiently solve the model. With a case study of Southern California, HOME was compared to 1) directly solving the original integer linear programming-based network design problem, and 2) employing the widely used genetic algorithm. Results suggest that HOME can find optimal solutions with limited computational resources. The proposed framework powered by HOME provides a computationally efficient way to support urban air mobility planning.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Semiglobal Safety-Filtered Extremum Seeking With Unknown CBFs

We introduce a safe extremum-seeking (Safe ES) algorithm which achieves the minimization of an unknown objective function while ensuring that an unknown, yet measured, control barrier function (CBF) remains above an arbitrarily small negative value for all time. In other words, “practical safety” is maintained during the entire period of convergence to the constrained extremum. Our design is based on quadratic program (QP) CBF style filters for safety, which is applied in an average and estimated sense. Using nonsmooth analysis tools, we guarantee semiglobal practical asymptotic (SPA) stability of the global constrained optimum, practical convergence to the safe set if starting in a condition violating the CBF, and practical safety for all time—semiglobally—if starting in safe set. The safety result of the paper is analogous with modern notions of SPA stability, guaranteeing that, for any small violation of safety, there exist design coefficients which guarantee that such a small violation is not exceeded. The paper outlines a set of sufficient conditions on the barrier and objective functions, and by way of a Lyapunov argument, we demonstrate that nonconvex constrained optimization problems can be solved. We present these results in the setting of a static map and a dynamical system. A simulation example illustrates the results.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

FedEFsz: Fair Cross-Silo Federated Learning System With Error-Bounded Lossy Compression

Cross-Silo federated learning systems have been identified as an efficient approach to scaling DNN training across geographically-distributed data silos to preserve the privacy of the training data. Communication efficiency and fairness are two major issues that need to be both satisfied when federated learning systems are deployed in practice. Simultaneously guaranteeing both of them, however, is exceptionally difficult because simply combining communication reduction and fairness optimization approaches often causes non-converged training or drastic accuracy degradation. Here, to bridge this gap, we propose FedEFsz. On the one hand, it integrates the state-of-the-art error-bounded lossy compressor SZ3 into cross-silo federated learning systems to significantly reduce communication traffic during the training. On the other hand, it achieves a high fairness (i.e., rather consistent model accuracy and performance across different clients) through a carefully designed heuristic algorithm that can tune the error-bound of SZ3 for different clients during the training. Extensive experimental results based on a GPU cluster with 65 GPU cards show that FedEFsz improves the fairness across different benchmarks by up to 60.88% and meanwhile reduces the communication traffic by up to 315×.

Cross-Silo Federated Learning Systems↗
DOE OSTI2025

Extending High-Level Synthesis with AI/ML Methods

Artificial Intelligence (AI) and Machine Learning (ML) methods provide significant opportunities of improving quality of results when performing high-level synthesis (HLS). For example, they can be used to model and predict metrics of the final design (e.g., area, considering aspects such as interconnect overhead for different device technologies), facilitating exploration when searching for the best design trade-offs. They can also enable identifying hidden correlations across the various phases of the synthesis and the various optimizations performed, identifying the most effective pipelines. Finally, in more general terms, bio-inspired heuristic algorithms can improve the design space exploration for the synthesis process in terms of time and quality of the result. This paper discusses opportunities and challenges to augment HLS with AI/ML using as example flow the SODA Synthesizer, an open-source hardware generation toolchain which includes SODA-OPT, a hardware/software partitioning and pre-optimization tool developed with the MLIR framework, and PandA-Bambu, a state-of-the art HLS tool. SODA interfaces with OpenROAD to provide a complete end-to-end toolchain.

artificial intelligence↗
DOE OSTI2024

Teko Usage in Aria

Demonstration of Teko preconditioning capability in Aria. Proposed future development work to aid preconditioner selection via simple heuristic algorithms is presented. Some highlight applications of Teko are included. These contain brief physics descriptions, solver performance, and solver convergence information details. Notably, no geometric information or otherwise sensitive information is provided.

Phillips, Malachi↗
NASA NTRS1972

Techniques for generating highly reliable redundant systems.

A simple heuristic algorithm for designing highly reliable modularly redundant computer systems under complexity constraints is presented. The technique, which produces near optimal solutions, is intuitively appealing and easy to apply. The algorithms performance is shown to compare very well with the optimal solution obtained via a computerized model for dynamic programming.

White, J. B.↗
NASA NTRS1973

Automated thematic mapping and change detection of ERTS-A images

The author has identified the following significant results. For the recognition of terrain types, spatial signatures are developed from the diffraction patterns of small areas of ERTS-1 images. This knowledge is exploited for the measurements of a small number of meaningful spatial features from the digital Fourier transforms of ERTS-1 image cells containing 32 x 32 picture elements. Using these spatial features and a heuristic algorithm, the terrain types in the vicinity of Phoenix, Arizona were recognized by the computer with a high accuracy. Then, the spatial features were combined with spectral features and using the maximum likelihood criterion the recognition accuracy of terrain types increased substantially. It was determined that the recognition accuracy with the maximum likelihood criterion depends on the statistics of the feature vectors. Nonlinear transformations of the feature vectors are required so that the terrain class statistics become approximately Gaussian. It was also determined that for a given geographic area the statistics of the classes remain invariable for a period of a month but vary substantially between seasons.

Gramenopoulos, N.↗
NASA NTRS1986

Engineering calculations for communications satellite systems planning

Observed solution times were analyzed for the extended gradient and cyclic coordinate search procedures. The times used in the analysis come from computer runs made during a previously-reported experiment conducted to assess the quality of the solutions to a BSS synthesis problem found by the two search methods. The results of a second experiment with a Fixed Satellite Service (FSS) test problem are also presented. Computational results are summarized for mixed integer programming approaches for solving FSS synthesis problems. A promising heuristic algorithm is described. A synthesis model is discussed for orbital arc allotment optimization. Research plans for the near future are also presented.

Reilly, C. H.↗
NASA NTRS1987

Optimal placement of excitations and sensors for verification of large dynamical systems

The computationally difficult problem of the optimal placement of excitations and sensors to maximize the observed measurements is studied within the framework of combinatorial optimization, and is solved numerically using a variation of the simulated annealing heuristic algorithm. Results of numerical experiments including a square plate and a 960 degrees-of-freedom Control of Flexible Structure (COFS) truss structure, are presented. Though the algorithm produces suboptimal solutions, its generality and simplicity allow the treatment of complex dynamical systems which would otherwise be difficult to handle.

Salama, M.↗
NASA NTRS1987

Range and mission scheduling automation using combined AI and operations research techniques

Ground-based systems for Satellite Command, Control, and Communications (C3) operations require a method for planning, scheduling and assigning the range resources such as: antenna systems scattered around the world, communications systems, and personnel. The method must accommodate user priorities, last minute changes, maintenance requirements, and exceptions from nominal requirements. Described are computer programs which solve 24 hour scheduling problems, using heuristic algorithms and a real time interactive scheduling process.

Arbabi, Mansur↗
NASA NTRS1989

Error control techniques for satellite and space communications

The performance of bandwidth efficient trellis codes on channels with phase jitter, or those disturbed by jamming and impulse noise is analyzed. An heuristic algorithm for construction of bandwidth efficient trellis codes with any constraint length up to about 30, any signal constellation, and any code rate was developed. Construction of good distance profile trellis codes for sequential decoding and comparison of random coding bounds of trellis coded modulation schemes are also discussed.

Costello, Daniel J., Jr.↗
NASA NTRS1987

Scheduling periodic jobs using imprecise results

One approach to avoid timing faults in hard, real-time systems is to make available intermediate, imprecise results produced by real-time processes. When a result of the desired quality cannot be produced in time, an imprecise result of acceptable quality produced before the deadline can be used. The problem of scheduling periodic jobs to meet deadlines on a system that provides the necessary programming language primitives and run-time support for processes to return imprecise results is discussed. Since the scheduler may choose to terminate a task before it is completed, causing it to produce an acceptable but imprecise result, the amount of processor time assigned to any task in a valid schedule can be less than the amount of time required to complete the task. A meaningful formulation of the scheduling problem must take into account the overall quality of the results. Depending on the different types of undesirable effects caused by errors, jobs are classified as type N or type C. For type N jobs, the effects of errors in results produced in different periods are not cumulative. A reasonable performance measure is the average error over all jobs. Three heuristic algorithms that lead to feasible schedules with small average errors are described. For type C jobs, the undesirable effects of errors produced in different periods are cumulative. Schedulability criteria of type C jobs are discussed.

Chung, Jen-Yao↗
NASA NTRS1990

Balancing Loads Among Parallel Data Processors

Heuristic algorithm minimizes amount of memory used by multiprocessor system. Distributes load of many identical, short computations among multiple parallel digital data processors, each of which has its own (local) memory. Each processor operates on distinct and independent set of data in larger shared memory. As integral part of load-balancing scheme, total amount of space used in shared memory minimized. Possible applications include artificial neural networks or image processors for which "pipeline" and vector methods of load balancing inappropriate.

Baffes, Paul Thomas↗