More on Wire Routing with ASP

Abstract

Wire routing is an important component in the design of very large scale integrated circuits (VLSI). In a recent work Er-dem et al. argued that routing problems can be solved by general-purpose answer-set programming solvers. They pro-posed to view routing as a planning problem in which mul-tiple 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.