A heuristic algorithm for the testing of asynchronous circuits
Heuristic algorithm for computation of failures detection tests in asynchronous sequential logic circuits
Putzolu, G. R.↗
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.
Runway Operations Planning: A Two-Stage Heuristic Algorithm
The airport runway is a scarce resource that must be shared by different runway operations (arrivals, departures and runway crossings). Given the possible sequences of runway events, careful Runway Operations Planning (ROP) is required if runway utilization is to be maximized. From the perspective of departures, ROP solutions are aircraft departure schedules developed by optimally allocating runway time for departures given the time required for arrivals and crossings. In addition to the obvious objective of maximizing throughput, other objectives, such as guaranteeing fairness and minimizing environmental impact, can also be incorporated into the ROP solution subject to constraints introduced by Air Traffic Control (ATC) procedures. This paper introduces a two stage heuristic algorithm for solving the Runway Operations Planning (ROP) problem. In the first stage, sequences of departure class slots and runway crossings slots are generated and ranked based on departure runway throughput under stochastic conditions. In the second stage, the departure class slots are populated with specific flights from the pool of available aircraft, by solving an integer program with a Branch & Bound algorithm implementation. Preliminary results from this implementation of the two-stage algorithm on real-world traffic data are presented.
Anagnostakis, Ioannis↗
Exact and Heuristic Algorithms for Runway Scheduling
This paper explores the Single Runway Scheduling (SRS) problem with arrivals, departures, and crossing aircraft on the airport surface. Constraints for wake vortex separations, departure area navigation separations and departure time window restrictions are explicitly considered. The main objective of this research is to develop exact and heuristic based algorithms that can be used in real-time decision support tools for Air Traffic Control Tower (ATCT) controllers. The paper provides a multi-objective dynamic programming (DP) based algorithm that finds the exact solution to the SRS problem, but may prove unusable for application in real-time environment due to large computation times for moderate sized problems. We next propose a second algorithm that uses heuristics to restrict the search space for the DP based algorithm. A third algorithm based on a combination of insertion and local search (ILS) heuristics is then presented. Simulation conducted for the east side of Dallas/Fort Worth International Airport allows comparison of the three proposed algorithms and indicates that the ILS algorithm performs favorably in its ability to find efficient solutions and its computation times.
safe & surface operations↗
Heuristic algorithms for design of integrated monitoring of geologic carbon storage sites
Designs for Risk Evaluation and Management (DREAM) is a tool developed under the National Risk Assessment Partnership (NRAP) to enhance geologic carbon storage safety and efficiency. Using potential leakage scenarios generated externally by the users preferred history-matching approach, DREAM constructs ideal combinations of sensor locations in the right place at the right time to detect as many leaks as possible, detect them as early as possible, and minimize cost. This user-friendly tool, developed in Java, features a window-based GUI for input and a 3D visualization tool for viewing the domain space and optimized monitoring plans. DREAM's latest version accommodates real-world usage by allowing for joint optimization of wellbore point sensor placements and surface geophysics survey geometries, and by using more efficient multi-objective optimization algorithms. We show an example where, these two improvements combined allow us to support containment assurance and go from detecting 80–90 % of the potential CO 2 leakage to +99.7 %, a step-change improvement that can make the deciding difference in whether a site is suitable for geologic carbon storage. Though developed for geologic carbon storage, this tool would be equally applicable in many surface or offshore environmental monitoring projects.
58 GEOSCIENCES↗
A heuristic optimization algorithm for arranging an N page open string
Heuristic optimization algorithm for arranging N page open string
Source record↗
Generating Dominating Sets Using Locally Defined Centrality Measures
The dominating set problem has many practical applications but is well-known to be NP-hard. Therefore, there is a need for efficient heuristic algorithms, especially in applications such as ad hoc wireless networks. Most distributed algorithms proposed in the literature assume that each node has knowledge of the network structure. We propose a distributed heuristic algorithm that uses two rounds of communication, and where each node has only local information, both in terms of network structure and dominating set assignment. First, each node calculates a local centrality measure to determine whether it is part of the dominating set D. The second round guarantees D is a dominating set by adding any non-dominated nodes. We compare several centrality measures and show that the Shapley centrality, derived from the Shapley value in game theory, is theoretically motivated and performs well in practice on several synthetic and real-world networks.
Network↗
Efficient mapping algorithms for scheduling robot inverse dynamics computation on a multiprocessor system
Two efficient mapping algorithms for scheduling the robot inverse dynamics computation consisting of m computational modules with precedence relationship to be executed on a multiprocessor system consisting of p identical homogeneous processors with processor and communication costs to achieve minimum computation time are presented. An objective function is defined in terms of the sum of the processor finishing time and the interprocessor communication time. The minimax optimization is performed on the objective function to obtain the best mapping. This mapping problem can be formulated as a combination of the graph partitioning and the scheduling problems; both have been known to be NP-complete. Thus, to speed up the searching for a solution, two heuristic algorithms were proposed to obtain fast but suboptimal mapping solutions. The first algorithm utilizes the level and the communication intensity of the task modules to construct an ordered priority list of ready modules and the module assignment is performed by a weighted bipartite matching algorithm. For a near-optimal mapping solution, the problem can be solved by the heuristic algorithm with simulated annealing. These proposed optimization algorithms can solve various large-scale problems within a reasonable time. Computer simulations were performed to evaluate and verify the performance and the validity of the proposed mapping algorithms. Finally, experiments for computing the inverse dynamics of a six-jointed PUMA-like manipulator based on the Newton-Euler dynamic equations were implemented on an NCUBE/ten hypercube computer to verify the proposed mapping algorithms. Computer simulation and experimental results are compared and discussed.
Lee, C. S. G.↗
Aerial drone fleet deployment optimization with endogenous battery replacements for direct delivery of time-sensitive products
Aerial drones offer a distinct potential to reduce the delivery time and energy consumption for the delivery of time-sensitive and small products. However, there is still a need in the relevant industry to understand the performance of drone-based delivery under different business needs and drone operating conditions. We studied a drone deployment optimization problem for direct delivery of time-sensitive products with release dates to customers maintaining a specified time window. This paper presents a new mixed-integer programming model, new valid inequalities, a new greedy heuristic algorithm, and a Genetic algorithm to help business owners optimally schedule and route their drone fleet minimizing the required fleet size, the required number of additional batteries, and total energy consumption. A realistic feature of the optimization method is that instead of replacing the drone battery after each return to the depot, it keeps track of the remaining energy in the drone battery and decides on battery replacements accounting for the drone routing and the user-specified minimum required battery energy. Numerical results based on real data from drone flight tests and prepared food delivery industry provide insights into the effect of different practical drone operating parameters on the required fleet size, the required number of battery replacements, and energy consumption. Here, results demonstrate that the proposed heuristic algorithm substantially outperforms the accelerated CPLEX in runtime while sacrificing the solution quality by a small amount. Additionally, results show that using a mixed fleet of hexacopter and quadcopter drones reduces the total energy consumption by 48.52% compared to using a homogeneous fleet of only hexacopters.
Drone energy consumption↗
Scheduling Tasks In Parallel Processing
Algorithms sought to minimize time and cost of computation. Report describes research on scheduling of computations tasks in system of multiple identical data processors operating in parallel. Computational intractability requires use of suboptimal heuristic algorithms. First algorithm called "list heuristic", variation of classical list scheduling. Second algorithm called "cluster heuristic" applied to tightly coupled tasks and consists of four phases. Third algorithm called "exchange heuristic", iterative-improvement algorithm beginning with initial feasible assignment of tasks to processors and periods of time. Fourth algorithm is iterative one for optimal assignment of tasks and based on concept called "simulated annealing" because of mathematical resemblance to aspects of physical annealing processes.
Price, Camille C.↗
Quantum Gate-Model Approaches to Exact and Approximate Optimization
Many of the most challenging computational problems arising in practical applications are tackled by heuristic algorithms which have not been rigorously proven to outperform other approaches but rather have been empirically demonstrated to be effective. While quantum heuristics have been proposed since the early days of quantum computing, true empirical evaluation of the real-world performance of these algorithms is only becoming possible now as increasingly powerful quantum gate-model devices continue to come online.In this talk, I will give an overview of the NASA QuAIL team's ongoing investigation into quantum gate-model heuristic algorithms for exact and approximate optimization. In particular, we consider the performance of the Quantum Approximate Optimization Algorithm on NP-hard optimization problems, and describe algorithm parameter setting strategies for real-world quantum hardware. We then show a generalization of QAOA circuits, the Quantum Alternating Operator Ansatz, especially suitable for low-resource implementations of QAOA for problems with hard (feasibility) constraints. The talk will conclude with a discussion of research challenges, particularly for optimization and sampling applications of QAOA, and the potential of more general quantum heuristics to give advantages over classical computers.
Hadfield, Stuart↗
Task scheduling in dataflow computer architectures
Dataflow computers provide a platform for the solution of a large class of computational problems, which includes digital signal processing and image processing. Many typical applications are represented by a set of tasks which can be repetitively executed in parallel as specified by an associated dataflow graph. Research in this area aims to model these architectures, develop scheduling procedures, and predict the transient and steady state performance. Researchers at NASA have created a model and developed associated software tools which are capable of analyzing a dataflow graph and predicting its runtime performance under various resource and timing constraints. These models and tools were extended and used in this work. Experiments using these tools revealed certain properties of such graphs that require further study. Specifically, the transient behavior at the beginning of the execution of a graph can have a significant effect on the steady state performance. Transformation and retiming of the application algorithm and its initial conditions can produce a different transient behavior and consequently different steady state performance. The effect of such transformations on the resource requirements or under resource constraints requires extensive study. Task scheduling to obtain maximum performance (based on user-defined criteria), or to satisfy a set of resource constraints, can also be significantly affected by a transformation of the application algorithm. Since task scheduling is performed by heuristic algorithms, further research is needed to determine if new scheduling heuristics can be developed that can exploit such transformations. This work has provided the initial development for further long-term research efforts. A simulation tool was completed to provide insight into the transient and steady state execution of a dataflow graph. A set of scheduling algorithms was completed which can operate in conjunction with the modeling and performance tools previously developed. Initial studies on the performance of these algorithms were done to examine the effects of application algorithm transformations as measured by such quantities as number of processors, time between outputs, time between input and output, communication time, and memory size.
Katsinis, Constantine↗
Heuristic-based scheduling algorithm for high level synthesis
A new scheduling algorithm is proposed which uses a combination of a resource utilization chart, a heuristic algorithm to estimate the minimum number of hardware units based on operator mobilities, and a list-scheduling technique to achieve fast and near optimal schedules. The schedule time of this algorithm is almost independent of the length of mobilities of operators as can be seen from the benchmark example (fifth order digital elliptical wave filter) presented when the cycle time was increased from 17 to 18 and then to 21 cycles. It is implemented in C on a SUN3/60 workstation.
Mohamed, Gulam↗
A new algorithm for attitude-independent magnetometer calibration
A new algorithm is developed for inflight magnetometer bias determination without knowledge of the attitude. This algorithm combines the fast convergence of a heuristic algorithm currently in use with the correct treatment of the statistics and without discarding data. The algorithm performance is examined using simulated data and compared with previous algorithms.
Alonso, Roberto↗
Intelligent perturbation algorithms for space scheduling optimization
Intelligent perturbation algorithms for space scheduling optimization are presented in the form of the viewgraphs. The following subject areas are covered: optimization of planning, scheduling, and manifesting; searching a discrete configuration space; heuristic algorithms used for optimization; use of heuristic methods on a sample scheduling problem; intelligent perturbation algorithms are iterative refinement techniques; properties of a good iterative search operator; dispatching examples of intelligent perturbation algorithm and perturbation operator attributes; scheduling implementations using intelligent perturbation algorithms; major advances in scheduling capabilities; the prototype ISF (industrial Space Facility) experiment scheduler; optimized schedule (max revenue); multi-variable optimization; Space Station design reference mission scheduling; ISF-TDRSS command scheduling demonstration; and example task - communications check.
Kurtzman, Clifford R.↗
Benefits Assessment of Algorithmically Combining Generic High Altitude Airspace Sectors
In today's air traffic control operations, sectors that have traffic demand below capacity are combined so that fewer controller teams are required to manage air traffic. Controllers in current operations are certified to control a group of six to eight sectors, known as an area of specialization. Sector combinations are restricted to occur within areas of specialization. Since there are few sector combination possibilities in each area of specialization, human supervisors can effectively make sector combination decisions. In the future, automation and procedures will allow any appropriately trained controller to control any of a large set of generic sectors. The primary benefit of this will be increased controller staffing flexibility. Generic sectors will also allow more options for combining sectors, making sector combination decisions difficult for human supervisors. A sector-combining algorithm can assist supervisors as they make generic sector combination decisions. A heuristic algorithm for combining under-utilized air space sectors to conserve air traffic control resources has been described and analyzed. Analysis of the algorithm and comparisons with operational sector combinations indicate that this algorithm could more efficiently utilize air traffic control resources than current sector combinations. This paper investigates the benefits of using the sector-combining algorithm proposed in previous research to combine high altitude generic airspace sectors. Simulations are conducted in which all the high altitude sectors in a center are allowed to combine, as will be possible in generic high altitude airspace. Furthermore, the algorithm is adjusted to use a version of the simplified dynamic density (SDD) workload metric that has been modified to account for workload reductions due to automatic handoffs and Automatic Dependent Surveillance Broadcast (ADS-B). This modified metric is referred to here as future simplified dynamic density (FSDD). Finally, traffic demand sets with increased air traffic demand are used in the simulations to capture the expected growth in air traffic demand by the mid-term.
Bloem, Michael↗
Quantum Approximate Optimization with Hard and Soft Constraints
Challenging computational problems arising in the practical world are frequently tackled by heuristic algorithms. Small universal quantum computers will emerge in the next year or two, enabling a substantial broadening of the types of quantum heuristics that can be investigated beyond quantum annealing. The immediate question is What experiments should we prioritize that will give us insight into quantum heuristics? One leading candidate is the quantum approximate optimization algorithm (QAOA) metaheuristic. Here, we provide a framework for designing QAOA circuits for a variety of combinatorial optimization problems with both hard constraints that must be met and soft constraints whose violation we wish to minimize. We work through a number of examples, and discuss design principles and implementation considerations.
Hadfield, Stuart↗
Redundant Disk Arrays in Transaction Processing Systems
We address various issues dealing with the use of disk arrays in transaction processing environments. We look at the problem of transaction undo recovery and propose a scheme for using the redundancy in disk arrays to support undo recovery. The scheme uses twin page storage for the parity information in the array. It speeds up transaction processing by eliminating the need for undo logging for most transactions. The use of redundant arrays of distributed disks to provide recovery from disasters as well as temporary site failures and disk crashes is also studied. We investigate the problem of assigning the sites of a distributed storage system to redundant arrays in such a way that a cost of maintaining the redundant parity information is minimized. Heuristic algorithms for solving the site partitioning problem are proposed and their performance is evaluated using simulation. We also develop a heuristic for which an upper bound on the deviation from the optimal solution can be established.
Mourad, Antoine Nagib↗
Using a Portfolio of Algorithms for Planning and Scheduling
The Automated Scheduling and Planning Environment (ASPEN) software system, aspects of which have been reported in several previous NASA Tech Briefs articles, includes a subsystem that utilizes a portfolio of heuristic algorithms that work synergistically to solve problems. The nature of the synergy of the specific algorithms is that their likelihoods of success are negatively correlated: that is, when a combination of them is used to solve a problem, the probability that at least one of them will succeed is greater than the sum of probabilities of success of the individual algorithms operating independently of each other. In ASPEN, the portfolio of algorithms is used in a planning process of the iterative repair type, in which conflicts are detected and addressed one at a time until either no conflicts exist or a user-defined time limit has been exceeded. At each choice point (e.g., selection of conflict; selection of method of resolution of conflict; or choice of move, addition, or deletion) ASPEN makes a stochastic choice of a combination of algorithms from the portfolio. This approach makes it possible for the search to escape from looping and from solutions that are locally but not globally optimum.
Sherwood, Robert↗