SEARCH · Engineering Papers

Results for “Capacity Analysis”

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 847 records · Page 47

All sources NASA NTRS DOE OSTI

NASA NTRS2008

Preliminary Analysis for an Optimized Oil-Free Rotorcraft Engine Concept

Recent developments in gas foil bearing technology have led to numerous advanced high-speed rotating system concepts, many of which have become either commercial products or experimental test articles. Examples include Oil-Free microturbines, motors, generators and turbochargers. The driving forces for integrating gas foil bearings into these high-speed systems are the benefits promised by removing the oil lubrication system. Elimination of the oil system leads to reduced emissions, increased reliability, and decreased maintenance costs. Another benefit is reduced power plant weight. For rotorcraft applications, this would be a major advantage, as every pound removed from the propulsion system results in a payload benefit. Implementing foil gas bearings throughout a rotorcraft gas turbine engine is an important long-term goal that requires overcoming numerous technological hurdles. Adequate thrust bearing load capacity and potentially large gearbox applied radial loads are among them. However, by replacing the turbine end, or hot section, rolling element bearing with a gas foil bearing many of the above benefits can be realized. To this end, engine manufacturers are beginning to explore the possibilities of hot section gas foil bearings in propulsion engines. This paper presents a logical follow-on activity by analyzing a conceptual rotorcraft engine to determine the feasibility of a foil bearing supported core. Using a combination of rotordynamic analyses and a load capacity model, it is shown to be reasonable to consider a gas foil bearing core section.

Howard, Samuel A.↗

NASA NTRS1976

Environmental parameters of the Tennessee River in Alabama. 2: Physical, chemical, and biological parameters

Physical, chemical and biological water quality data from five sites in the Tennessee River, two in Guntersville Reservoir and three in Wheeler Reservoir were correlated with climatological data for three annual cycles. Two of the annual cycles are for the years prior to the Browns Ferry Nuclear Power Plant operations and one is for the first 14 months of Plant operations. A comparison of the results of the annual cycles indicates that two distinct physical conditions in the reservoirs occur, one during the warm months when the reservoirs are at capacity and one during the colder winter months when the reservoirs have been drawn-down for water storage during the rainy months and for weed control. The wide variations of physical and chemical parameters to which the biological organisms are subjected on an annual basis control the biological organisms and their population levels. A comparison of the parameters of the site below the Power plant indicates that the heated effluent from the plant operating with two of the three reactors has not had any effect on the organisms at this site. Recommendations given include the development of prediction mathematical models (statistical analysis) for the physical and chemical parameters under specific climatological conditions which affect biological organisms. Tabulated data of chemical analysis of water and organism populations studied is given.

Rosing, L. M.↗

NASA NTRSDate not supplied

Decision Aid for Conjunction Risk Mitigation by Differential Drag

In the previous five years, the rate of conjunctions that the NASA Conjunction Assessment Risk Analysis (CARA) team processed and analyzed has more than tripled. (NASA CARA, 2024) New missions in the early development phases are now required to plan for dealing with conjunctions under the present space environment, and also projecting forward into a future likely with even further increased utilization of the space environment. Some missions are investigating the possibility of using differential drag to remediate conjunctions without expending limited fuel or for missions without propulsive capabilities. The NASA CARA team studied the historical record of conjunctions to evaluate the circumstances under which differential drag may be successfully applied and have developed a series of tables to use as a decision aid for missions considering differential drag. Currently, if a CARA-protected mission with maneuvering capabilities is predicted to have a conjunction with probability of collision (Pc) greater than 7E-5 (the default value of the ‘yellow threshold’, which may have some other value agreed by CARA and the mission during the Orbital Collison Avoidance Planning (OCAP) process), CARA will use its Maneuver Trade Space (MTS) tool to evaluate and recommend options for the timing and magnitude of a risk mitigation maneuver (RMM), based on the mission’s capabilities. If the conjunction’s Pc is greater than 1E-4, the ‘red threshold’, then an RMM must be executed per NASA Procedural Requirements (NPR) 8079.1 (NASA, 2023), although missions may execute an RMM even if the Pc is lower. The magnitude of the maneuver is typically a few cm/s, and CARA estimates how many will be required for the mission’s nominal lifetime – typically a few per year – during the OCAP process, to inform the mission’s delta-V requirement. For traditional satellites, this is usually smaller than other requirements for orbit insertion, maintenance, and disposal, but for CubeSats or other small satellite missions, a propulsion system may not provide much more than a few cm/s of delta-V or may not fit at all within the available budget of money, time, size, weight, and/or power (SWaP). Conversely, CubeSats often have deployable solar panels, which offer the capacity to have much higher areas facing some directions than others. Such a mission can instead use ‘differential drag’ to remediate a conjunction -- in other words, change its drag area (usually increasing) to deviate from the predicted collision course. This is how Planet’s Dove spacecraft maintain their formations and remediate conjunction risks without having on-board propulsion (Foster, et al., 2017) (Griffith, et al., 2021). CARA has been developing improvements to MTS to support differential-drag for NASA's missions -- where it is effective. CARA records all conjunctions of their protected payloads, with historical records starting in 2005 (with significant conjunction events starting to occur on or after 2013). From this record, approximately 7,300 had a Pc greater than 1E-4 at 3 days prior to the time of closest approach, the time analyzed for differential drag efficacy. Of those, approximately 4,300 had fully-defined covariance matrices stored for both the primary and secondary objects; this set of conjunctions is the basis for the analysis of this work. CARA’s MTS tool was used to propagate the primary satellite forward from that decision point with varying degrees of increase to ballistic coefficient (BC). Because these conjunctions came from multiple missions, the nondimensional ‘delta-BC’ factor was used to quantify and normalize the increase in ballistic coefficient, defined as follows: Delta-BC = BC_new / BC_old - 1 Positive delta-BC factors represent an increase in drag compared to the nominal attitude, while negative delta-BC factors (to a minimum of -1) represent a decrease in drag. At the conclusion of the differential-drag ‘maneuver’, the Pc was recalculated to evaluate whether or not the conjunction was mitigated (Pc < 3E-6). These results were then binned and sorted along several axes, including altitude, amount of delta-BC, and (pre-maneuver) rate of energy dissipation (EDR), to identify underlying patterns. The altitude plot is shown in Figure 1. To validate this analysis, we consulted the record of a NASA mission which uses differential drag to maintain its orbit and remediate conjunction risk. CARA’s empirical record of the mission’s orbit history suggests it achieves a delta-BC of 2.2. Of the twenty-one RMM plans that were submitted by this mission, eighteen were matched with conjunctions in the historical record; of those, twelve were successfully remediated (final measured Pc < 3E-6), and six were not. This is consistent with the expected efficacy for missions orbiting at that altitude. We are presently simulating this mission’s RMMs with MTS; this work is ongoing, but so far, the MTS results are qualitatively in agreement with the empirical results -- correctly predicting that a maneuver would or would not remediate a conjunction, if not exactly matching the final post-remediation Pc value. We found that differential drag was most successful for satellites with perigees below 560 km, and which could adopt an average delta-BC of 2 or greater (that is, increasing their ballistic coefficient by a factor of 3). However, this is a difficult threshold for a mission to clear; very few spacecraft are capable of adopting a high-drag configuration for 72 hours continuously. Planet’s Dove spacecraft use differential drag to remediate conjunctions (Griffith, et al., 2021), and they have a maximum delta-BC factor of 9, but in practice (with mission and charging constraints) they achieve a time-averaged delta-BC that is closer to 2 (Foster, et al., 2017). A mission’s differential drag utility strongly depends on the operational constraints that has the capacity to limit the time-averaged delta-BC. A mission with a high maximum delta-BC of 5 or more can have an effective delta-BC of less than 1 due to operational constraints such as instrument and solar panel pointing, especially if this constraint results in holding an intermediate drag value for most of its orbit. CARA has developed tables that can be used as decision aids to advise missions-in-development about the best way to utilize their differential drag capabilities. For missions below 560 km with the operational flexibility to devote multiple days to holding a high-drag configuration (or a sufficiently high drag ratio to compensate for limitations on that time), they are -- more likely than not -- able to successfully remediate high-risk conjunctions. Conversely, missions that do not meet these exacting criteria -- most missions -- can instead be advised to use on-board propulsion systems to perform RMMs, or to turn their minimum-area face towards the approach vector, thereby reducing Pc at the moment of conjunction due to the decreased Hard-Body Radius (HBR), that is a strongly correlated variable in the Pc calculations. (NASA, 2023)

conjunction assessment↗

NASA NTRS2003

Robonaut: a robot designed to work with humans in space

The Robotics Technology Branch at the NASA Johnson Space Center is developing robotic systems to assist astronauts in space. One such system, Robonaut, is a humanoid robot with the dexterity approaching that of a suited astronaut. Robonaut currently has two dexterous arms and hands, a three degree-of-freedom articulating waist, and a two degree-of-freedom neck used as a camera and sensor platform. In contrast to other space manipulator systems, Robonaut is designed to work within existing corridors and use the same tools as space walking astronauts. Robonaut is envisioned as working with astronauts, both autonomously and by teleoperation, performing a variety of tasks including, routine maintenance, setting up and breaking down worksites, assisting crew members while outside of spacecraft, and serving in a rapid response capacity.

Man-Machine Systems↗

NASA NTRS2010

Instrument for Analysis of Greenland's Glacier Mills

A new instrument is used to study the inner workings of Greenland s glacier mills by riding the currents inside a glacier s moulin. The West Greenland Moulin Explorer instrument was deployed into a tubular shaft to autonomously record temperature, pressure, 3D acceleration, and location. It is built with a slightly positive buoyancy in order to assist in recovery. The unit is made up of several components. A 3-axis MEMS (microelectromechanical systems) accelerometer with 0.001-g resolution forms the base of the unit. A pressure transducer is added that is capable of withstanding 500 psi (=3.4 MPa), and surviving down to -40 C. An Iridium modem sends out data every 10 minutes. The location is traced by a GPS (Global Positioning System) unit. This GPS unit is also used for recovery after the mission. Power is provided by a high-capacity lithium thionyl chloride D-sized battery. The accelerometer is housed inside a cylindrical, foot-long (=30 cm) polyvinyl chloride (PVC) shell sealed at each end with acrylic. The pressure transducer is attached to one of these lids and a MEMS accelerometer to the other, recording 100 samples per second per axis.

Behar, Alberto E.↗

NASA NTRS1999

High Pressure Water Stripping Using Multi-Orifice Nozzles

The use of multi-orifice rotary nozzles greatly increases the speed and stripping effectiveness of high pressure water blasting systems, but also greatly increases the complexity of selecting and optimizing the operating parameters. The rotational speed of the nozzle must be coupled with its transverse velocity as it passes across the surface of the substrate being stripped. The radial and angular positions of each orifice must be included in the analysis of the nozzle configuration. Orifices at the outer edge of the nozzle head move at a faster rate than the orifices located near the center. The energy transmitted to the surface from the impact force of the water stream from an outer orifice is therefore spread over a larger area than energy from an inner orifice. Utilizing a larger diameter orifice in the outer radial positions increases the total energy transmitted from the outer orifice to compensate for the wider distribution of energy. The total flow rate from the combination of all orifices must be monitored and should be kept below the pump capacity while choosing orifice to insert in each position. The energy distribution from the orifice pattern is further complicated since the rotary path of all the orifices in the nozzle head pass through the center section. All orifices contribute to the stripping in the center of the path while only the outer most orifice contributes to the stripping at the edge of the nozzle. Additional orifices contribute to the stripping from the outer edge toward the center section. With all these parameters to configure and each parameter change affecting the others, a computer model was developed to track and coordinate these parameters. The computer simulation graphically indicates the cumulative affect from each parameter selected. The result from the proper choices in parameters is a well designed, highly efficient stripping system. A poorly chosen set of parameters will cause the nozzle to strip aggressively in some areas while leaving the coating untouched in adjacent sections. The high pressure water stripping system can be set to extremely aggressive conditions allowing stripping of hard to remove adhesives, paint systems, and even cladding and chromate conversion coatings. The energy force can also be reduced to strip coatings from thin aluminum substrates without causing any damage or deterioration to the substrate's surface. High pressure water stripping of aerospace components has thus proven to be an efficient and cost effective method for cleaning and removing coatings.

Hoppe, David↗

NASA NTRS2000

Synthesis of Single Wall Carbon Nanotubes by Plasma Arc: Role of Plasma Parameters

Single wall carbon nanotubes (SWNT) are porous objects on the molecular scale and have a low density, which gives them potential applications as adsorbent for molecular hydrogen. Their H2 absorption capacity published in the literature varies from 4 to 10% by mass according to the purity of the materials and storage conditions. Optimization of production methods of SWNTs should permit improving these new materials for storage of hydrogen. In this article, we show the potential of using SWNTs in hydrogen storage. In particular, we pose problems associated with synthesis, purification, and opening up of the nanotubes. We present an electric arc process currently used at laboratory scale to produce single wall carbon nanotubes. We discuss, in particular, operating conditions that permit growth of nanotubes and some plasma parameters that assure control of the material. Analysis of the process is carried out with the aid of local measurements of temperature and scanning and transmission electron microscopy of the materials.

Farhart, Samir↗

NASA NTRS1998

Short Haul Civil Tiltrotor Study in MIDAS: Auto versus Manual Nacelle Procedures for Commanded Go-Around

Tiltrotor aircraft combine the speed and range of a turboprop performance with the ability to take off and land in a vertical mode like a helicopter. These aircraft will transport passengers from city center to city center and from satellite airports to major hub airports to make connections to long range travel. The Short Haul Civil Tiltrotor (SH(CT)) being studied by NASA is a concept 40 passenger civil tiltrotor (CTR) transport. The Man-machine Integration Design and Analysis System (MIDAS) was used to evaluate human performance in terms of crew procedures and pilot workload for a simulated 40 passenger Civil Tiltrotor Transport on a steep approach to a vertiport. The scenario for the simulation was a normal approach to the vertiport that is interrupted by a commanded go-around at the landing decision point. The simulation contrasted an automated discrete nacelle mode control with a fully manual nacelle control mode for the go-around. The MIDAS simulation showed that the pilot task loading during approach and for the commanded go-around is high and that pilot workload is near capacity throughout. The go-around in manual nacelle mode was most demanding, resulting in additional time requirements to complete necessary tasks.

Atencio, Adolph, Jr.↗

NASA NTRS2000

Holographic Optical Data Storage

Although the basic idea may be traced back to the earlier X-ray diffraction studies of Sir W. L. Bragg, the holographic method as we know it was invented by D. Gabor in 1948 as a two-step lensless imaging technique to enhance the resolution of electron microscopy, for which he received the 1971 Nobel Prize in physics. The distinctive feature of holography is the recording of the object phase variations that carry the depth information, which is lost in conventional photography where only the intensity (= squared amplitude) distribution of an object is captured. Since all photosensitive media necessarily respond to the intensity incident upon them, an ingenious way had to be found to convert object phase into intensity variations, and Gabor achieved this by introducing a coherent reference wave along with the object wave during exposure. Gabor's in-line recording scheme, however, required the object in question to be largely transmissive, and could provide only marginal image quality due to unwanted terms simultaneously reconstructed along with the desired wavefront. Further handicapped by the lack of a strong coherent light source, optical holography thus seemed fated to remain just another scientific curiosity, until the field was revolutionized in the early 1960s by some major breakthroughs: the proposition and demonstration of the laser principle, the introduction of off-axis holography, and the invention of volume holography. Consequently, the remainder of that decade saw an exponential growth in research on theory, practice, and applications of holography. Today, holography not only boasts a wide variety of scientific and technical applications (e.g., holographic interferometry for strain, vibration, and flow analysis, microscopy and high-resolution imagery, imaging through distorting media, optical interconnects, holographic optical elements, optical neural networks, three-dimensional displays, data storage, etc.), but has become a prominent am advertising, and security medium as well. The evolution of holographic optical memories has followed a path not altogether different from holography itself, with several cycles of alternating interest over the past four decades. P. J. van Heerden is widely credited for being the first to elucidate the principles behind holographic data storage in a 1963 paper, predicting bit storage densities on the order of 1/lambda(sup 3) with source wavelength lambda - a fantastic capacity of nearly 1 TB/cu cm for visible light! The science and engineering of such a storage paradigm was heavily pursued thereafter, resulting in many novel hologram multiplexing techniques for dense data storage, as well as important advances in holographic recording materials. Ultimately, however, the lack of such enabling technologies as compact laser sources and high performance optical data I/O devices dampened the hopes for the development of a commercial product. After a period of relative dormancy, successful applications of holography in other arenas sparked a renewed interest in holographic data storage in the late 1980s and the early 1990s. Currently, with most of the critical optoelectronic device technologies in place and the quest for an ideal holographic recording medium intensified, holography is once again considered as one of several future data storage paradigms that may answer our constantly growing need for higher-capacity and faster-access memories.

Timucin, Dogan A.↗

NASA NTRS2014

Nuclear Cryogenic Propulsion Stage Conceptual Design and Mission Analysis

The Nuclear Cryogenic Propulsion Stage (NCPS) is an in-space transportation vehicle, comprised of three main elements, designed to support a long-stay human Mars mission architecture beginning in 2035. The stage conceptual design and the mission analysis discussed here support the current nuclear thermal propulsion going on within partnership activity of NASA and the Department of Energy (DOE). The transportation system consists of three elements: 1) the Core Stage, 2) the In-line Tank, and 3) the Drop Tank. The driving mission case is the piloted flight to Mars in 2037 and will be the main point design shown and discussed. The corresponding Space Launch System (SLS) launch vehicle (LV) is also presented due to it being a very critical aspect of the NCPS Human Mars Mission architecture due to the strong relationship between LV lift capability and LV volume capacity.

Kos, Larry D.↗

NASA NTRS1975

Perspective on the span-distributed-load concept for application to large cargo aircraft design

Results of a simplified analysis of the span-distributed-load concept (in which payload is placed within the wing structure) are presented. It is shown that a design based on these principles has a high potential for application to future large air cargo transport. Significant improvements are foreseen in increased payload fraction and productivity and in reduced fuel consumption and operating costs. A review of the efforts in the 1940's to develop all-wing aircraft shows the potential of transferring those early technological developments to current design of distributed-load aircraft. Current market analyses are projected to 1990 to show the future commercial demand for large capacity freighters. Several configuration designs which would serve different market requirements for these large freighters are discussed as are some of the pacing-technology requirements.

Whitehead, A. H., Jr.↗

NASA NTRS2004

Aircraft Wake Vortex Measurements at Denver International Airport

Airport capacity is constrained, in part, by spacing requirements associated with the wake vortex hazard. NASA's Wake Vortex Avoidance Project has a goal to establish the feasibility of reducing this spacing while maintaining safety. Passive acoustic phased array sensors, if shown to have operational potential, may aid in this effort by detecting and tracking the vortices. During August/September 2003, NASA and the USDOT sponsored a wake acoustics test at the Denver International Airport. The central instrument of the test was a large microphone phased array. This paper describes the test in general terms and gives an overview of the array hardware. It outlines one of the analysis techniques that is being applied to the data and gives sample results. The technique is able to clearly resolve the wake vortices of landing aircraft and measure their separation, height, and sinking rate. These observations permit an indirect estimate of the vortex circulation. The array also provides visualization of the vortex evolution, including the Crow instability.

Dougherty, Robert P.↗

NASA NTRS1990

An analysis of space power system masses

Various space electrical power system masses are analyzed with particular emphasis on the power management and distribution (PMAD) portion. The electrical power system (EPS) is divided into functional blocks: source, interconnection, storage, transmission, distribution, system control and load. The PMAD subsystem is defined as all the blocks between the source, storage and load, plus the power conditioning equipment required for the source, storage and load. The EPS mass of a wide range of spacecraft is then classified as source, storage or PMAD and tabulated in a database. The intent of the database is to serve as a reference source for PMAD masses of existing and in-design spacecraft. The PMAD masses in the database range from 40 kg/kW to 183 kg/kW across the spacecraft systems studied. Factors influencing the power system mass are identified. These include the total spacecraft power requirements, total amount of load capacity and physical size of the spacecraft. It is found that a new utility class of power systems, represented by Space Station Freedom, is evolving.

Kenny, Barbara H.↗

NASA NTRS1990

An analysis of space power system masses

Kenny, Barbara H.↗

NASA NTRS2010

Analysis of Different Cost Functions in the Geosect Airspace Partitioning Tool

A new cost function representing air traffic controller workload is implemented in the Geosect airspace partitioning tool. Geosect currently uses a combination of aircraft count and dwell time to select optimal airspace partitions that balance controller workload. This is referred to as the aircraft count/dwell time hybrid cost function. The new cost function is based on Simplified Dynamic Density, a measure of different aspects of air traffic controller workload. Three sectorizations are compared. These are the current sectorization, Geosect's sectorization based on the aircraft count/dwell time hybrid cost function, and Geosect s sectorization based on the Simplified Dynamic Density cost function. Each sectorization is evaluated for maximum and average workload along with workload balance using the Simplified Dynamic Density as the workload measure. In addition, the Airspace Concept Evaluation System, a nationwide air traffic simulator, is used to determine the capacity and delay incurred by each sectorization. The sectorization resulting from the Simplified Dynamic Density cost function had a lower maximum workload measure than the other sectorizations, and the sectorization based on the combination of aircraft count and dwell time did a better job of balancing workload and balancing capacity. However, the current sectorization had the lowest average workload, highest sector capacity, and the least system delay.

Wong, Gregory L.↗

NASA NTRS1998

A Photo Album of Earth Scheduling Landsat 7 Mission Daily Activities

Landsat7 is a member of a new generation of Earth observation satellites. Landsat7 will carry on the mission of the aging Landsat 5 spacecraft by acquiring high resolution, multi-spectral images of the Earth surface for strategic, environmental, commercial, agricultural and civil analysis and research. One of the primary mission goals of Landsat7 is to accumulate and seasonally refresh an archive of global images with full coverage of Earth's landmass, less the central portion of Antarctica. This archive will enable further research into seasonal, annual and long-range trending analysis in such diverse research areas as crop yields, deforestation, population growth, and pollution control, to name just a few. A secondary goal of Landsat7 is to fulfill imaging requests from our international partners in the mission. Landsat7 will transmit raw image data from the spacecraft to 25 ground stations in 20 subscribing countries. Whereas earlier Landsat missions were scheduled manually (as are the majority of current low-orbit satellite missions), the task of manually planning and scheduling Landsat7 mission activities would be overwhelmingly complex when considering the large volume of image requests, the limited resources available, spacecraft instrument limitations, and the limited ground image processing capacity, not to mention avoidance of foul weather systems. The Landsat7 Mission Operation Center (MOC) includes an image scheduler subsystem that is designed to automate the majority of mission planning and scheduling, including selection of the images to be acquired, managing the recording and playback of the images by the spacecraft, scheduling ground station contacts for downlink of images, and generating the spacecraft commands for controlling the imager, recorder, transmitters and antennas. The image scheduler subsystem autonomously generates 90% of the spacecraft commanding with minimal manual intervention. The image scheduler produces a conflict-free schedule for acquiring images of the "best" 250 scenes daily for refreshing the global archive. It then equitably distributes the remaining resources for acquiring up to 430 scenes to satisfy requests by international subscribers. The image scheduler selects candidate scenes based on priority and age of the requests, and predicted cloud cover and sun angle at each scene. It also selects these scenes to avoid instrument constraint violations and maximizes efficiency of resource usage by encouraging acquisition of scenes in clusters. Of particular interest to the mission planners, it produces the resulting schedule in a reasonable time, typically within 15 minutes.

Potter, William↗

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 NTRS2008

From Informal Safety-Critical Requirements to Property-Driven Formal Validation

Most of the efforts in formal methods have historically been devoted to comparing a design against a set of requirements. The validation of the requirements themselves, however, has often been disregarded, and it can be considered a largely open problem, which poses several challenges. The first challenge is given by the fact that requirements are often written in natural language, and may thus contain a high degree of ambiguity. Despite the progresses in Natural Language Processing techniques, the task of understanding a set of requirements cannot be automatized, and must be carried out by domain experts, who are typically not familiar with formal languages. Furthermore, in order to retain a direct connection with the informal requirements, the formalization cannot follow standard model-based approaches. The second challenge lies in the formal validation of requirements. On one hand, it is not even clear which are the correctness criteria or the high-level properties that the requirements must fulfill. On the other hand, the expressivity of the language used in the formalization may go beyond the theoretical and/or practical capacity of state-of-the-art formal verification. In order to solve these issues, we propose a new methodology that comprises of a chain of steps, each supported by a specific tool. The main steps are the following. First, the informal requirements are split into basic fragments, which are classified into categories, and dependency and generalization relationships among them are identified. Second, the fragments are modeled using a visual language such as UML. The UML diagrams are both syntactically restricted (in order to guarantee a formal semantics), and enriched with a highly controlled natural language (to allow for modeling static and temporal constraints). Third, an automatic formal analysis phase iterates over the modeled requirements, by combining several, complementary techniques: checking consistency; verifying whether the requirements entail some desirable properties; verify whether the requirements are consistent with selected scenarios; diagnosing inconsistencies by identifying inconsistent cores; identifying vacuous requirements; constructing multiple explanations by enabling the fault-tree analysis related to particular fault models; verifying whether the specification is realizable.

Cimatti, Alessandro↗