Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “backtracking”

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 NTRS2009

Computing Bounds on Resource Levels for Flexible Plans

A new algorithm efficiently computes the tightest exact bound on the levels of resources induced by a flexible activity plan (see figure). Tightness of bounds is extremely important for computations involved in planning because tight bounds can save potentially exponential amounts of search (through early backtracking and detection of solutions), relative to looser bounds. The bound computed by the new algorithm, denoted the resource-level envelope, constitutes the measure of maximum and minimum consumption of resources at any time for all fixed-time schedules in the flexible plan. At each time, the envelope guarantees that there are two fixed-time instantiations one that produces the minimum level and one that produces the maximum level. Therefore, the resource-level envelope is the tightest possible resource-level bound for a flexible plan because any tighter bound would exclude the contribution of at least one fixed-time schedule. If the resource- level envelope can be computed efficiently, one could substitute looser bounds that are currently used in the inner cores of constraint-posting scheduling algorithms, with the potential for great improvements in performance. What is needed to reduce the cost of computation is an algorithm, the measure of complexity of which is no greater than a low-degree polynomial in N (where N is the number of activities). The new algorithm satisfies this need. In this algorithm, the computation of resource-level envelopes is based on a novel combination of (1) the theory of shortest paths in the temporal-constraint network for the flexible plan and (2) the theory of maximum flows for a flow network derived from the temporal and resource constraints. The measure of asymptotic complexity of the algorithm is O(N O(maxflow(N)), where O(x) denotes an amount of computing time or a number of arithmetic operations proportional to a number of the order of x and O(maxflow(N)) is the measure of complexity (and thus of cost) of a maximumflow algorithm applied to an auxiliary flow network of 2N nodes. The algorithm is believed to be efficient in practice; experimental analysis shows the practical cost of maxflow to be as low as O(N1.5). The algorithm could be enhanced following at least two approaches. In the first approach, incremental subalgorithms for the computation of the envelope could be developed. By use of temporal scanning of the events in the temporal network, it may be possible to significantly reduce the size of the networks on which it is necessary to run the maximum-flow subalgorithm, thereby significantly reducing the time required for envelope calculation. In the second approach, the practical effectiveness of resource envelopes in the inner loops of search algorithms could be tested for multi-capacity resource scheduling. This testing would include inner-loop backtracking and termination tests and variable and value-ordering heuristics that exploit the properties of resource envelopes more directly.

Muscvettola, Nicola↗
NASA NTRS2013

Network Penetration Testing and Research

This paper will focus the on research and testing done on penetrating a network for security purposes. This research will provide the IT security office new methods of attacks across and against a company's network as well as introduce them to new platforms and software that can be used to better assist with protecting against such attacks. Throughout this paper testing and research has been done on two different Linux based operating systems, for attacking and compromising a Windows based host computer. Backtrack 5 and BlackBuntu (Linux based penetration testing operating systems) are two different "attacker'' computers that will attempt to plant viruses and or NASA USRP - Internship Final Report exploits on a host Windows 7 operating system, as well as try to retrieve information from the host. On each Linux OS (Backtrack 5 and BlackBuntu) there is penetration testing software which provides the necessary tools to create exploits that can compromise a windows system as well as other operating systems. This paper will focus on two main methods of deploying exploits 1 onto a host computer in order to retrieve information from a compromised system. One method of deployment for an exploit that was tested is known as a "social engineering" exploit. This type of method requires interaction from unsuspecting user. With this user interaction, a deployed exploit may allow a malicious user to gain access to the unsuspecting user's computer as well as the network that such computer is connected to. Due to more advance security setting and antivirus protection and detection, this method is easily identified and defended against. The second method of exploit deployment is the method mainly focused upon within this paper. This method required extensive research on the best way to compromise a security enabled protected network. Once a network has been compromised, then any and all devices connected to such network has the potential to be compromised as well. With a compromised network, computers and devices can be penetrated through deployed exploits. This paper will illustrate the research done to test ability to penetrate a network without user interaction, in order to retrieve personal information from a targeted host.

Murphy, Brandon F.↗
DOE OSTI2023

A trailing ribosome speeds up RNA polymerase at the expense of transcript fidelity via force and allostery

In prokaryotes, translation can occur on mRNA that is being transcribed in a process called coupling. How the ribosome affects the RNA polymerase (RNAP) during coupling is not well understood. Here, we reconstituted the E. coli coupling system and demonstrated that the ribosome can prevent pausing and termination of RNAP and double the overall transcription rate at the expense of fidelity. Moreover, we monitored single RNAPs coupled to ribosomes and show that coupling increases the pause-free velocity of the polymerase and that a mechanical assisting force is sufficient to explain the majority of the effects of coupling. Also, by cryo-EM, we observed that RNAPs with a terminal mismatch adopt a backtracked conformation, while a coupled ribosome allosterically induces these polymerases toward a catalytically active anti-swiveled state. Finally, we demonstrate that prolonged RNAP pausing is detrimental to cell viability, which could be prevented by polymerase reactivation through a coupled ribosome.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2023

Inverse aqueous transport modeling for emergency response

ALGE is a three-dimensional, finite-difference aqueous transport model that simulates pollutant fate and transport in lakes, rivers, bays, and estuaries by solving the prognostic equations of mass, momentum, and energy. Its current modeling capabilities include transport of dissolved tracer for a series of predefined basins across the continental United States. Recently, an inverse method (also known as backtracking) has been added to ALGE to provide a possible source of a pollutant should one be detected by a sensor in a body of water and a source is not known. This inverse method is a three step process that uses an algorithm to inverse the flow. We demonstrate the new model’s capabilities through simulating the 2021 Piney Point spill in Tampa Bay, Florida (USA). This involves moving tracer backwards from its detection points, encompassing a potential source area, and applying Bayes’ Theorem and $\frac{𝜒}{𝑄}$ to reduce the area within which the true source could be located.

hydrological modeling↗
DOE OSTI2023

Structural basis for DNA proofreading

DNA polymerase (DNAP) can correct errors in DNA during replication by proofreading, a process critical for cell viability. However, the mechanism by which an erroneously incorporated base translocates from the polymerase to the exonuclease site and the corrected DNA terminus returns has remained elusive. Here, we present an ensemble of nine high-resolution structures representing human mitochondrial DNA polymerase Gamma, Polγ, captured during consecutive proofreading steps. The structures reveal key events, including mismatched base recognition, its dissociation from the polymerase site, forward translocation of DNAP, alterations in DNA trajectory, repositioning and refolding of elements for primer separation, DNAP backtracking, and displacement of the mismatched base into the exonuclease site. Altogether, our findings suggest a conserved ‘bolt-action’ mechanism of proofreading based on iterative cycles of DNAP translocation without dissociation from the DNA, facilitating primer transfer between catalytic sites. Functional assays and mutagenesis corroborate this mechanism, connecting pathogenic mutations to crucial structural elements in proofreading steps.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2022

Automatic derivation of many-body theories based on general Fermi vacua

This paper describes Wick&D, an implementation of the algebra of second-quantized operators normal ordered with respect to general correlated references and the corresponding Wick theorem [D. Mukherjee, Chem. Phys. Lett. 274, 561 (1997) and W. Kutzelnigg and D. Mukherjee, J. Chem. Phys. 107, 432 (1997)]. Wick&D employs a compact representation of operators and a backtracking algorithm to efficiently evaluate Wick contractions. Since Wick&D can handle both fully and partially contracted terms, it can be applied to both projective and Fock-space many-body formalisms. To demonstrate the usefulness of Wick&D, here we use it to evaluate the single-reference coupled cluster equations up to octuple excitations and report an automated derivation and implementation of the second-order driven similarity renormalization group multireference perturbation theory.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2022

RNA polymerase II trapped on a molecular treadmill: Structural basis of persistent transcriptional arrest by a minor groove DNA binder

Elongating RNA polymerase II (Pol II) can be paused or arrested by a variety of obstacles. These obstacles include DNA lesions, DNA-binding proteins, and small molecules. Hairpin pyrrole-imidazole (Py-Im) polyamides bind to the minor groove of DNA in a sequence-specific manner and induce strong transcriptional arrest. Remarkably, this Py-Im–induced Pol II transcriptional arrest is persistent and cannot be rescued by transcription factor TFIIS. In contrast, TFIIS can effectively rescue the transcriptional arrest induced by a nucleosome barrier. The structural basis of Py-Im–induced transcriptional arrest and why TFIIS cannot rescue this arrest remain elusive. Here we determined the X-ray crystal structures of four distinct Pol II elongation complexes (Pol II ECs) in complex with hairpin Py-Im polyamides as well as of the hairpin Py-Im polyamides–dsDNA complex. We observed that the Py-Im oligomer directly interacts with RNA Pol II residues, introduces compression of the downstream DNA duplex, prevents Pol II forward translocation, and induces Pol II backtracking. These results, together with biochemical studies, provide structural insight into the molecular mechanism by which Py-Im blocks transcription. Our structural study reveals why TFIIS fails to promote Pol II bypass of Py-Im–induced transcriptional arrest.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2020

Wave function analysis with a maximum flow algorithm

An efficient algorithm for computing the maximum-flow path in a network is applied to the identification of the dominant configuration state functions (CSFs) in a graphically contracted function (GCF), configuration interaction, wave function. The flow network is a space of spin-adapted CSFs represented by a Shavitt graph, wherein the nodes correspond to orbital occupations and spin quantum numbers. The graph nodes are connected by arcs, and an arc density is defined as sums of the associated squared CSF coefficients. A max-min approach determines an upper bound to the maximum possible incoming flow for each graph node. A backtracking step generates a candidate walk and is followed by a limited search of alternative branching paths for the dominant CSF. The arc density contributions are removed from the graph, and the algorithm is reapplied to the updated graph. This list of generated walks can be partitioned in order to guarantee that the dominant CSFs have been identified. All of the steps in this algorithm are computationally efficient and do not depend on the potentially large dimension of the underlying linear CSF expansion space. An analysis of low-lying valence states of C-2 illustrates the method.

74 ATOMIC AND MOLECULAR PHYSICS↗
NASA NTRS1973

QA4, a language for artificial intelligence.

Introduction of a language for problem solving and specifically robot planning, program verification, and synthesis and theorem proving. This language, called question-answerer 4 (QA4), embodies many features that have been found useful for constructing problem solvers but have to be programmed explicitly by the user of a conventional language. The most important features of QA4 are described, and examples are provided for most of the material introduced. Language features include backtracking, parallel processing, pattern matching, set manipulation, and pattern-triggered function activation. The language is most convenient for use in an interactive way and has extensive trace and edit facilities.

Derksen, J. A. C.↗
NASA NTRS1976

Injection boundary dynamics during a geomagnetic storm

A series of proton and electron injections were observed by Explorer 45 associated with several substorms during the main phase of the Feb. 24, 1972 geomagnetic storm. The 1- to 290-keV protons and 1- to 560-keV electrons were observed in the evening quadrant up to L of about 5.2. A model distorted dipole magnetic field and McIlwain's E3 convection electric field were used to backtrack the energy-dispersed electron and proton fluxes to their source at the time of injection. The source turns out to be a region extending over several earth radii outside an injection boundary. In the night magnetosphere, the inferred injection boundary is displaced inward with each successive substorm. The energy dispersion plot of the particles injected during orbit 314 indicates that as the energy of the observed particles decreases there is a smooth transition to the position of the plasmapause. This suggests that for that substorm the injection boundary and the plasmapause were one and the same. The proton 'noses' reported by Smith and Hoffman (1974) are discussed.

Konradi, A.↗
NASA NTRS1978

Path selection process utilizing rapid estimation scheme

The paper describes the use of a rapid estimation scheme for path selection by a roving vehicle. Essentially, the evaluation procedure simulates movement of the rover over each of several corridors lying radially outward from the scanning position. Two levels of corridors are used, and the path selection scheme selects the optimal primary corridor according to a dynamic programming algorithm. In the present version, the length of the corridors is variable. The rapid estimation scheme provides information to define corridor dimensions. This corridor structure, which varies as a function of the terrain, eliminates the need for backtracking, except in certain extreme cases. Computer results are promising in that obstacles were avoided while corridor lengths were kept to a maximum where safety permitted.

Ring, H.↗
NASA NTRS1985

Deviser - An AI planner for spacecraft operations

The 'Deviser III' automated spacecraft mission planner prototype can plan complete Voyager spacecraft operational sequences consisting of over 100 data capture goals, working 10-50 times faster than a human analyst. The planner generates a loop-free network of actions and events resembling a program evaluation and review technique chart. Actions, events, and inferences are the building blocks from which plans are assembled. It is noted that, for a very large spacecraft mission plan, the backtracking through remembered decision trees entailed by this artificial intelligence system can consume megabite quantities of computer memory.

Vere, S. A.↗
NASA NTRS1987

SWITCH user's manual

The planning program, SWITCH, and its surrounding changed-goal-replanning program, Runaround, are described. The evolution of SWITCH and Runaround from an earlier planner, DEVISER, is recounted. SWITCH's plan representation, and its process of building a plan by backward chaining with strict chronological backtracking, are described. A guide for writing knowledge base files is provided, as are narrative guides for installing the program, running it, and interacting with it while it is running. Some utility functions are documented. For the sake of completeness, a narrative guide to the experimental discrepancy-replanning feature is provided. Appendices contain knowledge base files for a blocksworld domain, and a DRIBBLE file illustrating the output from, and user interaction with, the program in that domain.

Source record↗
NASA NTRS1988

Space station payload operations scheduling with ESP2

The Mission Analysis Division of the Systems Analysis and Integration Laboratory at the Marshall Space Flight Center is developing a system of programs to handle all aspects of scheduling payload operations for Space Station. The Expert Scheduling Program (ESP2) is the heart of this system. The task of payload operations scheduling can be simply stated as positioning the payload activities in a mission so that they collect their desired data without interfering with other activities or violating mission constraints. ESP2 is an advanced version of the Experiment Scheduling Program (ESP) which was developed by the Mission Integration Branch beginning in 1979 to schedule Spacelab payload activities. The automatic scheduler in ESP2 is an expert system that embodies the rules that expert planners would use to schedule payload operations by hand. This scheduler uses depth-first searching, backtracking, and forward chaining techniques to place an activity so that constraints (such as crew, resources, and orbit opportunities) are not violated. It has an explanation facility to show why an activity was or was not scheduled at a certain time. The ESP2 user can also place the activities in the schedule manually. The program offers graphical assistance to the user and will advise when constraints are being violated. ESP2 also has an option to identify conflict introduced into an existing schedule by changes to payload requirements, mission constraints, and orbit opportunities.

Stacy, Kenneth L.↗
NASA NTRS1987

A database/knowledge structure for a robotics vision system

Desirable properties of robotics vision database systems are given, and structures which possess properties appropriate for some aspects of such database systems are examined. Included in the structures discussed is a family of networks in which link membership is determined by measures of proximity between pairs of the entities stored in the database. This type of network is shown to have properties which guarantee that the search for a matching feature vector is monotonic. That is, the database can be searched with no backtracking, if there is a feature vector in the database which matches the feature vector of the external entity which is to be identified. The construction of the database is discussed, and the search procedure is presented. A section on the support provided by the database for description of the decision-making processes and the search path is also included.

Dearholt, D. W.↗
NASA NTRS1990

Neural Network Solves "Traveling-Salesman" Problem

Experimental electronic neural network solves "traveling-salesman" problem. Plans round trip of minimum distance among N cities, visiting every city once and only once (without backtracking). This problem is paradigm of many problems of global optimization (e.g., routing or allocation of resources) occuring in industry, business, and government. Applied to large number of cities (or resources), circuits of this kind expected to solve problem faster and more cheaply.

Thakoor, Anilkumar P.↗
NASA NTRS1990

Space communications scheduler: A rule-based approach to adaptive deadline scheduling

Job scheduling is a deceptively complex subfield of computer science. The highly combinatorial nature of the problem, which is NP-complete in nearly all cases, requires a scheduling program to intelligently transverse an immense search tree to create the best possible schedule in a minimal amount of time. In addition, the program must continually make adjustments to the initial schedule when faced with last-minute user requests, cancellations, unexpected device failures, quests, cancellations, unexpected device failures, etc. A good scheduler must be quick, flexible, and efficient, even at the expense of generating slightly less-than-optimal schedules. The Space Communication Scheduler (SCS) is an intelligent rule-based scheduling system. SCS is an adaptive deadline scheduler which allocates modular communications resources to meet an ordered set of user-specified job requests on board the NASA Space Station. SCS uses pattern matching techniques to detect potential conflicts through algorithmic and heuristic means. As a result, the system generates and maintains high density schedules without relying heavily on backtracking or blind search techniques. SCS is suitable for many common real-world applications.

Straguzzi, Nicholas↗
NASA NTRS1992

Artificial intelligence approach to planning the robotic assembly of large tetrahedral truss structures

An assembly planner for tetrahedral truss structures is presented. To overcome the difficulties due to the large number of parts, the planner exploits the simplicity and uniformity of the shapes of the parts and the regularity of their interconnection. The planning automation is based on the computational formalism known as production system. The global data base consists of a hexagonal grid representation of the truss structure. This representation captures the regularity of tetrahedral truss structures and their multiple hierarchies. It maps into quadratic grids and can be implemented in a computer by using a two-dimensional array data structure. By maintaining the multiple hierarchies explicitly in the model, the choice of a particular hierarchy is only made when needed, thus allowing a more informed decision. Furthermore, testing the preconditions of the production rules is simple because the patterned way in which the struts are interconnected is incorporated into the topology of the hexagonal grid. A directed graph representation of assembly sequences allows the use of both graph search and backtracking control strategies.

Homemdemello, Luiz S.↗