Summary Maps for Lifelong Visual Localization

Robots that use vision for localization need to handle environments that are subject to seasonal and structural change, and operate under changing lighting and weather conditions. We present a framework for lifelong localization and mapping designed to provide robust and metrically accurate online localization in these kinds of changing environments. Our system iterates between offline map building, map summary, and online localization. The offline mapping fuses data from multiple visually varied datasets, thus dealing with changing environments by incorporating new information. Before passing these data to the online localization system, the map is summarized, selecting only the landmarks that are deemed useful for localization. This Summary Map enables online localization that is accurate and robust to the variation of visual information in natural environments while still being computationally efficient. We present a number of summary policies for selecting useful features for localization from the multisession map, and we explore the tradeoff between localization performance and computational complexity. The system is evaluated on 77 recordings, with a total length of 30 kilometers, collected outdoors over 16 months. These datasets cover all seasons, various times of day, and changing weather such as sunshine, rain, fog, and snow. We show that it is possible to build consistent maps that span data collected over an entire year, and cover day‐to‐night transitions. Simple statistics computed on landmark observations are enough to produce a Summary Map that enables robust and accurate localization over a wide range of seasonal, lighting, and weather conditions.     

Path‐space Motion Estimation and Decomposition for Robust Animation Filtering

Renderings of animation sequences with physics‐based Monte Carlo light transport simulations are exceedingly costly to generate frame‐by‐frame, yet much of this computation is highly redundant due to the strong coherence in space, time and among samples. A promising approach pursued in prior work entails subsampling the sequence in space, time, and number of samples, followed by image‐based spatio‐temporal upsampling and denoising. These methods can provide significant performance gains, though major issues remain: firstly, in a multiple scattering simulation, the final pixel color is the composite of many different light transport phenomena, and this conflicting information causes artifacts in image‐based methods. Secondly, motion vectors are needed to establish correspondence between the pixels in different frames, but it is unclear how to obtain them for most kinds of light paths (e.g. an object seen through a curved glass panel). To reduce these ambiguities, we propose a general decomposition framework, where the final pixel color is separated into components corresponding to disjoint subsets of the space of light paths. Each component is accompanied by motion vectors and other auxiliary features such as reflectance and surface normals. The motion vectors of specular paths are computed using a temporal extension of manifold exploration and the remaining components use a specialized variant of optical flow. Our experiments show that this decomposition leads to significant improvements in three image‐based applications: denoising, spatial upsampling, and temporal interpolation.     

Hydrophilic polycarbonate chips for generation of oil-in-water (O/W) and water-in-oil-in-water (W/O/W) emulsions

Modification of the surfaces of polycarbonate (PC) with the use of a solution of tin (II) chloride renders them hydrophilic. The surface draping is stable against exposure to water and to alcohols. Exposure to alkanes reduces but does not diminish the effect. The method is compatible—in using the same solvent and temperature—with the hydrophobic modification of PC (Jankowski et al. in Lab Chip 11:1151–1156, 2011). The combination of these methods makes it possible to generate single and multiple monodisperse emulsions with the use of flow-focusing junctions in systems made in PC—a material that is suitable for fabrication of multilayer, high-throughput microfluidic devices.     

Hydrophilic polycarbonate chips for generation of oil-in-water (O/W) and water-in-oil-in-water (W/O/W) emulsions

Modification of the surfaces of polycarbonate (PC) with the use of a solution of tin (II) chloride renders them hydrophilic. The surface draping is stable against exposure to water and to alcohols. Exposure to alkanes reduces but does not diminish the effect. The method is compatible—in using the same solvent and temperature—with the hydrophobic modification of PC Jankowski et al. ( Lab Chip 11:748–752, 2011). The combination of these methods makes it possible to generate single and multiple monodisperse emulsions with the use of flow-focusing junctions in systems made in PC—material that is suitable for fabrication of multilayer, high throughput microfluidic devices.     

An efficient algorithm for positive realizations

We observe that successive applications of known results from the theory of positive systems lead to an efficient general algorithm for positive realizations of transfer functions. We give two examples to illustrate the algorithm, one of which complements an earlier result of [L. Benvenuti, L. Farina, An example of how positivity may force realizations of ‘large’ dimensions, Systems Control Lett. 36 (1999) 261–266]. Finally, we improve a lower-bound of [B. Nagy, M. Matolcsi, A lower-bound on the dimension of positive realizations, IEEE Trans. Circuits Syst. I 50 (2003) 782–784] to indicate that the algorithm is indeed efficient in general.     

Reduced Aggregate Scattering Operators for Path Tracing

Aggregate scattering operators (ASOs) describe the overall scattering behavior of an asset (i.e., an object or volume, or collection thereof) accounting for all orders of its internal scattering. We propose a practical way to precompute and compactly store ASOs and demonstrate their ability to accelerate path tracing. Our approach is modular avoiding costly and inflexible scene‐dependent precomputation. This is achieved by decoupling light transport within and outside of each asset, and precomputing on a per‐asset level. We store the internal transport in a reduced‐dimensional subspace tailored to the structure of the asset geometry, its scattering behavior, and typical illumination conditions, allowing the ASOs to maintain good accuracy with modest memory requirements. The precomputed ASO can be reused across all instances of the asset and across multiple scenes. We augment ASOs with functionality enabling multi‐bounce importance sampling, fast short‐circuiting of complex light paths, and compact caching, while retaining rapid progressive preview rendering. We demonstrate the benefits of our ASOs by efficiently path tracing scenes containing many instances of objects with complex inter‐reflections or multiple scattering.     

On Word Equations in One Variable

For a word equation E of length n in one variable x occurring # _x times in E a resolution algorithm of O(n+# _x log n) time complexity is presented here. This is the best result known and for the equations that feature #_x < \fracnlogn\#_{x}<\frac{n}{\log n} it yields time complexity of O(n) which is optimal. Additionally it is proven here that the set of solutions of any one-variable word equation is either of the form F or of the form F∪(uv)⁺ u where F is a set of O(log n) words and u, v are some words such that uv is a primitive word.     

Model Checking Abilities of Agents: A Closer Look

Alternating-time temporal logic (atl) is a logic for reasoning about open computational systems and multi-agent systems. It is well known that atl model checking is linear in the size of the model. We point out, however, that the size of an atl model is usually exponential in the number of agents. When the size of models is defined in terms of states and agents rather than transitions, it turns out that the problem is (1) Δ ₃ ^P -complete for concurrent game structures, and (2) Δ ₂ ^P -complete for alternating transition systems. Moreover, for “Positive atl” that allows for negation only on the level of propositions, model checking is (1) Σ ₂ ^P -complete for concurrent game structures, and (2) NP-complete for alternating transition systems. We show a nondeterministic polynomial reduction from checking arbitrary alternating transition systems to checking turn-based transition systems, We also discuss the determinism assumption in alternating transition systems, and show that it can be easily removed. In the second part of the paper, we study the model checking complexity for formulae of atl with imperfect information (atl _ir ). We show that the problem is Δ ₂ ^P -complete in the number of transitions and the length of the formula (thereby closing a gap in previous work of Schobbens in Electron. Notes Theor. Comput. Sci. 85(2), 2004). Then, we take a closer look and use the same fine structure complexity measure as we did for atl with perfect information. We get the surprising result that checking formulae of atl _ir is also Δ ₃ ^P -complete in the general case, and Σ ₂ ^P -complete for “Positive atl _ir ”. Thus, model checking agents’ abilities for both perfect and imperfect information systems belongs to the same complexity class when a finer-grained analysis is used.     

On Reduction Systems Equivalent to the Non-associative Lambek Calculus with the Empty String

The article concludes a series of results on cut-rule axiomatizabilityof the Lambek calculus. It is proved that the non-associativeproduct-free Lambek calculus with the empty string (NL₀) isnot finitely axiomatizable if the only rule of inference admittedis Lambek's cut rule. The proof makes use of the (infinitely)cut-rule axiomatized calculus NC designed by the author exactlyfor that purpose.