Search NASA⌕ Search

SEARCH · Search NASA

Results for “routing problems”

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 55 records · Page 3

An analysis of long and medium-haul air passenger demand, volume 1

A basic model was developed which is a two equation pair econometric system in which air passenger demand and airline level-of-service are the endogenous variables. The model aims to identify the relationship between each of these two variables and its determining factors, and to identify the interaction of demand and level-of-service with each other. The selected variable for the measure of air passenger traffic activity in a given pair market is defined as the number of passengers in a given time that originate in one region and fly to the other region for purposes other than to make a connection to a third region. For medium and long haul markets, the model seems to perform better for larger markets. This is due to a specification problem regarding the route structure variable. In larger markets, a greater percentage of nonlocal passengers are accounted for by this variable. Comparing the estimated fare elasticities of long and medium haul markets, it appears that air transportation demand is more price elastic in longer haul markets. Long haul markets demand will saturate with a fewer number of departures than will demand in medium haul markets.

Eriksen, S. E.↗

PIFEX: An advanced programmable pipelined-image processor

PIFEX is a pipelined-image processor being built in the JPL Robotics Lab. It will operate on digitized raster-scanned images (at 60 frames per second for images up to about 300 by 400 and at lesser rates for larger images), performing a variety of operations simultaneously under program control. It thus is a powerful, flexible tool for image processing and low-level computer vision. It also has applications in other two-dimensional problems such as route planning for obstacle avoidance and the numerical solution of two-dimensional partial differential equations (although its low numerical precision limits its use in the latter field). The concept and design of PIFEX are described herein, and some examples of its use are given.

Gennery, D. B.↗

Synchronization in neural nets

The paper presents an artificial neural network concept (the Synchronizable Oscillator Networks) where the instants of individual firings in the form of point processes constitute the only form of information transmitted between joining neurons. In the model, neurons fire spontaneously and regularly in the absence of perturbation. When interaction is present, the scheduled firings are advanced or delayed by the firing of neighboring neurons. Networks of such neurons become global oscillators which exhibit multiple synchronizing attractors. From arbitrary initial states, energy minimization learning procedures can make the network converge to oscillatory modes that satisfy multi-dimensional constraints. Such networks can directly represent routing and scheduling problems that consist of ordering sequences of events.

Vidal, Jacques J.↗

Exact Solutions to Time-dependent Mdps

We describe an extension of the Markov decision process model in which a continuous time dimension is included in the state space. This allows for the representation and exact solution of a wide range of problems in which transitions or rewards vary over time. We examine problems based on route planning with public transportation and telescope observation scheduling.

Boyan, Justin A.↗

Integrated Thermal Response Modeling System For Hypersonic Entry Vehicles

We describe all extension of the Markov decision process model in which a continuous time dimension is included ill the state space. This allows for the representation and exact solution of a wide range of problems in which transitions or rewards vary over time. We examine problems based on route planning with public transportation and telescope observation scheduling.

Chen, Y.-K.↗

Experiences with serial and parallel algorithms for channel routing using simulated annealing

Two algorithms for channel routing using simulated annealing are presented. Simulated annealing is an optimization methodology which allows the solution process to back up out of local minima that may be encountered by inappropriate selections. By properly controlling the annealing process, it is very likely that the optimal solution to an NP-complete problem such as channel routing may be found. The algorithm presented proposes very relaxed restrictions on the types of allowable transformations, including overlapping nets. By freeing that restriction and controlling overlap situations with an appropriate cost function, the algorithm becomes very flexible and can be applied to many extensions of channel routing. The selection of the transformation utilizes a number of heuristics, still retaining the pseudorandom nature of simulated annealing. The algorithm was implemented as a serial program for a workstation, and a parallel program designed for a hypercube computer. The details of the serial implementation are presented, including many of the heuristics used and some of the resulting solutions.

Brouwer, Randall Jay↗

Automated Conflict Resolution, Arrival Management and Weather Avoidance for ATM

The paper describes a unified solution to three types of separation assurance problems that occur in en-route airspace: separation conflicts, arrival sequencing, and weather-cell avoidance. Algorithms for solving these problems play a key role in the design of future air traffic management systems such as NextGen. Because these problems can arise simultaneously in any combination, it is necessary to develop integrated algorithms for solving them. A unified and comprehensive solution to these problems provides the foundation for a future air traffic management system that requires a high level of automation in separation assurance. The paper describes the three algorithms developed for solving each problem and then shows how they are used sequentially to solve any combination of these problems. The first algorithm resolves loss-of-separation conflicts and is an evolution of an algorithm described in an earlier paper. The new version generates multiple resolutions for each conflict and then selects the one giving the least delay. Two new algorithms, one for sequencing and merging of arrival traffic, referred to as the Arrival Manager, and the other for weather-cell avoidance are the major focus of the paper. Because these three problems constitute a substantial fraction of the workload of en-route controllers, integrated algorithms to solve them is a basic requirement for automated separation assurance. The paper also reviews the Advanced Airspace Concept, a proposed design for a ground-based system that postulates redundant systems for separation assurance in order to achieve both high levels of safety and airspace capacity. It is proposed that automated separation assurance be introduced operationally in several steps, each step reducing controller workload further while increasing airspace capacity. A fast time simulation was used to determine performance statistics of the algorithm at up to 3 times current traffic levels.

Erzberger, H.↗

Fourth International Symposium on Long-Range Sound Propagation

Long range sound propagation is an aspect of many acoustical problems ranging from en route aircraft noise to the acoustic detection of aircraft. Over the past decade, the University of Mississippi and the Open University of England, together with a third institution, have held a symposium approx. every 2 years so that experts in the field of long range propagation could exchange information on current research, identify areas needing additional work, and coordinate activities as much as possible. The Fourth International Symposium on Long Range Sound Propagation was jointly sponsored by the University of Mississippi, the Open University of England, and NASA. Papers were given in the following areas: ground effects on propagation; infrasound propagation; and meteorological effects on sound propagation. A compilation of the presentations made at the symposium is presented along with a list of attendees, and the agenda.

Willshire, William L., Jr.↗

The Chorus Conflict and Loss of Separation Resolution Algorithms

The Chorus software is designed to investigate near-term, tactical conflict and loss of separation detection and resolution concepts for air traffic management. This software is currently being used in two different problem domains: en-route self- separation and sense and avoid for unmanned aircraft systems. This paper describes the core resolution algorithms that are part of Chorus. The combination of several features of the Chorus program distinguish this software from other approaches to conflict and loss of separation resolution. First, the program stores a history of state information over time which enables it to handle communication dropouts and take advantage of previous input data. Second, the underlying conflict algorithms find resolutions that solve the most urgent conflict, but also seek to prevent secondary conflicts with the other aircraft. Third, if the program is run on multiple aircraft, and the two aircraft maneuver at the same time, the result will be implicitly co-ordinated. This implicit coordination property is established by ensuring that a resolution produced by Chorus will comply with a mathematically-defined criteria whose correctness has been formally verified. Fourth, the program produces both instantaneous solutions and kinematic solutions, which are based on simple accel- eration models. Finally, the program provides resolutions for recovery from loss of separation. Different versions of this software are implemented as Java and C++ software programs, respectively.

Butler, Ricky W.↗

SatNet: A Benchmark for Satellite Scheduling Optimization

Satellites provide essential services such as networking and weather tracking, and the number of near-earth and deep space satellites are expected to grow rapidly in the coming years. Communications with terrestrial ground stations is one of the critical functionalities of any space mission. Satellite scheduling is a problem that has been scientifically investigated since the 1970s. A central aspect of this problem is the need to consider resource contention and satellite visibility constraints as they require line of sight. Due to the combinatorial nature of the problem, prior solutions such as linear programs and evolutionary algorithms require extensive compute capabilities to output a feasible schedule for each scenario. Machine learning based scheduling can provide an alternative solution by training a model with historical data and generating a schedule quickly with model inference. We present SatNet, a benchmark for satellite scheduling optimization based on historical data from the NASA Deep Space Network. We propose formulation of the satellite scheduling problem as a Markov Decision Process and use reinforcement learning (RL) policies to generate schedules. The nature of constraints imposed by SatNet differ from other combinatorial optimization problems such as vehicle routing studied in prior literature. Our initial results indicate that RL is an alternative optimization approach that can generate candidate solutions of comparable quality to existing state-of-the-practice results. However, we also find that RL policies overfit to the training dataset and do not generalize well to new data, thereby necessitating continued research on reusable and generalizable agents.

Wilson, Brian↗

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↗

Neural Network Solves "Traveling-Salesman" Problem

Experimental electronic neural network solves "traveling-salesman" problem. Plans round trip of minimum distance among N cities, visiting every city once and only once (without backtracking). This problem is paradigm of many problems of global optimization (e.g., routing or allocation of resources) occuring in industry, business, and government. Applied to large number of cities (or resources), circuits of this kind expected to solve problem faster and more cheaply.

Thakoor, Anilkumar P.↗

Flight Crew Factors for CTAS/FMS Integration in the Terminal Area

Center TRACON Automation System (CTAS)/Flight Management System (FMS) integration on the flightdeck implies flight crews flying coupled in highly automated FMS modes [i.e. Vertical Navigation (VNAV) and Lateral Navigation (LNAV)] from top of descent to the final approach phase of flight. Pilots may also have to make FMS route edits and respond to datalink clearances in the Terminal Radar Approach Control (TRACON) airspace. This full mission simulator study addresses how the introduction of these FMS descent procedures affect crew activities, workload, and performance. It also assesses crew acceptance of these procedures. Results indicate that the number of crew activities and workload ratings are significantly reduced below current day levels when FMS procedures can be flown uninterrupted, but that activity numbers increase significantly above current day levels and workload ratings return to current day levels when FMS procedures are interrupted by common ATC interventions and CTAS routing advisories. Crew performance showed some problems with speed control during FMS procedures. Crew acceptance of the FMS procedures and route modification requirements was generally high; a minority of crews expressed concerns about use of VNAV in the TRACON airspace. Suggestions for future study are discussed.

Crane, Barry W.↗

Separation-Compliant, Optimal Routing and Control of Scheduled Arrivals in a Terminal Airspace

We address the problem of navigating a set (fleet) of aircraft in an aerial route network so as to bring each aircraft to its destination at a specified time and with minimal distance separation assured between all aircraft at all times. The speed range, initial position, required destination, and required time of arrival at destination for each aircraft are assumed provided. Each aircraft's movement is governed by a controlled differential equation (state equation). The problem consists in choosing for each aircraft a path in the route network and a control strategy so as to meet the constraints and reach the destination at the required time. The main contribution of the paper is a model that allows to recast this problem as a decoupled collection of problems in classical optimal control and is easily generalized to the case when inertia cannot be neglected. Some qualitative insight into solution behavior is obtained using the Pontryagin Maximum Principle. Sample numerical solutions are computed using a numerical optimal control solver. The proposed model is first step toward increasing the fidelity of continuous time control models of air traffic in a terminal airspace. The Pontryagin Maximum Principle implies the polygonal shape of those portions of the state trajectories away from those states in which one or more aircraft pair are at minimal separation. The model also confirms the intuition that, the narrower the allowed speed ranges of the aircraft, the smaller the space of optimal solutions, and that an instance of the optimal control problem may not have a solution at all (i.e., no control strategy that meets the separation requirement and other constraints).

transportation network↗

A network flow model for load balancing in circuit-switched multicomputers

In multicomputers that utilize circuit switching or wormhole routing, communication overhead depends largely on link contention - the variation due to distance between nodes is negligible. This has a major impact on the load balancing problem. In this case, there are some nodes with excess load (sources) and others with deficit load (sinks) and it is required to find a matching of sources to sinks that avoids contention. The problem is made complex by the hardwired routing on currently available machines: the user can control only which nodes communicate but not how the messages are routed. Network flow models of message flow in the mesh and the hypercube were developed to solve this problem. The crucial property of these models is the correspondence between minimum cost flows and correctly routed messages. To solve a given load balancing problem, a minimum cost flow algorithm is applied to the network. This permits one to determine efficiently a maximum contention free matching of sources to sinks which, in turn, tells one how much of the given imbalance can be eliminated without contention.

Bokhari, Shahid H.↗

A network flow model for load balancing in circuit-switched multicomputers

In multicomputers that utilize circuit switching or wormhole routing, communication overhead depends largely on link contention - the variation due to distance between nodes is negligible. This has a major impact on the load balancing problem. In this case, there are some nodes with excess load (sources) and others with deficit load (sinks) and it is required to find a matching of sources to sinks that avoids contention. The problem is made complex by the hardwired routing on currently available machines: the user can control only which nodes communicate but not how the messages are routed. Network flow models of message flow in the mesh and the hypercube were developed to solve this problem. The crucial property of these models is the correspondence between minimum cost flows and correctly routed messages. To solve a given load balancing problem, a minimum cost flow algorithm is applied to the network. This permits one to determine efficiently a maximum contention free matching of sources to sinks which, in turn, tells one how much of the given imbalance can be eliminated without contention.

Bokhari, Shahid H.↗

Agent Reward Shaping for Alleviating Traffic Congestion

Traffic congestion problems provide a unique environment to study how multi-agent systems promote desired system level behavior. What is particularly interesting in this class of problems is that no individual action is intrinsically "bad" for the system but that combinations of actions among agents lead to undesirable outcomes, As a consequence, agents need to learn how to coordinate their actions with those of other agents, rather than learn a particular set of "good" actions. This problem is ubiquitous in various traffic problems, including selecting departure times for commuters, routes for airlines, and paths for data routers. In this paper we present a multi-agent approach to two traffic problems, where far each driver, an agent selects the most suitable action using reinforcement learning. The agent rewards are based on concepts from collectives and aim to provide the agents with rewards that are both easy to learn and that if learned, lead to good system level behavior. In the first problem, we study how agents learn the best departure times of drivers in a daily commuting environment and how following those departure times alleviates congestion. In the second problem, we study how agents learn to select desirable routes to improve traffic flow and minimize delays for. all drivers.. In both sets of experiments,. agents using collective-based rewards produced near optimal performance (93-96% of optimal) whereas agents using system rewards (63-68%) barely outperformed random action selection (62-64%) and agents using local rewards (48-72%) performed worse than random in some instances.

Tumer, Kagan↗

A Survey of Collective Intelligence

This chapter presents the science of "COllective INtelligence" (COIN). A COIN is a large multi-agent systems where: i) the agents each run reinforcement learning (RL) algorithms; ii) there is little to no centralized communication or control; iii) there is a provided world utility function that, rates the possible histories of tile full system. Tile conventional approach to designing large distributed systems to optimize a world utility does not use agents running RL algorithms. Rather that approach begins with explicit modeling of the overall system's dynamics, followed by detailed hand-tuning of the interactions between the components to ensure that they "cooperate" as far as the world utility is concerned. This approach is labor-intensive, often results in highly non-robust systems, and usually results in design techniques that, have limited applicability. In contrast, with COINs we wish to solve the system design problems implicitly, via the 'adaptive' character of the RL algorithms of each of the agents. This COIN approach introduces an entirely new, profound design problem: Assuming the RL algorithms are able to achieve high rewards, what reward functions for the individual agents will, when pursued by those agents, result in high world utility? In other words, what reward functions will best ensure that we do not have phenomena like the tragedy of the commons, or Braess's paradox? Although still very young, the science of COINs has already resulted in successes in artificial domains, in particular in packet-routing, the leader-follower problem, and in variants of Arthur's "El Farol bar problem". It is expected that as it matures not only will COIN science expand greatly the range of tasks addressable by human engineers, but it will also provide much insight into already established scientific fields, such as economics, game theory, or population biology.

Wolpert, David H.↗