Boundaries and Topological Algorithms

This thesis develops a model for the topological structure of situations. In this model, the topological structure of space is altered by the presence or absence of boundaries, such as those at the edges of objects. This allows the intuitive meaning of topological concepts such as region connectivity, function continuity, and preservation of topological structure to be modeled using the standard mathematical definitions. The thesis shows that these concepts are important in a wide range of artificial intelligence problems, including low-level vision, high-level vision, natural language semantics, and high-level reasoning.

From Genetic Algorithms to Efficient Organization

The work described in this thesis began as an inquiry into the nature and use of optimization programs based on "genetic algorithms." That inquiry led, eventually, to three powerful heuristics that are broadly applicable in gradient-ascent programs: First, remember the locations of local maxima and restart the optimization program at a place distant from previously located local maxima. Second, adjust the size of probing steps to suit the local nature of the terrain, shrinking when probes do poorly and growing when probes do well. And third, keep track of the directions of recent successes, so as to probe preferentially in the direction of most rapid ascent. These algorithms lie at the core of a novel optimization program that illustrates the power to be had from deploying them together. The efficacy of this program is demonstrated on several test problems selected from a variety of fields, including De Jong's famous test-problem suite, the traveling salesman problem, the problem of coordinate registration for image guided surgery, the energy minimization problem for determining the shape of organic molecules, and the problem of assessing the structure of sedimentary deposits using seismic data.

On the Convergence of Stochastic Iterative Dynamic Programming Algorithms

Recent developments in the area of reinforcement learning have yielded a number of new algorithms for the prediction and control of Markovian environments. These algorithms, including the TD(lambda) algorithm of Sutton (1988) and the Q-learning algorithm of Watkins (1989), can be motivated heuristically as approximations to dynamic programming (DP). In this paper we provide a rigorous proof of convergence of these DP-based learning algorithms by relating them to the powerful techniques of stochastic approximation theory via a new convergence theorem. The theorem establishes a general class of convergent algorithms to which both TD(lambda) and Q-learning belong.

Scaling algorithms for distributed max flow

Bibliography: p. 22-24.

The Influence of Adjacent Segment on the Reliability of Cu Dual Damascene Interconnects

Three terminal ‘dotted-I’ interconnect structures, with vias at both ends and an additional via in the middle, were tested under various test conditions. Mortalities (failures) were found in right segments with jL value as low as 1250 A/cm, and the mortality of a dotted-I segment is dependent on the direction and magnitude of the current in the adjacent segment. Some mortalities were also found in the right segments under a test condition where no failure was expected. Cu extrusion along the delaminated Cu/Si₃N₄ interface near the central via region was believed to cause the unexpected failures. From the time-to-failure (TTF), it is possible to quantify the Cu/Si₃N₄ interfacial strength and bonding energy. Hence, the demonstrated test methodology can be used to investigate the integrity of the Cu dual damascene processes. As conventionally determined critical jL values in two-terminal via-terminated lines cannot be directly applied to interconnects with branched segments, this also serves as a good methodology to identify the critical effective jL values for immortality.