Wire routing and satisfiability planning

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

doi:10.1007/3-540-44957-4_55

Wire routing and satisfiability planning

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

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

13 Citations (Scopus)

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 language	English
Title of host publication	Computational Logic - CL 2000
Subtitle of host publication	First International Conference London, UK, July 24–28, 2000 Proceedings
Editors	John Lloyd, Veronica Dahl, Ulrich Furbach, Manfred Kerber, Kung-Kiu Lau, Catuscia Palamidessi, Luís Moniz Pereira, Yehoshua Sagiv, Peter J. Stuckey
Place of Publication	Berlin
Publisher	Springer Verlag
Pages	822-836
Number of pages	15
Edition	1st
ISBN (Electronic)	9783540449577
ISBN (Print)	9783540677970
DOIs	https://doi.org/10.1007/3-540-44957-4_55
Publication status	Published - 24 Jul 2000
Event	1st International Conference on Computational Logic, CL 2000 - London, United Kingdom Duration: 24 Jul 2000 → 28 Jul 2000 https://link.springer.com/book/10.1007/3-540-44957-4

Publication series

Name	Lecture Notes in Computer Science
Volume	1861
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Name	Lecture Notes in Artificial Intelligence
ISSN (Print)	2945-9133
ISSN (Electronic)	2945-9141

Name	CL: International Conference on Computational Logic Proceedings

Conference

Conference	1st International Conference on Computational Logic, CL 2000
Country/Territory	United Kingdom
City	London
Period	24/07/00 → 28/07/00
Internet address	https://link.springer.com/book/10.1007/3-540-44957-4

Scopus Subject Areas

Theoretical Computer Science
General Computer Science

User-Defined Keywords

Very Large Scale Integrate
Action Language
Default Theory
Plan Fact
Circuit Component

Access to Document

10.1007/3-540-44957-4_55

Cite this

Erdem, E., Lifschitz, V., & Wong, M. D. F. (2000). Wire routing and satisfiability planning. In J. Lloyd, V. Dahl, U. Furbach, M. Kerber, K.-K. Lau, C. Palamidessi, L. M. Pereira, Y. Sagiv, & P. J. Stuckey (Eds.), Computational Logic - CL 2000: First International Conference London, UK, July 24–28, 2000 Proceedings (1st ed., pp. 822-836). (Lecture Notes in Computer Science; Vol. 1861), (Lecture Notes in Artificial Intelligence ), (CL: International Conference on Computational Logic Proceedings). Springer Verlag. https://doi.org/10.1007/3-540-44957-4_55

Erdem, Esra ; Lifschitz, Vladimir ; Wong, Martin D. F. / Wire routing and satisfiability planning. Computational Logic - CL 2000: First International Conference London, UK, July 24–28, 2000 Proceedings. editor / John Lloyd ; Veronica Dahl ; Ulrich Furbach ; Manfred Kerber ; Kung-Kiu Lau ; Catuscia Palamidessi ; Luís Moniz Pereira ; Yehoshua Sagiv ; Peter J. Stuckey. 1st. ed. Berlin : Springer Verlag, 2000. pp. 822-836 (Lecture Notes in Computer Science). (Lecture Notes in Artificial Intelligence ). (CL: International Conference on Computational Logic Proceedings).

@inproceedings{8fe96dd84204438b989f0e552a2890d1,

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.",

keywords = "Very Large Scale Integrate, Action Language, Default Theory, Plan Fact, Circuit Component",

author = "Esra Erdem and Vladimir Lifschitz and Wong, {Martin D. F.}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000.; 1st International Conference on Computational Logic, CL 2000 ; Conference date: 24-07-2000 Through 28-07-2000",

year = "2000",

month = jul,

day = "24",

doi = "10.1007/3-540-44957-4_55",

language = "English",

isbn = "9783540677970",

series = "Lecture Notes in Computer Science",

publisher = "Springer Verlag",

pages = "822--836",

editor = "John Lloyd and Veronica Dahl and Ulrich Furbach and Manfred Kerber and Kung-Kiu Lau and Catuscia Palamidessi and Pereira, {Lu{\'i}s Moniz} and Yehoshua Sagiv and Stuckey, {Peter J.}",

booktitle = "Computational Logic - CL 2000",

address = "Germany",

edition = "1st",

url = "https://link.springer.com/book/10.1007/3-540-44957-4",

}

Erdem, E, Lifschitz, V & Wong, MDF 2000, Wire routing and satisfiability planning. in J Lloyd, V Dahl, U Furbach, M Kerber, K-K Lau, C Palamidessi, LM Pereira, Y Sagiv & PJ Stuckey (eds), Computational Logic - CL 2000: First International Conference London, UK, July 24–28, 2000 Proceedings. 1st edn, Lecture Notes in Computer Science, vol. 1861, Lecture Notes in Artificial Intelligence , CL: International Conference on Computational Logic Proceedings, Springer Verlag, Berlin, pp. 822-836, 1st International Conference on Computational Logic, CL 2000, London, United Kingdom, 24/07/00. https://doi.org/10.1007/3-540-44957-4_55

Wire routing and satisfiability planning. / Erdem, Esra; Lifschitz, Vladimir; Wong, Martin D. F.
Computational Logic - CL 2000: First International Conference London, UK, July 24–28, 2000 Proceedings. ed. / John Lloyd; Veronica Dahl; Ulrich Furbach; Manfred Kerber; Kung-Kiu Lau; Catuscia Palamidessi; Luís Moniz Pereira; Yehoshua Sagiv; Peter J. Stuckey. 1st. ed. Berlin: Springer Verlag, 2000. p. 822-836 (Lecture Notes in Computer Science; Vol. 1861), (Lecture Notes in Artificial Intelligence ), (CL: International Conference on Computational Logic Proceedings).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Wire routing and satisfiability planning

AU - Erdem, Esra

AU - Lifschitz, Vladimir

AU - Wong, Martin D. F.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2000.

PY - 2000/7/24

Y1 - 2000/7/24

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.

KW - Very Large Scale Integrate

KW - Action Language

KW - Default Theory

KW - Plan Fact

KW - Circuit Component

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

U2 - 10.1007/3-540-44957-4_55

DO - 10.1007/3-540-44957-4_55

M3 - Conference proceeding

AN - SCOPUS:84867827502

SN - 9783540677970

T3 - Lecture Notes in Computer Science

SP - 822

EP - 836

BT - Computational Logic - CL 2000

A2 - Lloyd, John

A2 - Dahl, Veronica

A2 - Furbach, Ulrich

A2 - Kerber, Manfred

A2 - Lau, Kung-Kiu

A2 - Palamidessi, Catuscia

A2 - Pereira, Luís Moniz

A2 - Sagiv, Yehoshua

A2 - Stuckey, Peter J.

PB - Springer Verlag

CY - Berlin

T2 - 1st International Conference on Computational Logic, CL 2000

Y2 - 24 July 2000 through 28 July 2000

ER -

Erdem E, Lifschitz V, Wong MDF. Wire routing and satisfiability planning. In Lloyd J, Dahl V, Furbach U, Kerber M, Lau KK, Palamidessi C, Pereira LM, Sagiv Y, Stuckey PJ, editors, Computational Logic - CL 2000: First International Conference London, UK, July 24–28, 2000 Proceedings. 1st ed. Berlin: Springer Verlag. 2000. p. 822-836. (Lecture Notes in Computer Science). (Lecture Notes in Artificial Intelligence ). (CL: International Conference on Computational Logic Proceedings). doi: 10.1007/3-540-44957-4_55

Wire routing and satisfiability planning

Abstract

Publication series

Conference

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this