The Traveling Salesman Problem in Robotics
Background
In the classical traveling salesman problem one is required to find an optimal or
sub-optimal tour through multiple targets/cities/goals.
For this one needs to know the cost of traveling between any two cities.
Hence there are
costs (corresponding to the
connections between n cities) to be known.
In robotics, to find the cost of traveling between two targets/goals for a robot,
one must first plan a collision-free path between them for the robot.
But finding
paths may be computationally very expensive in complex
environments.
For example in the path-planning environment
depicted in the rightmost figure above, the robot needs to find an optimal collision-free
tour through 50 target configurations. 50 targets corresponds to
=1225 path-planner
calls which can be very time consuming.
So is it possible to find a tour without explicitly calling the path-planner 1225 times?
The new multi-goal tour planner, GREEDY-MGP, is able to do that. For example in this
problem, GREEDY-MGP is able to find a tour with just 177 (vs 1225) path-planner calls.
For details see the
paper
which descibes GREEDY-MGP.
Planning Multi-Goal Tours in MPK
The multi-goal tour planner, GREEDY-MGP, has
been incorporated in MPK.
Try the following multi-goal planning examples. Press 'F7'
after executing these
commands to invoke the planner.
- ./prog/fmstudio ./scenes/mpkIrbCar.iv 1 2 3 4 5 6 7
- ./prog/fmstudio ./scenes/mpkIrbDrill.iv 1 2 3 4 5 6 7
Change '/' to '\' if executing from MS-DOS.
The general syntax is: "fmstudio < scenefile > < idx1 idx2 ... >".
For the above examples you would need to download additional workcell
geometries from the download page.
Publications
mpk@robotics.Stanford.EDU
Last modified: Mon Mar 10 23:22:19 PST 2003
