AUTOROUTING WITH THE A* ALGORITHM

Searching for the best PC board layout

* This article contains the following executables: NEVIN.ZIP

Randy Nevin

Randy holds a BS in computer science from Oregon State University and an MS in computer science from the University of Washington. He has worked for Microsoft since 1983 on various programming languages and networking products. He can be reached at 1731 211th PL NE, Redmond, WA 98053.


A few years ago, a friend of mine designed an adapter board for the IBM PC. The tools he used were blue and red strips of tape, a sharp knife, large sheets of clear plastic, and a generous amount of patience. It took him several weeks, and after the first board was tested he discovered that some of the traces were incorrect and had to be cut with the knife and rerouted with a solder and wires. This caused me to start thinking about ways to use the power of the computer to simplify this tedious, error-prone job.

The design of a printed circuit board implements an electronic circuit. First you create a schematic. From this you derive a list of chips and other components that perform the required functions, and a list of the pins that need to be connected. Together, these lists are referred to as the "net-list." As long as the connections are made correctly, you usually don't care where the traces (the wires embedded in the board) are placed.

As you can imagine (or may already know), designing a PC board is a complex search problem with a seemingly infinite number of possible solutions. Luckily, there are algorithms from the field of artificial intelligence that we can use to design computer programs called "autorouters" that do this searching for you. In this article, I'll look at two algorithms: The breadth-first and A* (pronounced as "A Star") search algorithms. This article is actually based on an application I wrote to layout, view, and laser-print circuit board designs. Because of the length of that application (nearly 2500 lines of C code), I'll focus my discussion here on the pseudocode that implements the two algorithms mentioned and the source code that implements the A* algorithm. The entire C source code that implements the printed circuit board layout system is available on DDJ's Forum on CompuServe, DDJ's on-line service, and on the disks mentioned at the end of this article.

What Is Autorouting?

Autorouting is one of a class of global optimization problems that are difficult to solve. A good circuit board layout, for example, minimizes things like:

At the same time, the layout maximizes things like signal strength, reliability, and ease of debugging. The overall value of a board design is a function of all of these often conflicting variables. It is usually acceptable to find a solution that satisfies a set of constraints, because finding the globally optimal solution is infeasible for all but the most trivial problems.

Autorouting can also be viewed as a collection of search problems. The individual problems deal with finding a route and laying down a trace between two locations. There are many algorithms for solving search problems, each with different running time characteristics and data space requirements.

Autorouting search algorithms typically operate in two phases{1}, treating the board as a matrix of cells. The first phase starts at the source cell and searches for the target cell, usually by going in several directions at the same time. The algorithm builds an auxiliary data structure to keep track of how each cell was reached (this is referred to as "Pred" in the algorithms in Figure 1 and Figure 2 ). The first phase ends when the target cell has been found, and the second phase begins. If the first phase exhausts all possibilities without reaching the target cell, then no route exists between them, and there is no reason to do the second phase.

Figure 1: Pseudocode for the breadth-first algorithm

  BFS Algorithm (* breadth-first search *)
      (* Search a graph or state space, depending on the problem
         definition.  *)
      (* S is the start node, T is the goal node.  *)
      (* Open is an ordered list of nodes (ordered by arrival time;
         nodes enter at the tail and leave at the head), also called a
         queue.  Closed is a set of nodes (order doesn't matter).  In
         general, nodes that need to be searched are put on Open.  As they
         are searched, they are removed from Open and put in Closed.  *)
      (* Pred is defined for each node, and is a list of "came from"
         indications, so when we finally reach T, we traverse Pred to
         construct a path to S. *)

  1 Open <- {S} (* a list of one element *)
    Closed <- {} (* the empty set *)
    Pred [S] <- NULL, found <- FALSE
    WHILE Open <> {} and not found DO
  5   x <- the first node on Open
      Open <- Open - {x} (* remove x from Open *)
      Closed <- Closed + {x} (* put x in Closed *)
      IF x = T THEN found <- TRUE (* we're done *)
      ELSE (* continue search through node x *)
  10   let R be the set of neighboring nodes of x
       FOR each y in R DO
           IF y is not on Open or in Closed THEN
              Pred[y] <- x (* remember where we came from *)
              Open <- Open + {y} (* put y on Open (at the tail) *)
  15 IF found THEN
        use Pred[T] to find Pred[Pred[T]] and so on until S is reached
        (* this traces out the solution path in reverse *)
     ELSE T cannot be reached from S

The second phase uses the auxiliary data structure to trace the route from the target cell back to the source cell, actually laying down the electrical connections. The second phase is identical for the breadth-first and A* search algorithms. But the first phase is different, and it is this phase that gives these algorithms different behaviors.

The main data structures used in the first phase are the Open queue and the Closed set, which hold cell coordinates. Because a cell's coordinates uniquely identify it, we'll say that the Open queue and Closed set contain cells. Cell coordinates will be represented as r2c3s1 for the cell at row 2, column 3, side 1, or as r2c3 when it is understood that all cells are on the same side of the board. To remind ourselves that Open is a queue and Closed is a set, when we talk about adding cells to them, we will put the cells "on" the queue and "in" the set. Initially, the Open queue contains the source cell and the Closed set is empty.

The first phase is a loop, which removes an element from the head of the Open queue, puts it in the Closed set (which indicates that it has been searched), and checks to see if it is the target cell. If so, the first phase is done. Otherwise, the neighbors of the cell (those adjacent to it) are placed on the Open queue, and the loop continues. As we'll see later, the essential difference in the breadth-first and A* search algorithms is the order in which the neighbors are placed on the Open queue.

Breadth-First Search

Figure 1 contains pseudocode for the breadth-first search algorithm. This algorithm works by processing a first in/first out (FIFO) queue of open cells; that is, cells that have been reached, but not yet searched. Initially, the open queue contains only the source cell. A cell is removed from the head of the open queue, placed in the set of closed cells (cells that have been searched), and checked to see if it is the target cell. If not, its neighbors are placed at the tail of the open queue. Neighboring cells that have already been reached are ignored. (If a cell's coordinates are on the open queue or in the closed set, then it has been reached, otherwise, it has not.) This continues until one of two things happens:

A version of breadth-first search known as Lee's algorithm{2} has served as the basis for some autorouters since the early 1960s. The original algorithm does not consider diagonally adjacent cells as neighbors, and consequently, the back-tracking phase can create only horizontal and vertical traces. We'll enhance the algorithm so that diagonally adjacent cells are neighbors, thus enabling it to produce diagonal traces. Unfortunately, Lee's algorithm suffers from a behavior inherent in the breadth-first search technique, which limits its application to problems of relatively small size. As the distance between the source and target cells increases by a factor of N, the number of cells processed by Lee's algorithm -- and therefore processing time -- increases by the square of N.

Figure 2 shows the behavior of Lee's algorithm while searching for a path between the source cell S (r5c5) and the target cell T (r8c8). Lee's algorithm does not specify the order in which neighboring cells are placed on the open queue, but we'll use the compass directions north, east, south, and west, followed by northeast, southeast, southwest, and northwest. This order tends to produce traces with a minimal number of turns.

In Figure 2a, the source cell (r5c5) has been searched, and its eight neighbors have been placed on the open queue. The arrows indicate the direction from which each cell was reached, and correspond to the Pred data structure. After the first eight cells on the open queue have been reached and moved to the closed set, the algorithm searches the configuration in Figure 2b, where there are sixteen cells on the open queue. Once these sixteen cells have been searched, the configuration in Figure 2c is reached. Now the target cell (r8c8) is fourth from the end on the open queue, and a solution is imminent. Searching r8c8, the algorithm recognizes it as the target cell, and uses the Pred data structure to construct a trace back to the source cell.

You can see that the search progresses outward from the source cell in all directions, like ripples when you throw a pebble into the water. If we double the size of the problem so that S and T are six cells apart, the number of cells searched and therefore the processing time will be about four times as great. If we triple the size of the problem, the number of cells searched will be roughly nine times more. Thus, the behavior of Lee's algorithm is quadratic in the size of the problem, which makes it infeasible for large problems.

A* Search

Figure 3 gives pseudocode for the A* search algorithm, while Listing One shows it implemented in C. This method also works by processing a queue of open cells, which initially contains only the source cell. But this is a priority queue, which means cells are inserted according to the estimated distance to the target{3}, not just at the end. Cells that are on the shortest estimated path from source to target go to the head of the queue. The A* algorithm removes the cell from the head of the open queue and checks to see if it's the target. If not, the neighboring cells are put on the open queue at the proper position. The algorithm checks neighboring cells that have already been searched to see if the new path between them and the source is shorter than the previous one. If it is, they are repositioned on the open queue according to the new estimated path length from source to target. As in breadth-first search, this continues until the target cell has been found or the open queue is empty.

Figure 3: Pseudocode for the A* algorithm

  A* Algorithm (* heuristic search *)
     (* Search a graph or state space, depending on the problem
        definition.  *)
     (* S is the start node, T is the goal node.  *)
     (* Open is an ordered list of nodes (ordered by lowest F value;
        see below), also called a priority queue.  Closed is a set of
        nodes (order doesn't matter).  In general, nodes that need to be
        searched are put on Open (at the proper position).  As they are
        searched, they are removed from Open and put in Closed.
        Occasionally a newer, better route will be found to a node after
        it has already been searched, in which case we remove it from
        Closed and put it back on Open to be reconsidered.  *)
     (* G[x] is the distance already traveled to get from S to node x,
        and is known exactly.  H(x) is a function (heuristic) which
        returns an estimate of the distance from node x to T.  F[x] is
        the estimated distance from S to T by going through node x, and
        is computed by F[x] = G[x] + H(x).  H(x) can be calculated for
        any node, but F[x] and G[x] only become defined when node x is
        visited.  *)
     (* Pred is defined for each node, and is a list of "came from"
        indications, so when we finally reach T, we traverse Pred to
        construct a path to S.  *)
     (* Distance (x,y) is a function for calculating the distance
        between two neighboring nodes.  *)
  1 Open <- {S} (* a list of one element *)
    Closed <- {} (* the empty set *)
    G[S] <- 0, F[S] <- 0, Pred[S] <- NULL, found <- FALSE
    WHILE Open <> {} and not found DO
  5    x <- the first node on Open (* node with smallest F value *)
       Open <- Open - {x} (* remove x from Open *)
       Closed <- Closed + {x} (* put x in Closed *)
       IF x = T THEN found <- TRUE (* we're done *)
       ELSE (* continue search through node x *)
  10           let R be the set of neighboring nodes of x
               FOR each y in R DO
                  IF y is not on Open or in Closed THEN
                     G[y] <- G[x] + Distance (x,y)
                     F[y] <- G[y] + H(y) (* estimate solution path
                      length *)
  15                 Pred[y] <- x (* remember where we came from *)
                     Open <- Open + {y} (* put y on Open *)
                  ELSE (* y is on Open or in Closed *)
                     IF (G[x] + Distance (x,y)) < G[y] THEN
                        (* we've found a better route to y *)
  20                    G[y] <- G[x] + Distance (x,y)
                        F[y] <- G[y] + H(y)
                        Pred[y] <- x (* remember where we came from *)
                        IF y is on Open THEN
                           reposition y according to F[y]
  25                    ELSE (* y is in Closed *)
                           Closed <- Closed - {y} (* remove y from Closed *)
                           Open <- Open + {y} (* put y on Open *)
     IF found THEN
        use Pred[T] to find Pred[Pred[T]] and so on until S is reached
  30    (* this traces out the solution path in reverse *)
     ELSE T cannot be reached from S

A* depends on being able to estimate the distance between a cell and the target cell. In the case of autorouting, a simple measure of this distance is available, and this helps A* to concentrate the search in the direction most likely to succeed. The more accurate the estimate, the faster the search.

In practice, A* does not suffer from the quadratic behavior of Lee's algorithm, it solves similar problems faster and can be applied to larger problems where Lee's algorithm performs poorly. As the distance between the source and target cells increases, the number of cells processed by A* increases, but not as dramatically as with Lee's algorithm.

Figure 4 shows the behavior of the A* search algorithm. A* does not specify whether new cells go in front of or behind cells already on the open queue that evaluate to identical estimated path lengths. We use the convention that they are placed in front. This minimizes the time to insert a cell on the open queue.

In Figure 4a, the source cell (r3c3) has been searched, and its eight neighbors are on the open queue. Each cell on the open queue also includes the estimated length of the shortest path from S to T that goes through that cell. After the first cell (r4c4) has been searched and moved to the closed set, the configuration in Figure 4b is reached, where there are 12 cells on the open queue. After searching the next cell (r5c5), the algorithm reaches the configuration in Figure 4c. Now the target cell (r6c6) is at the head of the open queue, and a solution will be found on the next iteration of the loop. Searching r6c6, A* recognizes it as the target and uses the Pred data structure to construct a trace back to the source cell.

You can see that the search progresses more directly toward the target cell. The target draws the search much as the earth's gravity pulls objects toward the center of mass. If we double the size of the problem, the search will process about twice as many cells, and if we triple its size, the search will run through three times as many. This linear behavior makes A* more attractive for autorouting than the quadratic Lee's algorithm. With the incorporation of the heuristic -- the rule, that guides the search in the direction most likely to succeed -- it is difficult to estimate worst case behavior. However, A* will never take more time than Lee's algorithm, and it will never search any cells that Lee's algorithm could avoid.

Optimizations and Generalizations

The algorithms in Figures 1 and 3 solve the general search problem. When these algorithms are implemented and customized to a particular application, there are ways to speed them up.

The A* algorithm in Figure 3 recomputes the heuristic H(y) when it discovers a better way to reach a cell. Depending on how difficult this heuristic is to compute, you can probably save some work at the expense of complicating the algorithm. When lines 20 and 21 of Figure 3 are executed, the previous values of G[y] and F[y] are destroyed. But F[y] = G[y] + H(y), so you could save F[y] - G[y] (which is H(y)) in a temporary variable, and use that variable instead of recomputing H(y) on line 21. Also, the common sub-expression G[x] + Distance(x,y) should be placed in a temporary variable, instead of being computed twice (lines 18 and 20).

Often, rather than searching for a path between two individual cells, what is really desired is a path between one of a set of source cells and one of a set of target cells (as when connecting power and ground pins). Both algorithms can be modified by adding the entire set of source cells to the initial open queue, and checking for a member of the set of target cells on each iteration. When this is done, the heuristic used by the A* algorithm becomes more complicated. It must estimate the minimum distance from the current cell to any one of the target cells.

For breadth-first search, once the target cell is placed on the open queue, it is pointless to add any more cells to the open queue because when this happens, the problem is solved. An appropriate shortcut would be to insert a check before line 13 in Figure 1 to see if y is the target cell. If it is, use Pred[y] to construct the trace back to the source cell, and return.

Memory Requirements

Both search algorithms use quite a bit of memory to solve problems of non-trivial size. The breadth-first search algorithm needs memory to represent the board, the predecessor structure, and the closed set. The A* search algorithm needs these also, plus structures for F[x] and G[x] (see Figure 3). In addition, both algorithms dynamically allocate memory for the open cell queue.

The board is represented as a pair of two-dimensional arrays -- one for the front side, the other for the back -- in which the dimensions are the number of rows and columns of cells. Not counting holes and traces relating to holes (Figure 5, groups A, B, and C), there are 30 possible cell contents, which can be represented with 5 bits per cell.

The hole-related cells are more difficult to enumerate; they can be combined in many ways. If we simply assign 1 bit to each of the eight traces in groups B and C, and add one more bit to indicate a hole, 14 bits will be sufficient to represent any cell. On a board of N rows and M columns, we'll need N*M*28 bits total.

The predecessor structure is also a pair of two-dimensional arrays, where an entry must be able to represent one of the eight compass directions or an indication for the opposite side of the board. This takes 4 bits per cell, or N*M*8 bits total.

The closed set can be represented by a pair of two-dimensional, single-bit arrays, where a bit is one if the corresponding cell has been searched, and zero otherwise. This will take N*M*2 bits total.

F[x] and G[x] will be similar to the board arrays, but they must contain a 16-bit integer for each cell, requiring N*M*64 bits total. Note that if memory usage needs to be minimized at the cost of increased processing time, we could omit the F[x] arrays, and calculate the F values as they are needed from the G[x] arrays and the heuristic function, H(x).

Breadth-first search thus requires N*M*38 bits, and A* needs N*M*102 bits of static memory. For a printed circuit board 4 x 13 inches (80 cells x 260 cells), breadth-first search will need 98,800 bytes and A* will need 265,200 bytes. Different algorithms that solve the same problem often trade off memory against processing time to achieve better performance. This is the case with A* versus the breadth-first search.</entry>

More Details.

Locality of Reference

Despite the fact that A* requires more memory than breadth-first search, A* exhibits better memory usage patterns. This is because it shows better locality of reference than breadth-first search. Locality of reference deals with the sequence in which memory locations are used, and consists of two rules of thumb: 1. The memory location currently being referenced is likely to be referenced again in the near future, and 2. Memory locations near the one currently being referen