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 181 records · Page 10
All sourcesNASA NTRSDOE OSTI
NASA NTRS1988

Parallel discrete event simulation using shared memory

With traditional event-list techniques, evaluating a detailed discrete-event simulation-model can often require hours or even days of computation time. By eliminating the event list and maintaining only sufficient synchronization to ensure causality, parallel simulation can potentially provide speedups that are linear in the numbers of processors. A set of shared-memory experiments, using the Chandy-Misra distributed-simulation algorithm, to simulate networks of queues is presented. Parameters of the study include queueing network topology and routing probabilities, number of processors, and assignment of network nodes to processors. These experiments show that Chandy-Misra distributed simulation is a questionable alternative to sequential-simulation of most queueing network models.

Reed, Daniel A.↗
NASA NTRS2016

ASTAR Flight Test: Overview and Spacing Results

The purpose of the NASA Langley Airborne Spacing for Terminal Arrival Routes (ASTAR) research aboard the Boeing ecoDemonstrator aircraft was to demonstrate the use of NASA's ASTAR algorithm using contemporary tools of the Federal Aviation Administration's Next Generation Air Transportation System (NEXTGEN). EcoDemonstrator is a Boeing test program which utilizes advanced experimental equipment to accelerate the science of aerospace and environmentally friendly technologies. The ASTAR Flight Test provided a proof-of-concept flight demonstration that exercised an algorithmic-based application in an actual aircraft. The test aircraft conducted Interval Management operations to provide time-based spacing off a target aircraft in non-simulator wind conditions. Work was conducted as a joint effort between NASA and Boeing to integrate ASTAR in a Boeing supplied B787 test aircraft while using a T-38 aircraft as the target. This demonstration was also used to identify operational risks to future flight trials for the NASA Air Traffic Management Technology Demonstration expected in 2017.

Roper, Roy D.↗
NASA NTRSDate not supplied

Formalization of the Bellman-Ford Algorithm for Airspace Applications

This paper describes the formal verification of one of the most well-known algorithms for finding the shortest path between all vertices in a directed graph, namely the Bellman-Ford algorithm. This formal verification, performed in the Prototype Verification System (PVS), is motivated by two applications in the aerospace domain which use the algorithm for path planning. The first is a pre-flight calculation that uses an adapted version of Bellman-Ford to find a route intended to maximize GNSS availability throughout the flight. The second is a more traditional application intended to find the shortest path between an autonomous aircraft's current position and a goal waypoint, while avoiding regions of space specified by geofences. A novel aspect of this formal verification effort is the inclusion of two distinct models of computation for the algorithm, one being a traditional serial computation, and the other being an explicitly parallel computation. The ability to use parallel computation in the Bellman-Ford algorithm is in fact why it was chosen over other traditionally more performant algorithms, especially for the GNSS application, where the size of the graph makes a purely serial computation infeasible.

formal verification↗
NASA NTRS1971

An algorithm for terminal air traffic control

An area-navigation method for automatic control of aircraft arriving in a random fashion from the en-route centers to the near terminal area is proposed. Control is exercised by a ground computer that sequences and schedules the aircraft. Altitude segregation is used to separate aircraft in velocity classes. Merging of all aircraft occurs near the outer marker. The merging region is designed so that no near misses will occur if the aircraft follow the assigned trajectories.

Sarris, A. H.↗
NASA NTRS2019

Evaluation of Classifier Complexity for Delay Tolerant Network Routing

The growing popularity of small cost effective satellites (SmallSats, CubeSats, etc.) creates the potential for a variety of new science applications involving multiple nodes functioning together or independently to achieve a task, such as swarms and constellations. As this technology develops and is deployed for missions in Low Earth Orbit and beyond, the use of delay tolerant networking (DTN) techniques may improve communication capabilities within the network. In this paper, a network hierarchy is developed from heterogeneous networks of SmallSats, surface vehicles, relay satellites and ground stations which form an integrated network. There is a tradeoff between complexity, flexibility, and scalability of user defined schedules versus autonomous routing as the number of nodes in the network increases. To address these issues, this work proposes a machine learning classifier based on DTN routing metrics. A framework is developed which will allow for the use of several categories of machine learning algorithms (decision tree, random forest and deep learning) to be applied to a dataset of historical network statistics, which allows for the evaluation of algorithm complexity versus performance to be explored. We develop the emulation of a hierarchical network, consisting of tens of nodes which form a cognitive network architecture. CORE (Common Open Research Emulator) is used to emulate the network using bundle protocol and DTN IP neighbor discovery.

Dudukovich, Rachel↗
NASA NTRS1990

On well-partial-order theory and its application to combinatorial problems of VLSI design

We nonconstructively prove the existence of decision algorithms with low-degree polynomial running times for a number of well-studied graph layout, placement, and routing problems. Some were not previously known to be in p at all; others were only known to be in p by way of brute force or dynamic programming formulations with unboundedly high-degree polynomial running times. Our methods include the application of the recent Robertson-Seymour theorems on the well-partial-ordering of graphs under both the minor and immersion orders. We also briefly address the complexity of search versions of these problems.

Fellows, M.↗
NASA NTRS2012

A Comparative Study of Interval Management Control Law Capabilities

This paper presents a new tool designed to allow for rapid development and testing of different control algorithms for airborne spacing. This tool, Interval Management Modeling and Spacing Tool (IM MAST), is a fast-time, low-fidelity tool created to model the approach of aircraft to a runway, with a focus on their interactions with each other. Errors can be induced between pairs of aircraft by varying initial positions, winds, speed profiles, and altitude profiles. Results to-date show that only a few of the algorithms tested had poor behavior in the arrival and approach environment. The majority of the algorithms showed only minimal variation in performance under the test conditions. Trajectory-based algorithms showed high susceptibility to wind forecast errors, while performing marginally better than the other algorithms under other conditions. Trajectory-based algorithms have a sizable advantage, however, of being able to perform relative spacing operations between aircraft on different arrival routes and flight profiles without employing ghosting. methods. This comes at the higher cost of substantially increased complexity, however. Additionally, it was shown that earlier initiation of relative spacing operations provided more time for corrections to be made without any significant problems in the spacing operation itself. Initiating spacing farther out, however, would require more of the aircraft to begin spacing before they merge onto a common route.

Barmore, Bryan E.↗
NASA NTRS2013

NASA Tech Briefs, December 2013

Topics include: Microwave Kinetic Inductance Detector With; Selective Polarization Coupling; Flexible Microstrip Circuits for; Superconducting Electronics; CFD Extraction Tool for TecPlot From DPLR Solutions; RECOVIR Software for Identifying Viruses; Enhanced Contact Graph Routing (ECGR) MACHETE Simulation Model; Orbital Debris Engineering Model (ORDEM) v.3; Scatter-Reducing Sounding Filtration Using a Genetic Algorithm and Mean Monthly Standard Deviation; Thermo-Mechanical Methodology for Stabilizing Shape Memory Alloy Response; Hermetic Seal Designs for Sample Return Sample Tubes; Silicon Alignment Pins: An Easy Way To Realize a Wafer-to-Wafer Alignment; Positive-Buoyancy Rover for Under Ice Mobility; Electric Machine With Boosted Inductance to Stabilize Current Control; International Space Station-Based Electromagnetic Launcher for Space Science Payloads; Advanced Hybrid Spacesuit Concept Featuring Integrated Open Loop and Closed Loop Ventilation Systems; Data Quality Screening Service.

Source record↗
NASA NTRS1983

A simple Lagrangian forecast system with aviation forecast potential

A trajectory forecast procedure is developed which uses geopotential tendency fields obtained from a simple, multiple layer, potential vorticity conservative isentropic model. This model can objectively account for short-term advective changes in the mass field when combined with fine-scale initial analyses. This procedure for producing short-term, upper-tropospheric trajectory forecasts employs a combination of a detailed objective analysis technique, an efficient mass advection model, and a diagnostically proven trajectory algorithm, none of which require extensive computer resources. Results of initial tests are presented, which indicate an exceptionally good agreement for trajectory paths entering the jet stream and passing through an intensifying trough. It is concluded that this technique not only has potential for aiding in route determination, fuel use estimation, and clear air turbulence detection, but also provides an example of the types of short range forecasting procedures which can be applied at local forecast centers using simple algorithms and a minimum of computer resources.

Petersen, R. A.↗
NASA NTRS2012

Optimal Integration of Departure and Arrivals in Terminal Airspace

Coordination of operations with spatially and temporally shared resources such as route segments, fixes, and runways improves the efficiency of terminal airspace management. Problems in this category include scheduling and routing, thus they are normally difficult to solve compared with pure scheduling problems. In order to reduce the computational time, a fast time algorithm formulation using a non-dominated sorting genetic algorithm (NSGA) was introduced in this work and applied to a test case based on existing literature. The experiment showed that new method can solve the whole problem in fast time instead of solving sub-problems sequentially with a window technique. The results showed a 60% or 406 second delay reduction was achieved by sharing departure fixes (more details on the comparison with MILP results will be presented in the final paper). Furthermore, the NSGA algorithm was applied to a problem in LAX terminal airspace, where interactions between 28% of LAX arrivals and 10% of LAX departures are resolved by spatial segregation, which may introduce unnecessary delays. In this work, spatial segregation, temporal segregation, and hybrid segregation were formulated using the new algorithm. Results showed that spatial and temporal segregation approaches achieved similar delay. Hybrid segregation introduced much less delay than the other two approaches. For a total of 9 interacting departures and arrivals, delay reduction varied from 4 minutes to 6.4 minutes corresponding flight time uncertainty from 0 to 60 seconds. Considering the amount of flights that could be affected, total annual savings with hybrid segregation would be significant.

high density terminal↗
NASA NTRS1999

Avoiding Braess' Paradox Through Collective Intelligence

In an Ideal Shortest Path Algorithm (ISPA), at each moment each router in a network sends all of its traffic down the path that will incur the lowest cost to that traffic. In the limit of an infinitesimally small amount of traffic for a particular router, its routing that traffic via an ISPA is optimal, as far as cost incurred by that traffic is concerned. We demonstrate though that in many cases, due to the side-effects of one router's actions on another routers performance, having routers use ISPA's is suboptimal as far as global aggregate cost is concerned, even when only used to route infinitesimally small amounts of traffic. As a particular example of this we present an instance of Braess' paradox for ISPA'S, in which adding new links to a network decreases overall throughput. We also demonstrate that load-balancing, in which the routing decisions are made to optimize the global cost incurred by all traffic currently being routed, is suboptimal as far as global cost averaged across time is concerned. This is also due to "side-effects", in this case of current routing decision on future traffic. The theory of COllective INtelligence (COIN) is concerned precisely with the issue of avoiding such deleterious side-effects. We present key concepts from that theory and use them to derive an idealized algorithm whose performance is better than that of the ISPA, even in the infinitesimal limit. We present experiments verifying this, and also showing that a machine-learning-based version of this COIN algorithm in which costs are only imprecisely estimated (a version potentially applicable in the real world) also outperforms the ISPA, despite having access to less information than does the ISPA. In particular, this COIN algorithm avoids Braess' paradox.

Wolpert , David H.↗
NASA NTRS1992

A VLSI implementation of DCT using pass transistor technology

A VLSI design for performing the Discrete Cosine Transform (DCT) operation on image blocks of size 16 x 16 in a real time fashion operating at 34 MHz (worst case) is presented. The process used was Hewlett-Packard's CMOS26--A 3 metal CMOS process with a minimum feature size of 0.75 micron. The design is based on Multiply-Accumulate (MAC) cells which make use of a modified Booth recoding algorithm for performing multiplication. The design of these cells is straight forward, and the layouts are regular with no complex routing. Two versions of these MAC cells were designed and their layouts completed. Both versions were simulated using SPICE to estimate their performance. One version is slightly faster at the cost of larger silicon area and higher power consumption. An improvement in speed of almost 20 percent is achieved after several iterations of simulation and re-sizing.

Kamath, S.↗
NASA NTRSDate not supplied

Alert Timing Assessment for Unmanned Aircraft System Terminal Area Operations

A Detect and Avoid (DAA) system is an essential enabler for integrating Unmanned Aircraft Systems (UAS) into the U.S. National Airspace System. A DAA system uses a suite of sensors, trackers and alerting and guidance algorithms to assist a remote pilot in maintaining separation from airborne traffic. The initial minimum performance standards focused on en route operations; in order to facilitate operations in and around the airport environment, this paper presents the derivation of the early alert threshold for UAS terminal operations.

Unmanned Aircraft Systems↗
NASA NTRSDate not supplied

Toward Time Synchronization in Delay Tolerant Network based Solar System Internetworking

The expanding presence in space will place an increased dependency on networked communications– a scalable communications infrastructure; that is, the Solar System Internet (SSI). Upcoming developments towards a SSI include NASA’s upcoming LunaNet, or lunar Internet, which provides multi-hop multi-path communications using Delay Tolerant Networking (DTN). DTN has been an active area of research and development, particularly in routing, security, and optimization. DTNs are marked by mobility, disconnection, and a wide variance of latencies (propagation and processing delays). In this paper, we outline progress towards a theory of time synchronization across such a network. An underlying assumption of DTN is that the network is time synchronized already, rather than synchronization being provided as a service. While this is necessary for schedule-based routing, which is necessarily prevalent in DTNs, it is so deeply ingrained as to be built into the primary unit of data in DTNs– the bundle. Indeed, a bundle’s creation timestamp and its time to live (called the lifetime) are based on time, and there are special recommendations for systems that lack accurate clocks. The assumption of time synchronization makes sense when limiting considerations to smaller-scale and more traditional space communication. However, just as end-to-end connectivity cannot be guaranteed in DTNs, neither can access to a reference or authoritative clock. In this more general case, it might be necessary to synchronize over time-varying meshes, and perhaps even to consider relativistic effects. Moreover, by imposing synchronization restrictions in order to sustain a network, the effectiveness of the network to achieve scalability will be necessarily muted. To work towards a time synchronization theory for DTNs, we build upon past successes in modeling DTNs using time-varying graphs and sheaves. This includes error and limitation estimation, which allows one to define domains over which schedule-based routing is possible, up to some threshold sensitivity. Despite the theoretical nature of these results, the approaches taken are also algorithmic, and hence lend themselves to practical implementations. The paper concludes with comparisons of the various methods along with suggestions for future work.

Delay Tolerant Networking↗
NASA NTRS2016

Deconflicting Wind-Optimal Aircraft Trajectories in North Atlantic Oceanic Airspace

North Atlantic oceanic airspace accommodates more than 1000 flights daily, and is subjected to very strong winds. Flying wind-optimal trajectories yields time and fuel savings for each individual flight. However, when taken together, these trajectories induce a large amount of potential en-route conflicts. This paper analyses the detected conflicts, figuring out conflict distribution in time and space. It further describes an optimization algorithm aimed at reducing the number of conflicts for a daily set of flights on strategic level. Several trajectory modification strategies are discussed, followed with simulation results. Finally, an algorithm improvement is presented aiming at better preserving the trajectory optimality.

wind-optimal trajectories↗
NASA NTRSDate not supplied

Planning for Compilation of a Quantum Algorithm for Graph Coloring

Recently, the problem of compiling general quantum algorithms for implementation on near-term quantum processors has been introduced to the AI community. Previous work demonstrated that temporal planning is an attractive approach for part of this compilation task, specifically, the routing of circuits that implement the Quantum Alternating Operator Ansatz (QAOA) applied to theMaxCut problem on a quantum processor architecture. In this paper, we extend the earlier work to route circuits that implement QAOAfor Graph Coloring problems. QAOA for coloring requires execution of more, and more complex, operations on the chip, which makes routing a more challenging problem. We evaluate the approach on state-of-the-art hardware architectures from leading quantum computing companies. Additionally, we investigate applying the planning approach to qubit initialization as well as routing. Our empirical evaluation shows that temporal planning compares well to reasonable analytic upper bounds [20], and that solving qubit initialization with a classical planner generally helps temporal planners in finding shorter-makespan compilations for QAOA for Graph Coloring.These advances suggest that temporal planning can be an effective approach for more complex quantum computing algorithms and architectures.

Minh Do↗
NASA NTRS2015

Strategic Time-Based Metering that Assures Separation for Integrated Operations in a Terminal Airspace

This paper reports an algorithm for strategic time-based metering of air traffic arriving and departing from a large ( tens of nautical miles) area (called here, the commitment region) around an airport or metroplex. The algorithm assures separation continuously in time and avoids a dictation of intent to an aircraft crew. This is accomplished by allowing an aircraft (specifically, its Flight Management System) to specify, and commit to, an intended route and ground speed profile along that route within the commitment region, and by supplying the time at which to enter the region to the aircraft crew. The airspace that comprises the commitment region need not be confined to the terminal airspace and can include some of the enroute space: the size and shape of the commitment region are parameters in the algorithm. An exact formula for including speed profile uncertainty in the algorithm is provided. The algorithm is applied to a number of data sets recorded during actual air traffic operations in the Southern California TRACON in July of 2014 and the Atlanta TRACON in November and December of 2013. The results of the numerical simulations indicate that the algorithm succeeds at keeping the aircraft separated, but introduces, in its current implementation, more separation than that observed in actual operations. This excess separation can be reduced by modeling more accurately the Visual Flight Rules separation practices, a direction for future research.

air traffic management↗
NASA NTRS1988

Search Problems in Mission Planning and Navigation of Autonomous Aircraft

An architecture for the control of an autonomous aircraft is presented. The architecture is a hierarchical system representing an anthropomorphic breakdown of the control problem into planner, navigator, and pilot systems. The planner system determines high level global plans from overall mission objectives. This abstract mission planning is investigated by focusing on the Traveling Salesman Problem with variations on local and global constraints. Tree search techniques are applied including the breadth first, depth first, and best first algorithms. The minimum-column and row entries for the Traveling Salesman Problem cost matrix provides a powerful heuristic to guide these search techniques. Mission planning subgoals are directed from the planner to the navigator for planning routes in mountainous terrain with threats. Terrain/threat information is abstracted into a graph of possible paths for which graph searches are performed. It is shown that paths can be well represented by a search graph based on the Voronoi diagram of points representing the vertices of mountain boundaries. A comparison of Dijkstra's dynamic programming algorithm and the A* graph search algorithm from artificial intelligence/operations research is performed for several navigation path planning examples. These examples illustrate paths that minimize a combination of distance and exposure to threats. Finally, the pilot system synthesizes the flight trajectory by creating the control commands to fly the aircraft.

Krozel, James A.↗