Recent Results on Stability Analysis of an Optimal Assembly Line Balance

Two assembly line balancing problems are addressed. The first problem (called SALBP-1) is to minimize number of linearly ordered stations for processing n partially ordered operations V = {1, 2, ..., n} within the fixed cycle time c. The second problem (called SALBP-2) is to minimize cycle time for processing partially ordered operations V on the fixed set of m linearly ordered stations. The processing time ti of each operation i ∈V is known before solving problems SALBP-1 and SALBP-2. However, during the life cycle of the assembly line the values ti are definitely fixed only for the subset of automated operations V\V . Another subset V ⊆ V includes manual operations, for which it is impossible to fix exact processing times during the whole life cycle of the assembly line. If j ∈V , then operation times tj can differ for different cycles of the production process. For the optimal line balance b of the assembly line with operation times t1, t2, ..., tn, we investigate stability of its optimality with respect to possible variations of the processing times tj of the manual operations j ∈ V .

Върху два подхода за преподаване на понятията в курса по компютърна топология

Kalin Georgiev, Dimitrina Stavrova - We consider two approaches for introducing topological notions in a course of Computational Topology. One is an intuitive inductive introduction of a notion; the other is theoretical-analytical one. As an example we treat the notions of interior, closure and boundary of a set in a topological space. We analyze several visual representations as well as analytical ones. Examples of tests and quiz problems are considered. Comparisons of student’s achievement on different type of problems are presented.

On Gruenhage spaces, separating σ-isolated families, and their relatives

We prove that, given a topological space X, the following conditions are equivalent. (α) X is a Gruenhage space. (β) X has a countable cover by sets of small local diameter (property SLD) by F∩G sets. (γ) X has a separating σ-isolated family M⊂F∩G. (δ) X has a one-to-one continuous map into a metric space which has a σ-isolated base of F∩G sets. Besides, we provide an example which shows Fragmentability ⇏ property SLD ⇏ the space to be Gruenhage.

A multi-hypothesis topological SLAM approach for loop closing on edge-ordered graphs

We present a method for topological SLAM that specifically targets loop closing for edge-ordered graphs. Instead of using a heuristic approach to accept or reject loop closing, we propose a probabilistically grounded multi-hypothesis technique that relies on the incremental construction of a map/state hypothesis tree. Loop closing is introduced automatically within the tree expansion, and likely hypotheses are chosen based on their posterior probability after a sequence of sensor measurements. Careful pruning of the hypothesis tree keeps the growing number of hypotheses under control and a recursive formulation reduces storage and computational costs. Experiments are used to validate the approach.

The space of make: A topological account of the studio

Approaches to art-practice-as-research tend to draw a distinction between the processes of creative practice and scholarly reflection. According to this template, the two sites of activity – studio/desk, work/writing, body/mind – form the ‘correlative’ entity known as research. Creative research is said to be produced by the navigation of world and thought: spaces that exist in a continual state of tension with one another. Either we have the studio tethered to brute reality while the desk floats free as a site for the fluid cross-pollination of texts and concepts. Or alternatively, the studio is characterized by the amorphous, intuitive play of forms and ideas, while the desk represents its cartography, mapping and fixing its various fluidities. In either case, the research status of art practice is figured as a fundamentally riven space. However, the nascent philosophy of Speculative Realism proposes a different ontology – one in which the space of human activity comprises its own reality, independent of human perception. The challenge it poses to traditional metaphysics is to rethink the world as if it were a real space. When applied to practice-led research, this reconceptualization challenges the creative researcher to consider creative research as a contiguous space – a topology where thinking and making are not dichotomous points but inflections in an amorphous and dynamic field. Instead of being subject to the vertical tension between earth and air, a topology of practice emphasizes its encapsulated, undulating reality – an agentive ‘object’ formed according to properties of connectedness, movement and differentiation. Taking the central ideas of Quentin Meillassoux and Graham Harman as a point of departure, this paper will provide a speculative account of the interplay of spatialities that characterise the author’s studio practice. In so doing, the paper will model the innovative methodological potential produced by the analysis of topological dimensions of the studio and the way they can be said to move beyond the ‘geo-critical’ divide.

Faster Algorithms for Incremental Topological Ordering.Robert Tarjan

We present two online algorithms for maintaining a topological order of a directed acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm takes O(m 1/2) amortized time per arc and our second algorithm takes O(n 2.5/m) amortized time per arc, where n is the number of vertices and m is the total number of arcs. For sparse graphs, our O(m 1/2) bound improves the best previous bound by a factor of logn and is tight to within a constant factor for a natural class of algorithms that includes all the existing ones. Our main insight is that the two-way search method of previous algorithms does not require an ordered search, but can be more general, allowing us to avoid the use of heaps (priority queues). Instead, the deterministic version of our algorithm uses (approximate) median-finding; the randomized version of our algorithm uses uniform random sampling. For dense graphs, our O(n 2.5/m) bound improves the best previously published bound by a factor of n 1/4 and a recent bound obtained independently of our work by a factor of logn. Our main insight is that graph search is wasteful when the graph is dense and can be avoided by searching the topological order space instead. Our algorithms extend to the maintenance of strong components, in the same asymptotic time bounds.

Growth of Space Ordered on GaAs（100） Vicinal 1.3μm InAs Quantum Dots Substrates by MOCVD

Space ordered 1.3μm self-assembled InAs QDs are grown on GaAs（100） vicinal substrates by MOCVD. Photoluminescence measurements show that the dots on vicinal substrates have a much higher PL intensity and a narrower FWHM than those of dots on exact substrates, which indicates better material quality. To obtain 1.3μm emissions of InAs QDs, the role of the so called InGaAs strain cap layer （SCL） and the strain buffer layer （SBL） in the strain relaxation process in quantum dots is studied. While the use of SBL results only in a small change of emission wavelength,SCL can extend the QD＇s emission over 1.3μm due to the effective strain reducing effect of SCL.

Quantum simulation of a topological Mott insulator with Rydberg atoms in a Lieb lattice

We propose a realistic scheme to quantum simulate the so-far experimentally unobserved topological Mott insulator phase-an interaction-driven topological insulator-using cold atoms in an optical Lieb lattice. To this end, we study a system of spinless fermions in a Lieb lattice, exhibiting repulsive nearest-and next-to-nearest-neighbor interactions and derive the associated zero-temperature phase diagram within mean-field approximation. In particular, we analyze how the interactions can dynamically generate a charge density wave ordered, a nematic, and a topologically nontrivial quantum anomalous Hall phase. We characterize the topology of the different phases by the Chern number and discuss the possibility of phase coexistence. Based on the identified phases, we propose a realistic implementation of this model using cold Rydberg-dressed atoms in an optical lattice. The scheme, which allows one to access, in particular, the topological Mott insulator phase, robustly and independently of its exact position in parameter space, merely requires global, always-on off-resonant laser coupling to Rydberg states and is feasible with state-of-the-art experimental techniques that have already been demonstrated in the laboratory.

Summarizing level-two topological relations in large spatial datasets

Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this article, we present several novel techniques to effectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important level-two topological relations: contains, contained, overlap, and disjoint. We first present a novel framework to construct a multiscale Euler histogram in 2D space with the guarantee of the exact summarization results for aligned windows in constant time. To minimize the storage space in such a multiscale Euler histogram, an approximate algorithm with the approximate ratio 19/12 is presented, while the problem is shown NP-hard generally. To conform to a limited storage space where a multiscale histogram may be allowed to have only k Euler histograms, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy in approximately summarizing aligned windows. Then, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. We also investigate the problem of nonaligned windows and the problem of effectively partitioning the data space to support nonaligned window queries. Finally, we extend our techniques to 3D space. Our extensive experiments against both synthetic and real world datasets demonstrate that the approximate multiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost efficiency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for many popular real datasets.

Multiscale histograms: Summarizing topological relations in large spatial datasets

Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this paper, we present several novel techniques to eectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important topological relations: contains, contained, overlap, and disjoint. We rst present a novel framework to construct a multiscale histogram composed of multiple Euler histograms with the guarantee of the exact summarization results for aligned windows in constant time. Then we present an approximate algorithm, with the approximate ratio 19/12, to minimize the storage spaces of such multiscale Euler histograms, although the problem is generally NP-hard. To conform to a limited storage space where only k Euler histograms are allowed, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy. Finally, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. Our extensive experiments against both synthetic and real world datasets demonstrated that the approximate mul- tiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost effciency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for the real datasets.

The non-existence of a universal topological type space

The concept of types was introduced by Harsányi[8]. In the literature there are two approaches for formalizing types, type spaces: the purely measurable and the topological models. In the former framework Heifetz and Samet [11] showed that the universal type space exists and later Meier[13] proved that it is complete. In this paper we examine the topological approach and conclude that there is no universal topological type space in the category of topological type spaces.

Discussions in space

In-place digital augmentation enhances the experience of physical spaces through digital technologies that are directly accessible within that space. This can take place in many forms and ways, e.g., through location-aware applications running on the individuals’ portable devices, such as smart phones, or through large static devices, such as public displays, which are located within the augmented space and accessible by everyone. The hypothesis of this study is that in-place digital augmentation, in the context of civic participation, where citizens collaboratively aim at making their community or city a better place, offers significant new benefits, because it allows access to services or information that are currently inaccessible to urban dwellers where and when they are needed: in place. This paper describes our work in progress deploying a public screen to promote civic issues in public, urban spaces, and to encourage public feedback and discourse via mobile phones.

Robot navigation in sensor space

This thesis investigates the problem of robot navigation using only landmark bearings. The proposed system allows a robot to move to a ground target location specified by the sensor values observed at this ground target posi- tion. The control actions are computed based on the difference between the current landmark bearings and the target landmark bearings. No Cartesian coordinates with respect to the ground are computed by the control system. The robot navigates using solely information from the bearing sensor space. Most existing robot navigation systems require a ground frame (2D Cartesian coordinate system) in order to navigate from a ground point A to a ground point B. The commonly used sensors such as laser range scanner, sonar, infrared, and vision do not directly provide the 2D ground coordi- nates of the robot. The existing systems use the sensor measurements to localise the robot with respect to a map, a set of 2D coordinates of the objects of interest. It is more natural to navigate between the points in the sensor space corresponding to A and B without requiring the Cartesian map and the localisation process. Research on animals has revealed how insects are able to exploit very limited computational and memory resources to successfully navigate to a desired destination without computing Cartesian positions. For example, a honeybee balances the left and right optical flows to navigate in a nar- row corridor. Unlike many other ants, Cataglyphis bicolor does not secrete pheromone trails in order to find its way home but instead uses the sun as a compass to keep track of its home direction vector. The home vector can be inaccurate, so the ant also uses landmark recognition. More precisely, it takes snapshots and compass headings of some landmarks. To return home, the ant tries to line up the landmarks exactly as they were before it started wandering. This thesis introduces a navigation method based on reflex actions in sensor space. The sensor vector is made of the bearings of some landmarks, and the reflex action is a gradient descent with respect to the distance in sensor space between the current sensor vector and the target sensor vec- tor. Our theoretical analysis shows that except for some fully characterized pathological cases, any point is reachable from any other point by reflex action in the bearing sensor space provided the environment contains three landmarks and is free of obstacles. The trajectories of a robot using reflex navigation, like other image- based visual control strategies, do not correspond necessarily to the shortest paths on the ground, because the sensor error is minimized, not the moving distance on the ground. However, we show that the use of a sequence of waypoints in sensor space can address this problem. In order to identify relevant waypoints, we train a Self Organising Map (SOM) from a set of observations uniformly distributed with respect to the ground. This SOM provides a sense of location to the robot, and allows a form of path planning in sensor space. The navigation proposed system is analysed theoretically, and evaluated both in simulation and with experiments on a real robot.

Using incomplete online metric maps for topological exploration with the Gap Navigation Tree

This paper presents a general, global approach to the problem of robot exploration, utilizing a topological data structure to guide an underlying Simultaneous Localization and Mapping (SLAM) process. A Gap Navigation Tree (GNT) is used to motivate global target selection and occluded regions of the environment (called “gaps”) are tracked probabilistically. The process of map construction and the motion of the vehicle alters both the shape and location of these regions. The use of online mapping is shown to reduce the difficulties in implementing the GNT.