My Travels With my A(u)nts :

Distributed Ant Robotics

"Go to the ant, thou sluggard; consider her ways, and be wise:
Which having no guide, overseer, or ruler,
Provideth her meat in the summer,
and gathereth her food in the harvest"
(Proverbs vi 6-8) 

Welcome to Israel A. Wagner's Home Page;
it's about Ants, Robots and Computation 

Keywords: Ant Robotics, VLSI, Java, Simulation 

In this page you will find abstracts, demo's and pointers to my research work in Ant-Algorithms, VLSI, and other topics,
as well as some links to other sites.

Recently updated at June 17, 2007

Contents

  1. Bio and CV
  2. New: Ant-Robotics Tutorial in IJCAI 2003
  3. Research in Ant-Robotics
    1. Publications
    2. Ph.D. thesis abstract (hebrew) (english)
    3. AMAI - From Ants to A(ge)nts - a Special Issue on Ant-Robotics
    4. Ants as Seen by Ha'aretz (hebrew)
  4. Research in VLSI
    1. VLSI Research Publications
    2. OnLine animated circuit simulator
  5. Other Research Topics
  6. On-Line Simulators
  7. Spatial Openness Tools
  8. Teaching
    1. Topics in MultiRobotics
    2. Algorithmic Aspects in VLSI Design
  9. Links to other sites you may wish to browse

Go to:
Intelligent Systems Lab
Technion CS department
Pixel Club
IBM HRL Research Seminar

Publications in Ant - Robotics

The following is a list of abstracts of my research publications.
The research in ant robotics has started in the course of my Ph.D. studies, under the supervision of Prof. Freddy Bruckstein and Dr. Micha Lindenbaum.
Generally, the topic is "Distributed Ant Robotics" which means that we borrow ideas from the world of insects, and analyze their usage in the context of multi-robot and multi-a(ge)nt systems.

  1. Row Straightening via Local Interactions


I. A. Wagner, A. M. Bruckstein,
Technical report CIS-9406, Center for Intelligent Systems, Technion, Haifa, May 1994. Circuits, Systems, and Signal Processing, Vol. 16, No. 3, 1997.

  1. Probabilistic Pursuits on the Grid


A. M. Bruckstein, C. L. Mallows, I. A. Wagner,
Technical report CIS-9411, Center for Intelligent Systems, Technion, Haifa, September 1994, revised: February 1995.
American Mathematical Monthly , Vol. 104, No. 4, April 1997, pp. 323-343.

  1. Cooperative Cleaners - a Study in Ant Robotics


I. A. Wagner, A. M. Bruckstein,
Proceedings of the 3rd French-Israeli Symposium on Robotics , Herzlia, May 1995. (A later version was presented at the 1st Online Workshop on Evolutionary Computation, Nagoya university and the WWW, October 1995.) The complete version is in: Technical report CIS-9512, Center for Intelligent Systems, Technion, Haifa, June 1995, and in A. Paulraj, V. Roychowdhury, C. D. Schaper - ed., Communications, Computation, Control, and Signal Processing: A Tribute to Thomas Kailath, Kluwer Academic Publishers, The Netherlands, 1997, pp. 289-308.

  1. Smell as a Computational Resource - a Lesson We Can Learn from the Ant


I. A. Wagner, M. Lindenbaum, A. M. Bruckstein,
Proceedings of the ISTCS'96 - 4'th Israeli Symposium on Theory of Computing and Systems, Jerusalem, June 10-11, 1996.

  1. Distributed Covering by Ant-Robots Using Evaporating Traces


I. A. Wagner, M. Lindenbaum, A. M. Bruckstein,
IEEE Trans. Rob. Aut., October 1999, Volume 15, Number 05, pp. 918-933.

  1. On-Line Graph Searching by a Smell-Oriented Vertex Process


I. A. Wagner, M. Lindenbaum, A. M. Bruckstein,
presented in: AAAI-97 Workshop on On-Line Search, July 28, 1997, Providence, Rhode Island

  1. Efficiently Searching a Graph by a Smell-Oriented Vertex Process


I. A. Wagner, M. Lindenbaum, A. M. Bruckstein,
Annals of Mathematics and Artificial Intelligence 24 (1998) pp. 211-223

  1. Robotic Exploration, Brownian Motion and Electrical Resistance


I. A. Wagner, M. Lindenbaum, A. M. Bruckstein,
to be presented in: RANDOM'98 - 2nd International workshop on Randomization and Approximation Techniques in Computer Science, Barcelona, Spain, October 1998 (LNCS #1518, Springer Verlag, pp. 116-130).

  1. Efficiently Exploring a Continuous Unknown Domain by an Ant Inspired Process


I. A. Wagner, M. Lindenbaum, A. M. Bruckstein,
to be presented in: ANTS'98 - From Ant Colonies to Artificial Ants: 1st International Workshop on Ant Colony Optimization, Brussels, Belgium, October, 1998.

  1. MAC vs. PC - Determinism and Randomness as Complementary Approaches to Robotic Exploration of Continuous Unknown Domains


I. A. Wagner, M. Lindenbaum, A. M. Bruckstein,
CIS Technical Report # CIS9814
IJRR - International Journal of Robotics Research, Volume: 19, Number: 1, January 2000, pp. 12-31.

  1. Hamiltonian(t) - An Ant-Inspired Heuristic for Recognizing Hamiltonian Graphs


I. A. Wagner, A. M. Bruckstein, Ant-Algorithms Session in CEC'99

  1. ANTS: Agents, Networks, Trees, and Subgraphs


I. A. Wagner, M. Lindenbaum, A. M. Bruckstein,
to appear in Special issue on Ant Colony Optimization in the Future Generation Computer Systems journal, North Holland (Editors: Dorigo, Di Caro and Stutzle), June 2000, Vol. 16 No. 8, pp. 915-926.
Technical Report CIS-2000-03

  1. A Distributed Ant Algorithm for Efficiently Patrolling a Network


V. M. Yanovski, I. A. Wagner, A. M. Bruckstein, Ants'2000
and CIS Technical Report CIS-2002-05

  1. "From Ants to A(ge)nts: A Special Issue on Ant-Robotics,"


I. A. Wagner, A. M. Bruckstein,  Annals of Mathematics and Artificial Intelligence, Special Issue on Ant-Robotics, 2001, Volume 31, Number 1-4, pp. 1-5.

  1. "Vertex-Ant-Walk - A robust method for efficient exploration of faulty graphs,"


V. Yanovski, I. A. Wagner, A. M. Bruckstein, Annals of Mathematics and Artificial Intelligence, Special Issue on Ant-Robotics, 2001, Volume 31, Number 1-4, pp. 99-112.

  1.  "A distributed ant algorithm for efficiently patrolling a network,"


V. Yanovski, I. A. Wagner, A. M. Bruckstein, Workshop on Interdisciplinary Applications of Graph Theory and Algorithms, April 17-18, 2001, Haifa Holiday Inn Hotel,

Algorithmica (2003) 37: 165-186.

  1. "Discrete Bee Dance Algorithms for Pattern Formation on a Grid",
    Noam Gordon, Israel A. Wagner and Alfred M. Bruckstein, Technical Report CIS-2003-03,
    to appear in Web Intelligence 2003 (WI 2003)
  2. "Gathering Multiple Robotic A(ge)nts with Limited Sensing Capabilities",
    Noam Gordon, Israel A. Wagner and Alfred M. Bruckstein,
    ANTS 2004 - Fourth International Workshop on Ant Colony Optimization and Swarm Intelligence, September 5-8, 2004, Brussels, Belgium.
    LNCS 3172

  3. "On Swarm Optimality In Dynamic And Symmetric Environments", Yaniv Altshuler, Israel A. Wagner and Alfred M. Bruckstein, ICINCO-MARS-05, 2005

  4. "The Cooperative Hunters - Efficient Cooperative Search For Smart Targets Using UAV Swarms", Yaniv Altshuler, Vladimir Yanovski, Israel A. Wagner and Alfred M. Bruckstein, ICINCO-MARS-05, 2005

  5. "Swarm Robotics for a Dynamic Cleaning Problem", Y. Altshuler, A.M. Bruckstein, I.A. Wagner, IEEE Swarm Intelligence Symposium, 2005
  6. “A Linear-Time Constant-Space Algorithm for the Boundary Fill Problem”, V. M. Yanovsky, I. A. Wagner and A. M. Bruckstein, The Computer Journal.2007; 0: bxm004v1-5
  7. “Robust and Efficient Covering of Unknown Continuous Domains with Simple, Ant-Like A(ge)nts”,  E. Osherovich, V. Yanovski, I. A. Wagner and A. M.  Bruckstein, BISFAI 2007, Ramat-Gan, Israel

 

·  Back to List of contents 

 

Abstracts

Row Straightening via Local Interactions

  1. Authors:
    1. Israel A. Wagner - CS Dept., Technion.
    2. Alfred M. Bruckstein - CS Dept., Technion.
  2. "row.pdf"-Full version in a PDF file
  3. Abstract: A number of agents can arrange themselves equidistantly in a row via a sequence of adjustments, based on a simple ``local'' interaction. The convergence of the configuration to the desired one is exponentially fast. A similarity is shown between this phenomenon and the dynamics of pulse propagation along a distributed RC line, and a conjecture is made concerning the evolution of a similar system with a probabilistic rule of behavior.
  4. Evolution of the row straightening process
  5. Technical report CIS-9406, Center for Intelligent Systems, Technion, Haifa, May 1994. Accepted for publication in Circuits, Systems, and Signal Processing .
  6. Keywords: curve evolution, matrix eigenstructure, multiagent systems, VLSI interconnects.

Back to List of contents

Probabilistic Pursuits on the Grid

  1. Authors:
    1. Alfred M. Bruckstein - CS Dept., Technion, Haifa 32000, Israel
    2. Colin L. Mallows - Statistics Research Department, AT&T Bell Labs, Murray Hill, NJ 07974,USA
    3. Israel A. Wagner
  2. "brw.pdf"-Full version in a PDF file
  3. Abstract: It has recently been shown that the paths of a sequence of a(ge)nts engaged in a chain of continuous pursuits converge to the straight line between the origin and destination. We prove that a similar result holds for a discrete probabilistic pursuit model of pursuit on the integer grid. This model of pursuit leads to interesting results also in the context of linear and cyclic pursuits.
  4. Cyclic probabilistic pursuit
  5. American Mathematical Monthly , Vol. 104, No. 4, April 1997, pp. 323-343.
  6. Keywords: ant pursuit, probabilistic motion, biased random walk.

Back to List of contents

Cooperative Cleaners - a Study in Ant Robotics

  1. Authors:
    1. Israel A. Wagner - CS Dept., Technion
    2. Alfred M. Bruckstein - CS Dept., Technion
  2. "dr.pdf"-Full version in a PDF file
  3. Abstract: In the world of living creatures, ``simple minded'' animals often cooperate to achieve common goals with amazing performance. One can consider this idea in the context of robotics, and suggest models for programming goal-oriented evolutionary behavior into the members of a group of simple robots lacking global supervision. This can be done by controlling the local interactions between the robot agents, to have them jointly carry out a given mission. As a test case we analyze the problem of many simple robots cooperating to clean the dirty floor of a non-convex region over the integer grid, using the dirt on the floor as the main means of inter-robot communication.
  4. Proceedings of the 3rd French-Israeli Symposium on Robotics , Herzlia, May 1995. (A later version was presented at the 1st Online Workshop on Evolutionary Computation, Nagoya university and the WWW, October 1995.) The complete version is in: Technical report CIS-9512, Center for Intelligent Systems, Technion, Haifa, June 1995 , and in A. Paulraj, V. Roychowdhury, C. D. Schaper - ed., Communications, Computation, Control, and Signal Processing: A Tribute to Thomas Kailath, Kluwer Academic Publishers, The Netherlands, 1997 , pp. 289-308.
  5. Cooperative cleaners example
  6. Keywords: multiagent systems, distributed robotics, robotic cleaning.

Back to List of contents

Smell as a Computational Resource - a Lesson We Can Learn from the Ant

  1. Authors:
    1. Israel A. Wagner - IBM HRL and CS Dept., Technion
    2. Micha Lindenbaum - CS Dept., Technion
    3. Alfred M. Bruckstein - CS Dept., Technion
  2. "rc.pdf"-Full version in a PDF file
  3. Abstract: Some insects are known to use chemicals called pheromones for various communication and coordination tasks. We investigate the ability of a group of robots, that communicate by leaving traces, to perform the task of cleaning the floor of an un-mapped building, or any task that requires the traversal of an unknown, dynamic network.
  4. Proceedings of the ISTCS'96 - 4'th Israeli Symposium on Theory of Computing and Systems, Jerusalem, June 10-11, 1996.

Back to List of contents

Distributed Covering by Ant-Robots Using Evaporating Traces

  1. Authors:
    1. Israel A. Wagner - IBM HRL and CS Dept., Technion
    2. Micha Lindenbaum - CS Dept., Technion
    3. Alfred M. Bruckstein - CS Dept., Technion
  2. "tra_oct99.pdf"-Full version in PDF
  3. Abstract: Ants and other insects are known to use chemicals called pheromones for various communication and coordination tasks. In this paper we investigate the ability of a group of robots, that communicate by leaving traces, to perform the task of cleaning the floor of an un-mapped building, or any task that requires the traversal of an unknown region. More specifically, we consider robots which leave chemical odor traces that evaporate with time, and are able to evaluate the strength of smell at every point they reach, with some measurement error. Our abstract model is a decentralized multia(ge)nt adaptive system with a shared memory, moving on a graph whose vertices are the floor-tiles. We describe three methods of covering a graph in a distributed fashion, using smell traces that gradually vanish with time, and show that they all result in eventual task completion, two of them in a time polynomial in the number of tiles. As opposed to existing traversal methods (e.g. Depth First Search), our algorithms are adaptive: they will complete the traversal of the graph even if some of the a(ge)nts die or the graph changes (edges/vertices added or deleted) during the execution, as long as the graph stays connected. Another advantage of our agent interaction processes is the ability of agents to use noisy information at the cost of longer cover time.
  4. IEEE Transactions on Robotics and Automation October 1999, Volume 15, Number 5, pp. 918-933.

Back to List of contents

On-Line Graph Searching by a Smell-Oriented Vertex Process

  1. Authors:
    1. Israel A. Wagner - IBM HRL and CS Dept., Technion
    2. Micha Lindenbaum - CS Dept., Technion
    3. Alfred M. Bruckstein - CS Dept., Technion
  2. "vaw.pdf"-Full version in a PDF file
  3. Abstract: An ant walks along the edges of a graph G, occasionally leaving pheromone traces at vertices, and using those traces to guide its exploration. We show that the ant can cover the graph within time O(ND) where N is the number of vertices and D the diameter of G. The use of traces achieves a trade-off between random and self-avoiding walks, as it can give lower priority to already visited neighbors. A Hamiltonian cycle in G, if one exists, is a limit cycle of the smell directed graph exploration process.
  4. Annals of Mathematics and Artificial Intelligence 24 (1998) pp. 211-223


also presented in: AAAI-97 Workshop on On-Line Search, July 28, 1997, Providence, Rhode Island

  1. Keywords: on-line, graph search, covering, hamiltonian cycle, ant robotics.

Back to List of contents

Robotic Exploration, Brownian Motion and Electrical Resistance

  1. Authors:
    1. Israel A. Wagner - IBM HRL and CS Dept., Technion
    2. Micha Lindenbaum - CS Dept., Technion
    3. Alfred M. Bruckstein - CS Dept., Technion
  2. "pc_short.pdf"-Extended abstract in a PDF file
  3. Abstract: A random method for exploring a continuous unknown planar domain with almost no sensors is described. The expected cover time is shown to be proportional to the electrical resistance of the domain, thus extending a famous result for graphs (Chandra et. al. 89). An upper bound on the variance is also shown, and some open questions are suggested for further research.
  4. to be presented in: RANDOM'98 - 2nd International workshop on Randomization and Approximation Techniques in Computer Science, Barcelona, Spain, October 1998 (LNCS #1518, Springer Verlag, pp. 116-130).
  5. Keywords: robotic exploration, cover time, Brownian motion, sheet resistance

Back to List of contents

Efficiently Exploring a Continuous Unknown Domain by an Ant Inspired Process

  1. Authors:
    1. Israel A. Wagner - IBM HRL and CS Dept., Technion
    2. Micha Lindenbaum - CS Dept., Technion
    3. Alfred M. Bruckstein - CS Dept., Technion
  2. "mac_short.pdf"-Extended abstract in a PDF file
  3. Abstract: An ant-inspired method is described for exploring a continuous unknown planar region by a group of robots having limited sensors and no explicit communication. Such a method has applications in robotics where a robot with limited sensing capabilities but with the ability to leave marks on the ground has to cover a closed region for purposes of cleaning a dirty floor, painting a wall, or demining a mine-field. We formalize the problem and suggest the "mark and cover" (MAC) rule of motion to solve it using temporary markers (``pheromones'') as means of navigation and indirect communication. The convergence of the algorithm is proved, and its cover time is shown to be the asymptotically optimal O(A/a), A being the total area and a - the area covered by the robot in a single step.
  4. to be presented in: ANTS'98 - From Ant Colonies to Artificial Ants: 1st International Workshop on Ant Colony Optimization}, Brussels, Belgium, October, 1998.

Back to List of contents

MAC vs. PC - Determinism and Randomness as Complementary Approaches to Robotic Exploration of Continuous Unknown Domains

  1. Authors:
    1. Israel A. Wagner - IBM HRL and CS Dept., Technion
    2. Micha Lindenbaum - CS Dept., Technion
    3. Alfred M. Bruckstein - CS Dept., Technion
  2. "mac_ijrr.pdf"- PDF file
  3. Abstract: Two methods are described for exploring a continuous unknown planar region by a group of robots having limited sensors and no explicit communication. We formalize the problem and show a lower bound on the length of any solution. A deterministic "mark and cover" (MAC) algorithm is then described to solve the problem using short-lived navigational markers as means of navigation and indirect communication. The convergence of the algorithm is proved, and its cover time is shown to be the asymptotically optimal O(A/a), A being the total area and a - the area covered by the robot in a single step. The MAC algorithm is tested against an alternative randomized "probabilistic covering" (PC) method, which does not rely on sensors but is still able to cover an unknown region in an expected time that depends polynomially on the dimensions of the region. Both algorithms enable cooperation of several robots to achieve faster covergae. Finally we show that the two methods can be combined to yield a third, hybrid algorithm with a better tradeoff between performance and robustness.
  4. snapshots from the MAC-PC simulator:


  1. CIS Technical Report # CIS9814

Back to List of contents

Efficiently Exploring a Continuous Unknown Domain by an Ant Inspired Process

  1. Authors:
    1. Israel A. Wagner - IBM HRL and CS Dept., Technion
    2. Micha Lindenbaum - CS Dept., Technion
    3. Alfred M. Bruckstein - CS Dept., Technion
  2. "mac_short.pdf"-Extended abstract in a PDF file
  3. Abstract: An ant-inspired method is described for exploring a continuous unknown planar region by a group of robots having limited sensors and no explicit communication. Such a method has applications in robotics where a robot with limited sensing capabilities but with the ability to leave marks on the ground has to cover a closed region for purposes of cleaning a dirty floor, painting a wall, or demining a mine-field. We formalize the problem and suggest the "mark and cover" (MAC) rule of motion to solve it using temporary markers (``pheromones'') as means of navigation and indirect communication. The convergence of the algorithm is proved, and its cover time is shown to be the asymptotically optimal O(A/a), A being the total area and a - the area covered by the robot in a single step.
  4. to be presented in: ANTS'98 - From Ant Colonies to Artificial Ants: 1st International Workshop on Ant Colony Optimization}, Brussels, Belgium, October, 1998.

Back to List of contents

Hamiltonian(t) - An Ant-Inspired Heuristic for Recognizing Hamiltonian Graphs

  1. Authors:
    1. Israel A. Wagner - IBM HRL and CS Dept., Technion
    2. Alfred M. Bruckstein - CS Dept., Technion
  2. "ham.pdf"-Extended abstract in a PDF file
  3. Abstract: Given a graph G(V,E), we consider the problem of deciding whether G is Hamiltonian, that is - whether or not there is a simple cycle in E spanning all vertices in V. This problem is known to be NP-complete, hence cannot be solved in time polynomial in |V| unless P=NP. The problem is a special case of the Travelling Salesperson Problem (TSP), that was extensively studied in the literature, and has recently been attacked by various ant-colony methods. We address the Hamiltonian cycle problem using a new ant-inspired approach, based on repeated covering of the graph. Our method is based on a process in which an ant traverses the graph by moving from vertex to vertex along the edges while leaving traces in the vertices, and deciding on the next step according to the level of traces in the surrounding neighborhood. We show that Hamiltonian cycles are limit cycles of the process, and investigate the average time needed by our ant process to recognize a Hamiltonian graph, on the basis of simulations made over large samples of random graphs with varying density of edges.
  4. to be presented in: Ant-Algorithms Session in CEC'99
  5. Keywords: hamiltonian cycle, ant algorithms

Back to List of contents

ANTS: Agents, Networks, Trees, and Subgraphs

  1. Authors:
    1. Israel A. Wagner - IBM HRL and CS Dept., Technion
    2. Micha Lindenbaum - CS Dept., Technion
    3. Alfred M. Bruckstein - CS Dept., Technion
  2. "aw.pdf"- PDF file
  3. Abstract: Efficient exploration of large networks is a central issue in data mining and network maintenance applications. In most existing work there is a distinction between the active ``searcher'' which both executes the algorithm and holds the memory and the passive ``searched graph'' over which the searcher has no control at all. Large dynamic networks like the Internet, where the nodes are powerful computers and the links have narrow bandwidth and are heavily-loaded, call for a different paradigm, in which a non-centralized group of one or more lightweight autonomous agents traverse the network in a completely distributed and parallelizable way. Potential advantages of such a paradigm would be fault tolerance against network and agent failures, and reduced load on the busy nodes due to the small amount of memory and computing resources required by the agent in each node. Algorithms for network covering based on this paradigm could be used in today's Internet as a support for data mining and network control algorithms. Recently, a "Vertex Ant Walk" (VAW) method has been suggested for searching an undirected, connected graph by an a(ge)nt that walks along the edges of the graph, occasionally leaving ``pheromone'' traces at nodes, and using those traces to guide its exploration. It was shown there that the ant can cover a static graph within time nd where n is the number of vertices and $d$ the diameter of the graph. In this work we further investigate the performance of the VAW method on dynamic graphs, where edges may appear or disappear during the search process. In particular we prove that


(a) if a certain spanning subgraph S is stable during the period of covering, then the VAW method is guaranteed to cover the graph within time nd_{s}, where d_{s} is the diameter of S, and
(b) if a failure occurs on each edge with probability p, then the expected cover time is bounded from above by nd[(log D / log (1/p)) + (1+p^2)/(1-p)], where D is the maximum vertex-degree in G. We also show that
(c) if G is a static tree then it is covered within time 2n.
to appear in Special issue on Ant Colony Optimization in the Future Generation Computer Systems journal, North Holland (Editor M. Dorigo)

Back to List of contents

A distributed ant algorithm for efficiently patrolling a network

  1. Authors:
    1. Vladimir M. Yanovski - CS Dept., Technion
    2. Israel A. Wagner - IBM HRL and CS Dept., Technion
    3. Alfred M. Bruckstein - CS Dept., Technion
  2. "eaw.pdf" - PDF file
  3. Abstract:  We consider the problem of patrolling - i.e. ongoing exploration of a network by a decentralized group of simple  memoryless robotic agents. The model for the network is an undirected graph,  and our goal, beyond complete exploration, is to achieve close to uniform frequency of traversal of the graph's edges.


A simple multi-agent exploration algorithm is presented and analyzed. It is shown that a single agent following this procedure enters, after a transient period, a periodic motion which is an extended Eulerian cycle, during which all edges are traversed an identical number of times. We further prove that if the network is Eulerian, a single agent goes into an Eulerian cycle within 2ED steps, E being the number of edges in the graph and D - its diameter. For a team of k agents, we show that after at most 2(1 + 1/k)ED steps the numbers of edge visits in the network are balanced up to a factor of two. In addition, various aspects of the algorithm are demonstrated by simulations.

  1. A preliminary version presented in: Ants'2000

A journal article:  Algorithmica (2003) 37: 165-186.

  1. Keywords: Euler cycle, ant algorithms, decentralized network search

Back to List of contents

Robotics Projects

 


MAC (Mark And Cover)

 


Ant-Like Covering with Evaporating Traces

 

Back to List of contents

Simulators (JAVA and PostScript)

 


Vertex-Ant-Walk (Java)


MAC, PC and other gadgets (Java)


An Animated PostScript Demo (PostScript) 


Hamiltonian(t) Simulation (Java) by Sharon Salmon & Amir Shneider


Ant Pursuits (Java) by Tamir Heyman & Tzach Leviatan


Patrolling Ants for Network (PAN) (Java) by Mark Matusevich & Vladimir Yanovski
(part of the AntWorks project) 


 


SpatialOpenness 1 (with Dafna Gewirtzman)
Project 1: (Java + VRML Applet, programmed by Ido Zelman and Yifat Zinger)


SpatialOpenness 2  (with Dafna Gewirtzman)
Project 2: (MATLAB, refined properties, programmed by Dimitry Batenkov and Ben Riva)


Animated Circuit Simulation (Java, programmed by Leonid Kleyman and Evgeny Skarbovsky in VLSI Lab)
>>> NEW VERSION (April 2001) WITH NEW FEATURES <<<

 


Jcookies - using cookies to save/load data within a JAVA applet (by Amit Caspi & Yoav Zur)


Zero-Space Boundary Filling Applet (by V. Yanovsky)


Back to List of contents

Publications in VLSI related topics:

  1. An Efficient Algorithm for Some MultiRow Layout Problems


J. A. Feldman, I. A. Wagner, S. Wimer,
IEEE Transactions on CAD, August 93.

  1. An Interactive VLSI CAD Tool for Yield Estimation


I. A. Wagner, I. Koren,
IEEE Transactions on Semiconductor Manufacturing, MAY 1995, pp. 130-138.

  1. The Effect of Spot Defects on the Parametric Yield of Long Interconnection Lines


I. A. Wagner, I. Koren,
Proceedings of DFT95 - International Workshop on Defect and Fault Tolerance in VLSI Systems , Lafayette, LA, Nov. 1995.

  1. Net Assignment and Image Definition for Optimal CMOS Cell Layout


J.A. Feldman, O. Gat, I.A. Wagner, S. Wimer,
Technical report 88.375, IBM Israel Science and Technology, MATAM, Haifa, February 1997.

  1. A Novel Method for Stochastic Nonlinearity Analysis of a CMOS Pipeline ADC,


D. Goren, E. Shamsaev, I. A. Wagner,
Design Automation Conference (DAC'38), July 18-21, 2001, Las Vegas, Nevada, USA, pp. 127-132.

  1. Gate-Diffusion Input (GDI) - A Novel Power Efficient Method for Digital Circuits: A Design Methodology,


A. Morgenshtein, A. Fish, I.A. Wagner,
ASIC/SOC 2001, September 12-15 2001, Hyatt Regency, Washington DC, USA. (postponed).

  1. AN INTERCONNECT-AWARE METHODOLOGY FOR ANALOG AND MIXED SIGNAL DESIGN, BASED ON HIGH BANDWIDTH (OVER 40 GHz) ON-CHIP TRANSMISSION LINE APPROACH,


D Goren, M Zelikson, T C Galambos, R Gordin, B Livshitz, A Amir, A Sherman and I A Wagner,
DATE 2002, Paris, 4-8 March, 2002.

  1. GATE-DIFFUSION INPUT (GDI) - A TECHNIQUE FOR LOW POWER DESIGN OF DIGITAL CIRCUITS: ANALYSIS AND CHARACTERIZATION, A. Morgenshtein, A. Fish, I.A. Wagner, ISCAS 2002, Scottsdale, AZ, May 26-29, 2002.
  2. Gate-Diffusion Input (GDI) - A Power Efficient Method for Digital Combinatorial Circuits,
    Arkadiy Morgenshtein , Alexander Fish  and Israel A. Wagner,
    IEEE Transactions on VLSI, Volume: 10 Issue: 5 , Oct 2002, Page(s): 566 -581
  3. On-chip Interconnect-Aware Design and Modeling Methodology, Based on High Bandwidth Transmission Line Devices,
    D. Goren, M. Zelikson, R. Gordin, I. A. Wagner, A. Barger, A. Amir, B. Livshitz, A. Sherman, Y. Tretiakov, R. Groves, J. Park, D. Jordan, S. Strang, R. Singh, C. Dickey, D. Harame,
    DAC 2003, Chicago, September 2-6, 2003.

  4. Logic Gates as Repeaters (LGR) for Timing Optimization of SoC Interconnects,
    M. Moreinis, A. Morgenshtein, I. A. Wagner, A. Kolodny
    IFIP VLSI SoC 2003 - International Conference on Very Large Scale Integration of Systems-on-Chip   -   Darmstadt, Germany, December 1-3, 2003.

  5. AN EFFICIENT IMPLEMENTATION OF D-FLIP-FLOP USING THE GDI TECHNIQUE,
    Arkadiy Morgenshtein , Alexander Fish  and Israel A. Wagner,
    ISCAS 2004, Vancouver, May 23-26, 2004. 
  6. Reliability and Yield: a Joint Defect-oriented Approach,
    Roman Barsky and Israel A. Wagner,
    DFT'04 , The 19th IEEE International Symposium on Defect and Fault Tolerance in VLSI Systems, Cannes, France, October 11-13, 2004.
  7. Electromigration-Dependent Parametric Yield Estimation,
    Roman Barsky and Israel A. Wagner,
    ICECS'04 - International Conference on Electronics, Circuits and Systems, Tel-Aviv, Israel, December 13-15, 2004.
  8. REPEATER INSERTION COMBINED WITH LGR METHODOLOGY FOR ON-CHIP INTERCONNECT TIMING OPTIMIZATION,
    M. Moreinis, A. Morgenshtein, I. A. Wagner, A. Kolodny,
    ICECS'04 - International Conference on Electronics, Circuits and Systems, Tel-Aviv, Israel, December 13-15, 2004.
  9. “Logic Gates as Repeaters (LGR) for Area-Efficient Timing Optimization”,
    M. Moreinis, A. Morgenshtein, I. A. Wagner, A. Kolodny, IEEE T-VLSI, Nov. 2006, Volume 14,  Issue: 11, pp.: 1276-1281

 

Back to List of contents

An Efficient Algorithm for Some MultiRow Layout Problems

  1. Authors:


Jack A. Feldman, Israel A. Wagner and Shmuel Wimer -
IBM Haifa Research Lab., MATAM Haifa 31905, Israel

  1. "MultirowTCAD93.pdf" - a pdf of the paper in IEEE Transactions on CAD, August 93.
  2. Abstract: Automatic generation of standard CMOS logic cell has been studied intensively during the last decade. Some maturity has been achieved and several commercial tools are available. The continuous progress in VLSI technology presents new challenges in developing efficient algorithms for the layout of standard CMOS logic cells and in combining them within functional macros. In this paper, three multi-row layout problems are presented: transistor orientation, contact positioning and symbolic-to-shape translation . It is shown that these multi-row problems have a common property which we call quantitative dependency Using this property, an optimization technique is presented that is based on penalty-delay. We prove that the penalty-delay strategy assures optimality. This technique results in a linear time algorithm that solves the above problems optimally. The algorithmic approach is based on the observation that optimal layout decisions in any region within a cell or a macro depend only on quantitative measures of the decisions in other regions, rather than on their details. This suggests to depart from the traditional approach of handling the different regions separately and combining them afterwards into a single unit, an approach that may degrade the quality of final layout. Instead, the entire macro can be processed at once, taking into account the mutual dependency between distinguished regions.
  4. Keywords: Dynamic Programming, VLSI CAD, VLSI Layout Optimization.

Back to List of contents

An Interactive VLSI CAD Tool for Yield Estimation

  1. Authors:
    1. Israel A. Wagner - IBM Haifa Research Lab., MATAM Haifa 31905, Israel
    2. Israel Koren - Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, MA 01003, USA
  2. "tsm.pdf"- PDF file
  3. Abstract: The yield of a VLSI chip depends, among other factors, on the sensitivity of the chip to defects occurring during the fabrication process. To predict this sensitivity, one usually needs to compute the so-called critical area (Ac) which reflects how many and how large the defects must be in order to result in a circuit failure. The main computational problem in yield estimation is to calculate Ac efficiently for complicated, irregular layouts. A novel approach is suggested for this problem that results in an algorithm that will solve it efficiently. This paper provides an interactive accurate and fast method for the rapid evaluation of critical area as a design tool with good visual feedback to allow layout improvement for higher yield. The algorithm is compared to other yield-prediction methods, which use either the Monte-Carlo approach (VLASIC) or a deterministic approach (SCA), and is shown to be faster. It also has the advantage that it can graphically show a detailed `defect sensitivity map' that can assist a chip designer in improving the yield of his/her layout.
  5. IEEE Transactions on Semiconductor Manufacturing, MAY 1995, pp. 130-138.
  6. Keywords: VLSI yield analysis, critical area, interactive CAD tools

Back to List of contents

The Effect of Spot Defects on the Parametric Yield of Long Interconnection Lines

  1. Authors:
    1. Israel A. Wagner - IBM Haifa Research Lab., MATAM Haifa 31905, Israel
    2. Israel Koren - Department of Electrical and Computer Engineering, University of Massachusetts, Amherst, MA 01003, USA
  2. "py.pdf"- PDF file
  3. Abstract: The effect of non-catastrophic (or soft) defects (i.e., neither short nor open) on long interconnection lines is analyzed and an estimate is derived for the frequency-dependent critical area for such lines. The analysis is based on a transmission-line model of interconnection lines, and the reflections caused by the defect are taken into account. This analysis results in an estimated prediction of the parametric yield, and a practical recommendation for a better jog insertion in VLSI routing.
  5. Proceedings of DFT95 - International Workshop on Defect and Fault Tolerance in VLSI Systems , Lafayette, LA, Nov. 1995.
  6. Keywords: parametric yield, VLSI interconnection lines, crosstalk capacitance

Back to List of contents

Net Assignment and Image Definition for Optimal CMOS Cell Layout

  1. Authors:
    1. J.A. Feldman, O. Gat, I.A. Wagner, S. Wimer - IBM Haifa Research Lab., MATAM Haifa 31905, Israel
  2. Abstract: The goal of achieving more and more performance per silicon area requires CMOS logic cells to have high area efficiency, especially when a full-custom VLSI layout is attempted. This goal becomes very difficult with the increase of cell complexity that is typically found in full-custom design. Automatic cell generation that has been proved to be a productivity factor in semi-custom VLSI layout, is unfortunately less successful in full-custom design. The success in productivity gain for semi-custom layout stems mainly from the restrictions imposed by the cell image concept, that can be handled nicely by algorithmic-based cell generation tools. This however conflicts the attitude of full-custom design methodology to drop many design constraints in order to achieve high performance. In order to resolve the conflict, a novel technique to optimally utilize CMOS cell area is proposed. The new technique is based on an algorithmic framework for the optimal assignment of nets to routing regions within the cell, employing a general integer programming model. This model enables specific customization for a large set of routing objectives and considerations. The new approach can be used either for semi-custom design where it allows for more area efficient standard cell libraries, or in full-custom design, where image constraints can be relaxed to yield high performance cells and macros, particularly in data-path layout. An automatic cell generator implementing the above method was successfully used for the layout of data-path functions. Experimental data will be presented that demonstrates the efficiency of our approach, despite the NP-completeness of the general integer programming problem.
  3. Technical report 88.375, IBM Israel Science and Technology,MATAM, Haifa, February 1997.
  4. Keywords: VLSI routing, semi-custom VLSI design, automatic cell generation

Back to List of contents

A Novel Method for Stochastic Nonlinearity Analysis of a CMOS Pipeline ADC

  1. Authors:
    1. David Goren, Eliyahu Shamsaev, Israel A. Wagner - IBM Haifa Research Lab., MATAM Haifa 31905, Israel
  2. era.pdf - a PDF file
  3. Abstract: An analytic approach is presented for estimating the nonlinearity of an analog to digital converter (ADC)  as a  function of the variations in the circuit devices. The approach is demonstrated for the case of a pipeline ADC with digital error correction. Under some mild assumptions on the expected variations,  the error probability is expressed as a simple explicit function of the standard deviations in the components' parameters: gain errors, comparator offset errors and  resistor errors.  The analytical expression is verified for Integral Non Linearity (INL),  and its limits are studied


using Monte-Carlo simulations of a 10 bit pipeline ADC structure.
 

  1. Design Automation Conference (DAC'38), July 18-21, 2001, Las Vegas, Nevada, USA, pp. 127-132.
  2. Keywords: Analog to digital conversion, Pipeline, INL, Stochastic analysis.

Back to List of contents

· 

Gate-Diffusion Input (GDI) - A Novel Power Efficient Method for Digital Circuits: A Design Methodology

  1. Authors:
    1. A. Morgenshtein - Technion, Haifa 32000
    2. A. Fish - Ben-Gurion University, Beersheba
    3. I.A. Wagner - IBM Haifa Research Lab., MATAM Haifa 31905, Israel
  2. Abstract:  GDI (Gate Diffusion Input) - a new technique of low power digital combinatorial circuit design is described. This technique allows reducing power consumption, propagation delay and area of digital circuits, while maintaining low complexity of logic design.  Performance comparison with traditional CMOS and various PTL design techniques is presented. The different methods are compared with respect to the layout area, number of devices, delay and power dissipation. Issues like technology compatibility, top-down design and pre-computing synthesis are discussed, showing advantages and drawbacks of GDI as compared to other methods. Several logic circuits have been implemented in various design styles. Their properties are discussed, simulation results are reported and measurements of a test chip.
  3. ASIC/SOC 2001 conference, September 12-15 2001, Hyatt Regency, Washington DC, USA.
  4. Keywords: low power design, CMOS, power-delay tradeoff.

Back to List of contents

 

Publications in Other Topics

  1. D. Fisher-Gewirtzman, I. A. Wagner, "Spatial Openness as a Metric for Comparative Evaluation of Dense built-Up Environments," First International Workshop on Architectural and Urban Ambient Environment, February, 6-7-8, 2002, Nantes, France.
  2. D. Fisher-Gewirtzman, I. A. Wagner, "Spatial openness as a practical metric for evaluating built-up environments,"
    Environment and Planning B: Planning and Design 2003, volume 30(1) January, pages 37 - 49
  3. D. Fisher-Gewirtzman, I. A. Wagner, "The Spatial Openness Metric for Evaluating Urban Environments"
    Journal of Architectural and Planning Research , to appear
  4. D. Fisher-Gewirtzman, D. Shach-Pinsly, I. A. Wagner, M. Burt, "Urban coastal environments: quantitative methods for visual analysis and comparative evaluation"
    Urban Design International , to appear

 


Back to List of contents

 

Links

Math & Theoretical Computer Science:

American Mathematical Monthly

Topics in Mathematics

AMS (American Mathematical Society)

Math - General Resources

Theoretical CS database

SIGACT News Theory Calendar

The Hamiltonian Page

Planar Graphs

Eric's Treasure Trove of Mathematics

Interactive Mathematics Miscellany and Puzzles

Conway's "Life" Miscellany

Internet Resources for the College Math Student

Algorithms

Collected Algorithms of the ACM

The Stony Brook Algorithm Repository

Scott Gasch's Algorithm Archive

Geometry in Action: discrete and computational geometry

A Survey of Global Optimization Methods (Gray et al)

The Geometry Centere

The Internet

Internet Tutorial

Robots in the Web

About Search Engines

What are people searching for right now?

A(ge)nts and Robots:

Intelligent Systems Lab, Technion

Robohoo!

Robotics lab - UC Berkeley

MIT Media Lab

The Ants: A Community of Microrobots

Robot Vacuum Cleaner Contest

Friendly Machines - Consumer Robotics

LEGO Mindstorm

Homing: solution for content management and personalization

Robot Shopping Center

Live Ant Farm (some fun)

Robotics FAQ Table of Contents

Stiquito Colony Info

Small robots manufacturers

RobotBooks.com

Ant Colony Optimization - Marco Dorigo's page

RobotCafe.com - Robotics News, Tutorials, Discussion Forums, Books, and a comprehensive directory of Robotics Links.

VLSI

VLSIhoo

IBM Microelectronics

Yield and Reliability in VLSI

DFT'97 - Defect and Fault Tolerance in VLSI Systems

Great Microprocessors of the Past and Present

CPU Info Center

IBM:

Main site

Research Division

Haifa Research Lab

IBM technologies: SOI, copper, SiGe and others

Java:

Java Applets (developer.com)

TechTools on Java

IBM Java Web Site - Graphics

A JAVA ILP Machine

ACM/IBM Quest for Java '98 Contest: Rules & Judging

IBM Centre for Java Technology -- AIX Developer Area

Cafe del Sol

IBM/Java Site Index

The Mad Scientist

IBM Java Update

Java Home at IBM

Java 3D API

Java at SUN

Jave Programming Course

LaTex:

Math Typesetting

LaTeX help

MATLAB:

MATLAB Tips and Previews

Omikron Delta (Israel)

MATLAB at MathWorks

Societies:

TCS Virtual Address Book: Deluxe

nationalgeographic

Artificial Intelligence In Israel

Solid-State Circuits Society

MAA Online

ACM, The First Society in Computing

IEEE Robotics and Automation Society Home Page

IEEE Home Page

Conferences, Workshops, etc.:

FOCS'99

Ants in CEC'99

ICRA'99

STOC'99

ANTS'98

AMAI'98

RANDOM'98

AAAI-97 Workshop on On-Line Search

ISTCS'96

ISCAS 2002

BISFAI 2007

Seminars,Colloquia, etc.:

The Faculty of Industrial Engineering and Management

Technion Mathematics Net

Computer Science Colloquia

books & journals:

MacMillan E-Books

Mathematical Problems in Engineering

Sefarim Store

Library of Congress

HotWired!

Journal of Robotics and Autonomous Systems (Elsevier)

http://www.thebookplace.com/

Top 100 Computer Magazines (ABC)

Deaf Magazine

Osborne/McGraw-Hill

International Journal of Machine Tools and Manufacture

Amazon

Journal of Graph Algorithms and Applications

Kluwer Academic Publishers

Journals in EE library

Robot Books.com

International Journal of Robotics Research

Dbook

Barnes & Noble

Technion Library

Steimatzky

Springer Verlag

BooksPrice (Multiple Price Comparison)

Animation:

Wallace and Gromit

ASIFA – Israeli Animators Association

Aniboom

Animation in Java applets (JavaWorld, March 1996)

Animation Express

News:

TechWeb, BYTE, Captain Internet

Ha'aretz, Israel News Today, Jerusalem Post, Globes, Israel On Line, Arutz 2 News Walla! News

ABCNews, CNN, Salon, Slate, USA today

TV in Israel

WWW Search:

Google, MonkeySweat, Metacrawler, AltaVista, LookSmart, Yahoo

Walla , arts-technology.com

Others:

Philosophy Sites on the Internet,

Kashrut.com, Halakhic times, Shamash: Jewish things

The Comic Strip, Snoopy's Doghouse, Dilbert,

Dilbert Fans,

Webster Dictionary

Medicine

Moreshet

Back to List of contents

send e-mail (to wagner@il.ibm.com)

 

You are the 2n'th visitor, where n=log2 (# visits so far)

/html>