A multiagent approach to managing air traffic flow

Intelligent air traffic flow management is one of the fundamental challenges facing the Federal Aviation Administration (FAA) today. FAA estimates put weather, routing decisions and airport condition induced delays at 1,682,700 h in 2007 (FAA OPSNET Data, US Department of Transportation website, ), resulting in a staggering economic loss of over $41 billion (Joint Economic Commission Majority Staff, Your flight has been delayed again, 2008). New solutions to the flow management are needed to accommodate the threefold increase in air traffic anticipated over the next two decades. Indeed, this is a complex problem where the interactions of changing conditions (e.g., weather), conflicting priorities (e.g., different airlines), limited resources (e.g., air traffic controllers) and heavy volume (e.g., over 40,000 flights over the US airspace) demand an adaptive and robust solution. In this paper we explore a multiagent algorithm where agents use reinforcement learning (RL) to reduce congestion through local actions. Each agent is associated with a fix (a specific location in 2D space) and has one of three actions: setting separation between airplanes, ordering ground delays or performing reroutes. We simulate air traffic using FACET which is an air traffic flow simulator developed at NASA and used extensively by the FAA and industry. Our FACET simulations on both artificial and real historical data from the Chicago and New York airspaces show that agents receiving personalized rewards reduce congestion by up to 80% over agents receiving a global reward and by up to 90% over a current industry approach (Monte Carlo estimation).     

Provably correct runtime monitoring

Runtime monitoring is an established technique to enforce a wide range of program safety and security properties. We present a formalization of monitoring and monitor inlining, for the Java Virtual Machine. Monitors are security automata given in a special-purpose monitor specification language, ConSpec. The automata operate on finite or infinite strings of calls to a fixed API, allowing local dependencies on parameter values and heap content. We use a two-level class file annotation scheme to characterize two key properties: (i) that the program is correct with respect to the monitor as a constraint on allowed program behavior, and (ii) that the program has a copy of the given monitor embedded into it. As the main application of these results we sketch a simple inlining algorithm and show how the two-level annotations can be completed to produce a fully annotated program which is valid in the standard sense of Floyd/Hoare logic. This establishes the mediation property that inlined programs are guaranteed to adhere to the intended policy. Furthermore, validity can be checked efficiently using a weakest precondition based annotation checker, thus preparing the ground for on-device checking of policy adherence in a proof-carrying code setting.     

A constraint programming-based solution approach for medical resident scheduling problems

Persistent calls come from within the graduate medical education community and from external sources for regulating the resident duty hours in order to meet the obligations about the quality of resident education, the well-being of residents themselves, and the quality of patient care services. The report of the Accreditation Council for Graduate Medical Education (ACGME) proposes common program requirements for resident hours. In this paper, we first develop a mixed-integer programming model for scheduling residents’ duty hours considering the on-call night, day-off, rest period, and total work-hour ACGME regulations as well as the demand coverage requirements of the residency program. Subsequently, we propose a column generation model that consists of a master problem and an auxiliary problem. The master problem finds a configuration of individual schedules that minimizes the sum of deviations from the desired service levels for the day and night periods. The formulation of this problem is possible by representing the feasible schedules using column variables, whereas the auxiliary problem finds the whole set of feasible schedules using constraint programming. The proposed approach has been tested on a series of problems using real data obtained from a hospital. The results indicate that high-quality schedules can be obtained within a few seconds.     

Efficient evaluation functions for evolving coordination

Abstract This paper presents fitness evaluation functions that efficiently evolve coordination in large multi-component systems. In particular, we focus on evolving distributed control policies that are applicable to dynamic and stochastic environments. While it is appealing to evolve such policies directly for an entire system, the search space is prohibitively large in most cases to allow such an approach to provide satisfactory results. Instead, we present an approach based on evolving system components individually where each component aims to maximize its own fitness function. Though this approach sidesteps the exploding state space concern, it introduces two new issues: (1) how to create component evaluation functions that are aligned with the global evaluation function; and (2) how to create component evaluation functions that are sensitive to the fitness changes of that component, while remaining relatively insensitive to the fitness changes of other components in the system. If the first issue is not addressed, the resulting system becomes uncoordinated; if the second issue is not addressed, the evolutionary process becomes either slow to converge or worse, incapable of converging to good solutions. This paper shows how to construct evaluation functions that promote coordination by satisfying these two properties. We apply these evaluation functions to the distributed control problem of coordinating multiple rovers to maximize aggregate information collected. We focus on environments that are highly dynamic (changing points of interest), noisy (sensor and actuator faults), and communication limited (both for observation of other rovers and points of interest) forcing the rovers to evolve generalized solutions. On this difficult coordination problem, the control policy evolved using aligned and component-sensitive evaluation functions outperforms global evaluation functions by up to 400%. More notably, the performance improvements increase when the problems become more difficult (larger, noisier, less communication). In addition we provide an analysis of the results by quantifying the two characteristics (alignment and sensitivity discussed above) leading to a systematic study of the presented fitness functions.     

Analyzing and visualizing multiagent rewards in dynamic and stochastic domains

The ability to analyze the effectiveness of agent reward structures is critical to the successful design of multiagent learning algorithms. Though final system performance is the best indicator of the suitability of a given reward structure, it is often preferable to analyze the reward properties that lead to good system behavior (i.e., properties promoting coordination among the agents and providing agents with strong signal to noise ratios). This step is particularly helpful in continuous, dynamic, stochastic domains ill-suited to simple table backup schemes commonly used in TD(λ)/Q-learning where the effectiveness of the reward structure is difficult to distinguish from the effectiveness of the chosen learning algorithm. In this paper, we present a new reward evaluation method that provides a visualization of the tradeoff between the level of coordination among the agents and the difficulty of the learning problem each agent faces. This method is independent of the learning algorithm and is only a function of the problem domain and the agents’ reward structure. We use this reward property visualization method to determine an effective reward without performing extensive simulations. We then test this method in both a static and a dynamic multi-rover learning domain where the agents have continuous state spaces and take noisy actions (e.g., the agents’ movement decisions are not always carried out properly). Our results show that in the more difficult dynamic domain, the reward efficiency visualization method provides a two order of magnitude speedup in selecting good rewards, compared to running a full simulation. In addition, this method facilitates the design and analysis of new rewards tailored to the observational limitations of the domain, providing rewards that combine the best properties of traditional rewards.     

Simulation of exhaust gas reforming of propane in a heat exchange integrated microchannel reactor

Exhaust gas reforming of propane to a hydrogen-rich mixture in a single, heat-exchange integrated, adiabatic, catalytic microchannel is modeled and simulated at different exhaust gas compositions from conventional gasoline and diesel fueled engines. Propane is considered as the model hydrocarbon for the complex fuels such as gasoline and diesel. The single microchannel is considered to be the characteristic unit of the catalytic exhaust gas reformer involving identical channels located parallel to each other. Steady-state simulations, carried out by the finite volume method, involve parametric variations of the total feed flow rate, and the amounts of propane and steam injected externally into the exhaust gas (reformer feed) stream. The results show that effective heat transfer and uniform temperature distribution, which are critical for the successful operation of the exhaust gas reformer, can be obtained in the microchannel configuration even at low gas hourly space velocities (GHSVs) at which the conventional packed-bed reformers usually lead to remarkable hot-spot formation. Production of H₂ and CO is favored by the addition of higher amounts of propane and steam into the reformer feed. Increasing the total feed flow rate, hence the GHSV is found to improve heat distribution along the microchannel at the expense of reduced product yields due to insufficient contact time.     

A case for trading risk in complex conceptual design trade studies

Complex conceptual system design trade studies traditionally consider risk after a conceptual design has been created. Further, one person is often tasked with collecting risk information and managing it from each subsystem. This paper proposes a method to explicitly consider and trade risk on the same level as other important system-level variables during the creation of conceptual designs in trade studies. The proposed risk trading method advocates putting each subsystem engineer in control of risk for each subsystem. A risk vector is proposed that organizes many different risk metrics for communication between subsystems. A method of coupling risk models to dynamic subsystem models is presented. Several risk visualization techniques are discussed. A trade study example is presented based upon a simplified spacecraft model. Results from introducing the risk trading methodology into a simulated Collaborative Design Center are presented. The risk trading method offers an approach to more thoroughly consider risk during the creation of conceptual designs in trade studies.     

POSS-based hybrid thermosets via photoinduced copper-catalyzed azide–alkyne cycloaddition click chemistry

An efficient approach for the preparation of inorganic/organic hybrid thermosets via photoinduced copper-catalyzed azide–alkyne cycloaddition click chemistry is established. Highly cross-linked thermoset polymers have been practically obtained by this technique using multifunctional compounds, tri-alkyne (1,1,1-tris[4-(2-propynyloxy) phenyl]-ethane) with octakis-azido-POSS or tri-azide (3,3′-((2-((3-azido-2-hydroxypropoxy)methyl)-2-ethylpropane-1,3-diyl)bis(oxy))bis(1-azidopropan-2-ol)) in the presence of Cu(II)Br₂/N,N,N′,N″,N?-pentamethyldiethylenetriamine/2-dimethoxy-2-phenyl acetophenone. The homogeneously distributed POSS nanoparticles are clearly detected in the TEM micrographs; whereas the TGA analysis shows that the obtained hybrid thermosets are thermally stable up to 360 °C and begin to lose weight at higher temperatures with a char yield of 23–50% at 800 °C.     

A CONSTRAINT PROGRAMMING HEURISTIC FOR A HETEROGENEOUS VEHICLE ROUTING PROBLEM WITH SPLIT DELIVERIES

This article considers fresh goods distribution of a retail chain store in Turkey. The problem is formulated as a vehicle routing problem with a heterogeneous fleet for which no exact algorithm has ever been designed to solve it. A fast and effective algorithm based on constraint programming is proposed for the solution. The procedure is tested on some of the benchmark problems in literature. The real-life case is first solved assuming that delivery of a customer cannot be split between vehicles. Then it is resolved considering split deliveries. Solutions of both strategies are compared with the current performance of the firm to determine a distribution strategy. Results indicate considerable improvement in the performance of the firm.