More on Wire Routing with ASP

Deborah East and Miroslaw Truszczynski

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.