Engineering Papers⌕ Search

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.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 127 records · Page 7
All sourcesNASA NTRSDOE OSTI
NASA NTRS2011

Defining Dynamic Route Structure

This poster describes a method for defining route structure from flight tracks. Dynamically generated route structures could be useful in guiding dynamic airspace configuration and helping controllers retain situational awareness under dynamically changing traffic conditions. Individual merge and diverge intersections between pairs of flights are identified, clustered, and grouped into nodes of a route structure network. Links are placed between nodes to represent major traffic flows. A parametric analysis determined the algorithm input parameters producing route structures of current day flight plans that are closest to todays airway structure. These parameters are then used to define and analyze the dynamic route structure over the course of a day for current day flight paths. Route structures are also compared between current day flight paths and more user preferred paths such as great circle and weather avoidance routing.

Zelinski, Shannon↗
NASA NTRS2012

Identification of Robust Terminal-Area Routes in Convective Weather

Convective weather is responsible for large delays and widespread disruptions in the U.S. National Airspace System, especially during summer. Traffic flow management algorithms require reliable forecasts of route blockage to schedule and route traffic. This paper demonstrates how raw convective weather forecasts, which provide deterministic predictions of the vertically integrated liquid (the precipitation content in a column of airspace) can be translated into probabilistic forecasts of whether or not a terminal area route will be blocked. Given a flight route through the terminal area, we apply techniques from machine learning to determine the likelihood that the route will be open in actual weather. The likelihood is then used to optimize terminalarea operations by dynamically moving arrival and departure routes to maximize the expected capacity of the terminal area. Experiments using real weather scenarios on stormy days show that our algorithms recommend that a terminal-area route be modified 30% of the time, opening up 13% more available routes that were forecast to be blocked during these scenarios. The error rate is low, with only 5% of cases corresponding to a modified route being blocked in reality, whereas the original route is in fact open. In addition, for routes predicted to be open with probability 0.95 or greater by our method, 96% of these routes (on average over time horizon) are indeed open in the weather that materializes

Pfeil, Diana Michalek↗
DOE OSTI2024

A real-time energy and cost efficient vehicle route assignment neural recommender system

Here, this paper presents a neural network recommender system algorithm for assigning vehicles to routes based on energy and cost criteria. In this work, we applied this new approach to efficiently identify the most cost-effective medium and heavy duty truck (MDHDT) powertrain technology, from a total cost of ownership (TCO) perspective, for given trips. We employ a machine learning based approach to efficiently estimate the energy consumption of various candidate vehicles over given routes, defined as sequences of links (road segments), with little information known about internal dynamics, i.e. using high level macroscopic route information. A complete recommendation logic is then developed to allow for real-time optimum assignment for each route, subject to the operational constraints of the fleet. We show how this framework can be used to (1) efficiently provide a single trip recommendation with a top-k vehicles star ranking system, and (2) engage in more general assignment problems where n vehicles need to be deployed over m (m ≤ n) trips. This new assignment system has been deployed and integrated into the POLARIS. Transportation System Simulation Tool for use in research conducted by the Department of Energy's Systems and Modeling for Accelerated Research in Transportation (SMART) Mobility Consortium (SMART, 2024).

Energy consumption↗
NASA NTRS2010

How Formal Methods Impels Discovery: A Short History of an Air Traffic Management Project

In this paper we describe a process of algorithmic discovery that was driven by our goal of achieving complete, mechanically verified algorithms that compute conflict prevention bands for use in en route air traffic management. The algorithms were originally defined in the PVS specification language and subsequently have been implemented in Java and C++. We do not present the proofs in this paper: instead, we describe the process of discovery and the key ideas that enabled the final formal proof of correctness

Butler, Ricky W.↗
DOE OSTI2026

Data Fusion for the Development of a Multimodal Freight Transload Facilities Dataset in the U.S.

To withstand the growing demand of commodity volume and its strain on the transportation infrastructure, it is necessary to identify the flow of commodities by route and mode. However, a national multimodal freight routing model does not exist for the U.S. The development of such model requires multiple building blocks, such as virtual representations of roadway, railway, and waterway networks, transload facilities (TFs), and access/egress links. Most of these blocks have a robust database in the U.S., except for the TFs. Here, this paper presents the fusion of dispersed and heterogeneous representations of multimodal TFs into a single, comprehensive, geospatial freight TF dataset. The TF dataset is derived from several sources, including the U.S. Army Corps of Engineers Master Docks Plus, the National Transportation Atlas Database, the Intermodal Association of North America, industry publications, and other public information. First, individual datasets were queried and reconciled. A geocoding/reverse geocoding process was applied to get the best street address and latitude/longitude location for each terminal. Then, duplicate terminals were identified by a fuzzy match algorithm based on terminal name and location, and removed. Validation was performed by visual inspection of random facilities. The main contributions of this work are: a publicly available version of the TF dataset, including facility location and multimodal transfer capability of 9,003 facilities, and an enterprise-version with the same facilities but including commodity handling capabilities. The main purpose of developing the TF dataset is to inform multimodal routing algorithms. The proposed TF dataset allows for credibly modeling the multimodal transfer of commodities within shipment routes.

Commodity Routing↗
DOE OSTI2023

Systemwide Planning with a Branch-and-Price Algorithm for Pavement-Marking Assessment Data Collection via the Mobile Retroreflectivity Unit Routing Model

The visibility of pavement markings is one of the most critical factors for traffic safety, and a periodical assessment plan is crucial for maintaining this function. Traditional assessment methods, such as visual windshield surveys or manual testing using handheld devices, are unsafe, time-consuming, and labor-intensive. In recent years, transportation agencies have begun to adopt the use of mobile retroreflectivity units (MRUs) for condition assessment of pavement markings. MRUs, different from other manual methods, can be utilized to collect large-scale retroreflectivity data in an efficient manner. However, no relevant research has yet proposed a mathematical optimization model for arranging the evaluation schedule and paths of MRUs. This study aims to propose a MRU routing model, and an efficient solution methodology. A branch-and-price algorithm, including column generation and branch-and-bound, was implemented. Computational experiments have been conducted based on actual tasks from the Florida MRU program for validation. In conclusion, results show that the proposed solution methodology with a set partitioning model in this study not only finds the optimal solution for problems with tasks less than 60, but also effectively narrows the solution gap to be within 1.0% for problems with tasks less than 131.

42 ENGINEERING↗
DOE OSTI2016

Security-Oriented and Load-Balancing Wireless Data Routing Game in the Integration of Advanced Metering Infrastructure Network in Smart Grid

Ensuring flexible and reliable data routing is indispensable for the integration of Advanced Metering Infrastructure (AMI) networks, we propose a secure-oriented and load-balancing wireless data routing scheme. A novel utility function is designed based on security routing scheme. Then, we model the interactive security-oriented routing strategy among meter data concentrators or smart grid meters as a mixed-strategy network formation game. Finally, such problem results in a stable probabilistic routing scheme with proposed distributed learning algorithm. One contributions is that we studied that different types of applications affect the routing selection strategy and the strategy tendency. Another contributions is that the chosen strategy of our mixed routing can adaptively to converge to a new mixed strategy Nash equilibrium (MSNE) during the learning process in the smart grid.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2020

Time-reversal of an unknown quantum state

For decades, researchers have sought to understand how the irreversibility of the surrounding world emerges from the seemingly time-symmetric, fundamental laws of physics. Quantum mechanics conjectured a clue that final irreversibility is set by the measurement procedure and that the time-reversal requires complex conjugation of the wave function, which is overly complex to spontaneously appear in nature. Building on this Landau-Wigner conjecture, it became possible to demonstrate that time-reversal is exponentially improbable in a virgin nature and to design an algorithm artificially reversing a time arrow for a given quantum state on the IBM quantum computer. However, the implemented arrow-of-time reversal embraced only the known states initially disentangled from the thermodynamic reservoir. Here we develop a procedure for reversing the temporal evolution of an arbitrary unknown quantum state. This opens the route for general universal algorithms sending temporal evolution of an arbitrary system backward in time.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2017

Using Map Service API for Driving Cycle Detection for Wearable GPS Data: Preprint

Following advancements in smartphone and portable global positioning system (GPS) data collection, wearable GPS data have realized extensive use in transportation surveys and studies. The task of detecting driving cycles (driving or car-mode trajectory segments) from wearable GPS data has been the subject of much research. Specifically, distinguishing driving cycles from other motorized trips (such as taking a bus) is the main research problem in this paper. Many mode detection methods only focus on raw GPS speed data while some studies apply additional information, such as geographic information system (GIS) data, to obtain better detection performance. Procuring and maintaining dedicated road GIS data are costly and not trivial, whereas the technical maturity and broad use of map service application program interface (API) queries offers opportunities for mode detection tasks. The proposed driving cycle detection method takes advantage of map service APIs to obtain high-quality car-mode API route information and uses a trajectory segmentation algorithm to find the best-matched API route. The car-mode API route data combined with the actual route information, including the actual mode information, are used to train a logistic regression machine learning model, which estimates car modes and non-car modes with probability rates. The experimental results show promise for the proposed method's ability to detect vehicle mode accurately.

33 ADVANCED PROPULSION SYSTEMS↗
NASA NTRS1994

Continental-scale river flow in climate models

The hydrologic cycle is a major part of the global climate system. There is an atmospheric flux of water from the ocean surface to the continents. The cycle is closed by return flow in rivers. In this paper a river routing model is developed to use with grid box climate models for the whole earth. The routing model needs an algorithm for the river mass flow and a river direction file, which has been compiled for 4 deg x 5 deg and 2 deg x 2.5 deg resolutions. River basins are defined by the direction files. The river flow leaving each grid box depends on river and lake mass, downstream distance, and an effective flow speed that depends on topography. As input the routing model uses monthly land source runoff from a 5-yr simulation of the NASA/GISS atmospheric climate model (Hansen et al.). The land source runoff from the 4 deg x 5 deg resolution model is quartered onto a 2 deg x 2.5 deg grid, and the effect of grid resolution is examined. Monthly flow at the mouth of the world's major rivers is compared with observations, and a global error function for river flow is used to evaluate the routing model and its sensitivity to physical parameters. Three basinwide parameters are introduced: the river length weighted by source runoff, the turnover rate, and the basinwide speed. Although the values of these parameters depend on the resolution at which the rivers are defined, the values should converge as the grid resolution becomes finer. When the routing scheme described here is coupled with a climate model's source runoff, it provides the basis for closing the hydrologic cycle in coupled atmosphere-ocean models by realistically allowing water to return to the ocean at the correct location and with the proper magnitude and timing.

Miller, James R.↗
NASA NTRSDate not supplied

Deep Reinforcement Learning based Routing in an Air-to-Air Ad-hoc Network

This paper studies the Multiple Sources and Multiple Destinations (MSMD) routing problem in a dynamic Air-to-Air Ad-hoc Network (AAAN). We consider a spectrum limited scenario where multiple links have to share the same frequency channel so that co-channel interference becomes inevitable. As a result, routing decisions and spectrum access are coupled and must be jointly considered. This paper proposes a deep Q-learning based algorithm to find an optimal routing and channel selection strategy that minimizes the end-to-end communication delay. Specifically, under the assumption that only local information is available to every node, the Deep Q-Network (DQN) is trained offline to learn the optimal routing and channel selection strategy. After the trained DQN is implemented in every node, multiple relay nodes can simultaneously determine their next-hop relay and channel selections in real-time. Simulation results demonstrate the efficacy of our proposed algorithm.

AAAN↗
NASA NTRSDate not supplied

Deep Reinforcement Learning based Routing in an Air-to-Air Ad-hoc Network

This paper studies the Multiple Sources and Multiple Destinations (MSMD) routing problem in a dynamic Air-to-Air Ad-hoc Network (AAAN). We consider a spectrum limited scenario where multiple links have to share the same frequency channel so that co-channel interference becomes inevitable. As a result, routing decisions and spectrum access are coupled and must be jointly considered. This paper proposes a deep Q-learning based algorithm to find an optimal routing and channel selection strategy that minimizes the end-to-end communication delay. Specifically, under the assumption that only local information is available to every node, the Deep Q-Network (DQN) is trained offline to learn the optimal routing and channel selection strategy. After the trained DQN is implemented in every node, multiple relay nodes can simultaneously determine their next-hop relay and channel selections in real-time. Simulation results demonstrate the efficacy of our proposed algorithm.

AAAN↗
DOE OSTI2019

Future SDN-HPON Control Plane Architecture and Protocol for On-Demand Terabit End-to-End Extreme-Scale Science Applications

The UC Davis team conducted architecture, algorithm and experimental studies for next generation ultra-high-bandwidth optical networks in support of extreme-scale science applications. In particular, over the course of this 3-year project, the UC Davis team achieved the following main accomplishments: Designed a network architecture for automated multi-domain service provisioning: Designed information exchange schemes between autonomous systems (domains) Designed application programming interfaces to orchestrate resource reservation in data centers, high performance computation facilities, and communication networks belonging to different autonomous systems Experimentally assessed the multi-domain network architecture in a distributed field trial set-up connecting premises in three continents Designed a broker-based orchestrated multi-domain optical networking framework supporting observe-analyze-act cycle based cognitive inter-domain service provisioning: Designed an inter-domain operation mechanism, e.g., topology abstraction, for the broker plane and domain managers to collaboratively accomplish inter-domain service provisioning while respecting the autonomy of each administrative domain Designed an alien wavelength monitoring scheme and an artificial neural network based optical signal-to-noise ratio estimator for quality-of-transmission aware inter-domain service provisioning Developed a deep neural network based multi-domain traffic predictor and a cognitive routing and spectrum assignment algorithm to realize knowledge-based autonomous traffic engineering in multi-domain networks Implemented an optical signal-to-noise ratio estimator and traffic predictor with Google’s Tensor flow and assessed their performance using experimental and synthetic data Demonstrated the benefits of the proposed cognitive schemes with experiments ona two-domain elastic optical network testbed and evaluations on a six-domain simulation framework Built a two-domain software-defined networking control plane testbed using the ONOS platform and demonstrated the workflow of broker and domain manager cooperation, including hierarchical performance monitoring, topology abstraction and cognitive resource allocation. Designed self-learning cognitive service provisioning schemes using advanced machine learning technologies: Designed a self-taught anomaly detection framework for optical networks, including an unsupervised data clustering module for pattern recognition, a supervised data regression and classification module for online anomaly detection, and the system operation principle Experimentally validated the effectiveness of the self-taught anomaly detection framework with various failure/anomaly scenarios. Designed a self-learning autonomic routing, modulation and spectrum assignment (RMSA) provisioning framework for elastic optical networks with deep reinforcement learning. Designed effective modeling and training mechanisms for the self-learning RMSA framework Conducted extensive numerical simulations with various traffic patterns and topologies to verify the advantage of the self-learning RMSA framework.

42 ENGINEERING↗
DOE OSTI2012

Approximate Weighted Matching On Emerging Manycore and Multithreaded Architectures

Graph matching is a prototypical combinatorial problem with many applications in computer science and scientific computing, but algorithms for computing optimal matchings are challenging to parallelize. Approximate matching algorithms provide an alternate route for parallelization, and in many contexts compute near-optimal matchings for large-scale graphs. We present sharedmemory parallel implementations for computing half-approximate weighted matching on state-of-the-art multicore (Intel Nehalem and AMD Magny-Cours), manycore (Nvidia Tesla and Nvidia Fermi) and massively multithreaded (Cray XMT) platforms. We provide two implementations: the first implementation uses shared work queues, and is suited to all these platforms; the second implementation is based on dataflow principles, and exploits the architectural features of the Cray XMT. Using a carefully chosen dataset that exhibits characteristics from a wide range of real-world applications, we show scalable performance across different platforms. In particular, for one instance of the input, an R-MAT graph (RMAT-G), we show speedups of: about 32 on 48 cores of an AMD Magny-Cours; 7 on 8 cores of Intel Nehalem; 3 on Nvidia Tesla and 10 on Nvidia Fermi relative to one core of Intel Nehalem; and 60 on 128 processors of Cray XMT. We demonstrate good weak and strong scaling for graphs with up to a billion edges using up to 12, 800 threads. Given the breadth of this work, we focus on simplicity and portability of software rather than excessive fine-tuning for each platform. To the best of our knowledge, this is the first such large-scale study of the half-approximate weighted matching problem on shared-memory platforms. Driven by the critical enabling role of combinatorial algorithms such as matching in scientific computing and the emergence of informatics applications, there is a growing demand to support irregular computations on current and future computing platforms. In this context, we evaluate the capability of emerging multithreaded platforms to tolerate latency induced by irregular memory access patterns, and to support fine-grained parallelism via light-weight synchronization mechanisms. By contrasting the architectural features of these platforms against the Cray XMT, which is specifically designed to support irregular memory-intensive applications, we delineate the impact of these choices on performance.

Halappanavar, Mahantesh↗
NASA NTRS1992

Communications and control for electric power systems

A long-term strategy for the integration of new control technologies for power generation and delivery is proposed: the industry would benefit from an evolutionary approach that would adapt to its needs future technologies as well as those that it has so far not heeded. The integrated operation of the entire system, including the distribution system, was proposed as a future goal. The AbNET communication protocols are reviewed, and additions that were made in 1991 are described. In the original network, traffic was controlled by polling at the master station, located at the substation, and routed by a flooding algorithm. In a revised version, the polling and flooding are modified. The question of interfacing low-energy measurement transducers or instrument transformers is considered. There is presently little or no agreement on what the output of optical current transducers (CT's) should be. Appendices deal with the calibration of current transducers; with Delta modulation, a simple means of serially encoding the output of an OCT; and with noise shaping, a method of digital signal processing that trades off the number of bits in a digital sample for a higher number of samples.

Kirkham, H.↗
DOE OSTI2019

Authentication Protocol for ICS without Encryption

Industrial control systems (ICS) describes the different types of control systems and associated instrumentation, which includes the devices, systems, networks, and controls used to operate and/or automate industrial processes. Depending on the industry, each ICS functions differently and are built to electronically manage tasks efficiently. Historically, industrial plants have included networking, and changes have been made over time without consideration for security. Many ICS devices currently have inadequate security features. Adding encryption in ICS is undesirable because many of the new detection method involves deep packet inspection. Therefore, we propose to develop a method of providing authentication between devices without encrypting the data. This testbed design will allow rapid development and experimentation with Cyber Physical Systems. Modbus connects to a supervisory computer with a Remote Terminal Unit (RTU) in Supervisory Control and Data Acquisition (SCADA) systems. Our project seeks to enhance security in the ICS environment by adding device authentication to the lower levels of the plant floor. This approach was selected as it allows verification of the sender of data from level 1/level 0 devices up to supervisory systems. This addition is desirable as it adds enhanced verification to the integrity of system data without obscuring (via encryption) the data being transmitted across the network. This is important because many ICS systems are real time critical (decryption adds to latency) and many other good security options require deep packet inspection (which encryption completely defeats). To accomplish this, a proof of concept of adding an authentication scheme was designed and will be tested with a common ICS protocol. The setup includes a single serial cable connecting the serial ports on two devices, a Master and a Minion. Authentication will occur in the following methods: - Data layer involving Transport Layer Security/Secure Socket Layer (TLS/SSL); - TCP/IP route implementation; - Key exchange algorithm; - Raspberry Pi programming for authentication. A portion of the setup includes adding Raspberry Pi into the system as the device is handling the authentication for the network traffic. Modbus is the chosen ICS protocol. It is used to transmit signals from instrumentation and control devices back to a main controller or data gathering system. Typically, the device identity is assumed but not verified. For verifying device identity, we constructed a digital signature architecture with TLS. A novel adaptation of this is to use only the digital signature that is provided and not the encryption capability. This allows ICS traffic to flow unobscured while still providing verification for the integrity of the data. Verification of this process will involve adding additional I/O level network devices with spoofed IP addresses and detecting the authenticated versus unauthenticated traffic. Our TLS implementation will have encryption disabled but should still allow for digital signing of data. This will enable our system to distinguish between real end devices and spoofed end devices. This experiment is presently building the test setup. It is focusing on a small setting to identify authenticated and unauthenticated devices on the network. This should allow for scaling to a larger network size after the initial proof of concept. One concern with this scheme is a certificate deployment has a large scale key management. Network size will thus increase the key management task for security. In addition, we believe that further research should be done on exploring the use of this method to defeat man-in-the-middle attacks.

42 ENGINEERING↗
NASA NTRS2010

Concepts and Challenges for Environmentally Friendly En Route Operations

A flight trajectory optimization algorithm with fuel and contrails models, which develops alternative flight paths, provides policy makers the necessary data to make tradeoffs between persistent contrails mitigation and aircraft fuel consumption. This study develops an algorithm that calculates wind-optimal trajectories for cruising aircraft while avoiding the regions of airspace prone to persistent contrails formation. The optimal trajectory is derived using Singular Perturbation Method. The regions of airspace favorable to persistent contrails formation are modeled as high-risk areas that aircraft should avoid and are adjustable. The tradeoffs between persistent contrails formation and additional travel time are investigated for wind-optimal trajectories and various contrails-avoidance trajectories at 10 different cruising altitudes for flights departing from Chicago and San Diego to New York. The additional travel times required for avoiding 100% persistent contrails formation at various flight altitudes ranged from approximately 0% to 4.3% for flights from Chicago to New York. For flights between San Diego and New York, additional traveling times vary between 1.3% and 5% depending on the cruise altitude and the percentage of contrail avoidance. Talk will present the results of aircraft fuel consumptions that are proportional to the travel time for cruising aircraft.

Sridhar, Banavar↗