The joint movement of pebbles in solving the ($$N^2-1$$)-puzzle suboptimally and its applications in rule-based cooperative path-finding

The present paper deals with the problem of solving the (\(n^2 - 1\))-puzzle and cooperative path-finding (CPF) problems sub-optimally by rule-based algorithms. To solve the puzzle, we need to rearrange \(n^2 - 1\) pebbles in the \(n \times n\)-sized square grid using one vacant position to achieve the goal configuration. An improvement to the existing polynomial-time algorithm is proposed and experimentally analyzed. The improved algorithm represents an attempt to move pebbles in a more efficient way compared to the original algorithm by grouping them into so-called snakes and moving them together as part of a snake formation. An experimental evaluation has shown that the snakeenhanced algorithm produces solutions which are 8–9 % shorter than the solutions generated by the original algorithm. Snake-like movement has also been integrated into the rule-based algorithms used in solving CPF problems sub-optimally, which is a closely related task. The task in CPF consists in moving a group of abstract robots on an undirected graph to specific vertices. The robots can move to unoccupied neighboring vertices; no more than one robot can be placed in each vertex. The (\(n^2 - 1\))-puzzle is a special case of CPF where the underlying graph is a 4-connected grid and only one vertex is vacant. Two major rule-based algorithms for solving CPF problems were included in our study—BIBOX and PUSH-and-SWAP (PUSH-and-ROTATE). The use of snakes in the BIBOX algorithm led to consistent efficiency gains of around 30 % for the (\(n^2 - 1\))-puzzle and up to 50 % in for CPF problems on biconnected graphs with various ear decompositions and multiple vacant vertices. For the PUSH-and-SWAP algorithm, the efficiency gain achieved from the use of snakes was around 5–8 %. However, the efficiency gain was unstable and hardly predictable for PUSH-and-SWAP.     

Generating heavy particles with energy and momentum conservation

We propose a novel algorithm, called REGGAE, for the generation of momenta of a given sample of particle masses, evenly distributed in Lorentz-invariant phase space and obeying energy and momentum conservation. In comparison to other existing algorithms, REGGAE is designed for the use in multiparticle production in hadronic and nuclear collisions where many hadrons are produced and a large part of the available energy is stored in the form of their masses. The algorithm uses a loop simulating multiple collisions which lead to production of configurations with reasonably large weights.

Program summary

Program title: REGGAE (REscattering-after-Genbod GenerAtor of Events)Catalogue identifier: AEJR_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEJR_v1_0.htmlProgram obtainable from: CPC Program Library, Queen?s University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 1523No. of bytes in distributed program, including test data, etc.: 9608Distribution format: tar.gzProgramming language: C++Computer: PC Pentium 4, though no particular tuning for this machine was performed.Operating system: Originally designed on Linux PC with g++, but it has been compiled and ran successfully on OS X with g++ and MS Windows with Microsoft Visual C++ 2008 Express Edition, as well.RAM: This depends on the number of particles which are generated. For 10 particles like in the attached example it requires about 120 kB.Classification: 11.2Nature of problem: The task is to generate momenta of a sample of particles with given masses which obey energy and momentum conservation. Generated samples should be evenly distributed in the available Lorentz-invariant phase space.Solution method: In general, the algorithm works in two steps. First, all momenta are generated with the GENBOD algorithm. There, particle production is modeled as a sequence of two-body decays of heavy resonances. After all momenta are generated this way, they are reshuffled. Each particle undergoes a collision with some other partner such that in the pair center of mass system the new directions of momenta are distributed isotropically. After each particle collides only a few times, the momenta are distributed evenly across the whole available phase space. Starting with GENBOD is not essential for the procedure but it improves the performance.Running time: This depends on the number of particles and number of events one wants to generate. On a LINUX PC with 2 GHz processor, generation of 1000 events with 10 particles each takes about 3 s.     

Supervised relevance maps for increasing the distinctiveness of facial images

This paper shows how to improve holistic face analysis by assigning importance factors to different facial regions (termed as face relevance maps). We propose a novel supervised learning algorithm for generating face relevance maps to improve the discriminating capability of existing methods. We have successfully applied the developed technique to face identification based on the Eigenfaces and Fisherfaces methods, and also to gender classification based on principal geodesic analysis (PGA). We demonstrate how to iteratively learn the face relevance map using labelled data. Experimental results confirm the effectiveness of the developed approach.     

Colour and rotation invariant textural features based on Markov random fields

A visual appearance of natural materials significantly depends on acquisition circumstances, particularly illumination conditions and viewpoint position, whose variations cause difficulties in the analysis of real scenes. We address this issue with novel texture features, based on fast estimates of Markovian statistics, that are simultaneously rotation and illumination invariant. The proposed features are invariant to in-plane material rotation and illumination spectrum (colour invariance), they are robust to local intensity changes (cast shadows) and illumination direction. No knowledge of illumination conditions is required and recognition is possible from a single training image per material. The material recognition is tested on the currently most realistic visual representation - Bidirectional Texture Function (BTF), using CUReT and ALOT texture datasets with more than 250 natural materials. Our proposed features significantly outperform leading alternatives including Local Binary Patterns (LBP, LBP-HF) and texton MR8 methods.     

Registration of challenging image pairs: initialization, estimation, and decision

Our goal is an automated 2D-image-pair registration algorithm capable of aligning images taken of a wide variety of natural and man-made scenes as well as many medical images. The algorithm should handle low overlap, substantial orientation and scale differences, large illumination variations, and physical changes in the scene. An important component of this is the ability to automatically reject pairs that have no overlap or have too many differences to be aligned well.We propose a complete algorithm, including techniques for initialization, for estimating transformation parameters, and for automatically deciding if an estimate is correct. Keypoints extracted and matched between images are used to generate initial similarity transform estimates, each accurate over a small region. These initial estimates are rank-ordered and tested individually in succession. Each estimate is refined using the Dual-Bootstrap ICP algorithm, driven by matching of multiscale features. A three-part decision criteria, combining measurements of alignment accuracy, stability in the estimate, and consistency in the constraints, determines whether the refined transformation estimate is accepted as correct. Experimental results on a data set of 22 challenging image pairs show that the algorithm effectively aligns 19 of the 22 pairs and rejects 99.8% of the misalignments that occur when all possible pairs are tried. The algorithm substantially out-performs algorithms based on keypoint matching alone.     

Combining classifiers under probabilistic models: experimental comparative analysis of methods

This work will present a review of the concept of classifier combination based on the combined discriminant function. We will present a Bayesian approach, in which the discriminant function assumes the role of the posterior probability. We will propose a probabilistic interpretation of expert rules and conditions of knowledge consistency for expert rules and learning sets. We will suggest how to measure the quality of learning materials and we will use the measure mentioned above for an algorithm that eliminates contradictions in the rule set. In this work several recognition algorithms will be described, based on either: (i) pure rules, or; (ii) rules together with learning sets. Furthermore, the original concept of information unification, which enables the formation of rules on the basis of learning set or learning set on the basis of rules will be proposed. The obtained conclusions will serve as a spring‐board for the formulation of new project guidelines for this type of decision‐making system. At the end, experimental results of the proposed algorithms will be presented, both from computer generated data and for a real problem from the medical diagnostics field.     

Image auto-annotation with automatic selection of the annotation length

Developing a satisfactory and effective method for auto-annotating images that works under general conditions is a challenging task. The advantages of such a system would be manifold: it can be used to annotate existing, large databases of images, rendering them accessible to text search engines; or it can be used as core for image retrieval based on a query image’s visual content. Manual annotation of images is a difficult, tedious and time consuming task. Furthermore, manual annotations tend to show great inter-person variance: considering an image, the opinions about what elements are significant and deserve an annotation vary strongly. The latter poses a problem for the evaluation of an automatic method, as an annotation’s correctness is greatly subjective. In this paper we present an automatic method for annotating images, which addresses one of the existing methods’ major limitation, namely a fixed annotation length. The proposed method, PATSI, automatically chooses the resulting annotation’s length for each query image. It is held as simple as possible and a build-in parameter optimization procedure renders PATSI de-facto parameter free. Finally, PATSI is evaluated on standard datasets, outperforming various state-of-the-art methods.     

Surface hardening of Ti alloys by gas-phase nitridation: Kinetic control of the nitrogen surface activity

A new concept for surface hardening of titanium alloys has been developed and successfully applied to Ti-6Al-4V alloys: gas-phase nitridation under kinetic control of the nitrogen activity. This method avoids the formation of detrimental second-phase nitrides by nitriding under a very low nitrogen activity, combined with rapid diffusion of nitrogen into the specimen. The surface hardness of the Ti-6Al-4V alloy was increased by a factor of 2 to ≈ 12 GPa, with only modest attenuation of ductility. We have realized conditions for generating case depths of ≈ 25 μm in reasonable nitridation times. The nitrogen activity in the gas phase is generated by heating a powder pack of Cr and Cr₂N. A closed two-zone system allows the powder pack and the specimen to be at different temperatures, optimizing both the nitrogen partial pressure and the nitrogen diffusion into the specimen. This low-cost, conformal nitridation process generates a smoothly graded nitrogen concentration profile and can be applied to finished Ti alloy components.     

Alzheimer paired helical filaments (PHFs) studied by high-resolution TEM: what can vertical Pt-C replication tell us about the organization of the pronase-digested PHF core?

Untreated paired helical filaments (PHFs) and pronase-digested PHF-core filaments were stereoscopically imaged with a freeze-drying vertical platinum-carbon replication preparation method for TEM. The untreated PHF have an average wide region (W) = 22.8 +/- 2.4 nm, a narrow region (T) = 10.6 +/- 1.7 nm, and a helical turn period (L) = 78.6 +/- 13.4. The surfaces of the untreated PHF's fuzzy coat appears disorganized. The widths of the pronase-treated PHF-core filaments were significantly reduced (W(d) = 14.8 +/- 1.2 nm, T(d) = 5.7 +/- 1.0 nm, and L(d) = 75.4 +/- 17 nm). The surfaces of the untreated PHF contained approximately 1.1 nm strands, the same size as tau monomer ( approximately 1.0 nm). The pronase-digested PHF cores mostly contained approximately 1.6 +/- 0.3 nm strands although strand diameters ranged from 0.6-2.5 nm. The strands sometimes appear to be wrapped around the filament axis; less often, they appear to be roughly parallel to the PHF axis, and otherwise appear to be randomly oriented. Images of pronase-digested PHF core images are discussed in relation to the core's biochemical composition, its proposed beta structure, and structural subunit models. Images of the untreated and the pronase-digested PHF support a helical ribbon morphology.     

Tensile strains ahead of entry into the roll gap

Tensile strains ahead of entry into the roll gap were analysed using the finite element method and compared with results of the analytical approach developed by Pawelski [1]. The longitudinal tensile strains in the stock surface ahead of contact with the roll produced by frictional contact with the roll were calculated for the different roll gap aspect ratios, h_o/L = 0.1,…1 and Coulombic friction coefficient 0.1,…0.5. The results have been analysed in terms of oxide failure resulting from this kind of deformation and compared with predictions using the advanced oxide scale model. A simple formula has been developed to evaluate the longitudinal strain component at entry into the roll gap for a given friction coefficient and aspect ratio. It was related to cracking of the oxide scale in tension at this area. Prediction of the scale behaviour at this area is a key to understanding the friction and heat transfer phenomena taking place at the roll/stock interface. It is also important for optimisation of descaling operations.