For an interactive installation in which I’m using a custom built cnc machine I have the need to optimise the path that the head of the machine travels along a set of points (~250) in order to minimise the travelled distance (and so, time).
TLDR: given the points that you see what’s the shortest computable path?
I know that this is basically the TSP problem, so not really solvable, but I don’t need the best solution, but just one that it’s better than default one that I’m using (which goes in the way that points are added in my vector, so basically left to right and top to bottom)
I tried looking into A star (a*) and Dijkstra’s algorithm, but none of them seem to be good for my problem, since in my graph every node can possibly be connected to every other node, and I also want to find my start and end point.
I found this answer on math.stackexchange, which is not very helpful but at least it’s a start:
Does any of you have a hint on the approaches to take?
I need to compute this calculation only once and it should take max 5 seconds, since the app is realtime.
(that’s why I’m currently avoiding genetic algorithms)
Thanks @seb_ly, I was already trying a nn approach but I had some bugs so I’ll go back to it.
Also, I found some old addons already tackling this problem, I’ll test them and update this post if they work ok.
I’m pretty sure I checked both of these out, ofxTSP is brute force so can get VERY slow, I don’t quite remember what I discovered with ofxLaserTSP but I’m not sure it does anything more than NN - I could be wrong though, let me know if you figure it out.
Yes, after giving them a try I can say that you’re definitely right, @seb_ly!
I made a quick search on GitHub and I found this C++ implementation of a genetic algorithm optimised to solve tsp.
Seems pretty fast so for the moment I’m using this one.
I’ll compare the results with a nn approach and post back if there is any substantial difference.
To be honest, I glanced through the code of ofxTSP and I saw it was doing some brute force stuff so I quickly tried to compile it but since it didn’t (I’m using 0.10) I basically gave up and started looking for something more optimised.
I’ll try to do a benchmark using genetic algorithms versus nn as soon as possible, currently my brain is fried and can’t seem to properly code the nn version, but you can find my current code here: https://github.com/vvzen/maca-final/tree/master/shortest-path-test
Ok, I think I’ve managed to write a first rough nn approach.
Given for granted that I’m doing everything right (which may not be) these are the results so far (distance is expressed in mm):
So it seems that either nn or a ga are pretty similar. Of course the genetic algorithm approach heavily depends on the population size, number of generations and mutation rate, so tweaking these values can produce quite different results.
I basically load the points from a csv, the nn stuff starts at line 81 of ofApp.cpp.
I’m also posting the nn extract here:
// 1. Start on an arbitrary vertex as current vertex
int closest_p_index = 0;
glm::vec2 p = points.at(closest_p_index);
// continue while there are still points to visit
while (points_nn_path.size() < points.size()-1){
glm::vec2 p = points.at(closest_p_index);
ofLogNotice() << " points_nn_path: " << points_nn_path.size() << ", points: " << points.size();
float min_distance = 20000.0f;
for (int j = 0; j < points.size(); j++){
glm::vec2 other_p = points.at(j);
// check if we already have visited the other p, if so, just skip it
if(std::find(points_nn_path.begin(), points_nn_path.end(), other_p) == points_nn_path.end()) {
// 2. Find out the shortest edge connecting current vertex and an unvisited vertex V
float current_distance = ofDist(p.x, p.y, other_p.x, other_p.y);
if (current_distance < min_distance && current_distance > 0){
min_distance = current_distance;
// 3. make this point the next point
closest_p_index = j;
// 4. add it to the visited points
points_nn_path.push_back(other_p);
}
}
}
}
// compute distance of nn
for (int i = 0; i < points_nn_path.size()-1; i++){
auto p = points_nn_path.at(i);
auto next_p = points_nn_path.at(i+1);
nn_distance += ofDist(p.x, p.y, next_p.x, next_p.y);
}
Ah yes, there were a couple of flaws in your implementation, I think I’ve fixed them… let me double check and get back to you… but here are the results.
Wow @seb_ly that’s awesome! Way better than any genetic algorithm! If you want, feel free to make a pull request or just post the code here. Thank you so much!
thanks! I’ve made a pull request but the code is here for anyone else following along :
// 1. Start on an arbitrary vertex as current vertex
int closest_p_index = 0;
glm::vec2 p = points.at(closest_p_index);
// continue while there are still points to visit
while (points_nn_path.size() < points.size()-1){
glm::vec2 p = points.at(closest_p_index);
ofLogNotice() << " points_nn_path: " << points_nn_path.size() << ", points: " << points.size();
float min_distance = 20000.0f;
for (int j = 0; j < points.size(); j++){
glm::vec2 other_p = points.at(j);
// check if we already have visited the other p, if so, just skip it
// NB using this technique, duplicate points will be removed.
if(std::find(points_nn_path.begin(), points_nn_path.end(), other_p) == points_nn_path.end()) {
// 2. Find out the shortest edge connecting current vertex and an unvisited vertex V
float current_distance = ofDist(p.x, p.y, other_p.x, other_p.y);
if (current_distance < min_distance && current_distance > 0){
min_distance = current_distance;
// 3. make this point the next point
closest_p_index = j;
// but don't add it to the list until we've checked all the points against the first!
}
}
}
// now we can add it to the list of added points:
glm::vec2 other_p = points.at(closest_p_index);
points_nn_path.push_back(other_p);
}
The issue was that you didn’t finish iterating through the nested loop before adding the point to the list.
(sorry I just realised that Xcode used tabs instead of spaces which the rest of your code seems to use…)
Hi,
I know nothing about TSP, but I was curious to see if there is a simple way, during the path construction, to not ignore some close points at the cost to travel back to them later. Here’s what I mean:
Ignored points that require to travel a long distance to reach them:
A better result:
So I tried to modify a little bit the NN approch: the new point to add to the path is not the closest to the latest added one, but the closest to the mean of the 5 (for example) latest points already added.
Most of the time, this new approach doesn’t give better results: the generated path is longer than with the simple NN construction. But I share my experiments with you, because depending on the goal it can still be interesting sometimes, for aesthetic reasons. And also because I feel nice to play with
Here’s the source of the app that I made, based on yours, it now allow to edit the points: src.zip (3,3 Ko)
and my new solver:
void ofApp::solve_mean_nn( const vector< glm::vec2 > & in_points, vector< glm::vec2 > & out_points, size_t startIdx )
{
out_points.clear() ;
out_points.reserve( in_points.size() ) ;
if( in_points.size() < 2 ) return ;
// Add the first point to the path
out_points.push_back( in_points.at( startIdx ) ) ;
// Build a list of all the points that aren't included in the path yet
deque< glm::vec2 * > rest ;
size_t i = 0 ;
for( auto & p : in_points )
{
if( i++ != startIdx ) rest.push_back( const_cast< glm::vec2 * >( &p ) ) ;
}
// This is the mean of the last num_points_for_mean added to the path
// At the beginning we have only one point in the path
glm::vec2 mean = out_points.back() ;
size_t meanSize = 1 ;
// An iterator to the oldest point to consider for the mean
auto meanTailIt = out_points.rend() ;
// Loop while there are points not yet included in the path
while( ! rest.empty() )
{
auto end = rest.end() ;
auto best = rest.begin() ;
float min_distance = numeric_limits< float >::max() ;
// Loop over the points that are not included in the path to find the closest one
for( auto it = rest.begin() ; it != end ; it++ )
{
float distance = ofDistSquared( ( *it )->x, ( *it )->y, mean.x, mean.y ) ;
if( distance < min_distance )
{
min_distance = distance ;
best = it ;
}
}
// Add the closest point to the path
out_points.push_back( **best ) ;
if( meanSize < num_points_for_mean ) ++meanSize ;
// Advance the oldest point to consider for the mean
else meanTailIt-- ;
// Compute the mean of the lastest points in the path
mean.x = 0 ;
mean.y = 0 ;
for( auto it = out_points.rbegin() ; it != meanTailIt ; it++ ) mean += *it ;
mean /= float( meanSize ) ;
// Remove the closest point from the list of the points not yet used
rest.erase( best ) ;
}
}
Thanks for all of these tests, @lilive!
Interesting twist to the good old nn approach. It seems to work better with less points taken into account for the average. I think there’s a very good potential for many creative discoveries!
