SEARCH · Engineering Papers

Results for “Routing algorithm”

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 235 records · Page 13

All sources NASA NTRS DOE OSTI

NASA NTRS1987

Space-Subdivision Algorithm for Abstract Trajectories

Computational overhead in testing links between nodes reduced. Computationally efficient algorithm facilitates subdivision of n-dimensional spaces during selection, testing, or optimization of trajectories in those spaces. Reduces cost of computation in such diverse problems as scheduling of interrelated events to avoid conflicts, devising efficient production-line layouts and operating schedules, routing telephone calls, and analyzing the motions of gas particles.

Lyon, Douglas K.↗

NASA NTRS2012

Airborne Precision Spacing (APS) Dependent Parallel Arrivals (DPA)

The Airborne Precision Spacing (APS) team at the NASA Langley Research Center (LaRC) has been developing a concept of operations to extend the current APS concept to support dependent approaches to parallel or converging runways along with the required pilot and controller procedures and pilot interfaces. A staggered operations capability for the Airborne Spacing for Terminal Arrival Routes (ASTAR) tool was developed and designated as ASTAR10. ASTAR10 has reached a sufficient level of maturity to be validated and tested through a fast-time simulation. The purpose of the experiment was to identify and resolve any remaining issues in the ASTAR10 algorithm, as well as put the concept of operations through a practical test.

Smith, Colin L.↗

NASA NTRSDate not supplied

Autonomous Stabilization and Orientation Control of Hoisted Payloads

An orientation control system prototype has been developed for hoisted payloads. This system will allow payloads to be lifted off inclined surfaces while maintaining orientation control, allowing removal of tightly packed payloads without colliding with adjacent objects. For this concept, the payload is hoisted with a crane using a rigging system composed of a cable routed through two capstans and three or four attachment points on the payload. Motors rotate the capstans to adjust the cable lengths to the payload, and thereby control the orientation of the payload. Initial testing of the prototype was completed using manual control, however the algorithms necessary to fully automate the system are presented in this paper.

control↗

NASA NTRS1981

Evaluation of Microwave Landing System (MLS) effect on the delivery performance of a fixed-path metering and spacing system

Metering and spacing (M & S) system's algorithms described assume an aircraft two dimensional are navigation capability. The three navigation systems compared were: very high frequency omnidirectional range/distance measuring equipment (VOR/DME) and ILS, VOR/DME and + or - 40 MLS, and VOR/DME and + or - 60 MLS. Other factors studied were M & S tentative schedule point location, route geometry effects, and approach gate location effects. Summarized results are: the MLS offers some improvement over VOR/DME and ILS if all approach routes contain computer assisted turns; pilot reaction to moving the gate closer to the runway threshold may adversely affect M & S performance; and coupling en route metering to terminal scheduling transfers most of the terminal holding to more full efficient, higher altitude en route delay.

Credeur, L.↗

NASA NTRS1995

Performance and policy dimensions in internet routing

The Internet Routing Project, referred to in this report as the 'Highball Project', has been investigating architectures suitable for networks spanning large geographic areas and capable of very high data rates. The Highball network architecture is based on a high speed crossbar switch and an adaptive, distributed, TDMA scheduling algorithm. The scheduling algorithm controls the instantaneous configuration and swell time of the switch, one of which is attached to each node. In order to send a single burst or a multi-burst packet, a reservation request is sent to all nodes. The scheduling algorithm then configures the switches immediately prior to the arrival of each burst, so it can be relayed immediately without requiring local storage. Reservations and housekeeping information are sent using a special broadcast-spanning-tree schedule. Progress to date in the Highball Project includes the design and testing of a suite of scheduling algorithms, construction of software reservation/scheduling simulators, and construction of a strawman hardware and software implementation. A prototype switch controller and timestamp generator have been completed and are in test. Detailed documentation on the algorithms, protocols and experiments conducted are given in various reports and papers published. Abstracts of this literature are included in the bibliography at the end of this report, which serves as an extended executive summary.

Mills, David L.↗

NASA NTRS2000

Improved Results for Route Planning in Stochastic Transportation Networks

In the bus network problem, the goal is to generate a plan for getting from point X to point Y within a city using buses in the smallest expected time. Because bus arrival times are not determined by a fixed schedule but instead may be random. the problem requires more than standard shortest path techniques. In recent work, Datar and Ranade provide algorithms in the case where bus arrivals are assumed to be independent and exponentially distributed. We offer solutions to two important generalizations of the problem, answering open questions posed by Datar and Ranade. First, we provide a polynomial time algorithm for a much wider class of arrival distributions, namely those with increasing failure rate. This class includes not only exponential distributions but also uniform, normal, and gamma distributions. Second, in the case where bus arrival times are independent and geometric discrete random variable,. we provide an algorithm for transportation networks of buses and trains, where trains run according to a fixed schedule.

Boyan, Justin↗

NASA NTRS2008

Integrated Software Systems for Crew Management During Extravehicular Activity in Planetary Terrain Exploration

Initial planetary explorations with the Apollo program had a veritable ground support army monitoring the safety and health of the 12 astronauts who performed lunar surface extravehicular activities (EVAs). Given the distances involved, this will not be possible on Mars. A spacesuit for Mars must be smart enough to replace that army. The next generation suits can do so using 2 software systems serving as virtual companions, LEGACI (Life support, Exploration Guidance Algorithm and Consumable Interrogator) and VIOLET (Voice Initiated Operator for Life support and Exploration Tracking). The system presented in this study integrates data inputs from a suite of sensors into the MIII suit s communications, avionics and informatics hardware for distribution to remote managers and data analysis. If successful, the system has application not only for Mars but for nearer term missions to the Moon, and the next generation suits used on ISS as well. Field tests are conducted to assess capabilities for next generation spacesuits at Johnson Space Center (JSC) as well as the Mars and Lunar analog (Devon Island, Canada). LEGACI integrates data inputs from a suite of noninvasive biosensors in the suit and the astronaut (heart rate, suit inlet/outlet lcg temperature and flowrate, suit outlet gas and dewpoint temperature, pCO2, suit O2 pressure, state vector (accelerometry) and others). In the Integrated Walkback Suit Tests held at NASA-JSC and the HMP tests at Devon Island, communication and informatics capabilities were tested (including routing by satellite from the suit at Devon Island to JSC in Houston via secure servers at VCU in Richmond, VA). Results. The input from all the sensors enable LEGACI to compute multiple independent assessments of metabolic rate, from which a "best" met rate is chosen based on statistical methods. This rate can compute detailed information about the suit, crew and EVA performance using test-derived algorithms. VIOLET gives LEGACI voice activation capability, allowing the crew to query the suit, and receive feedback and alerts that will lead to corrective action. LEGACI and VIOLET can also automatically control the astronaut's cooling and consumable use rate without crew input if desired. These findings suggest that non-invasive physiological and environmental sensors supported with data analysis can allow for more effective management of mission task performance during EVA. Integrated remote and local view of data metrics allow crewmember to receive real time feedback in synch with mission control in preventing performance shortcomings for EVA in exploration missions.

Kuznetz, Lawrence↗

NASA NTRS2003

Methodology for Generating Conflict Scenarios by Time Shifting Recorded Traffic Data

A methodology is presented for generating conflict scenarios that can be used as test cases to estimate the operational performance of a conflict probe. Recorded air traffic data is time shifted to create traffic scenarios featuring conflicts with characteristic properties similar to those encountered in typical air traffic operations. First, a reference set of conflicts is obtained from trajectories that are computed using birth points and nominal flight plans extracted from recorded traffic data. Distributions are obtained for several primary properties (e.g., encounter angle) that are most likely to affect the performance of a conflict probe. A genetic algorithm is then utilized to determine the values of time shifts for the recorded track data so that the primary properties of conflicts generated by the time shifted data match those of the reference set. This methodology is successfully demonstrated using recorded traffic data for the Memphis Air Route Traffic Control Center; a key result is that the required time shifts are less than 5 min for 99% of the tracks. It is also observed that close matching of the primary properties used in this study additionally provides a good match for some other secondary properties.

Paglione, Mike↗

NASA NTRS1988

Scan line graphics generation on the massively parallel processor

Described here is how researchers implemented a scan line graphics generation algorithm on the Massively Parallel Processor (MPP). Pixels are computed in parallel and their results are applied to the Z buffer in large groups. To perform pixel value calculations, facilitate load balancing across the processors and apply the results to the Z buffer efficiently in parallel requires special virtual routing (sort computation) techniques developed by the author especially for use on single-instruction multiple-data (SIMD) architectures.

Dorband, John E.↗

NASA NTRS2013

NASA Tech Briefs, September 2013

Topics include: ISS Ammonia Leak Detection Through X-Ray Fluorescence; A System for Measuring the Sway of the Vehicle Assembly Building; Fast, High-Precision Readout Circuit for Detector Arrays; Victim Simulator for Victim Detection Radar; Hydrometeor Size Distribution Measurements by Imaging the Attenuation of a Laser Spot; Quasi-Linear Circuit; High-Speed, High-Resolution Time-to-Digital Conversion; Li-Ion Battery and Supercapacitor Hybrid Design for Long Extravehicular Activities; Ultrasonic Low-Friction Containment Plate for Thermal and Ultrasonic Stir Weld Processes; High-Powered, Ultrasonically Assisted Thermal Stir Welding; Next-Generation MKIII Lightweight HUT/Hatch Assembly; Centrifugal Sieve for Gravity-Level-Independent Size; Segregation of Granular Materials; Ion Exchange Technology Development in Support of the Urine Processor Assembly; Nickel-Graphite Composite Compliant Interface and/or Hot Shoe Material; UltraSail CubeSat Solar Sail Flight Experiment; Mechanism for Deploying a Long, Thin-Film Antenna From a Rover; Counterflow Regolith Heat Exchanger; Acquisition and Retaining Granular Samples via a Rotating Coring Bit; Very-Low-Cost, Rugged Vacuum System; Medicine Delivery Device With Integrated Sterilization and Detection; FRET-Aptamer Assays for Bone Marker Assessment, C-Telopeptide, Creatinine, and Vitamin D; Multimode Directional Coupler for Utilization of Harmonic Frequencies from TWTAs; Dual-Polarization, Multi-Frequency Antenna Array for use with Hurricane Imaging Radiometer; Complementary Barrier Infrared Detector (CBIRD) Contact Methods; Autonomous Control of Space Nuclear Reactors; High-Power, High-Speed Electro-Optic Pockels Cell Modulator; Covariance Analysis Tool (G-CAT) for Computing Ascent, Descent, and Landing Errors; Enigma Version 12; Micrometeoroid and Orbital Debris (MMOD) Shield Ballistic Limit Analysis Program; Spitzer Telemetry Processing System; Planetary Protection Bioburden Analysis Program; Wing Leading Edge RCC Rapid Response Damage Prediction Tool (IMPACT2); ISSM: Ice Sheet System Model; Automated Loads Analysis System (ATLAS); Integrated Main Propulsion System Performance Reconstruction Process/Models. Phoenix Telemetry Processor; Contact Graph Routing Enhancements Developed in ION for DTN; GFEChutes Lo-Fi; Advanced Strategic and Tactical Relay Request Management for the Mars Relay Operations Service; Software for Generating Troposphere Corrections for InSAR Using GPS and Weather Model Data; Ionospheric Specifications for SAR Interferometry (ISSI); Implementation of a Wavefront-Sensing Algorithm; Sally Ride EarthKAM - Automated Image Geo-Referencing Using Google Earth Web Plug-In; Trade Space Specification Tool (TSST) for Rapid Mission Architecture (Version 1.2); Acoustic Emission Analysis Applet (AEAA) Software; Memory-Efficient Onboard Rock Segmentation; Advanced Multimission Operations System (ATMO); Robot Sequencing and Visualization Program (RSVP); Automating Hyperspectral Data for Rapid Response in Volcanic Emergencies; Raster-Based Approach to Solar Pressure Modeling; Space Images for NASA JPL Android Version; Kinect Engineering with Learning (KEWL); Spacecraft 3D Augmented Reality Mobile App; MPST Software: grl_pef_check; Real-Time Multimission Event Notification System for Mars Relay; SIM_EXPLORE: Software for Directed Exploration of Complex Systems; Mobile Timekeeping Application Built on Reverse-Engineered JPL Infrastructure; Advanced Query and Data Mining Capabilities for MaROS; Jettison Engineering Trajectory Tool; MPST Software: grl_suppdoc; PredGuid+A: Orion Entry Guidance Modified for Aerocapture; Planning Coverage Campaigns for Mission Design and Analysis: CLASP for DESDynl; and Space Place Prime.

Source record↗

NASA NTRSDate not supplied

Advancing Autonomy in Distributed Space Systems: Insights From on-Orbit Testing with the Starling 1.0 Mission

Autonomous decision-making is crucial for enhancing mission effectiveness in Distributed Space Systems (DSS), particularly in multi-spacecraft operations where communication constraints and mission complexity pose challenges. The Distributed Spacecraft Autonomy (DSA) team at NASA’s Ames Research Center is advancing autonomy in DSS through five key technical areas: distributed resource and task management, reactive operations, system modeling and simulation, human-swarm interaction, and ad hoc network communications. The DSA experiment onboard the Starling 1.0 Mission showcases collaborative resource allocation for multi-point science data collection with four small spacecraft. Autonomy in decision-making is highlighted as a crucial factor for multi-spacecraft missions, enabling spacecraft to operate independently, reducing reliance on ground control. This capability is particularly significant for future deep-space missions, where communication delays and limited data transmission capacity make traditional command and control approaches impractical. This demonstration focuses on a GPS Channel Selection Experiment, leveraging emergent capabilities like "shared sampling" and "simultaneous sampling" to optimize channel selection across the spacecraft swarm. The experiment aims to capture ionospheric phenomena such as the Equatorial Ionization Anomaly and Polar Patches. The DSA system's autonomous reconfiguration ability is showcased, emphasizing its adaptability to natural phenomena without significant integration efforts. The GPS Channel Selection Experiment utilizes a dual-band GPS receiver to estimate plasma density in the ionosphere. Explorative and exploitative channel selections are employed based on the nature of observed phenomena. The performance of DSA algorithms is evaluated in terms of optimal channel allocations and responsiveness to changes in observed features. The DSA Flight Software utilizes the Core Flight System (cFS) framework, ensuring compatibility with the Starling 1.0 flight mission software. DSA showcases results from RTI’s Connext DDS Micro communication middleware, enabling message routing over the Ad-Hoc Network of Starling 1.0. This paper provides a comprehensive overview of the DSA experiment's initial results, emphasizing the advancements in autonomy for Distributed Space Systems and the successful collaboration with the Starling 1.0 mission.

Caleb Ashmore Adams↗

NASA NTRS2009

Convective Weather Avoidance with Uncertain Weather Forecasts

Convective weather events have a disruptive impact on air traffic both in terminal area and in en-route airspaces. In order to make sure that the national air transportation system is safe and efficient, it is essential to respond to convective weather events effectively. Traffic flow control initiatives in response to convective weather include ground delay, airborne delay, miles-in-trail restrictions as well as tactical and strategic rerouting. The rerouting initiatives can potentially increase traffic density and complexity in regions neighboring the convective weather activity. There is a need to perform rerouting in an intelligent and efficient way such that the disruptive effects of rerouting are minimized. An important area of research is to study the interaction of in-flight rerouting with traffic congestion or complexity and developing methods that quantitatively measure this interaction. Furthermore, it is necessary to find rerouting solutions that account for uncertainties in weather forecasts. These are important steps toward managing complexity during rerouting operations, and the paper is motivated by these research questions. An automated system is developed for rerouting air traffic in order to avoid convective weather regions during the 20- minute - 2-hour time horizon. Such a system is envisioned to work in concert with separation assurance (0 - 20-minute time horizon), and longer term air traffic management (2-hours and beyond) to provide a more comprehensive solution to complexity and safety management. In this study, weather is dynamic and uncertain; it is represented as regions of airspace that pilots are likely to avoid. Algorithms are implemented in an air traffic simulation environment to support the research study. The algorithms used are deterministic but periodically revise reroutes to account for weather forecast updates. In contrast to previous studies, in this study convective weather is represented as regions of airspace that pilots are likely to avoid. The automated system periodically updates forecasts and reassesses rerouting decisions in order to account for changing weather predictions. The main objectives are to reroute flights to avoid convective weather regions and determine the resulting complexity due to rerouting. The eventual goal is to control and reduce complexity while rerouting flights during the 20 minute - 2 hour planning period. A three-hour simulation is conducted using 4800 flights in the national airspace. The study compares several metrics against a baseline scenario using the same traffic and weather but with rerouting disabled. The results show that rerouting can have a negative impact on congestion in some sectors, as expected. The rerouting system provides accurate measurements of the resulting complexity in the congested sectors. Furthermore, although rerouting is performed only in the 20-minute - 2-hour range, it results in a 30% reduction in encounters with nowcast weather polygons (100% being the ideal for perfectly predictable and accurate weather). In the simulations, rerouting was performed for the 20-minute - 2-hour flight time horizon, and for the en-route segment of air traffic. The implementation uses CWAM, a set of polygons that represent probabilities of pilot deviation around weather. The algorithms were implemented in a software-based air traffic simulation system. Initial results of the system's performance and effectiveness were encouraging. Simulation results showed that when flights were rerouted in the 20-minute - 2-hour flight time horizon of air traffic, there were fewer weather encounters in the first 20 minutes than for flights that were not rerouted. Some preliminary results were also obtained that showed that rerouting will also increase complexity. More simulations will be conducted in order to report conclusive results on the effects of rerouting on complexity. Thus, the use of the 20-minute - 2-hour flight time horizon weather avoidance teniques performed in the simulation is expected to provide benefits for short-term weather avoidance.

Karahan, Sinan↗

NASA NTRS2004

Securing Mobile Networks in an Operational Setting

This paper describes a network demonstration and three month field trial of mobile networking using mobile-IPv4. The network was implemented as part of the US Coast Guard operational network which is a ".mil" network and requires stringent levels of security. The initial demonstrations took place in November 2002 and a three month field trial took place from July through September of 2003. The mobile network utilized encryptors capable of NSA-approved Type 1 algorithms, mobile router from Cisco Systems and 802.11 and satellite wireless links. This paper also describes a conceptual architecture for wide-scale deployment of secure mobile networking in operational environments where both private and public infrastructure is used. Additional issues presented include link costs, placement of encryptors and running routing protocols over layer-3 encryption devices.

Ivancic, William D.↗

NASA NTRS2019

Weather Design Considerations for the TASAR Traffic Aware Planner

The Traffic Aware Planner (TAP) is a decision support automation tool for trajectory planning and optimization intended for use on today’s flight deck. Drawing from a variety of on- and off-board data sources, TAP employs a sophisticated trajectory optimization algorithm that provides the aircrew with fuel- and time-saving reroute recommendations that are free of known conflicts with traffic, special use airspace, and severe convective weather. As this kind of weather is a significant part of the pilot’s decision-making process while planning trajectory changes en route, a series of investigations has been conducted into the integration of weather data and associated functionality into the TAP software. This paper reviews the weather data sources and functionality that have been incorporated into TAP to date, along with experience gathered in the course of the design process.

Lewis, Timothy A.↗

NASA NTRS2007

Real-Time Application of Multi-Satellite Precipitation Analysis for Floods and Landslides

Satellite data acquired and processed in real time now have the potential to provide the spacetime information on rainfall needed to monitor flood and landslide events around the world. This can be achieved by integrating the satellite-derived forcing data with hydrological models and landslide algorithms. Progress in using the TRMM Multi-satellite Precipitation Analysis (TMPA) as input to flood and landslide forecasts is outlined, with a focus on understanding limitations of the rainfall data and impacts of those limitations on flood/landslide analyses. Case studies of both successes and failures will be shown, as well as comparison with ground comparison data sets-- both in terms of rainfall and in terms of flood/landslide events. In addition to potential uses in real-time, the nearly ten years of TMPA data allow retrospective running of the models to examine variations in extreme events. The flood determination algorithm consists of four major components: 1) multi-satellite precipitation estimation; 2) characterization of land surface including digital elevation from NASA SRTM (Shuttle Radar Terrain Mission), topography-derived hydrologic parameters such as flow direction, flow accumulation, basin, and river network etc.; 3) a hydrological model to infiltrate rainfall and route overland runoff; and 4) an implementation interface to relay the input data to the models and display the flood inundation results to potential users and decision-makers, In terms of landslides, the satellite rainfall information is combined with a global landslide susceptibility map, derived from a combination of global surface characteristics (digital elevation topography, slope, soil types, soil texture, and land cover classification etc.) using a weighted linear combination approach. In those areas identified as "susceptible" (based on the surface characteristics), landslides are forecast where and when a rainfall intensity/duration threshold is exceeded. Results are described indicating general agreement with landslide occurrences.

Adler, Robert↗

NASA NTRS2007

Application of Multi-Satellite Precipitation Analysis to Floods and Landslides

Satellite data acquired and processed in real time now have the potential to provide the spacetime information on rainfall needed to monitor flood and landslide events around the world. This can be achieved by integrating the satellite-derived forcing data with hydrological models and landslide algorithms. Progress in using the TRMM Multi-satellite Precipitation Analysis (TMPA) as input to flood and landslide forecasts is outlined, with a focus on understanding limitations of the rainfall data and impacts of those limitations on flood/landslide analyses. Case studies of both successes and failures will be shown, as well as comparison with ground comparison data sets both in terms of rainfall and in terms of flood/landslide events. In addition to potential uses in real-time, the nearly ten years of TMPA data allow retrospective running of the models to examine variations in extreme events. The flood determination algorithm consists of four major components: 1) multi-satellite precipitation estimation; 2) characterization of land surface including digital elevation from NASA SRTM (Shuttle Radar Terrain Mission), topography-derived hydrologic parameters such as flow direction, flow accumulation, basin, and river network etc.; 3) a hydrological model to infiltrate rainfall and route overland runoff; and 4) an implementation interface to relay the input data to the models and display the flood inundation results to potential users and decision-makers. In terms of landslides, the satellite rainfall information is combined with a global landslide susceptibility map, derived from a combination of global surface characteristics (digital elevation topography, slope, soil types, soil texture, and land cover classification etc.) using a weighted linear combination approach. In those areas identified as "susceptible" (based on the surface characteristics), landslides are forecast where and when a rainfall intensity/duration threshold is exceeded. Results are described indicating general agreement with landslide occurrences. However, difficulties in comparing landslide event information (mostly from news reports) with the satellite-based forecasts are analyzed.

Adler, Robert↗

NASA NTRS1987

A system for routing arbitrary directed graphs on SIMD architectures

There are many problems which can be described in terms of directed graphs that contain a large number of vertices where simple computations occur using data from connecting vertices. A method is given for parallelizing such problems on an SIMD machine model that is bit-serial and uses only nearest neighbor connections for communication. Each vertex of the graph will be assigned to a processor in the machine. Algorithms are given that will be used to implement movement of data along the arcs of the graph. This architecture and algorithms define a system that is relatively simple to build and can do graph processing. All arcs can be transversed in parallel in time O(T), where T is empirically proportional to the diameter of the interconnection network times the average degree of the graph. Modifying or adding a new arc takes the same time as parallel traversal.

Tomboulian, Sherryl↗

NASA NTRS1984

Application of fuel/time minimization techniques to route planning and trajectory optimization

Rising fuel costs combined with other economic pressures have resulted in industry requirements for more efficient air traffic control and airborne operations. NASA has responded with an on-going research program to investigate the requirements and benefits of using new airborne guidance and pilot procedures that are compatible with advanced air traffic control systems and that will result in more fuel efficient flight. The results of flight testing an airborne computer algorithm designed to provide either open-loop or closed-loop guidance for fuel efficient descents while satisfying time constraints imposed by the air traffic control system is summarized. Some of the potential cost and fuel savings that are obtained with sophisticated vertical path optimization capabilities are described.

Knox, C. E.↗