The Traveling Salesman Problem in Robotics



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 $^nC_2$ costs (corresponding to the $^nC_2$ 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 $^nC_2$ 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 $^nC_2$ =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.
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.


Last modified: Mon Mar 10 23:22:19 PST 2003