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 91 records · Page 5

All sources NASA NTRS DOE OSTI

NASA NTRS2004

GSFC Technology Development Center Report

This report summarizes the activities of the GSFC Technology Development Center for 2003. The report forecasts activities planned for the year 2004. The GSFC Technology Development Center (TDC) develops station software including the Field System (FS), scheduling software (SKED), hardware including tools for station timing and meteorology, scheduling algorithms, operational procedures, and provides a pool of individuals to assist with station implementation, check-out, upgrades, and training.

Himwich, Ed↗

NASA NTRS1991

Automated power management and control

A comprehensive automation design is being developed for Space Station Freedom's electric power system. A joint effort between NASA's Office of Aeronautics and Exploration Technology and NASA's Office of Space Station Freedom, it strives to increase station productivity by applying expert systems and conventional algorithms to automate power system operation. The initial station operation will use ground-based dispatches to perform the necessary command and control tasks. These tasks constitute planning and decision-making activities that strive to eliminate unplanned outages. We perceive an opportunity to help these dispatchers make fast and consistent on-line decisions by automating three key tasks: failure detection and diagnosis, resource scheduling, and security analysis. Expert systems will be used for the diagnostics and for the security analysis; conventional algorithms will be used for the resource scheduling.

Dolce, James L.↗

NASA NTRS2001

GSFC IVS Technology Development Center Report

This report summarizes the activities of the Goddard Space Flight Center's (GSFC's) International Very Long Base Interferometry (VLBI) Service (IVS)Technology Development Center from the establishment of IVS to the end of 2000. The report forecasts activities planned for the year 2001. The GSFC IVS Technology Development Center (TDC) develops station software including the Field System (FS), scheduling software (SKED), hardware including tools for station timing and meteorology, scheduling algorithms, operational procedures, and provides a pool of individuals to assist with station implementation, check-out, upgrades, and training.

Himwich, Ed↗

NASA NTRS2002

Advanced Passive Microwave Radiometer Technology for GPM Mission

An interferometer-type passive microwave radiometer based on MMIC receiver technology and a thinned array antenna design is being developed under the Instrument Incubator Program (TIP) on a project entitled the Lightweight Rainfall Radiometer (LRR). The prototype single channel aircraft instrument will be ready for first testing in 2nd quarter 2003, for deployment on the NASA DC-8 aircraft and in a ground configuration manner; this version measures at 10.7 GHz in a crosstrack imaging mode. The design for a two (2) frequency preliminary space flight model at 19 and 35 GHz (also in crosstrack imaging mode) has also been completed, in which the design features would enable it to fly in a bore-sighted configuration with a new dual-frequency space radar (DPR) under development at the Communications Research Laboratory (CRL) in Tokyo, Japan. The DPR will be flown as one of two primary instruments on the Global Precipitation Measurement (GPM) mission's core satellite in the 2007 time frame. The dual frequency space flight design of the ERR matches the APR frequencies and will be proposed as an ancillary instrument on the GPM core satellite to advance space-based precipitation measurement by enabling better microphysical characterization and coincident volume data gathering for exercising combined algorithm techniques which make use of both radar backscatter and radiometer attenuation information to constrain rainrate solutions within a physical algorithm context. This talk will discuss the design features, performance capabilities, applications plans, and conical/polarametric imaging possibilities for the LRR, as well as a brief summary of the project status and schedule.

Smith, Eric A.↗

NASA NTRS2003

Shared Activity Coordination

Interacting agents that interleave planning and execution must reach consensus on their commitments to each other. In domains where agents have varying degrees of interaction and different constraints on communication and computation, agents will require different coordination protocols in order to efficiently reach consensus in real time. We briefly describe a largely unexplored class of real-time, distributed planning problems (inspired by interacting spacecraft missions), new challenges they pose, and a general approach to solving the problems. These problems involve self-interested agents that have infrequent communication but collaborate on joint activities. We describe a Shared Activity Coordination (SHAC) framework that provides a decentralized algorithm for negotiating the scheduling of shared activities in a dynamic environment, a soft, real-time approach to reaching consensus during execution with limited communication, and a foundation for customizing protocols for negotiating planner interactions. We apply SHAC to a realistic simulation of interacting Mars missions and illustrate the simplicity of protocol development.

coordination↗

NASA NTRS2003

Continual coordination through shared activities

Interacting agents that interleave planning and execution must reach consensus on their commitments to each other. In domains where agents have varying degrees of interaction and different constraints on communication and computation, agents will require different coordination protocols in order to efficiently reach consensus in real time. We briefly describe a largely unexplored class of realtime, distributed planning problems (inspired by interacting spacecraft missions), new challenges they pose, and a general approach to solving the problems. These problems involve self-interested agents that have infrequent communication but collaborate on joint activities. We describe a Shared Activity Coordination (SHAC) framework that provides a decentralized algorithm for negotiating the scheduling of shared activities over the lifetimes of separate missions, a soft, real-time approach to reaching consensus during execution with limited communication, and a foundation for customizing protocols for negotiating planner interactions. We apply SHAC to a realistic simulation of interacting Mars missions and illustrate the simplicity of protocol development.

planning↗

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 NTRS2011

Utilization of Ancillary Data Sets for Conceptual SMAP Mission Algorithm Development and Product Generation

The planned Soil Moisture Active Passive (SMAP) mission is one of the first Earth observation satellites being developed by NASA in response to the National Research Council's Decadal Survey, Earth Science and Applications from Space: National Imperatives for the Next Decade and Beyond [1]. Scheduled to launch late in 2014, the proposed SMAP mission would provide high resolution and frequent revisit global mapping of soil moisture and freeze/thaw state, utilizing enhanced Radio Frequency Interference (RFI) mitigation approaches to collect new measurements of the hydrological condition of the Earth's surface. The SMAP instrument design incorporates an L-band radar (3 km) and an L band radiometer (40 km) sharing a single 6-meter rotating mesh antenna to provide measurements of soil moisture and landscape freeze/thaw state [2]. These observations would (1) improve our understanding of linkages between the Earth's water, energy, and carbon cycles, (2) benefit many application areas including numerical weather and climate prediction, flood and drought monitoring, agricultural productivity, human health, and national security, (3) help to address priority questions on climate change, and (4) potentially provide continuity with brightness temperature and soil moisture measurements from ESA's SMOS (Soil Moisture Ocean Salinity) and NASA's Aquarius missions. In the planned SMAP mission prelaunch time frame, baseline algorithms are being developed for generating (1) soil moisture products both from radiometer measurements on a 36 km grid and from combined radar/radiometer measurements on a 9 km grid, and (2) freeze/thaw products from radar measurements on a 3 km grid. These retrieval algorithms need a variety of global ancillary data, both static and dynamic, to run the retrieval models, constrain the retrievals, and provide flags for indicating retrieval quality. The choice of which ancillary dataset to use for a particular SMAP product would be based on a number of factors, including its availability and ease of use, its inherent error and resulting impact on the overall soil moisture or freeze/thaw retrieval accuracy, and its compatibility with similar choices made by the SMOS mission. All decisions regarding SMAP ancillary data sources would be fully documented by the SMAP Project and made available to the user community.

freeze/thaw↗

NASA NTRS1991

A workstation-based evaluation of a far-field route planner for helicopters

Helicopter flight missions at very low, nap of the Earth, altitudes place a heavy workload on the pilot. To aid in reducing this workload, Ames Research Center has been investigating various types of automated route planners. As part of an automated preflight mission planner, a route planner algorithm aids in selecting the overall (far-field) route to be flown. During the mission, the route planner can be used to replan a new route in case of unexpected threats or change in mission requirements. An evaluation of a candidate route planning algorithm, based on dynamic programming techniques is described. This algorithm meets most of the requirements for route planning, both preflight and during the mission. In general, the requirements are to minimize the distance and/or fuel and the deviation from a flight time schedule, and must be flyable within the constraints of available fuel and time.

Warner, David N., Jr.↗

NASA NTRS2011

Scheduling Results for the THEMIS Observation Scheduling Tool

We describe a scheduling system intended to assist in the development of instrument data acquisitions for the THEMIS instrument, onboard the Mars Odyssey spacecraft, and compare results from multiple scheduling algorithms. This tool creates observations of both (a) targeted geographical regions of interest and (b) general mapping observations, while respecting spacecraft constraints such as data volume, observation timing, visibility, lighting, season, and science priorities. This tool therefore must address both geometric and state/timing/resource constraints. We describe a tool that maps geometric polygon overlap constraints to set covering constraints using a grid-based approach. These set covering constraints are then incorporated into a greedy optimization scheduling algorithm incorporating operations constraints to generate feasible schedules. The resultant tool generates schedules of hundreds of observations per week out of potential thousands of observations. This tool is currently under evaluation by the THEMIS observation planning team at Arizona State University.

Thermal Emission Imaging System (THEMIS)↗

NASA NTRS2017

A Virtual Laboratory for Aviation and Airspace Prognostics Research

Integration of Unmanned Aerial Vehicles (UAVs), autonomy, spacecraft, and other aviation technologies, in the airspace is becoming more and more complicated, and will continue to do so in the future. Inclusion of new technology and complexity into the airspace increases the importance and difficulty of safety assurance. Additionally, testing new technologies on complex aviation systems and systems of systems can be challenging, expensive, and at times unsafe when implementing real life scenarios. The application of prognostics to aviation and airspace management may produce new tools and insight into these problems. Prognostic methodology provides an estimate of the health and risks of a component, vehicle, or airspace and knowledge of how that will change over time. That measure is especially useful in safety determination, mission planning, and maintenance scheduling. In our research, we develop a live, distributed, hardware- in-the-loop Prognostics Virtual Laboratory testbed for aviation and airspace prognostics. The developed testbed will be used to validate prediction algorithms for the real-time safety monitoring of the National Airspace System (NAS) and the prediction of unsafe events. In our earlier work1 we discussed the initial Prognostics Virtual Laboratory testbed development work and related results for milestones 1 & 2. This paper describes the design, development, and testing of the integrated tested which are part of milestone 3, along with our next steps for validation of this work. Through a framework consisting of software/hardware modules and associated interface clients, the distributed testbed enables safe, accurate, and inexpensive experimentation and research into airspace and vehicle prognosis that would not have been possible otherwise. The testbed modules can be used cohesively to construct complex and relevant airspace scenarios for research. Four modules are key to this research: the virtual aircraft module which uses the X-Plane simulator and X-PlaneConnect toolbox, the live aircraft module which connects fielded aircraft using onboard cellular communications devices, the hardware in the loop (HITL) module which connects laboratory based bench-top hardware testbeds and the research module which contains diagnostics and prognostics tools for analysis of live air traffic situations and vehicle health conditions. The testbed also features other modules for data recording and playback, information visualization, and air traffic generation. Software reliability, safety, and latency are some of the critical design considerations in development of the testbed.

LVC-DE↗

NASA NTRS2021

Demonstrations of System-Level Autonomy for Spacecraft

System-level autonomy refers to autonomously meeting the crosscutting needs of a system through awareness and coordinated control spanning the system's breadth of capabilities. In contrast to function-level autonomy, which focuses on capabilities required to achieve a specific function such as surface navigation or image recognition, system-level autonomy addresses the needs to coordinate and manage activities and resources, and estimate the state, across subsystems. This paper describes demonstrations that were conducted on a spacecraft workstation testbed. The autonomy was provided by system-level planning and execution integrated with system-level estimators of orbit knowledge and spacecraft hardware health. These components are embedded in a system-level framework defining how goals are formed and executed, which elements exist, and how control authority is distributed among components. The planning and execution system at the heart of the framework has the capability to schedule, execute and monitor completion of tasks, as well as plan around unexpected events including new science opportunities and anomalies. The planning and scheduling system is the Multi-mission EXECutive (MEXEC), supported by the system-level health state estimator Model-Based Off-Nominal State Identification and Detection (MONSID), and Autonomous Navigation (AutoNav) algorithms, which determine the orbital system state based on optical observation of other targets. These components are applicable to many kinds of missions on different platforms. These demonstrations were elaborations of earlier experiments conducted on the ASTERIA (Arcsecond Space Telescope Enabling Research In Astrophysics) CubeSat, described in a companion submission [1]. The spacecraft’s extended mission served as an in-flight test platform, during which some individual autonomous capabilities were flown successfully. The autonomy experiments described here were performed on the ASTERIA workstation testbed.

Prather, Maurice↗

NASA NTRS1993

A new technology for manufacturing scheduling derived from space system operations

A new technology for producing finite capacity schedules has been developed in response to complex requirements for operating space systems such as the Space Shuttle, the Space Station, and the Deep Space Network for telecommunications. This technology has proven its effectiveness in manufacturing environments where popular scheduling techniques associated with Materials Resources Planning (MRPII) and with factory simulation are not adequate for shop-floor work planning and control. The technology has three components. The first is a set of data structures that accommodate an extremely general description of a factory's resources, its manufacturing activities, and the constraints imposed by the environment. The second component is a language and set of software utilities that enable a rapid synthesis of functional capabilities. The third component is an algorithmic architecture called the Five Ruleset Model which accommodates the unique needs of each factory. Using the new technology, systems can model activities that generate, consume, and/or obligate resources. This allows work-in-process (WIP) to be generated and used; it permits constraints to be imposed or intermediate as well as finished goods inventories. It is also possible to match as closely as possible both the current factory state and future conditions such as promise dates. Schedule revisions can be accommodated without impacting the entire production schedule. Applications have been successful in both discrete and process manufacturing environments. The availability of a high-quality finite capacity production planning capability enhances the data management capabilities of MRP II systems. These schedules can be integrated with shop-floor data collection systems and accounting systems. Using the new technology, semi-custom systems can be developed at costs that are comparable to products that do not have equivalent functional capabilities and/or extensibility.

Hornstein, R. S.↗

NASA NTRS1992

Reducing the complexity of software systems - A strategic software perspective

The results of a combined management and technical initiative aimed at reducing the size and complexity associated with developing operations planning, scheduling, and resource management software systems are presented. The initiative has produced operations concepts, functional requirements, system architectures, a comprehensive lexicon, and software tools to revolutionize the traditional software technology and development practices for planning, scheduling, and resource management systems used in space operations control centers. Examples of technology and practices to reduce complexity include a method for projecting design consequences from an operations concept, a universal architecture for heuristic algorithms, an object-oriented framework for describing large classes of problems that parametrically adapt to all domain peculiarities, the identification of general approaches which respond to changes with minimum impact on systems implementations, and a management structure for prototyping to minimize the risks of ill-conceived designs.

Hornstein, Rhoda S.↗

NASA NTRS2010

The Orion GN and C Data-Driven Flight Software Architecture for Automated Sequencing and Fault Recovery

The Orion Crew Exploration Vehicle (CET) is being designed to include significantly more automation capability than either the Space Shuttle or the International Space Station (ISS). In particular, the vehicle flight software has requirements to accommodate increasingly automated missions throughout all phases of flight. A data-driven flight software architecture will provide an evolvable automation capability to sequence through Guidance, Navigation & Control (GN&C) flight software modes and configurations while maintaining the required flexibility and human control over the automation. This flexibility is a key aspect needed to address the maturation of operational concepts, to permit ground and crew operators to gain trust in the system and mitigate unpredictability in human spaceflight. To allow for mission flexibility and reconfrgurability, a data driven approach is being taken to load the mission event plan as well cis the flight software artifacts associated with the GN&C subsystem. A database of GN&C level sequencing data is presented which manages and tracks the mission specific and algorithm parameters to provide a capability to schedule GN&C events within mission segments. The flight software data schema for performing automated mission sequencing is presented with a concept of operations for interactions with ground and onboard crew members. A prototype architecture for fault identification, isolation and recovery interactions with the automation software is presented and discussed as a forward work item.

King, Ellis↗

NASA NTRSDate not supplied

Explaining Soft-Goal Conflicts through Constraint Relaxations

Recent work suggests to explain trade-offs between soft goals in terms of their conflicts, i. e., minimal unsolvable soft-goal subsets. But this does not explain the conflicts themselves: Why can a given set of soft-goals not be jointly achieved? Here we approach that question in terms of the underlying constraints on plans in the task at hand, namely resource availability and time windows. In this context, a natural form of explanation for a soft-goal conflict is a minimal constraint relaxation under which the conflict disappears (“if the deadline was 1 hour later, it would work”). We explore algorithms for computing such explanations. A baseline is to simply loop over all relaxed tasks and compute the conflicts for each separately. We improve over this by two algorithms that leverage information – conflicts, reachable states – across relaxed tasks. We show that these algorithms can exponentially outperform the baseline in theory, and we run experiments confirming that advantage in practice.

Planning↗

NASA NTRS2004

Argumentation for coordinating shared activities

an increasing need for space missions to be able to collaboratively (and competitively) develop plans both within and across missions. In addition, interacting spacecraft that interleave onboard planning and execution must reach consensus on their commitments to each other prior to execution. In domains where missions have varying degrees of interaction and different constraints on communication and computation, the missions will require different coordination protocols in order to efficiently reach consensus with in their imposed deadlines. We describe a Shared Activity Coordination (SHAC) framework that provides a decentralized algorithm for negotiating the scheduling of shared activities over the lifetimes of multiple agents and a foundation for customizing protocols for negotiating planner interactions. We investigate variations of a few simple protocols based on argumentation and distributed constraints satisfaction techniques and evaluate their abilities to reach consistent solutions according to computation, time, and communication costs in an abstract domain where spacecraft propose joint measurements.

Mars↗

NASA NTRSDate not supplied

Optimized Trajectory Correction Burn Placement for NRHO Orbit Maintenance

NASA's future Artemis missions plan to utilize a near rectilinear halo orbit (NRHO) in the lunar vicinity to facilitate access to the lunar surface and place other critical assets to support human exploration. This exploration architecture requires a vehicle to remain in the NRHO for long periods of time ranging from several days, to weeks, to months, and even years. Consequently, periodic orbit maintenance burns become essential to ensure the spacecraft follows the desired reference trajectory in an efficient yet effective manner despite crew activity, navigation uncertainty, maneuver execution errors, disturbance accelerations, orbit insertion dispersions, and other system limitations. This work introduces a targeting algorithm that can be utilized to analyze a variety of targeting constraints and parameters that maximizes overall performance. Techniques associated with robust trajectory optimization are used to identify the optimized number and placement for NRHO trajectory correction (NTC) burns that accounts for the mission schedule, both a primary and backup navigation system, targeting strategies and burn plan configurations, vehicle venting, thruster selection, and integrated GN\&C performance. A notional scenario extracted from the NASA Artemis III mission is used to motivate and demonstrate these concepts and performance results.

Linear Covariance Analysis↗