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:
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?
1
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.
5
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.
In fact, the pins on such a processor aren’t numbered, but referenced by row and column:
4
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.
3