Search NASA⌕ Search

SEARCH · Search NASA

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 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS1986

Expected performance of m-solution backtracking

This paper derives upper bounds on the expected number of search tree nodes visited during an m-solution backtracking search, a search which terminates after some preselected number m problem solutions are found. The search behavior is assumed to have a general probabilistic structure. The results are stated in terms of node expansion and contraction. A visited search tree node is said to be expanding if the mean number of its children visited by the search exceeds 1 and is contracting otherwise. It is shown that if every node expands, or if every node contracts, then the number of search tree nodes visited by a search has an upper bound which is linear in the depth of the tree, in the mean number of children a node has, and in the number of solutions sought. Also derived are bounds linear in the depth of the tree in some situations where an upper portion of the tree contracts (expands), while the lower portion expands (contracts). While previous analyses of 1-solution backtracking have concluded that the expected performance is always linear in the tree depth, the model allows superlinear expected performance.

Nicol, D. M.↗
NASA NTRS1994

Empirical results on scheduling and dynamic backtracking

At the Honeywell Technology Center (HTC), we have been working on a scheduling problem related to commercial avionics. This application is large, complex, and hard to solve. To be a little more concrete: 'large' means almost 20,000 activities, 'complex' means several activity types, periodic behavior, and assorted types of temporal constraints, and 'hard to solve' means that we have been unable to eliminate backtracking through the use of search heuristics. At this point, we can generate solutions, where solutions exist, or report failure and sometimes why the system failed. To the best of our knowledge, this is among the largest and most complex scheduling problems to have been solved as a constraint satisfaction problem, at least that has appeared in the published literature. This abstract is a preliminary report on what we have done and how. In the next section, we present our approach to treating scheduling as a constraint satisfaction problem. The following sections present the application in more detail and describe how we solve scheduling problems in the application domain. The implemented system makes use of Ginsberg's Dynamic Backtracking algorithm, with some minor extensions to improve its utility for scheduling. We describe those extensions and the performance of the resulting system. The paper concludes with some general remarks, open questions and plans for future work.

Boddy, Mark S.↗
NASA NTRS2002

Backtracking and Re-execution in the Automatic Debugging of Parallelized Programs

In this work we describe a new approach using relative debugging to find differences in computation between a serial program and a parallel version of th it program. We use a combination of re-execution and backtracking in order to find the first difference in computation that may ultimately lead to an incorrect value that the user has indicated. In our prototype implementation we use static analysis information from a parallelization tool in order to perform the backtracking as well as the mapping required between serial and parallel computations.

Matthews, Gregory↗
NASA NTRS2000

Generalizing Backtrack-Free Search: A Framework for Search-Free Constraint Satisfaction

Tractable classes of constraint satisfaction problems are of great importance in artificial intelligence. Identifying and taking advantage of such classes can significantly speed up constraint problem solving. In addition, tractable classes are utilized in applications where strict worst-case performance guarantees are required, such as constraint-based plan execution. In this work, we present a formal framework for search-free (backtrack-free) constraint satisfaction. The framework is based on general procedures, rather than specific propagation techniques, and thus generalizes existing techniques in this area. We also relate search-free problem solving to the notion of decision sets and use the result to provide a constructive criterion that is sufficient to guarantee search-free problem solving.

Jonsson, Ari K.↗
NASA NTRS2003

A Graph Based Backtracking Algorithm for Solving General CSPs

Many AI tasks can be formalized as constraint satisfaction problems (CSPs), which involve finding values for variables subject to constraints. While solving a CSP is an NP-complete task in general, tractable classes of CSPs have been identified based on the structure of the underlying constraint graphs. Much effort has been spent on exploiting structural properties of the constraint graph to improve the efficiency of finding a solution. These efforts contributed to development of a class of CSP solving algorithms called decomposition algorithms. The strength of CSP decomposition is that its worst-case complexity depends on the structural properties of the constraint graph and is usually better than the worst-case complexity of search methods. Its practical application is limited, however, since it cannot be applied if the CSP is not decomposable. In this paper, we propose a graph based backtracking algorithm called omega-CDBT, which shares merits and overcomes the weaknesses of both decomposition and search approaches.

Pang, Wanlin↗
NASA NTRS2005

A Constraint-Based Planner for Data Production

This paper presents a graph-based backtracking algorithm designed to support constrain-tbased planning in data production domains. This algorithm performs backtracking at two nested levels: the outer- backtracking following the structure of the planning graph to select planner subgoals and actions to achieve them and the inner-backtracking inside a subproblem associated with a selected action to find action parameter values. We show this algorithm works well in a planner applied to automating data production in an ecological forecasting system. We also discuss how the idea of multi-level backtracking may improve efficiency of solving semi-structured constraint problems.

Pang, Wanlin↗
NASA NTRS1988

A flexible search strategy for production systems

Most problems considered to be solvable by expert systems have very large search space. It is imperative to use efficient search strategy in expert system tools. Thus, OPS5 uses a kind of hill climbing which is very efficient. However, hill climbing is inadequate for many problems because it is one of the least dependable search strategies. In order to make the search efficient and adequate one can: (1) adopt best-first search instead of hill climbing, or (2) modify hill climbing with intelligent backtracking. The second alternative is adopted. It is implemented in a production system called PRO2 embedded in C running on UNIX. It is called hill tracking. It is a general purpose tool for developing expert systems. This is a rule based production system with an effective, intelligent and flexible backtracking control mechanism, which makes the system more dependable. The advantages and disadvantages of PRO2 are discussed.

Dey, Pradip↗
NASA NTRS1988

The scheduling techniques of ESP2

The Mission Analysis Division of the Systems Analysis and Integration Laboratory at the Marshall Space Flight Center has developed a robust automatic scheduler which can produce detailed schedules for the multi-step activities required for payload operations on the Space Station. This scheduler, a part of the Expert Scheduling Program (ESP2), has five components: the bookkeeper, checker, loader, selector, and explainer. The bookkeeper maintains the usage profiles for nondepletable resources, consumables, equipment, crew, and the times of all the steps for the payload activities for several different schedules simultaneously. The checker searches the data maintained by the bookkeeper and finds times when the constraints of each step of an activity are satisfied. The loader is an expert system that uses the techniques of forward chaining, depth-first searching, and backtracking to manage the workings of the checker so that activities are placed in the schedule without violating constraints (such as crew, resources, and orbit opportunities). The checker searches the data maintained by the bookkeeper and finds times when the constraints of each step of an activity are satisfied. The loader is an expert system which uses the techniques of forward chaining, depth-first searching, and backtracking to manage the workings of the checker so that activities are placed in the schedule without violating the constraints. The selector has several methods of choosing the next activity for the loader to schedule. The explainer shows the user why an activity was or was not scheduled at a certain time; it offers a unique graphical explanation of how the expert system (the loader) works.

Jaap, John P.↗
NASA NTRS1992

Learning Impasses in Problem Solving

Problem Solving systems customarily use backtracking to deal with obstacles that they encounter in the course of trying to solve a problem. This paper outlines an approach in which the possible obstacles are investigated prior to the search for a solution. This provides a solution strategy that avoids backtracking.

Hodgson, J. P. E.↗
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.↗
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.↗