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 109 records · Page 6

Using Machine-Learning to Dynamically Generate Operationally Acceptable Strategic Reroute Options

The newly developed Trajectory Option Set (TOS), a preference-weighted set of alternative routes submitted by flight operators, is a capability in the U.S. traffic flow management system that enables automated trajectory negotiation between flight operators and Air Navigation Service Providers. The objective of this paper is to describe and demonstrate an approach for automatically generating pre-departure and airborne TOSs that have a high probability of operational acceptance. The approach uses hierarchical clustering of historical route data to identify route candidates. The probability of operational acceptance is then estimated using predictors trained on historical flight plan amendment data using supervised machine learning algorithms, allowing the routes with highest probability of operational acceptance to be selected for the TOS. Features used describe historical route usage, difference in flight time and downstream demand to capacity imbalance. A random forest was found to be the best performing algorithm for learning operational acceptability, with a model accuracy of 0.96. The approach is demonstrated for an historical pre-departure flight from Dallas/Fort Worth International Airport to Newark Liberty International Airport.

Evans, Antony↗

Using Machine-Learning to Dynamically Generate Operationally Acceptable Strategic Reroute Options

The newly developed Trajectory Option Set (TOS), a preference-weighted set of alternative routes submitted by flight operators, is a capability in the U.S. traffic flow management system that enables automated trajectory negotiation between flight operators and Air Navigation Service Providers. The objective of this paper is to describe and demonstrate an approach for automatically generating pre-departure and airborne TOSs that have a high probability of operational acceptance. The approach uses hierarchical clustering of historical route data to identify route candidates. The probability of operational acceptance is then estimated using predictors trained on historical flight plan amendment data using supervised machine learning algorithms, allowing the routes with highest probability of operational acceptance to be selected for the TOS. Features used describe historical route usage, difference in flight time and downstream demand to capacity imbalance. A random forest was found to be the best performing algorithm for learning operational acceptability, with a model accuracy of 0.96. The approach is demonstrated for an historical pre-departure flight from Dallas/Fort Worth International Airport to Newark Liberty International Airport.

Evans, Antony↗

A glimpse into the fungal metabolomic abyss: Novel network analysis reveals relationships between exogenous compounds and their outputs

Fungal specialized metabolites are a major source of beneficial compounds that are routinely isolated, characterized, and manufactured as pharmaceuticals, agrochemical agents, and industrial chemicals. The production of these metabolites is encoded by biosynthetic gene clusters that are often silent under standard growth conditions. There are limited resources for characterizing the direct link between abiotic stimuli and metabolite production. Herein, we introduce a network analysis-based, data-driven algorithm comprising two routes to characterize the production of specialized fungal metabolites triggered by different exogenous compounds: the direct route and the auxiliary route. Both routes elucidate the influence of treatments on the production of specialized metabolites from experimental data. The direct route determines known and putative metabolites induced by treatments and provides additional insight over traditional comparison methods. The auxiliary route is specific for discovering unknown analytes, and further identification can be curated through online bioinformatic resources. We validated our algorithm by applying chitooligosaccharides and lipids at two different temperatures to the fungal pathogen Aspergillus fumigatus. After liquid chromatography–mass spectrometry quantification of significantly produced analytes, we used network centrality measures to rank the treatments’ ability to elucidate these analytes and confirmed their identity through fragmentation patterns or in silico spiking with commercially available standards. Later, we examined the transcriptional regulation of these metabolites through real-time quantitative polymerase chain reaction. Our data-driven techniques can complement existing metabolomic network analysis by providing an approach to track the influence of any exogenous stimuli on metabolite production. Our experimental-based algorithm can overcome the bottlenecks in elucidating novel fungal compounds used in drug discovery.

59 BASIC BIOLOGICAL SCIENCES↗

Increasingly minimal bias routing

A system and algorithm configured to generate diversity at the traffic source so that packets are uniformly distributed over all of the available paths, but to increase the likelihood of taking a minimal path with each hop the packet takes. This is achieved by configuring routing biases so as to prefer non-minimal paths at the injection point, but increasingly prefer minimal paths as the packet proceeds, referred to herein as Increasing Minimal Bias (IMB).

97 MATHEMATICS AND COMPUTING↗

Increasingly minimal bias routing

A system and algorithm configured to generate diversity at the traffic source so that packets are uniformly distributed over all of the available paths, but to increase the likelihood of taking a minimal path with each hop the packet takes. This is achieved by configuring routing biases so as to prefer non-minimal paths at the injection point, but increasingly prefer minimal paths as the packet proceeds, referred to herein as Increasing Minimal Bias (IMB).

Bataineh, Abdulla↗

Increasingly minimal bias routing

A system and algorithm configured to generate diversity at the traffic source so that packets are uniformly distributed over all of the available paths, but to increase the likelihood of taking a minimal path with each hop the packet takes. This is achieved by configuring routing biases so as to prefer non-minimal paths at the injection point, but increasingly prefer minimal paths as the packet proceeds, referred to herein as Increasing Minimal Bias (IMB).

97 MATHEMATICS AND COMPUTING↗

Planning The Route Of A Robotic Land Vehicle

Algorithm enables experimental robotic land vehicle to follow automatically route computed on basis of terrain-height-map data. Computer executing algorithm merges coarser global topographical data with finer local topographical data obtained through stereoscopic video system as vehicle moves along, then smoothes merged elevation map, interpolates map to evenly-horizontally-spaced grid points, and differentiates map to produce data on slopes and roughness for use in calculations of traversability and optimum route(s). Distance traveled minimized to extent possible consistent with avoidance of obstacles.

Gennery, Donald B.↗

Determining the Effectiveness of Incorporating Geographic Information Into Vehicle Performance Algorithms

This thesis presents a research study using one year of driving data obtained from plug-in hybrid electric vehicles (PHEV) located in Sacramento and San Francisco, California to determine the effectiveness of incorporating geographic information into vehicle performance algorithms. Sacramento and San Francisco were chosen because of the availability of high resolution (1/9 arc second) digital elevation data. First, I present a method for obtaining instantaneous road slope, given a latitude and longitude, and introduce its use into common driving intensity algorithms. I show that for trips characterized by >40m of net elevation change (from key on to key off), the use of instantaneous road slope significantly changes the results of driving intensity calculations. For trips exhibiting elevation loss, algorithms ignoring road slope overestimated driving intensity by as much as 211 Wh/mile, while for trips exhibiting elevation gain these algorithms underestimated driving intensity by as much as 333 Wh/mile. Second, I describe and test an algorithm that incorporates vehicle route type into computations of city and highway fuel economy. Route type was determined by intersecting trip GPS points with ESRI StreetMap road types and assigning each trip as either city or highway route type according to whichever road type comprised the largest distance traveled. The fuel economy results produced by the geographic classification were compared to the fuel economy results produced by algorithms that assign route type based on average speed or driving style. Most results were within 1 mile per gallon ({approx}3%) of one another; the largest difference was 1.4 miles per gallon for charge depleting highway trips. The methods for acquiring and using geographic data introduced in this thesis will enable other vehicle technology researchers to incorporate geographic data into their research problems.

58 GEOSCIENCES↗

Departure Trajectory Synthesis and the Intercept Problem

Two areas of the departure problem in air traffic control are discussed. The first topic is the generation of climb-out trajectories to a fix. The trajectories would be utilized by a scheduling algorithm to allocate runways, sequence the proposed departures, and assign a departure time. The second area is concerned with finding horizontal trajectories to merge aircraft from the TRACON to an open slot in the en-route environment. Solutions are presented for the intercept problem for two cases: (1) the aircraft is traveling at the speed of the aircraft in the jetway; (2) the merging aircraft has to accelerate to reach the speed of the aircraft in the en-route stream. An algorithm is given regarding the computation of a solution for the latter case. For the former, a set of equations is given that allows us to numerically solve for the coordinate where the merge will occur.

Bolender, Michael A.↗

A Model Tree Generator (MTG) Framework for Simulating Hydrologic Systems: Application to Reservoir Routing

Data-driven algorithms have been widely used as effective tools to mimic hydrologic systems. Unlike black-box models, decision tree algorithms offer transparent representations of systems and reveal useful information about the underlying process. A popular class of decision tree models is model tree (MT), which is designed for predicting continuous variables. Most MT algorithms employ an exhaustive search mechanism and a pre-defined splitting criterion to generate a piecewise linear model. However, this approach is computationally intensive, and the selection of the splitting criterion can significantly affect the performance of the generated model. These drawbacks can limit the application of MTs to large datasets. To overcome these shortcomings, a new flexible Model Tree Generator (MTG) framework is introduced here. MTG is equipped with several modules to provide a flexible, efficient, and effective tool for generating MTs. The application of the algorithm is demonstrated through simulation of controlled discharge from several reservoirs across the Contiguous United States (CONUS).

54 ENVIRONMENTAL SCIENCES↗

Quantum many-body linear algebra, Hamiltonian moments, and a coupled-cluster inspired framework

Here, we propose a general strategy to develop quantum many-body approximations of primitives in linear algebra algorithms. As a practical example, we introduce a coupled-cluster inspired framework to produce approximate Hamiltonian moments and demonstrate its application in various linear algebra algorithms for ground state estimation. Through numerical examples, we illustrate the difference between the ground-state energies arising from quantum many-body linear algebra and those from the analogous many-body perturbation theory. Our results support the general idea of designing quantum many-body approximations outside of perturbation theory, providing a route to new algorithms and approximations.

Algorithms and data structure↗

Routing Problem for Unmanned Aerial Vehicle Patrolling Missions - A Progressive Hedging Algorithm

This paper presents a two-stage stochastic program to model a routing problem involving an Unmanned Aerial Vehicle (UAV) in the context of patrolling missions. In particular, given a set of targets and a set of supplemental targets corresponding to each target, the first stage decisions involve finding the sequence in which the vehicle has to visit the set of targets. Upon reaching each target, the UAV collects information and if the operator of the UAV deems that the information collected is not of sufficient fidelity, then the UAV has to visit all the supplemental targets corresponding to that target to collect additional information before proceeding to visit the next target. The problem is solved using a progressive hedging algorithm and extensive computational results corroborating the effectiveness of the proposed model and the solution methodology is presented.

33 ADVANCED PROPULSION SYSTEMS↗

High-dimensional Data-driven Energy optimization for Multi-Modal Transit Agencies (HD-EMMA) (Final Technical Report)

Public bus transit services in the U.S. are responsible for at least 19.7 million metric tons of CO 2 emission annually. Electric vehicles (EVs) can have a much lower environmental impact than comparable internal combustion engine vehicles (ICEVs), especially in urban areas. Unfortunately, EVs are also much more expensive than ICEVs. As a result, many public transit agencies can afford only mixed fleets of transit vehicles, consisting of EVs, hybrids (HEVs), and ICEVs. Transit agencies that operate such mixed fleets of vehicles face a challenging optimization problem: these agencies need to decide which vehicles are assigned to serving which transit trips. Since the advantage of EVs over ICEVs varies depending on the route and time of day (e.g., the benefit of EVs is higher in slower traffic with frequent stops and lower on highways), the assignment can have a significant effect on energy use and, hence, environmental impact. Through this project, we have developed reference data about energy collections and constructed a set of machine learning models that can accurately predict the energy consumption for the whole fleet at the level of each trip. We have used these models to develop a scheduling and assignment strategy that can rotate the different vehicle types across the transit agencies’ routes. The optimization algorithm ensures that the vehicles are matched to trips considering weather patterns, expected congestion, and road gradients to minimize the overall energy usage. We list the key observations from our project for other practitioners below. Details are available in the report, and the list of source code and our publications are included in the appendix. 1. We have demonstrated the feasibility of collecting, merging and analyzing large volumes of high-resolution real-world telemetry data from a mixed vehicle fleet. To mitigate the inherent noise of the recorded GPS points, the team developed an algorithm that filters data and maps the points onto a street. The algorithm considers previous and subsequent location measurements and different characteristics of nearby streets to determine how likely the vehicle travels on them. Then, the team segmented the time series into disjoint contiguous samples based on adjacent road segments and repeated the outlier detection and removal. For each data point, the team added features corresponding to elevation changes within the samples, weather features, such as temperature, and traffic data, such as speed ratio between actual speed and free-flow speed. 2. We have developed two forms of machine learning models that be used to understand and analyze the energy operations of a mixed vehicle transit fleet. The micro prediction model provides estimates of instantaneous energy prediction for all types of buses (diesel, hybrid, and electric). Such a model is important in evaluating the energy impacts of real-time bus operation strategies, but it is challenging due to diversified driving cycles of transit buses. The model can help the drivers understand the impact of their driving behaviors and short-term congestions. The macro prediction models estimate average energy consumption across the whole trip considering the features: distance traveled, various road-type features, elevation change, day of the week, time of day, various weather features (temperature, humidity, etc.), and traffic features (speed ratio and jam factor). 3. We have demonstrated that it is possible to transfer the machine learning models we have developed in this project to other teams and cities by using inductive transfer learning. We also showed that the performance of the macro energy prediction models can be improved using a multi-task learning approach where the learning parameters are shared between the models being developed for different vehicle types. The advantage of this approach is improved learning performance as the models can exploit common spatio-temporal and environmental characteristics. 4. Finally, we have developed trip and vehicle assignment and scheduling algorithms that use the energy prediction models and develop a trip to vehicle type (diesel, electric, hybrid) assignment for the whole operation to reduce overall emissions and cost. We have shown through simulations that the proposed algorithms can save $\$$ 48,910 in energy costs and 175 metric tons of CO 2 emission annually for CARTA.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

Development of a Heavy-Duty Electric Vehicle Integration and Implementation (HEVII) Tool

As demand for consumer electric vehicles (EVs) has drastically increased in recent years, manufacturers have been working to bring heavy-duty EVs to market to compete with Class 6-8 diesel-powered trucks. Many high-profile companies have committed to begin electrifying their fleet operations, but have yet to implement EVs at scale due to their limited range, long charging times, sparse charging infrastructure, and lack of data from in-use operation. Thus far, EVs have been disproportionately implemented by larger fleets with more resources. To aid fleet operators, it is imperative to develop tools to evaluate the electrification potential of heavy-duty fleets. However, commercially available tools, designed mostly for light-duty vehicles, are inadequate for making electrification recommendations tailored to a fleet of heavy-duty vehicles. The main challenge is that light-duty tools do not estimate real-time vehicle mass, a factor that has a disproportionate impact on the energy consumption of large commercial vehicles. The Heavy-Duty Electric Vehicle Integration and Implementation (HEVII) tool advances the state of the art in evaluating electrification potential and infrastructure requirements for fleets of commercial vehicles. In this work, the HEVII tool is demonstrated with non-uniformly sampled telematics data from an existing fleet to assess the suitability for electrification of each individual vehicle, determine optimal locations for charging infrastructure to support a fleet of EVs and analyze associated costs. Payload mass is predicted using sparse ground-truth data for all input drive cycles and an initial data analysis is conducted to assess the characteristics driving behaviors and energy consumption of the fleet using an adaptable vehicle model. Battery size requirements are determined by applying a novel charger placement algorithm to maximize routes that are viable for EVs and balance time delays with infrastructure development costs. This work details and demonstrates the different aspects of the HEVII tool, presenting preliminary results from an example use case.

ADVANCED PROPULSION SYSTEMS↗

Optimal guidance with obstacle avoidance for nap-of-the-earth flight

The development of automatic guidance is discussed for helicopter Nap-of-the-Earth (NOE) and near-NOE flight. It deals with algorithm refinements relating to automated real-time flight path planning and to mission planning. With regard to path planning, it relates rotorcraft trajectory characteristics to the NOE computation scheme and addresses real-time computing issues and both ride quality issues and pilot-vehicle interfaces. The automated mission planning algorithm refinements include route optimization, automatic waypoint generation, interactive applications, and provisions for integrating the results into the real-time path planning software. A microcomputer based mission planning workstation was developed and is described. Further, the application of Defense Mapping Agency (DMA) digital terrain to both the mission planning workstation and to automatic guidance is both discussed and illustrated.

Pekelsma, Nicholas J.↗

Towards Sheaf Theoretic Analyses for Delay Tolerant Networking

The goal of Delay Tolerant Networking (DTN) is to take a collection of heterogeneous, disparate connections between satellites, space assets, ground stations, and ground infrastructure and bring it together into a cohesive, functioning overlay network. Depending on the systems being considered, one can find links with a one-way light time exceeding minutes (and hours),periodic links which can sometimes be predicted by orbital mechanics, and restrictions based on the variety of capabilities built into these systems. These characteristics preclude traditional network models and routing techniques and have classically led to either rigid routing tables or purely probabilistic models. As the deeper underlying structures remain unknown, development of more DTN-optimized algorithms has lacked the necessary foundation. In a continuation of previous work, the goal of this paper is to identify and study these fundamental structures that exist in delay tolerant networks (DTN), with a focus on space networks. The current routing methodology has been to use contact graph routing (CGR) algorithms. CGR models a series of known contacts as a static graph. For CGR to work, this graph must be globally consistent and must have an accurate picture of the network. Because this is a globally controlled structure, there is little room for flexibility in the event of changes to the network which would naturally occur as the network grows. As a response to the desire for flexibility as the network changes, we introduced the mathematical structure known as sheaves to DTNs last year. The tag-line for sheaves is that they are a mathematically precise way of gluing local data together into unique global data. Thus, sheaves lend extra power to traditional models(and routing algorithms) by taking additional information and merging it, in as consistent a manner as possible, with the representation itself. The clearest example of how Earth-bound networks exhibit behavior that is “sheafy” is link state routers, which build a local-to-global picture of their network by gluing local information together into a global network, exactly as a sheaf would do. For routing within delay tolerant networks to truly exploit this structure, a deeper structure than a graph is required. In this paper, we develop sheaves that can work over directed graphs such as temporal flow networks, we construct a sheaf representation for Dijkstra’s algorithm, and we outline a construction for routing sheaves capable of modeling multicast scenarios. Finally, there is a section of future work suggesting follow-on research.

Robert Short↗

Network-Control Algorithm

Algorithm developed for optimal routing of packets of data along links of multilink, multinode digital communication network. Algorithm iterative and converges to cost-optimal assignment independent of initial assignment. Each node connected to other nodes through links, each containing number of two-way channels. Algorithm assigns channels according to message traffic leaving and arriving at each node. Modified to take account of different priorities among packets belonging to different users by using different delay constraints or imposing additional penalties via cost function.

Chan, Hak-Wai↗

Towards a Scalable and Reliable Real Time In-Network Data Analysis Infrastructure

The smart grid applications requires real time analysis, response within the order of milliseconds and high-reliability because of the mission critical structure of the power grid system. The only way to satisfy these requirements is in network data analysis and build-in redundancy routing for failures. To achieve this, we propose a data dissemination system that builds routes using network flow algorithms, have in network processing of the data and utilize data encoding to cope with high latencies.

99 GENERAL AND MISCELLANEOUS↗