The Physical Travelling Salesman Challenge 59
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."
sounds familiar (Score:5, Informative)
Sounds like a relative of the ICFP 2008 contest: http://www.cs.uchicago.edu/newsletter/353 [uchicago.edu]
Re: (Score:2)
"or drive the course yourself."
This exercise brought to you by your friendly neighbourhood petroleum company.
Uh, okay? (Score:5, Insightful)
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? (Score:5, Informative)
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: (Score:3)
Re: (Score:2)
I'm picturing someone stumbling out of an '86 Lincoln Towncar with a labcoat and goggles saying "DON'T WORRY I AM A SCIENTIST AND I AM DOING SCIENCE!" *bluuuuuuuuuuurgh*
Re:Uh, okay? (Score:4, Insightful)
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.
Not the point, but game's still weird (Score:2)
You're misunderstanding the TSP - in the standard problem, the distances are known in advance, but there are n-factorial possible routes, so if n's large, you can't just enumerate all of them to find the best one, which makes it hard to tell if the best route you've found so far is actually the best. In the mathematical version, you can quickly verify whether any particular route is valid (hits all the cities, using valid roads between them), so in the real world you could drive that. (The only way you wo
This is pointless... (Score:5, Insightful)
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: (Score:2, Insightful)
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: (Score:3)
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:Time (Score:2)
It might get easier.
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.
Same thing here, while the classic problem bitches about the extra mile or not, in the real world, if you have one road with crushing traffic, many other solutions become better even if they are 5 miles longer. That's fairly true in my area.
Re: (Score:3)
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.
Re:Time or other costs (Score:2)
No. The reason the pure problem is hard is that there are N-factorial possible solutions, which becomes infeasible to compute if N is large, and there aren't any good algorithms known to find the optimal solution that are better than enumerating them all. The reason for approximation algorithms is to get a pretty good answer in a reasonable amount of computation time, and there are algorithms that can provably get you within X% of the best solution (50% back in the late 70s), but they don't tell you anyt
Re: (Score:2)
In the classical problem, it's a cost function. You can weight time, distance, and whatever else into the cost function, but at its basis is a table of costs to travel between cities.. the cost between any two specific cities may depend on myriad factors, but is constant between those specific cities..
Re: (Score:1)
Re:This is pointless... (Score:5, Informative)
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: (Score:2)
Re: (Score:2)
Re: (Score:3)
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 com
A good puzzle always looks easy. (Score:2)
The traveling salesman problem is based on a table of distances between the city pairs.
More technically the 'distances' in the table are a set of pre-set weights on each link in the graph, the TSP algrothim finds the path that has the lowest sum of weights from the finite number of possible paths between nodes. At first glance, it may appear that you can simply swap 'time' for 'distance' but the curvy line in the video I haven't played yet is a big clue as to why that won't work here.
It doesn't matter to the problem HOW those distances are calculated, or even if they include other variables.
True, but it does matter WHEN you calculate them, in the classic TSP the weights are predefined constants for
PTSP Motivation (Score:5, Informative)
Re: (Score:2)
Re: (Score:1)
Re:PTSP Motivation? (Score:2)
Why do you say that the optimal TSP solutions don't create optimal PTSP paths? If you're just saying that "we're using time as a cost function, and for physics reasons it's not a simple multiple of distance", that's fine, you still know all the physics in advance so you can calculate your cost functions in advance, and use them to solve the TSP. Also, the article doesn't say how large N is, so it's hard to tell from reading it whether there are too many destinations to use an exact TSP algorithm and you n
is it still NP-complete? (Score:2)
Or are the additional factors introducing changes, which make it easier to get the optimal solution (i.e because the optimal solution isn't always the shortest)?
Probably NP-complete, but there are ambiguities (Score:2)
First, the "PTSP" (somewhat misleadingly named, since it uses video game physicsrather than realistic physics) appears to rely on a planar Euclidean map, so it might best be compared to the Euclidean Travelling Salemsan Problem (http://en.wikipedia.org/wiki/Travelling_salesman_problem#Euclidean_TSP), which is NP-complete but susceptible to polynomial time approximations (and pretty good ones in practice, I think).
The right sort of graph for a TSP corresponding to a given PTSP map is probably based on a Hilb
Re: (Score:2)
Re: (Score:2)
NP-Complete = NP-Hard and NP (Score:2)
Plus confusion about which TSP version (Score:2)
We've spoken at cross purposes a bit. There are two things commonly referred to as TSP:
Both of these are NP-Hard. The definition of NP-Complete refers only to yes/no problems, so it can't be applied to number 1. But people commonly say that TSP version 1 is NP-Complete since version 2 is NP-Complete, and a solution to versi
Re: (Score:2)
i think you can always transform the optimization problem into the decision problem, by asking if there is an solution less than an arbitrary n.
The real question for a NP-hard problem is: Can it be solved by a non-deterministic turing-machine in polynomial time?
There are many Problems, which can not be solved in P, but cannot even be solved in NP, so you need to show it CAN be solved in NP, then its NP-complete.
Re: (Score:2)
The detailed technicalities get tricky here. Some things that we say in conversation (including the trained specialists) aren't quite right based on the official definitions, but we correct them automatically in our heads.
i think you can always transform the optimization problem into the decision problem, by asking if there is an solution less than an arbitrary n.
Every optimization problem (such as my TSP 1) can be turned into a decision yes/no problem (such as my TSP 2) as you describe. The optimization problem is always at least as hard as the decision problem. But in principle the decision problem may be much easier. I don't have an example in m
Re: (Score:2)
i think, the decision problem can be much easier in some cases, but the crux is, you can always construct a counter example for each shortcut-version.
the problem of solving a optimization with decisions depends on the output you want to get. solving the exact optimization on the reals with a decision tree is not possible, but finding the least integer is simple with a NDTM, you just try each integer and your NTDM will solve the problem after m iterations, when m is the solution.
But as you already said, this
Travelling Salesman? (Score:1)
Just go to Amazon.com [amazon.com] instead. Problem solved!
What just happened? (Score:2)
Revised Instructions For AI (Score:3)
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...
It's been done (sort of) (Score:2)
where the objective is to direct the agent to visit all waypoints scattered around a map as quickly as possible.
http://en.wikipedia.org/wiki/Cannonball_Baker_Sea-To-Shining-Sea_Memorial_Trophy_Dash [wikipedia.org]
Screw the math stuff... (Score:2)
...I want a car that doesn't have friction or inertia. 0 to 60 in 0.0 seconds!
sign up (Score:1)
why do i have to SIGN UP for everything? So annoying.
Can we have a standard that there ALWAYS exist a username / password:
username: johndoe
password: johndoe
That way, I can try out these services without wasting my time to sign up.
Few days ago I was trying to download some demo of an application and it required me to sign up. So, I typed in "johndoe" for the username and was notified that that user already exists. I then (randomly) tried to login as johndoe / johndoe and it worked! I was able to download the
Level Up (Score:4, Funny)
What no farmers' daughters? (Score:2)
I always thought they figured into the travelling salesman problem.
In fact, I thought the were the point.
who is the moron that made it MUST LOG IN (Score:1)
wtf?
why everything needs an email and a user and a password.
Fuck off, im not interested in pests.
btw, thank you slash dot for not requiring user name and password.
MIT Hack Turns the Green Building Into a Giant Gam (Score:1)