3

I'm reading Skiena's Algorithm Design Manual and there is a problem on page 5, "Robot Tour Optimisation", where he says this about the sample problem: "Suppose we are given a robot arm equipped with a tool, say a soldering iron. In manufacturing circuit boards, all the chips and other components must be fastened onto the substrate. More specifically, each chip has a set of contact points that must be soldered to the board. To program the robot arm for this job, we must first construct an ordering of the contact points so the robot visits the first contact point, second, etc..."

"We must first construct an ordering" - that seems strange to me.

Because, well, every chip has certain number of pins and they're numbered and their position is documented, look here:

enter image description here

I mean that chip doesn't have a set of pins, it have an ordered list of pins, ok, it doesn't but it has very specific dimensions and specific order of pins on each side so their precise position (and order) can be easily calculated.

Maybe unrelated, but probably IRL the board is moving on some sort of clamp in X, Y dimension and soldering iron only goes up and down.

The simplest problem I can give as an example of Robot Optimisation tour is a pizza courier who rides a car and needs to visit all his clients (let's assume that traffic is near zero) and returns to the restaraunt with as little gasoline spent as possible. So he needs a tool (car navigator), that will solve this problem for him. And that navigation application needs to find the optimal route - so, it illustrates the problem.

Am I right that original problem illustration with robot arm is wrong?

Improve this question
1
  • 1
    Actually if you were hand-soldering a SMT chip like that you would solder alternate corners to prevent it tombstoning
    – Martin Beckett
    Aug 23, 2012 at 4:06

3 Answers 3

Reset to default
2

There are typically multiple chips of varying sizes on the board. In what order do you move among the chips? Are you are assuming that the arm would finish soldering one chip before moving on to the next? It may require less motion of the robot arm to solder the pins on adjacent edges of neighboring chips before finishing the pins the far side.

Improve this answer
5
  • Which is why creating an "ordering" of points is a sensible step; it allows the computer controlling the arm to optimize its movements.
    – Robert Harvey
    Aug 22, 2012 at 22:15
  • In that sense you're right, but in book it's said about a single chip, not all chips. But even in that case you described, it'll be easier not to order individual pins, but order chips that are fastened. So the task will be: we have n chips, what'll be the shortest path to solder them all. Meanwhile, while soldering each chip, we don't need to order it pins because they are already ordered in the chip specification.
    – user1449
    Aug 23, 2012 at 7:07
  • I'm talking about is that specific example in the book is invalid. Not that we can't somehow modify it to make it valid (as you probably did).
    – user1449
    Aug 23, 2012 at 7:13
  • 1
    @gasan, I've got the book right in front of me. I don't see any implication the problem involves soldering only a single chip. Right from the start the problem talks about the assembly of a circuit board containing multiple chips. The sentence you quote refers to "each" chip rather than "the" chip implies that multiple chips are being considered. The formal statement of the problem says that the input is a set of points in the plain. The contact points for a chip are a set of points in the plane, but then so is the union of those sets, which would be the set of all contact points on the board.
    – Charles E. Grant
    Aug 23, 2012 at 17:00
  • Yes, I got your point. Along with @RobertHarvey explaination, I think I finally understand the problem. Thank you.
    – user1449
    Aug 23, 2012 at 21:08
1

It's true that pins on a chip are numbered. But when figuring out the best order to solder the pins, the existing numbering isn't necessarily optimal. When pins are laid out in a line around the edge, the given numbering is probably optimal. But when you have some weird layout, like the layout in an x86 processor, it might not be.

Intel CPU

In fact, the pins on such a processor aren't numbered, but referenced by row and column:

Socket 478 Pin Assignment

Improve this answer
4
  • That's fine. But you still need some sort of "ordering," so that the robotic arm (or the computer controlling the robotic arm) can make the calculations to move the arm from one pin to the next.
    – Robert Harvey
    Aug 22, 2012 at 22:14
  • The chip you illustrated goes into a socket; it is not soldered directly to a board.
    – Robert Harvey
    Aug 22, 2012 at 22:20
  • Ah, but you have to solder the socket. :)
    – Martin C. Martin
    Aug 22, 2012 at 22:21
  • CPU sockets are Ball-Grid Array devices; they are soldered using a reflow technique that doesn't require a robot touching each individual pin.
    – Robert Harvey
    Aug 22, 2012 at 22:25
0

Before the robot can solder the pins, it must first know where the pins are, and it's probably more efficient to visit the pins in a specific sequence, than it is to visit them randomly. Hence, the ordering.

Remember, machines don't know anything except what you tell them, so if you want them to visit points in a specific sequence, you have to tell them what that sequence is, so it can perform the calculations to move the arm from one point to the next.

Note that the chip in your illustration is a surface-mount device; it is highly likely that it is soldered using a Vapor Phase or convection system, which solders all pins simultaneously without requiring a robotic arm. It is therefore probably not a very good example.

Improve this answer
3
  • It does know where the pins are, they position and all info is on the chip spec. There is no word random when you're talking about chip pins the are perfectly ordered. Okay you should calculate their exact position based on the dimensions of the chip and the number of pins, but that's a different task.
    – user1449
    Aug 23, 2012 at 7:15
  • 1
    @gasan: As others have pointed out, sequential ordering from the first pin to the last may not be the optimal ordering. If you're so concerned about this particular wording, why don't you contact the author and ask him what he meant?
    – Robert Harvey
    Aug 23, 2012 at 14:41
  • I got your point, the problem I have is that I don't understand how position of each contact pin is specified, so I tried to understand the whole process and find out what set exactly there is. You see, I was trying to understand what the set means, at first I thought about random set, then I understood that it's not random. Now I've got that it's ordered but not in the optimal order, so it needs further reordering to make it an optimal route. Thanks, I believe I finally understand the problem.
    – user1449
    Aug 23, 2012 at 21:05