algorithm for linear ordering problem?

[torekp]

I've got a moving belt with parts randomly scattered on it, and a sensor that can move in the direction across the width of the belt. I want to move the sensor to each part (if possible) as it comes along, then raster back and forth over the part for a while. The more time spent dwelling over the parts, and the less spent traveling between them, the better. Also the fewer parts missed altogether, the better.

I've looked on the web for solutions to the "Traveling Salesman Problem" and, more relevantly, the "Linear Ordering Problem", but what I've found was highly theoretical. Also, many of the computational methods people have used for those problems are too time-consuming. My belt moves fast. I need a rough-and-ready heuristic that gets not-too-horribly suboptimal results.

Is there any way to use Labview's Linear Programming optimization routine on this problem? Consider a three-part problem with parts A, B, C, and possible routes AB, BA, AC, CA, BC, CB. Could I impose contraints like 0 <= AB <= 1, 0 <= BA <= 1, 0 <= AB + BA + AC + CA <= 1, etc.? My problem is discrete, whereas Linear Programming is meant for optimization of continous variables, I think; but maybe that's OK?

Any help appreciated.

[mross]

I've got a moving belt with parts randomly scattered on it, and a sensor that can move in the direction across the width of the belt. I want to move the sensor to each part (if possible) as it comes along, then raster back and forth over the part for a while. The more time spent dwelling over the parts, and the less spent traveling between them, the better. Also the fewer parts missed altogether, the better.

I've looked on the web for solutions to the "Traveling Salesman Problem" and, more relevantly, the "Linear Ordering Problem", but what I've found was highly theoretical. Also, many of the computational methods people have used for those problems are too time-consuming. My belt moves fast. I need a rough-and-ready heuristic that gets not-too-horribly suboptimal results.

Is there any way to use Labview's Linear Programming optimization routine on this problem? Consider a three-part problem with parts A, B, C, and possible routes AB, BA, AC, CA, BC, CB. Could I impose contraints like 0 <= AB <= 1, 0 <= BA <= 1, 0 <= AB + BA + AC + CA <= 1, etc.? My problem is discrete, whereas Linear Programming is meant for optimization of continous variables, I think; but maybe that's OK?

Any help appreciated.

The best I can do is a little brainstorming. It occurs to me that you might get what you want from a vision system or a hybrid system. Maybe a low res camera could be used to send the sensor to the correct place for its more detailed work. I know that isn't what you asked for, sorry.

Mike

[LAVA 1.0 Content]

It was unclear to me what do you know of the system at runtime. The moving speed of the camera is probably known. How about the positions of the items, do you know it or do you have to use the cam to find the positions out? Do you know the number of items, the speed of the belt, the distance of the items along the belt or anything like that? The problem depends really on what you need to be able to do. If you have a very fast moving camera and you already know all the positions of all the objects, then you don't really need to do anything. Just hover above one item at a time for constant time and then move to next one. I assume however that this is not your case, so what is it?

[crelf]

Maybe a low res camera could be used to send the sensor to the correct place for its more detailed work.

You're right - the travelling salesman model is highly theoretical and I don't think it's actually what you're after in this case. I agree with the other guys: a cheap (~$1-2k) firewire camera and lens hooked into an IEEE-1349 card is your best bet. Allied Vision Technologies sells decent hardware at a good price (and they have a two week test drive programme), so as long as you've got some Vision experience and the NI-Vision toolkit, this job should be a cakewalk.

[LAVA 1.0 Content]

You're right - the travelling salesman model is highly theoretical and I don't think it's actually what you're after in this case. I agree with the other guys: a cheap (~$1-2k) firewire camera and lens hooked into an IEEE-1349 card is your best bet. Allied Vision Technologies sells decent hardware at a good price (and they have a two week test drive programme), so as long as you've got some Vision experience and the NI-Vision toolkit, this job should be a cakewalk.

If I recall correctly there was a LabVIEW OOP demo at NI Week on August about identifying objects using LabVIEW OOP. Maybe you can try to get the implementation of this demo into your hands, that may help you to identify the objects. Of course it may very well be that the demo really was just a demo with nothing real behind the scenes as it often is the case.

[crelf]

...identifying objects using LabVIEW OOP.

:thumbup: This would indeed be an excellent application for OO.

[torekp]

It was unclear to me what do you know of the system at runtime. The moving speed of the camera is probably known. How about the positions of the items, do you know it or do you have to use the cam to find the positions out? Do you know the number of items, the speed of the belt, the distance of the items along the belt or anything like that?

Actually there is a camera upstream already (forgot to mention that ) and I know the positions of the items, the speed of the belt, and the moving speed of the sensor. The sensor finds qualities of the items (namely, composition) that are not always visible to the camera. The only problem is to figure out the best order in which to visit the items. That more or less amounts to finding the path which minimizes total travel between items and the total number of items missed (with some relative weighting for importance). That's why I thought the Labview Linear Programming module might be helpful, because I have a large-dimensional optimization problem with constraints.

Here's a picture of a hypothetical belt, moving downward. The green lines represent the top speed of the sensor combined with the speed of belt motion; i.e. if you start at the bottom of a green line, you can move left or right only so fast. So for example, if you start at the bottom with the sharp-edged item, you'll miss a few items by the time you can move over to the left side. Or in the other green-lined example, if you have visited the upper-middle-right round item, you can't get to the sharp-edged item on the left.

So in this example, the thing to do would be to let the sharp-edged items go by, and visit all the others. Only, how to figure that out in the general case? Hope it makes more sense now. Thanks for your input.

[LAVA 1.0 Content]

Here's a picture of a hypothetical belt, moving downward.

If your problem is this easy, you should be easily able to use brute force to compute all possible routes and then choosing the best alternative. Start by dividing time into segments so that around 10 objects fits into one segment (I think brute force for ten is managable if not go to smaller number). For each segment determine all possible routes. The speed of your sensor limits the amount of possible routes quite a lot so you should't really get too many possible routes. You don't have to consider all possible routes, you can limit to those rotes where your camera either stays where it is or moves at maximum speed to either of the directions. In addition the movement between two objects can be centered in time so that the movement happens in halfway of the two object the sensor crosses. Below there is one example of such route.

If you then compute all possible this kind of routes using brute force for each time window, you get close to optimal route. You can optimize this route by allowing the windows to overlap so that in the middle of previous window you change strategy to the that of the next overlapping window. At the limit where the the temporal length of the window increases to infinity and the overlapping of two consequetive window is near to total you get best possible route, I think you get optimal existing route of all possible routes in the route-space.

If you want something more theoretical, try to check out this

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm