Pathfinding: Balancing Shortest Path with Closest in Z

Hi,

I’m working on a deposition fabrication project where I need to parse through 4000+ points as close to possible by ascending Z-height. At the moment I’ve just sorted the list by Z but it’s adding significant of travel time to the robot as it has to move between targets quite far away from each other.

I tried a different method by basically breaking up the list of points into partitions based on Z but the divisions that creates are problematic as many points sit underneath previously deposited ones.

I’m happy to lose bit of fidelity to exactly following Z-height to instead chose the next point closest in distance and in height, perhaps a 50/50 split? Does anyone have any ideas on how to implement this?

Kind regards,

Chris


1 Like

2000 points:

2 Likes

Joseph’s solution is the best you can get considering programming time and computation time.
Otherwise you will have to use some code

Hi Joseph,

Thanks for taking a look and that’s an interesting approach. I think the only problem is that I wasn’t clearer in my original description. As this is an additive robotic process, I can’t build things up in columns like that but more like this:

It’s kind of like in rough ‘layers’ except that not 2 points are exactly at the same height. I’m looking for something that will take one point, check maybe the closest 5 points around it and then pick the one closest in Z. Actually, now that I think of it I might have a go doing this with an Anemone loop. Though it might take a while for so many points.

C

I am still not 100% clear about your logic here:
Is it necessary that every point should be passed by robot?
If so, loop is not enough.

Yes, each point represents where some material needs to be deposited by the robot.

I’m trying a loop now just because I’m interested. I’ve done shortest path before. But yes, I agree it’s more difficult than that because it’s the travelling salesman thing +/ smallest incline. I found this person implementing something very similar with Galapogos but in my experience Galapogos needs a lot of time and I need it to work on 4K+ points.

Edit:

Yes, no good. My silly little loop doesn’t really work.

loop2

Hey! I changed the loop into this which reduces the travel time overall by 85%. Not bad!

1 Like

I think this is a really interesting problem.

The question of loop is that if every path finds its “own” best way. There will be no guarantee that all poins are passed, some point just leave there because no path is “interested” in it.

I recommend Joseph’s approach because it ensures that all points are passed by robot path. and every points got only passed by once, efficient.

By the way, is it OK that 2 pathes cross the same point? If so, I think shortest walk like Floyd would be best.

Here is an example:
I think your goal is “total path length” mininum.
In the picture the middle plan is better than the right one because it only has 138mm total path length.

Find one slope rate, here I use K=3 that seemed fits the situation. the K can be user specified or from some calculation.

The green line here is a K=3 line and I sweep the line from upper left corner to lowe right corner (green arrow), the first point the green line meet is our start position (red arrow).
To turn the geometry algo to GH calculation, you can use something like Max(3x-y) to find the most “upper left (K=3)” point.

Since we have defined K=3, we can draw a cone like shape, with K=3 and K=-3
Put the cone in our start point (red point) and pickup all blue points inside the cone.

From all these blue points, choose the most upper left (K=3) one just like before (green point), that is our 2nd point.

Repeat the process until there is no point left in the last cone (red cone)
In this case one path is finished. All points in this path should be labeled “Done” or something like that.

Repeat the same process, but exclude all points that is labeled “Done”: Find the 1st point using Max(3x-y), draw a cone, pick the points inside the cone, find the Max(3x-y) point in the cone, connect the path to that point, and so on.
Until no points can be found in the last cone, 2nd path is done.

As you can see, instead of the previous length 138mm which is draw by my feeling, this time I got 134mm because an algorithm is implemented.

This is just a very rough algorithm, something like greedy algorithm.
I am sure you can do better.

I hope this helps.

Good luck!

I almost forgot.
To reduce calculation time, we should use number calculation as possible instead of geometry one.
In 3d problem, we will have to draw an actual 3d cone and determine whether a point is inside the cone or not, instead of using Cone geometry and Point in brep component, we can use something like:

2 Likes

Yes, that always makes it a guessing game. At the very least, posting your geometry would also help.

I wrote an Anemone loop yesterday to do something similar to what you describe but abandon that approach because I wasn’t clear about your constraints. Re-constructing code from screen shots is a silly and error prone waste of time.

When someone apologies I don’t believe it’s generally the best idea to attack them afterwards in my experience, but that’s a decision for everyone to make on their own.

A 3dm file would be really really nice and helpful.
Honestly I still do not understand why you hadn’t upload them until now. Probrably something related to confidential info?

Yes, that is correct. The reason why I still thought it was worth posting because any method that worked on an arbitrary list of points coming from a Populate3D node would also work in the project context.

One of a trick that could help to make things more directional is a non uniform scale on z or x and y. So you could use classical tools.

Hi Laurent, thanks for offering some help too. If you can could you extrapolate a bit on what you mean? I’m not quite sure exactly what you mean about non uniform scaling?

x scales 0.5 and y scales 0.8
x != y that is non uniform scale

1 Like