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

 

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info

 

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


AWS Adds Support For Llama2 And Mistral To SageMaker Canvas
12/03/2024

As part of its effort to enable its customers to use generative AI for tasks such as content generation and summarization, Amazon has added these state of the art LLMs to SageMaker Canvas.



GitHub Enterprise Server Adds Deployment Rollout Controls
11/03/2024

Version 3.12 of GitHub Enterprise Server, the self-hosted version of GitHub that organizations can install on their own servers, has been released with support for restricting deployment rollouts [ ... ]


More News

Last Updated ( Friday, 20 April 2012 )