The Physical Travelling Salesman Challenge
Written by Alex Armstrong   
Friday, 20 April 2012

You probably know that the travelling salesman problem is one of the classics of computer science theory. Now we have a new challenge - the Physical Travelling Salesman Problem and anyone can join in.

The Physical Travelling Salesman Problem (PTSP) is really a lot of fun. The idea is similar to the original Travelling Salesman Problem - you simply have to visit each city or point in turn and travel the smallest distance. The "physical" in the problem's title is due to the extra difficulty of actually driving a vehicle around the course.

In this case the vehicle is simulated and obeys a simple set of dynamical rules - it has both friction and inertia to deal with. As a result you can't just move in a straight line from one point to the next. You have to steer your way round the course allowing time to decelerate and swing around corners.

 

ptspship

 

There are two competitions you can enter - a human solution or a bot-based solution. For the human competition you simply sign in to the site and start steering the ship.

For the bot version you have to design a program that does the same job. The coding is done in Java and all you have to do is provide a list of actions selected from six possible actions to steer the "ship" around the course. The ship can collide with obstacles and the objective is to complete the journey in the minimum number of steps.

To quote the website:

The PTSP was first introduced as a competition at the Genetic and Evolutionary Computation Conference (GECCO) in 2005. Compared to the TSP, the PTSP adds some interesting challenges over the standard TSP. For a given number of waypoints, PTSP solutions are much longer. For example, a 10 waypoint map may require a sequence of several hundred actions (force vectors) to solve it. Furthermore, the length of the optimal sequence is unknown in advance.

If you watch the video, you can see a human solution to the problem and stand a good chance of getting hooked on the challenge - so you have been warned!

 

Both the human and bot competitions have leader boards and it will be interesting to see if bots do better than humans - of course they will. You have to solve 20 maps and the software is all easy to download and use. As the number of maps seem to have a small number of points to visit, most of the difficulties in the algorithm will be about plotting the course and this suggests some sort of dynamic programming, optimization, genetic algorithm etc, is most likely to be successful.

 

PTSPgame1

 

The human competition runs to May 7th and the bot competition starts its final trials on the May 27th 2012.

More Information

The PTSP Competition

Related Articles

The Genetic Algorithm

 

blog comments powered by Disqus

 

To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.

 

Banner


DevArt Exhibition Now Open
05/07/2014

Google's DevArt is now on show at London's Barbican Centre as part of  Digital Revolution, the biggest exploration of digital creativity ever staged in the UK.



Microsoft's Android Patents Found Wanting
16/07/2014

After details were revealed of the  Android Patents that Microsoft uses within licensing deals with handset manufacturers, a report casts doubt on the validity of many of them.


More News

Last Updated ( Friday, 20 April 2012 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.