Search

This work seeks to develop (lower) performance bounds for a traffic scheduling problem that arises in many application contexts, ranging from industrial material handling and robotics to computer game animations and quantum computing. In a first approach, the sought bounds are obtained by applying the Lagrangian relaxation method to a MIP formulation of the considered scheduling problem that is based on a natural notion of “state” for the underlying traffic system and an analytical characterization of all the possible trajectories of this state over a predefined time horizon. But it is also shown that the corresponding “dual” problem that provides these bounds, can be transformed to a linear program (LP) with numbers of variables and constraints polynomially related to the size of the underlying traffic system and the employed time horizon in the MIP formulation. Furthermore, the derived LP formulation constitutes the LP relaxation of a second MIP formulation for the considered scheduling problem that can be obtained through an existing connection between this problem and the “integral multi-commodity flow” (IMCF) model of network optimization theory. Finally, the theoretical developments of the paper are complemented with a computational part that demonstrates the efficacy of the pursued methods in terms of the quality of the derived bounds, and their computational tractability.

This paper presents a heuristic algorithm for minimizing the makespan required to route a set of agents inhabiting a shared guidepath network from their initial locations to their respective destinations while observing a set of regulations that seek to ensure the safety and the integrity of the generated traffic. From an application standpoint, the presented developments are motivated by the traffic coordination challenges that arise in the context of many automated unit-load material handling systems and also in the transport of the ionized atoms that takes place in the context of quantum computing. From a methodological standpoint, our developments constitute a customization of the general “local-search” framework of combinatorial optimization theory to the traffic management problem that is considered in this paper. Hence, the presented results include a rigorous characterization of the considered problem and its solution space, detailed algorithms for the construction of the necessary initial solutions and the improving step for the pursued search, a complexity analysis of these algorithms, and a set of computational experiments that reveal and assess the computational efficiency of the presented algorithms and the efficacy of the derived solutions. The paper concludes with some suggestions for potential extensions of the presented results. Note to Practitioners —In many contemporary applications of automation science and engineering, a number of entities—or “agents”—must be transported expediently from their initial locations to certain destinations using a set of links that define the underlying “guidepath network.” Furthermore, various safety considerations require that the agents must be adequately separated during these transports, and the imposed restrictions turn the corresponding traffic coordination problem into a complex resource allocation problem, where the contested resources are the guidepath-network links. This paper presents a set of algorithms that can provide high-quality schedules for the resulting traffic-scheduling problems in a computationally efficient manner. These properties of our algorithms are established through the necessary theoretical analysis, but they are also demonstrated through a series of numerical experiments where they are shown capable to provide near-optimal solutions for some very complex problem instances in no more than a few seconds. In addition, our algorithms are “complete,” i.e., they will always provide a feasible schedule for any instantiation of the traffic-scheduling problem considered in this paper. Hence, they can effectively address the needs for “real-time” traffic management that arise in the context of the considered applications.

We study the Quantum Approximate Optimization Algorithm ( QAOA ) in the context of the Max-Cut problem. Noisy quantum devices are only able to accurately execute QAOA at low circuit depths, while classically-challenging problem instances may call for a relatively high circuit-depth. This is due to the need to build correlations between reachable pairs of vertices in potentially large graphs [ 16 ]. To enhance the solving power of low-depth QAOA, we introduce a classical pre-processing step that initializes QAOA with a biased superposition of possible cuts in the graph, referred to as a warm-start . In particular, we initialize QAOA with a solution to a low-rank semidefinite programming relaxation of the Max-Cut problem. Our experimental results show that this variant of QAOA , called QAOA-warm , is able to outperform standard QAOA on lower circuit depths in solution quality and training time. While this improvement is partly due to the classical warm-start, we find strong evidence of further improvement using QAOA circuit at small depth. We provide experimental evidence of improved performance as well as theoretical properties of the proposed framework.

Unique tags are often added to items to prevent counterfeiting and tampering. While there are many techniques for generating unique patterns, tags that are inexpensive, scalable, easy to read, and difficult to replicate are particularly useful for tracking applications. In this work, we present a novel tagging concept that utilizes self-assembly methods to create physically unclonable patterns using magnetic particles. By combining a distribution of Nd-Fe-B magnetic particles with a hard polymer inside a strong magnetic field, patterns are generated that are easily read using magneto-optic techniques. Image processing and template matching techniques are then used to determine the likelihood that two different magnetic tags are classified as the same. For optimal selections of particle percent mass, statistical analysis predicts that pattern matching yields at most one false positive for every 1015 true positives. Results further illustrate that variations in particle size and particle percent mass have a strong effect on the predicted pattern uniqueness. Finally, a magnetic field model was then used to help predict broad trends in pattern statistics and particle structures. This paper shows that magnetic self-assembly patterns hold promise as unique embedded tags for a large range of applications from microelectronics to luxury goods to low-cost off-the-shelf items.

This paper describes a heuristic algorithm for minimizing the makespan required to route a set of agents inhabiting a shared guidepath network from their initial locations to their respective destinations. The work is motivated by the operations taking place in the context of some unit-load material handling systems, like the zone-controlled AGV systems, and in quantum computers. This document presents a description of the considered problem and of the inner workings of the proposed algorithm, a complexity analysis of this algorithm, and a set of computational results that reveal the efficacy of the derived solutions. The paper concludes with some directions for future research on the considered problem and the further development of the presented results.

Recent work in the development of glass-ceramic scintillators at the Georgia Tech Research Institute (GTRI) has focused on modifying formulation of the oxide host glass and scintillating crystal phase, secondary heat treatment (ceramization) schedule, and processing improvement to ensure optical quality. These efforts have yielded considerable performance improvements to glass-ceramic scintillators, and have made them among the most promising composite scintillators under investigation. However, these materials still fall short of current commercially-available single crystal scintillators, and so new avenues must be pursued for continued improvements. The present investigation uses predictive simulations to inform the materials selection and process design for high refractive index layers to improve light extraction from the scintillator, and increased light output via bulk or surface plasmon interactions.

In a series of recent publications, we have addressed a class of traffic coordination problems that can be formulated as combinatorial scheduling problems, and we have developed a Lagrangian duality approach for obtaining (i) strong lower bounds for the corresponding optimal solution, and (ii) potential “seeds” for the construction of feasible, near-optimal solutions to these problems. In those past works, the corresponding “dual” problem was solved through a customized dual-ascent algorithm that took advantage of a distributed representation of the sub-differentials of the underlying “dual” function in order to compute efficiently ascending directions during the optimization process. In this paper we show that the fundamental insights that led to the aforementioned past developments, can also enable an efficient linear programming formulation for the considered “dual” problem.1

The field of quantum information processing is rapidly advancing. As the control of quantum systems approaches the level needed for useful computation, the physical hardware underlying the quantum systems is becoming increasingly complex. It is already becoming impractical to manually code control for the larger hardware implementations. In this chapter, we will employ an approach to the problem of system control that parallels compiler design for a classical computer. We will start with a candidate quantum computing technology, the surface electrode ion trap, and build a system instruction language which can be generated from a simple machine-independent programming language via compilation. We incorporate compile time generation of ion routing that separates the algorithm description from the physical geometry of the hardware. Extending this approach to automatic routing at run time allows for automated initialization of qubit number and placement and additionally allows for automated recovery after catastrophic events such as qubit loss. To show that these systems can handle real hardware, we present a simple demonstration system that routes two ions around a multi-zone ion trap and handles ion loss and ion placement. While we will mainly use examples from transport-based ion trap quantum computing, many of the issues and solutions are applicable to other architectures.

We consider a class of scheduling problems that concern the routing of a set of mobile agents over the edges of an underlying guidepath network. These problems are motivated by (i) the operations of some unit-load, automated material handling systems that are employed in many contemporary production and distribution facilities, and also by (ii) the operations that take place in the physical layouts implementing the elementary logical operations that are employed in quantum computing. The presented results include (a) a systematic formulation of the considered scheduling problems as mixed integer programs (MIPs), (b) a Lagrangian relaxation of these MIP formulations, and (c) the development of a customized dual-ascent algorithm for the systematic and expedient solution of the corresponding dual problem. The latter provides lower bounds for the original MIP formulations and potentially useful information for the construction of near-optimal routing schedules for the original problems.

Magnetic materials have traditionally faced several limitations for RF and power applications because of their unstable permeability with frequency and electric field. However, the same attributes of these materials, when designed at nanoscale, enable interesting nonlinear properties for applications as frequency-selective limiters and signal-to-noise enhancers. Anisotropic nanostructures also enhance frequency stability. This paper explores nanomagnetic arrays for such ultra-miniaturized RF components in multimode and multiband (MMMB) RF modules. Permalloy films and nanodot arrays were modeled for their frequency-response to assess their nonlinear properties. By designing the dimensions at nanoscale, field-dependent permeability spectra were obtained using micromagnetic simulations. Permalloy thinfilm and nanodot arrays were fabricated on silicon substrates using e-beam evaporation and e-beam nanolithography. The simulation results for blanket films were validated by characterizing the permeability spectra using strip-line structures. Results indicate that nanomagnetic films and arrays can be used to create nonlinear devices as building blocks for a variety of highly-integrated RF modules.

We schedule the Steane [[7,1,3]] error correction on a model ion trap architecture with ballistic transport. We compare the level one error rates for syndrome extraction using the Shor method of ancilla prepared in verified cat states to the DiVincenzo-Aliferis method without verification. The study examines how the quantum error correction circuit latency and error vary with the number of available ancilla and the choice of protocol for ancilla preparation and measurement. We find that with few exceptions the DiVincenzo-Aliferis method without cat state verification outperforms the standard Shor method. We also find that additional ancilla always reduces the latency but does not significantly change the error due to the high memory fidelity., Comment: 15 pages, 13 figures

Numerical simulation is used to study the linear and nonlinear effects of increasing incident power density on soft magnetic materials at the microscale. A magnetic field pulse with Gaussian time dependence and variable strength is numerically applied to a magnetic particulate in an equilibrium state. The field-dependent dynamic susceptibility (M/H) is calculated from the Fourier transform of the magnetization response. Calculations show that as the magnitude of the excitation field exceeds a critical value, the system becomes nonlinear. At this point, the ferromagnetic resonance should become suppressed and span a wider range of frequencies. Two systems are simulated in the linear and nonlinear regimes; one system shows complete agreement with established nonlinear theory, while the other shows unusual behavior. Both systems agree with linear theory at low fields, and vanishing susceptibility at excessively high fields is observed for both.

In this paper, the threshold is defined as the volume/surface fraction at which the DC magnetic susceptibility increases dramatically and is studied using micromagnetics and experimental measurements.

DC power and radio frequency technology design can benefit from theories which predict magnetic permeability for a composite of nano-microscale magnetic particles in a magnetically neutral host. In this paper, composite permeability is calculated by connecting the microscale physics of the particles to the effective properties of the composite. At the microscale, numerical predictions are performed for a representative particle exposed to a magnetic field pulse. The simulation yields the particle's magnetic susceptibility, which is then generalized using magnetodynamics theory to obtain the susceptibility of a distribution of particles. The micro-magnetic study is extended to clusters of particles in order to study particle interactions. Effective medium theory is then used to describe the composite susceptibility of particles distributed in a neutral host.