SEARCH · Search NASA

Results for “Planning Scheduling Algorithms”

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 181 records · Page 10

All sources NASA NTRS DOE OSTI

NASA NTRS2001

Computing the Envelope for Stepwise Constant Resource Allocations

Estimating tight resource level is a fundamental problem in the construction of flexible plans with resource utilization. In this paper we describe an efficient algorithm that builds a resource envelope, the tightest possible such bound. The algorithm is based on transforming the temporal network of resource consuming and producing events into a flow network with noises equal to the events and edges equal to the necessary predecessor links between events. The incremental solution of a staged maximum flow problem on the network is then used to compute the time of occurrence and the height of each step of the resource envelope profile. The staged algorithm has the same computational complexity of solving a maximum flow problem on the entire flow network. This makes this method computationally feasible for use in the inner loop of search-based scheduling algorithms.

Muscettola, Nicola↗

NASA NTRS1983

Time scheduling of a mix of 4D equipped and unequipped aircraft

In planning for a future automated air traffic system, it is necessary to confront the transition situation in which some percentage of the traffic must be handled by conventional means. A safe, efficient transition system is needed since initially not all aircraft will be able to respond to a more automated system. The specific problem addressed was that of time scheduling a mix of 4D-equipped aircraft (aircraft that can accurately meet a controller specified time schedule at selected way points in the terminal area) when operating in conjunction with unequipped aircraft (aircraft that require air traffic handling by means of standard vectoring techniques). First, a relationship between time separation and system capacity was developed. The time separations were incorporated into a set of scheduling algorithms which contain the required elements of flexibility needed for terminal-area operation, such as delaying aircraft and changing time separations. The problem of reducing the size of time separations allotted for vectored aircraft by means of computer assists to the controller was also addressed.

Tobias, L.↗

NASA NTRS1983

Time scheduling of a mix of 4D equipped and unequipped aircraft

Tobias, L.↗

NASA NTRS2004

Applying Squeaky-Wheel Optimization Schedule Airborne Astronomy Observations

We apply the Squeaky Wheel Optimization (SWO) algorithm to the problem of scheduling astronomy observations for the Stratospheric Observatory for Infrared Astronomy, an airborne observatory. The problem contains complex constraints relating the feasibility of an astronomical observation to the position and time at which the observation begins, telescope elevation limits, special use airspace, and available fuel. Solving the problem requires making discrete choices (e.g. selection and sequencing of observations) and continuous ones (e.g. takeoff time and setting up observations by repositioning the aircraft). The problem also includes optimization criteria such as maximizing observing time while simultaneously minimizing total flight time. Previous approaches to the problem fail to scale when accounting for all constraints. We describe how to customize SWO to solve this problem, and show that it finds better flight plans, often with less computation time, than previous approaches.

Frank, Jeremy↗

NASA NTRS2011

Solar Dynamics Observatory On-Orbit Jitter Testing, Analysis, and Mitigation Plans

The Solar Dynamics Observatory (SDO) was designed to understand the Sun and the Sun s influence on Earth. SDO was launched on February 11, 2010 carrying three scientific instruments: the Atmospheric Imaging Assembly (AIA), the Helioseismic and Magnetic Imager (HMI), and the Extreme Ultraviolet Variability Experiment (EVE). Both AIA and HMI are sensitive to high frequency pointing perturbations and have sub-arcsecond level line-of-sight (LOS) jitter requirements. Extensive modeling and analysis efforts were directed in estimating the amount of jitter disturbing the science instruments. To verify the disturbance models and to validate the jitter performance prior to launch, many jitter-critical components and subassemblies were tested either by the mechanism vendors or at the NASA Goddard Space Flight Center (GSFC). Although detailed analysis and assembly level tests were performed to obtain good jitter predictions, there were still several sources of uncertainties in the system. The structural finite element model did not have all the modes correlated to test data at high frequencies (greater than 50 Hz). The performance of the instrument stabilization system was not known exactly but was expected to be close to the analytical model. A true disturbance-to-LOS observatory level test was not available due to the tight schedule of the flight spacecraft, the cost in time and manpower, difficulties in creating gravity negation systems, and risks of damaging flight hardware. To protect the observatory jitter performance against model uncertainties, the SDO jitter team devised several on-orbit jitter reduction plans in addition to reserve margins on analysis results. Since some of these plans severely restricted the capabilities of several spacecraft components (e.g. wheels and High Gain Antennas), the SDO team performed on-orbit jitter tests to determine which jitter reduction plans, if any, were necessary to satisfy science LOS jitter requirements. The SDO on-orbit jitter tests were designed to satisfy the following four objectives: 1. Determine the acceptable reaction wheel operational speed range during Science Mode. 2. Determine HGA algorithm jitter parameters (number of stagger steps and enable/disable no-steprequests). 3. Determine acceptable EVE instrument filter wheels spin rates. 4. Determine if AIA instrument filter wheels excite the first AIA telescope structural mode. This paper provides detailed information on the SDO wheel jitter test plan, shows on-orbit jitter measurements and how ground predictions compare to those measurements, and describes the final jitter mitigation plan executed on SDO.

Liu, Kuo-Chia (Alice)↗

NASA NTRS2006

Exploiting Quantum Resonance to Solve Combinatorial Problems

Quantum resonance would be exploited in a proposed quantum-computing approach to the solution of combinatorial optimization problems. In quantum computing in general, one takes advantage of the fact that an algorithm cannot be decoupled from the physical effects available to implement it. Prior approaches to quantum computing have involved exploitation of only a subset of known quantum physical effects, notably including parallelism and entanglement, but not including resonance. In the proposed approach, one would utilize the combinatorial properties of tensor-product decomposability of unitary evolution of many-particle quantum systems for physically simulating solutions to NP-complete problems (a class of problems that are intractable with respect to classical methods of computation). In this approach, reinforcement and selection of a desired solution would be executed by means of quantum resonance. Classes of NP-complete problems that are important in practice and could be solved by the proposed approach include planning, scheduling, search, and optimal design.

Zak, Michail↗

NASA NTRS2012

Early Transition and Use of VIIRS and GOES-R Products by NWS Forecast Offices

The Visible Infrared Imaging Radiometer Suite (VIIRS) on the NPOESS Preparatory Project (NPP) satellite, part of the Joint Polar Satellite System (JPSS), and the ABI and GLM sensors scheduled for the GOES-R geostationary satellite will bring advanced observing capabilities to the operational weather community. The NASA Short-term Prediction Research and Transition (SPoRT) project at Marshall Space Flight Center has been facilitating the use of real-time experimental and research satellite data by NWS Weather Forecast Offices (WFOs) for a number of years to demonstrate the planned capabilities of future sensors to address particular forecast challenges through improve situational awareness and short-term weather forecasts. For the NOAA GOES-R Proving Ground (PG) activity, SPoRT is developing and disseminating selected GOES-R proxy products to collaborating WFOs and National Centers. SPoRT developed the a pseudo-Geostationary Lightning Mapper product and helped in the transition of the Algorithm Working Group (AWG) Convective Initiation (CI) proxy product for the Hazardous Weather Testbed (HWT) Spring Experiment,. Along with its partner WFOs, SPoRT is evaluating MODIS/GOES Hybrid products, which brings ABI-like data sets from existing NASA instrumentation in front of the forecaster for everyday use. The Hybrid uses near real-time MODIS imagery to demonstrate future ABI capabilities, while utilizing standard GOES imagery to provide the temporal frequency of geostationary imagery expected by operational forecasters. In addition, SPoRT is collaborating with the GOES-R hydrology AWG to transition a baseline proxy product for rainfall rate / quantitative precipitation estimate (QPE) to the OCONUS regions. For VIIRS, SPoRT is demonstrating multispectral observing capabilities and the utility of low-light channels not previously available on operational weather satellites to address a variety of weather forecast challenges. This presentation will discuss the results of transitioning these products to collaborating WFOs throughout the country.

Fuell, Kevin K.↗

NASA NTRS2019

Mission Planner Algorithm for Urban Air Mobility – Initial Performance Characterization

In this paper, an initial characterization was performed of the Mission Planner algorithm developed by NASA for Urban Air Mobility (UAM) operations research. The algorithm plans conflict-free trajectories for flights to support a given set of UAM passenger trips. The UAM trips are planned in an on-demand, first-come, first-served manner, such that any given trip is subject to the constraints imposed by previously planned trips. For this analysis, the mission planning algorithm considered only the trajectory constraints from previously-planned trips in one test condition and added vertiport constraints for the second test condition. The conflict and constraint resolution strategies used by the Mission Planner were characterized by their percentage contribution to planning iterations, their percentage effectiveness in those iterations, and their contributions to the departure delay applied to each UAM trip’s flight. With the exception of the climb and descent vertical speed strategies, most strategies showed reasonable or good performance in all test scenarios. In the test condition with vertipad constraints enabled, both the total number of iterations executed, and the number of flights that required planning iterations, was reduced for all scenarios. This was the result of the natural conditioning of the traffic achieved with scheduling and the additional information available to the Mission Planner from the vertiport scheduler. The next steps for this work will include improvements to the mission planning strategies and analyses with additional constraints and under other demand scenarios.

Guerreiro, Nelson M.↗

NASA NTRS2018

Polarimetric Remote Sensing of Atmospheric Aerosols: Instruments, Methodologies, Results, and Perspectives

Polarimetry is one of the most promising types of remote sensing for improved characterization of atmospheric aerosol. Indeed, aerosol particles constitute a highly variable atmospheric component characterized by a large number of parameters describing particle sizes, morphologies (including shape and internal structure), absorption and scattering properties, amounts, horizontal and vertical distribution, etc. Reliable monitoring of all these parameters is very challenging, and therefore the aerosol effects on climate and environment are considered to be among the most uncertain factors in climate and environmental research. In this regard, observations that provide both the angular distribution of the scattered atmospheric radiation as well as its polarization state at multiple wavelengths covering the UV–SWIR spectral range carry substantial implicit information on the atmospheric composition. Therefore, high expectations in improving aerosol characterization are associated with detailed passive photopolarimetric observations. The critical need to use space-borne polarimetry for global accurate monitoring of detailed aerosol properties was first articulated in the late 1980s and early 1990s. By now, several orbital instruments have already provided polarization observations from space, and a number of advanced missions are scheduled for launch in the coming years by international and national space agencies. The first and most extensive record of polarimetric imagery was provided by POLDER-I, POLDER-II, and POLDER/PARASOL multi-angle multi-spectral polarization sensors. Polarimetric observations with the POLDER-like design intended for collecting extensive multi-angular multi-spectral measurements will be provided by several instruments, such as the MAI/TG-2, CAPI/TanSat, and DPC/GF-5 sensors recently launched by the Chinese Space Agency. Instruments such as the 3MI/MetOp-SG, MAIA, SpexOne and HARP2 on PACE, POSP, SMAC, PCF, DPC–Lidar, ScanPol and MSIP/Aerosol-UA, MAP/Copernicus CO2 Monitoring, etc. are planned to be launched by different space agencies in the coming decade. The concepts of these future instruments, their technical designs, and the accompanying algorithm development have been tested intensively and analyzed using diverse airborne prototypes. Certain polarimetric capabilities have also been implemented in such satellite sensors as GOME-2/MetOp and SGLI/GCOM-C.

Aerosols↗

NASA NTRS2004

Robust local search for spacecraft operations using adaptive noise

Randomization is a standard technique for improving the performance of local search algorithms for constraint satisfaction. However, it is well-known that local search algorithms are constraints satisfaction. However, it is well-known that local search algorithms are to the noise values selected. We investigate the use of an adaptive noise mechanism in an iterative repair-based planner/scheduler for spacecraft operations. Preliminary results indicate that adaptive noise makes the use of randomized repair moves safe and robust; that is, using adaptive noise makes it possible to consistently achieve, performance comparable with the best tuned noise setting without the need for manually tuning the noise parameter.

planning↗

NASA NTRS2020

Preparing the JWST Observatory for Science Observations

The James Webb Space Telescope (JWST) is a large (6.5 m) near-and mid-infrared telescope scheduled for launch in 2021. JWST will be used to explore fundamental questions in astrophysics and planetary science, including the evolution of galaxies, the first light of stars, the formation of stars and planets as well as the characterization of exoplanets. To achieve these scientific goals, NASA and its international partners, the Canadian Space Agency (CSA) and the European Space Agency (ESA), have developed four science instruments for JWST and have prepared detailed commissioning plans for each. The NASA Project Science team has also outlined activities to characterize the performance of the Observatory as a whole. These activities include: 1) monitoring of the instrument and telescope cooldown for contamination mitigation; 2) measurements of straylight and other backgrounds for validation of the JWST stray light models as well as instrument background subtraction algorithms; 3) characterization of optical thermal distortion between its hot and cold telescope pointings within the observable field of regard and 4) trending of observatory performance parameters. Each of these activities has been planned in close collaboration with the observatory wavefront, commissioning planning, and science instrument teams. Here we present the plans for these activities, the expected results and how they will impact future guest observer (GO) proposals and JWST science community

Erin C Smith↗

NASA NTRS2008

Deep Space Network Scheduling Using Multi-Objective Optimization with Uncertainty

We have developed a novel technique to incorporate uncertainty modeling within an evolutionary algorithm approach to multi-objective scheduling, with the goal of identifying a Pareto frontier (tradeoff curve) that recognizes the likelihood of events that can impact the schedule outcome. Our approach is particularly applicable to the generation of multiobjective optimized robust schedules, where objectives are assigned a service level, for example that we require an objective value to be greater than or equal to X with Y% confidence. We have demonstrated that such an approach can, for example, minimize scheduling on less reliable resources, based solely on a resource reliability model and not on any ad hoc heuristics. We have also investigated an alternative method of optimizing for robustness, in which we add to the set of objectives a failure risk objective to minimize. We compare the advantages and disadvantages of these two approaches. Future plans for further developing this technology include its application to space-based observatory scheduling problems.

Johnston, Mark D.↗

NASA NTRS1990

Applications of artificial intelligence to mission planning

The scheduling problem facing NASA-Marshall mission planning is extremely difficult for several reasons. The most critical factor is the computational complexity involved in developing a schedule. The size of the search space is large along some dimensions and infinite along others. It is because of this and other difficulties that many of the conventional operation research techniques are not feasible or inadequate to solve the problems by themselves. Therefore, the purpose is to examine various artificial intelligence (AI) techniques to assist conventional techniques or to replace them. The specific tasks performed were as follows: (1) to identify mission planning applications for object oriented and rule based programming; (2) to investigate interfacing AI dedicated hardware (Lisp machines) to VAX hardware; (3) to demonstrate how Lisp may be called from within FORTRAN programs; (4) to investigate and report on programming techniques used in some commercial AI shells, such as Knowledge Engineering Environment (KEE); and (5) to study and report on algorithmic methods to reduce complexity as related to AI techniques.

Ford, Donnie R.↗

NASA NTRS2003

Total Ozone from the Ozone Monitoring System (OMI) using TOMS and DOAS Methods

The Ozone Monitoring Instrument (OMI) is the Dutch-Finnish contribution to NASA's EOS-Aura satellite scheduled for launch in January 2004. OMI is an imaging spectrometer that will measure the back-scattered Solar radiance in the wavelength range of 270 to 500 nm. The instrument provides near global coverage in one day with a spatial resolution of 13x24 square kilometers. OMI is a new instrument, with a heritage from TOMS, SBW, GOME, GOMOS and SCIAMACHY. OMI'S unique capabilities for measuring important trace gases and aerosols with a small footprint and daily global coverage, in conjunction with the other Aura instruments, will make a major contribution to our understanding of stratospheric and tropospheric chemistry and climate change. OMI will provide data continuity with the 23-year ozone record of TOMS. There are three ozone products planned for OMI: total column ozone, ozone profile and tropospheric column ozone. We are developing two different algorithms for total column ozone: one similar to the algorithm currently being used to process the TOMS data, and the other an improved version of the differential optical absorption spectroscopy (DOAS) method, which has been applied to GOME and SCIAMACHY data. The main reasons for starting with two algorithms for total ozone have to do with heritage and past experience; our long-term goal is to combine the two to develop a more accurate and reliable total ozone product for OMI. We will compare the performance of these two algorithms by applying both of them to the GOME data. We will examine where and how the results differ, and use the extensive TOMS-Dobson comparison studies to assess the performance of the DOAS algorithm.

Veefkind, J. P.↗

NASA NTRS2008

Proceedings of the Sixth NASA Langley Formal Methods (LFM) Workshop

Today's verification techniques are hard-pressed to scale with the ever-increasing complexity of safety critical systems. Within the field of aeronautics alone, we find the need for verification of algorithms for separation assurance, air traffic control, auto-pilot, Unmanned Aerial Vehicles (UAVs), adaptive avionics, automated decision authority, and much more. Recent advances in formal methods have made verifying more of these problems realistic. Thus we need to continually re-assess what we can solve now and identify the next barriers to overcome. Only through an exchange of ideas between theoreticians and practitioners from academia to industry can we extend formal methods for the verification of ever more challenging problem domains. This volume contains the extended abstracts of the talks presented at LFM 2008: The Sixth NASA Langley Formal Methods Workshop held on April 30 - May 2, 2008 in Newport News, Virginia, USA. The topics of interest that were listed in the call for abstracts were: advances in formal verification techniques; formal models of distributed computing; planning and scheduling; automated air traffic management; fault tolerance; hybrid systems/hybrid automata; embedded systems; safety critical applications; safety cases; accident/safety analysis.

Rozier, Kristin Yvonne↗

NASA NTRS2005

Current results from a Rover Science Data Analysis System

In this paper, we provide a brief overview of the OASIS system, and then describe our recent successes in integrating with and using rover hardware. OASIS currently works in a closed loop fashion with onboard control software (e.g., navigation and vision) and has the ability to autonomously perform the following sequence of steps: analyze gray scale images to find rocks, extract the properties of the rocks, identify rocks of interest, retask the rover to take additional imagery of the identified target and then allow the rover to continue on its original mission. We also describe the early 2004 ground test validation of specific OASIS components on selected Mars Exploration Rover (MER) images. These components include the rockfinding algorithm, RockIT, and the rock size feature extraction code. Our team also developed the RockIT GUI, an interface that allows users to easily visualize and modify the rock-finder results. This interface has allowed us to conduct preliminary testing and validation of the rockfinder's performance.

Coupled Layer Architecture for Robotic Autonomy (C↗

NASA NTRS2006

NASA Tech Briefs, September 2006

Topics covered include: Improving Thermomechanical Properties of SiC/SiC Composites; Aerogel/Particle Composites for Thermoelectric Devices; Patches for Repairing Ceramics and Ceramic- Matrix Composites; Lower-Conductivity Ceramic Materials for Thermal-Barrier Coatings; An Alternative for Emergency Preemption of Traffic Lights; Vehicle Transponder for Preemption of Traffic Lights; Automated Announcements of Approaching Emergency Vehicles; Intersection Monitor for Traffic-Light-Preemption System; Full-Duplex Digital Communication on a Single Laser Beam; Stabilizing Microwave Frequency of a Photonic Oscillator; Microwave Oscillators Based on Nonlinear WGM Resonators; Pointing Reference Scheme for Free-Space Optical Communications Systems; High-Level Performance Modeling of SAR Systems; Spectral Analysis Tool 6.2 for Windows; Multi-Platform Avionics Simulator; Silicon-Based Optical Modulator with Ferroelectric Layer; Multiplexing Transducers Based on Tunnel-Diode Oscillators; Scheduling with Automated Resolution of Conflicts; Symbolic Constraint Maintenance Grid; Discerning Trends in Performance Across Multiple Events; Magnetic Field Solver; Computing for Aiming a Spaceborne Bistatic- Radar Transmitter; 4-Vinyl-1,3-Dioxolane-2-One as an Additive for Li-Ion Cells; Probabilistic Prediction of Lifetimes of Ceramic Parts; STRANAL-PMC Version 2.0; Micromechanics and Piezo Enhancements of HyperSizer; Single-Phase Rare-Earth Oxide/Aluminum Oxide Glasses; Tilt/Tip/Piston Manipulator with Base-Mounted Actuators; Measurement of Model Noise in a Hard-Wall Wind Tunnel; Loci-STREAM Version 0.9; The Synergistic Engineering Environment; Reconfigurable Software for Controlling Formation Flying; More About the Tetrahedral Unstructured Software System; Computing Flows Using Chimera and Unstructured Grids; Avoiding Obstructions in Aiming a High-Gain Antenna; Analyzing Aeroelastic Stability of a Tilt-Rotor Aircraft; Tracking Positions and Attitudes of Mars Rovers; Stochastic Evolutionary Algorithms for Planning Robot Paths; Compressible Flow Toolbox; Rapid Aeroelastic Analysis of Blade Flutter in Turbomachines; General Flow-Solver Code for Turbomachinery Applications; Code for Multiblock CFD and Heat-Transfer Computations; Rotating-Pump Design Code; Covering a Crucible with Metal Containing Channels; Repairing Fractured Bones by Use of Bioabsorbable Composites; Kalman Filter for Calibrating a Telescope Focal Plane; Electronic Absolute Cartesian Autocollimator; Fiber-Optic Gratings for Lidar Measurements of Water Vapor; Simulating Responses of Gravitational-Wave Instrumentation; SOFTC: A Software Correlator for VLBI; Progress in Computational Simulation of Earthquakes; Database of Properties of Meteors; Computing Spacecraft Solar-Cell Damage by Charged Particles; Thermal Model of a Current-Carrying Wire in a Vacuum; Program for Analyzing Flows in a Complex Network; Program Predicts Performance of Optical Parametric Oscillators; Processing TES Level-1B Data; Automated Camera Calibration; Tracking the Martian CO2 Polar Ice Caps in Infrared Images; Processing TES Level-2 Data; SmaggIce Version 1.8; Solving the Swath Segment Selection Problem; The Spatial Standard Observer; Less-Complex Method of Classifying MPSK; Improvement in Recursive Hierarchical Segmentation of Data; Using Heaps in Recursive Hierarchical Segmentation of Data; Tool for Statistical Analysis and Display of Landing Sites; Automated Assignment of Proposals to Reviewers; Array-Pattern-Match Compiler for Opportunistic Data Analysis; Pre-Processor for Compression of Multispectral Image Data; Compressing Image Data While Limiting the Effects of Data Losses; Flight Operations Analysis Tool; Improvement in Visual Target Tracking for a Mobile Robot; Software for Simulating Air Traffic; Automated Vectorization of Decision-Based Algorithms; Grayscale Optical Correlator Workbench; "One-Stop Shopping" for Ocean Remote-Sensing and Model Data; State Analysis Database Tool; Generating CAHV and CAHVOmages with Shadows in ROAMS; Improving UDP/IP Transmission Without Increasing Congestion; FORTRAN Versions of Reformulated HFGMC Codes; Program for Editing Spacecraft Command Sequences; Flight-Tested Prototype of BEAM Software; Mission Scenario Development Workbench; Marsviewer; Tool for Analysis and Reduction of Scientific Data; ASPEN Version 3.0; Secure Display of Space-Exploration Images; Digital Front End for Wide-Band VLBI Science Receiver; Multifunctional Tanks for Spacecraft; Lightweight, Segmented, Mostly Silicon Telescope Mirror; Assistant for Analyzing Tropical-Rain-Mapping Radar Data; and Anion-Intercalating Cathodes for High-Energy- Density Cells.

Source record↗

NASA NTRS1989

Approximation algorithms for planning and control

A control system operating in a complex environment will encounter a variety of different situations, with varying amounts of time available to respond to critical events. Ideally, such a control system will do the best possible with the time available. In other words, its responses should approximate those that would result from having unlimited time for computation, where the degree of the approximation depends on the amount of time it actually has. There exist approximation algorithms for a wide variety of problems. Unfortunately, the solution to any reasonably complex control problem will require solving several computationally intensive problems. Algorithms for successive approximation are a subclass of the class of anytime algorithms, algorithms that return answers for any amount of computation time, where the answers improve as more time is allotted. An architecture is described for allocating computation time to a set of anytime algorithms, based on expectations regarding the value of the answers they return. The architecture described is quite general, producing optimal schedules for a set of algorithms under widely varying conditions.

Boddy, Mark↗