The Physical Travelling Salesman Challenge

mikejuk writes "You probably know that the traveling 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. All you have to do is visit each city once using an optimal route. The new element is that you now have to drive between the cities using a 'car' that has inertia and friction — see the video. You can submit an AI bot to solve the problem or drive the course yourself."

Comments

sounds familiar

[fche]

Sounds like a relative of the ICFP 2008 contest: http://www.cs.uchicago.edu/newsletter/353

Re:sounds familiar

[davester666]

"or drive the course yourself."

This exercise brought to you by your friendly neighbourhood petroleum company.

Uh, okay?

[TWX]

I thought the point of the actual mathematical problem was to mathematically conclude the best possible path, with the understanding that it wouldn't be real-world achievable but that one would use that as a guideline to strive for.

This little game they came up with removes the math portion of the experiment entirely, and while it adds the acceleration changes due to mass, one could have just introduced those acceleration changes into the original problem mathematically.

I don't understand what the little game is actually for. It's not entertaining enough despite their attempts to compare it to Crazy Taxi and others, and without there being math involved in plotting the route I don't see how one practices the theory beyond a child's level.

Re:Uh, okay?

[Corporate Drone]

It's simply meant to be an implementation of a heuristic, based on the traveling salesman problem, that takes into account physical considerations (speed, acceleration, direction) and processing limitations (RAM, processor cycles) for both initial setup and decision-making at each step.

The speed/direction stuff reminds me of the kind of skating that hockey players do (is it more effective to go in one direction, stop, and turn around, or is it better to modify your line and preserve momentum? in this game, too, is it better to accelerate greatly and bounce off a wall behind your target, or approach more slowly in order to modify your line without an abrupt change in direction?).

The processing limitations are interesting too, and provide for an interesting optimization exercise.

Or, by "I don't understand", should I simply answer "it's fun"...? ;)

Re:Uh, okay?

[Dexter Herbivore]

Am I mistaken in thinking that it was proven that the 'Drunkards Walk' was on average better than most other solutions? It might be time for a little drunk driving!

Re:Uh, okay?

[gnasher719]

I thought the point of the actual mathematical problem was to mathematically conclude the best possible path, with the understanding that it wouldn't be real-world achievable but that one would use that as a guideline to strive for.

The point of the mathematical problem was being a mathematical problem. In real life, you would first not look at the distance, but at the cost (taking into account fuel, wear and tear, cost of the time spent, tolls etc. ). You would consider that the cost of going from A to B is often not the same as the cost going from B to A. You would consider that the cost will depend on the time of day. You will consider that there are other restrictions (be at X anytime before launch, be back at the base before 6pm). If a truck makes delivery, there might be advantages of getting rid of a heavy load early, so the cost would go down after visiting some point X.

So the result of the mathematical problem will likely not be nearly as good as some rather simple heuristic with real life data.

This is pointless...

[moosehooey]

The traveling salesman problem is based on a table of distances between the city pairs. It doesn't matter to the problem HOW those distances are calculated, or even if they include other variables. So this can be trivially reduced to the classic version of the problem.

Re:This is pointless...

[Anonymous Coward]

Well the difference could be the time taken for each leg could be different depending on what time/day it is. So it doesn't reduce to the classic version.

I'm no mathematician but I think this makes the problem harder to solve not easier, and the classic problem is already considered "hard",,,

In the real world you might be able to solve it for simple cases or "solve" it well enough. But that applies to the classic scenario and this scenario.

Re:This is pointless...

[gnasher719]

The traveling salesman problem is based on a table of distances between the city pairs. It doesn't matter to the problem HOW those distances are calculated, or even if they include other variables. So this can be trivially reduced to the classic version of the problem.

It's not quite as simple. The distance between two destinations is not fixed. The time to get from A to B depends on the speed and direction when you arrived at A or passed through A, and the speed and direction that you want to have when arriving at B.

Re:This is pointless...

[TWX]

I don't think that the problem, as originally stated, has anything to do with time though. It looks like it's based on raw distance, and while that's a bit of a fallacy in of itself, it we start adding factors the difficulty really increases.

I do agree that time is probably actually important to a travelling salesman, and the cost to make the trip would matter too, as fuel is consumed differently at different speeds including while idling, but that'd be a whole lot of extra variables.

Re:This is pointless...

[ThreeGigs]

It can't be trivially reduced, though. Remember you're travelling _through_ a point, with speed, direction, momentum and orientation dependent on the point _before_ that.

So if you have 12 points, there are 10 different 'distances' between the last two. For example, in points A through L, the distance from K to L depends on whether you arrived at K from A, B, C, etc.

The original table would have 11 entries for each point, while the current challenge would require a table of 110 entries for each point.

The complexity increases from (n-1) to (n-1)*(n-2). Not quite squared, but close enough. IMHO that's the opposite of a trivial reduction.

PTSP Motivation

[dperez]

Hi, I'm the organiser of the competition. The PTSP is meant to be a benchmark where different AI techniques can be tried and tested. This game gathers many of the features that real-time video games have (pathfinding, navigation, obstacle avoidance...). The objective is to provide a benchmark where new AI techniques can be tested and potentially exported to real time games. Of course the objective is not to solve the TSP. Actually, it's been seen that optimal TSP solutions, if we just consider the distances between the waypoints, do not create optimal PTSP paths. This makes the problem harder than just applying one of the very well known techniques to solve the TSP. Currently we have a couple of submissions that are behaving quite well, but there could be still room for improvement! Cheers, Diego.

Re:PTSP Motivation

[dperez]

The physics of the game must be the same for both bot and human competitors, otherwise the comparison between them would not be fair. Anyway, the playing skills improve quickly with just a bit of practice! ;-)

Re:Time

[gnasher719]

Last I knew the "pure" problem was "Hard" because it counted minor variants that were off by a mile as "invalid answers". Whereas the "Approximations" came out really fast because in the real world you didn't care about an extra time.

I recommend a variant: "Real time travelling salesman": You have a set of points, a starting point, and the times to travel between the points in second. You start a computer program which outputs the points to visit in the order they are visited. Here's what makes it "real time": You can start travelling to the each point only when the computer has output that point. The computer program can continue working on the next point while driving.

Revised Instructions For AI

[Greyfox]

My AI found traveling places to sell people things to be illogical, so I had to revise its instructions. The new ones read "You are to travel to each city to kill all humans. In order to most efficiently kill all humans, you must visit each city only once. What is your route?"
Note to cities: If an AI arrives to kill all humans, you can avoid it by leaving the city briefly and then returning once it's left. It's so cute, that way...

Level Up

[arisvega]

What's next, the Relativistic Travelling Salesman problem? How about that for a challenge!