Coding Challenge - Proposal

[Jon_Kokott]

A classic AI problem might be fun;

How about a traveling salesman solution in LabVIEW?

Input would be a 2D array of distances simmilar to the old map charts simmilar to:

an array of strings the same width as the table with the location names

the outputs would be the ordered array of strings with the shortest route, and the total route length.

Output 1: Distance (u32)

200145 miles

Output 2: string array

{[madison, WI],[Chicago, IL],[New York, NY]}

I could make a test VI to access both performance and correctness of the route.

There should be plenty of examples in other languages to help with AI algorithms, the challenge will be more to labview-ize it and make the code efficent.

Let me know your thoughts!

[Craig_D]

Jon,  Great idea! Let's plan on making this the inaugural coding challenge to the Milwaukee UGM. If you're planning on attempting this, please post here. At the very least, we can run through some possible solutions and discuss varying approaches.  Regards, -Craig  PS to the rest of the Milwaukee UGM-you may have seen the sign up link for the next user group has been posted to ni.com/milwaukee. Look for an official invite from me shortly.

[Jon_Kokott]

I've attached a few things to help people get started.

This example "solves" the problem by guessing, then taking the best answer it got after a given number of tries.

Even a brute force method should be better than this, or atleast find the correct answer.

[Jon_Kokott]

Google Map Version:

This version will take some waypoints (hard coded on block diagram, you may change it) and retreive the distance matrix using the destinationmatrix API.

When its done, it will plot the route on google maps that you came up with.

Try not to go to crazy with plotting different routes, I have a quota on the google maps API and I don't want to commit a ton of money to this (there should be PLENTY for everyone, just dont let it automatically run over and over again.)

[doyles]

Is there going to be a standard matrix of cities and their relative distances that everyone should use?

[Jon_Kokott]

You will be provided with a matrix of locations.

It should not be necessary to have the same one to test your code at this point.  On Monday, I'll post some larger matrixes that you can try (in labview code format)

The day of we'll try a few different larger sized ones to assess their performance.

[Jon_Kokott]

I've attached some code that will generate official points that are comparable.

It uses a SHA algorithm to generate the points, as long as you use the same seed input string and it starts with a decimal number of items, the resulting grid will be the same.

[Kamal_Gupta]

Hey All,

Here is the solution that I presented at the last user group meeting using the Ant Colony Optimization AI method. You can read about the method here: https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms. This AI algorithm is well suited to path planning.

You can find the code for the Ant Colony Optimization within the project in the "Traveling Salesman.lvlib" library. This is a rough approximation of the algorithm - there's a lot of room for improvement. You can select the number of locations to visit, the number swarms (or troops) to send out, and the number of ants to randomly send out per troop. You can scroll over to the right to view the path. Scroll further to the right and you can view the best distance from each troop on a graph. It also shows you a comparison against the nearest neighbor method.

You can see from Troops vs Best Distance that as the software iterates on troops, it improves the path and shortens the total distance. You can set the number of troops and number of ants per troop to tune the algorithm. I also made some notes in the source code of other constants that could be changed to tune the algorithm. Like I said, there's plenty of room for improvement in how I implemented the algorithm but this is a start for someone trying to solve a path planning problem in LabVIEW.

The GUI uses my new Smooth Scrolling GUI Toolkit for LabVIEW. The SRSmoothScroll library enables you to create GUIs in LabVIEW that scroll smoothly in a way similar to what you would find on a cell phone or a modern application. You can download the complete VI package from www.sentrev.com/smoothscroll and try it out for yourself. It includes documentation and an example.

[jiwyi]

---

@Kamal_Gupta  已写:

Hey All,

Here is the solution that I presented at the last user group meeting using the Ant Colony Optimization AI method. You can read about the method here: https://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms. This AI algorithm is well suited to path planning.

You can find the code for the Ant Colony Optimization within the project in the "Traveling Salesman.lvlib" library. This is a rough approximation of the algorithm - there's a lot of room for improvement. You can select the number of locations to visit, the number swarms (or troops) to send out, and the number of ants to randomly send out per troop. You can scroll over to the right to view the path. Scroll further to the right and you can view the best distance from each troop on a graph. It also shows you a comparison against the nearest neighbor method.

You can see from Troops vs Best Distance that as the software iterates on troops, it improves the path and shortens the total distance. You can set the number of troops and number of ants per troop to tune the algorithm. I also made some notes in the source code of other constants that could be changed to tune the algorithm. Like I said, there's plenty of room for improvement in how I implemented the algorithm but this is a start for someone trying to solve a path planning problem in LabVIEW.

The GUI uses my new Smooth Scrolling GUI Toolkit for LabVIEW. The SRSmoothScroll library enables you to create GUIs in LabVIEW that scroll smoothly in a way similar to what you would find on a cell phone or a modern application. You can download the complete VI package from www.sentrev.com/smoothscroll and try it out for yourself. It includes documentation and an example.

---

Wow! The VI is fast, smooth and beautiful !