## Files in this item

FilesDescriptionFormat

application/pdf

9010946.pdf (6MB)
(no description provided)PDF

## Description

 Title: Geometric planning for VLSI routing and robot motion Author(s): Maddila, Sanjeev Rao Department / Program: Electrical and Computer Engineering Discipline: Electrical and Computer Engineering Degree Granting Institution: University of Illinois at Urbana-Champaign Degree: Ph.D. Genre: Dissertation Subject(s): Mathematics Engineering, Electronics and Electrical Computer Science Abstract: This thesis proposes a decomposition-based algorithmic paradigm, called planning with local experts, where the given global planning problem is decomposed into a set of subproblems that are each solved efficiently in a prescribed sequence and then the solutions of the subproblems are merged together.In the first part of the thesis, we investigate the problems of VLSI routing. In particular, we propose a way of decomposing the problem of routing in a general placement of rectangular modules into a set of subproblems of routing in junctions of L-, S-, T-, and X-shapes. We give non-trivial lower bounds on the channel widths of the associated channels of a junction. For example, we prove that $t\sb1$ + $t\sb2$ $\geq$ ${3\over2}$($d\sb1$ + $d\sb2$) for routing three-terminal nets in an L-shaped junction, where $t\sb1$ and $t\sb2$ are the widths, and $d\sb1$ and $d\sb2$ are the densities of the horizontal and vertical channels of the L-shaped junction, respectively. We also give routers for the general junctions, for the cases of routing two-, three-, and multi-terminal nets. For example, we prove that for routing two-terminal nets in an L-shaped junction $t\sb1$ + $t\sb2$ = $d\sb1$ + $d\sb2$, $t\sb1$ + $t\sb2$ $\leq$ ${3\over2}$($d\sb1$ + $d\sb2$) for the case of three-terminal nets, and $t\sb1$ + $t\sb2$ $\leq$ 2($d\sb1$ + $d\sb2$) for the case of multi-terminal nets.In the second part of the thesis, we investigate the problems of robot motion planning. In particular, we consider a technique to decompose the problem of moving a robot among a set of rectangles into a set of subproblems of moving the robot in certain localites. We give local experts for the local planning problems of moving a polygonal robot around a corner, and moving through a junction of general shape. For example, we give an $O$($m$ log $m$) algorithm for moving a convex $m$-gon around the corner in a corridor. Thus, using our decomposition scheme we develop an $O$($mn$ log $m$ + $n$ log $n$) algorithm for moving a convex polygon with $m$ corners among $n$ iso-oriented rectangles. Issue Date: 1989 Type: Text Language: English URI: http://hdl.handle.net/2142/22372 Rights Information: Copyright 1989 Maddila, Sanjeev Rao Date Available in IDEALS: 2011-05-07 Identifier in Online Catalog: AAI9010946 OCLC Identifier: (UMI)AAI9010946
﻿