Wire routing and satisfiability planning

Esra Erdem, Vladimir Lifschitz, Martin D F Wong

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

Abstract

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
EditorsVeronica Dahl, Ulrich Furbach, Manfred Kerber, Catuscia Palamidessi, Peter J. Stuckey, Luís Moniz Pereira, Yehoshua Sagiv, John Lloyd, Kung-Kiu Lau
PublisherSpringer-Verlag
Pages822-836
Number of pages15
ISBN (Electronic)3540677976, 9783540677970
StatePublished - Jan 1 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)
Volume1861
ISSN (Print)0302-9743

Other

Other1st International Conference on Computational Logic, CL 2000
CountryUnited Kingdom
CityLondon
Period7/24/007/28/00

Fingerprint

Routing
Planning
Wire
Robot
Robots
Path
Combinatorial optimization
Routing Problem
Intersect
Disjoint
Chip
Trajectories
Trajectory
Optimization
Networks (circuits)

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Erdem, E., Lifschitz, V., & Wong, M. D. F. (2000). Wire routing and satisfiability planning. In V. Dahl, U. Furbach, M. Kerber, C. Palamidessi, P. J. Stuckey, L. M. Pereira, Y. Sagiv, J. Lloyd, ... K-K. Lau (Eds.), Computational Logic - CL 2000 - 1st International Conference, Proceedings (pp. 822-836). (Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science); Vol. 1861). Springer-Verlag.

Wire routing and satisfiability planning. / Erdem, Esra; Lifschitz, Vladimir; Wong, Martin D F.

Computational Logic - CL 2000 - 1st International Conference, Proceedings. ed. / Veronica Dahl; Ulrich Furbach; Manfred Kerber; Catuscia Palamidessi; Peter J. Stuckey; Luís Moniz Pereira; Yehoshua Sagiv; John Lloyd; Kung-Kiu Lau. Springer-Verlag, 2000. p. 822-836 (Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science); Vol. 1861).

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

Erdem, E, Lifschitz, V & Wong, MDF 2000, Wire routing and satisfiability planning. in V Dahl, U Furbach, M Kerber, C Palamidessi, PJ Stuckey, LM Pereira, Y Sagiv, J Lloyd & K-K Lau (eds), Computational Logic - CL 2000 - 1st International Conference, Proceedings. Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science), vol. 1861, Springer-Verlag, pp. 822-836, 1st International Conference on Computational Logic, CL 2000, London, United Kingdom, 7/24/00.
Erdem E, Lifschitz V, Wong MDF. Wire routing and satisfiability planning. In Dahl V, Furbach U, Kerber M, Palamidessi C, Stuckey PJ, Pereira LM, Sagiv Y, Lloyd J, Lau K-K, editors, Computational Logic - CL 2000 - 1st International Conference, Proceedings. Springer-Verlag. 2000. p. 822-836. (Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)).
Erdem, Esra ; Lifschitz, Vladimir ; Wong, Martin D F. / Wire routing and satisfiability planning. Computational Logic - CL 2000 - 1st International Conference, Proceedings. editor / Veronica Dahl ; Ulrich Furbach ; Manfred Kerber ; Catuscia Palamidessi ; Peter J. Stuckey ; Luís Moniz Pereira ; Yehoshua Sagiv ; John Lloyd ; Kung-Kiu Lau. Springer-Verlag, 2000. pp. 822-836 (Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)).
@inproceedings{3be56324d10c42d0825a1d22afd42f71,
title = "Wire routing and satisfiability planning",
abstract = "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.",
author = "Esra Erdem and Vladimir Lifschitz and Wong, {Martin D F}",
year = "2000",
month = "1",
day = "1",
language = "English (US)",
series = "Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)",
publisher = "Springer-Verlag",
pages = "822--836",
editor = "Veronica Dahl and Ulrich Furbach and Manfred Kerber and Catuscia Palamidessi and Stuckey, {Peter J.} and Pereira, {Lu{\'i}s Moniz} and Yehoshua Sagiv and John Lloyd and Kung-Kiu Lau",
booktitle = "Computational Logic - CL 2000 - 1st International Conference, Proceedings",

}

TY - GEN

T1 - Wire routing and satisfiability planning

AU - Erdem, Esra

AU - Lifschitz, Vladimir

AU - Wong, Martin D F

PY - 2000/1/1

Y1 - 2000/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84867827502&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867827502&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84867827502

T3 - Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)

SP - 822

EP - 836

BT - Computational Logic - CL 2000 - 1st International Conference, Proceedings

A2 - Dahl, Veronica

A2 - Furbach, Ulrich

A2 - Kerber, Manfred

A2 - Palamidessi, Catuscia

A2 - Stuckey, Peter J.

A2 - Pereira, Luís Moniz

A2 - Sagiv, Yehoshua

A2 - Lloyd, John

A2 - Lau, Kung-Kiu

PB - Springer-Verlag

ER -