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
Y1 - 2000
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
U2 - 10.1007/3-540-44957-4_55
DO - 10.1007/3-540-44957-4_55
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 - 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
T2 - 1st International Conference on Computational Logic, CL 2000
Y2 - 24 July 2000 through 28 July 2000
ER -