More on Wire Routing with ASP

Answer Set Programming: Towards Efficient and Scalable Knowledge Representation and Reasoning

Volume

Papers from the 2001 AAAI Spring Symposium

Contents

Wire routing is an important component in the design of very large scale integrated circuits (VLSI). In a recent work Erdem et al. argued that routing problems can be solved by general-purpose answer-set programming solvers. They proposed to view routing as a planning problem in which multiple robots have to determine their paths between matching pins. As in other planning problems, the representation refers to time moments (or a counter of the number of steps taken). We propose a different approach which eliminates the need to represent time. In adition, we develop techniques to limit the search space by eliminating from consideration grid points that are far from the terminal points. We have experimented with our approach using both smodels and our program dcs. Both programs ran faster on representations proposed here than on the original ones.