11-19-2021 09:32 AM - edited 11-19-2021 09:35 AM
I am working with a laser machine. I'm having trouble aligning its coordinates. Right now I'm getting an array of coordinates to get the laser to work on but it's not properly arranged making the laser machine a waste of time to run. My job now is to rearrange the coordinates so that they work smoothly and with the least amount of time and I think near the origin (0,0) is the way to solve this problem. I have an idea like the 2 pictures below, it will help me optimize the running time of the laser machine, but I don't know any algorithm that can do that. Can anyone who has experience with this issue give me some advice.
Thank you for reading my thread!
11-19-2021 09:58 PM
I'm not sure I understand the question(s) you are asking. It seems to be that you are thinking about "optimizing" your "scan algorithm" before developing (and testing!) an algorithm. If you can't make the laser do a scan, then you can't make the laser to "a better scan".
Here are a few observations (made, I'll confess, without my writing any code, nor doing any tests, just "off the top of my head". I'll call the first scheme you proposed "rectangular", and the second "diagonal".
Just from a standpoint of "simplicity", there seems (to me) to be no contest. One algorithm is very simple to code, seems more efficient, Why don't you try writing some test code, one that creates an XY Graph connecting a 6 x 6 set of "dots" with line segments, and see if you can simulate moving your laser. Use the following rule every 0.1 sec, move the X and/or Y coordinate in steps of 0.1 (so the line moves from (1, 1) to (1. 2), or to (2.1), or to (2, 2) in 1 second. Now you can "see the path of the laser" and try out your algorithm(s). Which is easier to code?
Note that writing a little LabVIEW program that simulates a physical system (like a Laser and a "2-D Positioning System) is the ultimate "Virtual Instrument Engineering Workbench" output.
Have fun.
Bob Schor
11-20-2021 11:13 AM
The most efficient is the top (A), because the total travel is 35 units. each step is the same size and corresponds to the closest possible distance.
In your bottom example (B), the total distance is slightly more than 45 units and thus about 30% longer. Since you also need to move both x and y for most steps in B, the peak power requirement is higher. Depending on the encoders used, you might also get more error accumulation.
11-21-2021 09:34 AM - edited 11-21-2021 09:44 AM
I guess, the laser is used as drill at the drawn points?
Now, it depends on how fast the laser can move in which direction. Let's say it's mounted on one axis per direction, and can move with the same speed along each axis. If both axes are moving at the same time, the laser moves diagonally at a higher total speed. Finally, the time it takes to move from (0|0) to (0|1) is the same it takes form (0|0) to (1|1).
This means, though path B is longer than path A, the time is exactly the same, since in both cases, there are 35 connections between direct neighbor points with horizontal / vertical / diagonal segments.
Finally, each path connecting all points this way without points being visited twice will take the same time.
Depending on your process, it may be good if the last point is next to the first, so the laser has to move as little as possibe at the end, which reduces time until the next part can be processed.
If, on the other side, one axis is faster than the other, the faster one has to be throttled for diagonal paths, and the rule is not valid any more. In this case, the laser should move mostly along the faster axis, like path A, if the vertical axis is faster.
What about wear?
In path A, the laser moved 30 steps vertically and 5 horizontally (plus 5, if the laser has to move back to the origin)
In path B, there are 27 vertical and 30 horizontal steps, if I counted correctly (plus 5 for each)
So, Path A means less "milage" for the axes.
Edit:
This path has just one diagonal segement (higher wear), and the last point is next to the first one:
11-23-2021 05:22 AM
This is the classic travelling salesman problem:
artificial intelligence - Algorithm: shortest path between all points - Stack Overflow
11-23-2021 11:33 AM
The traveling salesman problem assumes no symmetry and is very general with N points scattered randomly and requires a trip back to the origin at the end. This gets very hard fast.
In a square grid, all neighbor distances are equal. A much simpler problem. I could not find a requirement to return to the origin at the end. In fact the pattern can be rotated for successive rounds such that the old endpoint is the new origin.
11-24-2021 02:33 AM
@altenbach wrote:
The traveling salesman problem assumes no symmetry and is very general with N points scattered randomly and requires a trip back to the origin at the end. This gets very hard fast.
In a square grid, all neighbor distances are equal. A much simpler problem. I could not find a requirement to return to the origin at the end. In fact the pattern can be rotated for successive rounds such that the old endpoint is the new origin.
It's still a np-complete problem.
It's worth the time to look what has been done. Hamilton path, Hamiltonian graph, solid grid path, etc. seem to give good results.
For instance np - Polynomial-time algorithm for travelling salesman in a grid (this one does return to 0,0).
This isn't a LabVIEW problem. I'm sure we'll still (try to) help, simply because it's fun.
11-24-2021 03:53 AM
Hi!
True, however, this problem is much easier.
On the other side, I made several real world assumptions for which we do not know if they apply here. Without that, we can't give a definite answer.
11-24-2021 12:50 PM
wiebe@CARYA wrote:
For instance np - Polynomial-time algorithm for travelling salesman in a grid (this one does return to 0,0).
But that assumes that even though there is a grid (limiting the choices to a max of 4 unvisited neighbors for each leg of the trip), the cost of traveling between adjacent pairs can differ, and maybe even depend on direction. In our problem, the cost is the same for all closest distances. Much simpler.
11-25-2021 03:04 AM
@Sebastian.Weber wrote:True, however, this problem is much easier.
I'm all for simpler and easier...