UTCS Artificial Intelligence
courses
talks/events
demos
people
projects
publications
software/data
labs
areas
admin
Wire Routing and Satisfiability Planning (2000)
Esra Erdem
,
Vladimir Lifschitz
and Martin Wong
Wire routing is the problem of determining the physical locations 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 optimization 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 solution whenever one exists.
View:
PS
Citation:
In
Proceedings of International Conference on Computational Logic
, pp. 822-836 2000.
Bibtex:
@INPROCEEDINGS{erd00, title={Wire Routing and Satisfiability Planning}, author={Esra Erdem and Vladimir Lifschitz and Martin Wong}, booktitle={Proceedings of International Conference on Computational Logic}, pages={822-836}, url="http://www.cs.utexas.edu/users/ai-lab?erd00", year={2000} }
People
Esra Erdem
Ph.D. Alumni
esraerdem [at] sabanciuniv edu
Vladimir Lifschitz
Faculty
vl [at] cs utexas edu
Areas of Interest
Action Languages
Automated Reasoning
Nonmonotonic Reasoning
Planning
Reasoning about Actions