Formal verification of conflict detection algorithms

Safety assessment of new air traffic management systems is a main issue for civil aviation authorities. Standard techniques such as testing and simulation have serious limitations in new systems that are significantly more autonomous than the older ones. In this paper, we present an innovative approach for establishing the correctness of conflict detection systems. Fundamental to our approach is the concept of trajectory, and how we represent a continuous physical trajectory by a continuous path in the x-y plane constrained by physical laws and operational requirements. From the model of trajectories, we extract, and formally prove, high-level properties that can serve as a framework to analyze conflict scenarios. We use the AILS (Airborne Information for Lateral Spacing) alerting algorithm as a case study of our approach. Published online: 19 November 2002     

Declarative Formalization of Reasoning Strategies: A Case Study on Heuristic Nonlinear Planning

We study the declarative formalization of reasoning strategies by presenting declarative formalizations of: (1) the SNLP algorithm for nonlinear planning, and (2) a particular algorithm for blocks world nonlinear planning proposed in this paper. The formal models of a heuristic forward chaining planner, which can take advantage of declarative formalizations of action selection strategies, and of a reasoning strategy based planner, which can use declarative formalizations of reasoning strategies, are proposed. The effectiveness of these systems is studied from formal and empirical points of view. Empirical results showing how the use of declarative formalizations of reasoning strategies can reduce the amount of search required for solving planning problems (with respect to state of the art planning systems) are presented.     

Packet Video Broadcasting with General-Purpose Operating Systems in an Ethernet

Video transmission with general-purpose PCs poses a number of requirements that radically differ from those of high-end dedicated video servers. We analyze the scenario of an Ethernet local area network in which a number of PCs are transmitting video streams, while other TCP/IP applications are also running concurrently. Our findings show that since the operating system clock resolution cannot cope with the transmission timing requirements the following holds: if the video transmission is performed with exact timing accuracy to maintain a constant rate then CPU load grows to 100%, thus blocking the PC for other user applications; on the other hand, if transmission is performed in a bursty manner, i.e. with sleep system calls, then CPU load decreases dramatically but the increased burstiness of the video stream has a negative impact on network performance (for example, capture effect in the Ethernet). Furthermore, the impact of video transmission over the rest of TCP/IP applications running on the same network depends heavily on the packet size. We provide an integrated analysis of operating system and network parameters to achieve video broadcasting while preserving timing requirements and minimizing the impact on other applications.     

Compiling CSPs into Tree-Driven Automata for Interactive Solving

Constraint programming techniques are widely used to model and solve decision problems and many algorithms have been developed to solve automatically and efficiently families of CSPs; nevertheless, they do not help solve interactive decision support problems, like product configuration. In such problems, the user chooses the values of the variables, and the role of the system is not to solve the CSP, but to help the user in this task. Dynamic global consistency maintaining is one of the most useful functionalities that should be offered by such a CSP platform. Unfortunately, this task is intractable in the worst case. Since interactivity requires short response times, intractability must be circumvented some way. To this end, compilation methods have been proposed that transform the original problem into a data structure allowing a short response time. In this paper, we extend the work of Amilhastre et al. [1] and Vempaty [15] by the use of a new structure, tree-driven automata, that takes advantage of the structural characteristics of configuration problems (decomposition of the components into independent subcomponents). Tree-driven automata can be far more compact than classical automata while keeping their good properties, especially a tractable complexity for the maintenance of global consistency.     

Comparison of Fe-Ni based alloys prepared by ball milling and rapid solidification

Mechanical alloying (MA) and rapid solidification (RS) are two important routes to obtain amorphous alloys. An Fe-Ni based metal-metalloid alloy (Fe₅₀Ni₃₀P₁₄Si₆) prepared by these two different processing routes was studied by differential scanning calorimetry, scanning electron microscopy with microanalysis, inductive coupled plasma, X-ray diffraction (XRD) and transmission Mössbauer spectroscopy (TMS). The results were compared with that obtained from other Fe-Ni based alloys of similar compositions. The structural analyses show that the materials obtained by mechanical alloying are not completely disordered after 40 h of milling whereas fully amorphous alloys were obtained by rapid solidification. TMS analyses show that, independent of the composition, after milling for 40 h, about 7% of the Fe remains unreacted. Furthermore, the thermal stability of mechanically alloyed samples is lower than that of the analogous material prepared by rapid solidification. In the MA alloys, a broad exothermic process associated to structural relaxation begins at low temperature. XRD patterns of crystallized alloys indicate that the crystallization products are bcc(Fe,Ni), fcc(Ni,Fe), and (Fe,Ni)-phosphides and -silicides.     

Anomalous Excess Heat Capacities of Ethanol + Alkane Mixtures

A thermodynamic study at atmospheric pressure on the ethanol + n-dodecane and ethanol + n-tridecane binary systems near their liquid-liquid critical points has been carried out. To this end, densities and speeds of sound were determined in the temperature range from 288.15 to 308.15 K, whereas differential scanning calorimetry was used to obtain isobaric heat capacities per unit volume from 288.15 to 303.15 K as well as liquid-liquid equilibrium curves. All these results for the mentioned properties were obtained over the complete composition range. They were used to obtain molar volumes, isentropic compressibilities, isobaric thermal expansivities, isothermal compressibilities, isochoric heat capacities, and the excess quantities of all these properties. An untypical behavior of the excess heat capacities at the lowest measuring temperatures resulting from the critical behavior of the isobaric heat capacity is observed. No clear anomalies for the excess volumetric properties are detected.     

Environmental Fatigue and Static Behavior of RC Beams Strengthened with Carbon-Fiber-Reinforced Polymer

Many countries around the world have tremendous needs to repair and strengthen their transportation infrastructure. Almost everywhere, traffic loads have reached levels largely exceeding design expectations. Northern countries also experience severe winter conditions that are combined with an extensive use of deicing salts and accelerate structural deterioration. In Canada, the extent of deterioration has prompted many authorities, including the federal and provincial governments, to investigate the potential use of fiber-reinforced polymer products to extend the life of their existing structures. However, it is widely recognized that the large-scale implementation of these products is often impaired by the lack of data on their durability. This paper presents an experimental project undertaken in order to assess the durability of reinforced concrete beams externally strengthened with two types of carbon-fiber-reinforced polymer (CFRP). The beams were first exposed to either wet-dry cycles or continuous immersion in water and then were loaded in fatigue. Finally, they were tested quasi-statically under four-point bending up to failure. The test results presented here provide some insights on the potential long-term performance of CFRP-strengthened beams exposed to severe environmental conditions.     

Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators

This paper is the result of a literature study carried out by the authors. It is a review of the different attempts made to solve the Travelling Salesman Problem with Genetic Algorithms. We present crossover and mutation operators, developed to tackle the Travelling Salesman Problem with Genetic Algorithms with different representations such as: binary representation, path representation, adjacency representation, ordinal representation and matrix representation. Likewise, we show the experimental results obtained with different standard examples using combination of crossover and mutation operators in relation with path representation.