Wire routing and satisfiability planning

Esra Erdem, Vladimir Lifschitz, Martin D.F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Wire routing is the problem of determining the physical lo- cations of all the wires interconnecting the circuit components on a chip. Since the wires cannot intersect with each other, they are competing for limited spaces, thus making routing a difficult combinatorial opti- mization problem. We present a new approach to wire routing that uses action languages and satisfiability planning. Its idea is to think of each path as the trajectory of a robot, and to understand a routing problem as the problem of planning the actions of several robots whose paths are required to be disjoint. The new method differs from the algorithms implemented in the existing routing systems in that it always correctly determines whether a given problem is solvable, and it produces a solu- tion whenever one exists.

Original languageEnglish (US)
Title of host publicationComputational Logic - CL 2000 - 1st International Conference, Proceedings
EditorsJohn Lloyd, Veronica Dahl, Ulrich Furbach, Manfred Kerber, Kung-Kiu Lau, Catuscia Palamidessi, Luís Moniz Pereira, Yehoshua Sagiv, Peter J. Stuckey
Number of pages15
ISBN (Electronic)3540677976, 9783540677970
StatePublished - 2000
Externally publishedYes
Event1st International Conference on Computational Logic, CL 2000 - London, United Kingdom
Duration: Jul 24 2000Jul 28 2000

Publication series

NameLecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
ISSN (Print)0302-9743


Other1st International Conference on Computational Logic, CL 2000
Country/TerritoryUnited Kingdom

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Wire routing and satisfiability planning'. Together they form a unique fingerprint.

Cite this