Agents learn from traveling salesman
By Eric Smalley, Technology Research NewsIt looks like the traveling salesman of old and the software agent of the future have something in common.
The classic traveling salesman problem of finding the most efficient route for a trip through several cities is the epitome of combinatorial optimization, a class of problems based on finding the best combination of a finite number of elements.
One traveling salesman-type algorithm, developed by Weixiong Zhang of Washington University, might improve how intelligent agents make decisions on the fly. Agents, and in particular multiagent systems, are becoming an increasingly important part of the Internet.
Combinatorial optimization problems are difficult because there is no formula for solving them exactly. Every possibility has to be examined in order to find the best solution and the number of possibilities increases exponentially as the size of the problem increases: for a traveling salesman passing through 15 cities there are billions of possible routes. Combinatorial optimization software is used for a wide range of problems, from laying out circuit boards to scheduling flights to analyzing genes.
Zhang has applied his algorithm to a scheme designed to make the most of the limited computational resources in multiagent systems. Agents are small pieces of software that traverse the Internet seeking out information or performing tasks on behalf of people or larger computer systems. They make decisions based on information they find or interactions with other agents. Multiagent systems acquire information from and coordinate the actions of many agents.
Zhang's scheme first simplifies combinatorial optimization problems so the algorithm can quickly find an acceptable, though not necessarily optimal, solution to the original problem. Then, using this solution as a starting point, it continues to repeat the process in an effort to get better solutions.
The Zhang algorithm searches through every possible route in traveling salesman-type problems, but discards a new route without following it all the way as soon as it becomes apparent it is longer than the best route already found.
The algorithm is designed for the more challenging versions of the traveling salesman problem that take into account one-way segments. "The distance... from city A to city B is not necessarily the same as the distance from B back to A," said Zhang, an associate professor of computer science at Washington University.
The algorithm can stop at any time and yield an answer. The longer the algorithm runs, the better the results, and the algorithm eventually finds the best solution. This approach allows for a trade-off between computational resources and the quality of the solution. "I just stop whenever I run out of time for the algorithm or I reach a point [where] I think that the quality of the solution I have at hand is good enough," said Zhang.
This type of approach works well for multiagent systems, which typically have limited amounts of time and computational resources and have to solve complicated problems that couldn't be anticipated by the agents' designers. For example, some multiagent systems monitor prices and negotiate transactions, all without the individual agents duplicating efforts or working at cross purposes.
"A lot of the traditional design strategies won't work [for multiagent systems]," said Zhang. "The traditional design strategy is you consider all the parameters and design the system that can meet those requirements. Since the problem I'm looking at is so dynamic, a lot of parameters won't be [known] until you run the system," he said.
The algorithm at the heart of Zhang's scheme simplifies the optimization problem considerably, said Jeremy Frank, a computer scientist at the NASA Ames Research Center. "Still, in the worst case, you have to look at a sizeable fraction of all of the possible orderings, and you still can't solve really large problems."
One drawback to the algorithm is that it is difficult to determine how close any solution is to the best solution, said Frank.
Other approaches use random samplings of possible solutions. They "may not be able to guarantee that the best solution is found after a finite amount of time, but [they] tend to get slightly better results faster," said Frank. "Thus, Zhang's approach could be viewed as a somewhat more conservative approach to [algorithms that can be stopped at any time]: guranteed results if sufficient time is spent, but generally it requires more time to get good solutions."
There are no technical hurdles to using the Zhang combinatorial optimization algorithm for practical applications, Zhang said.
Zhang published his work on simplifying optimization problems in the February, 2001 issue of Artificial Intelligence. The research was funded by the Defense Advanced Research Projects Agency (DARPA) and the National Science Foundation.
Timeline: Now
Funding: Government
TRN Categories: Data Structures and Algorithms
Story Type: News
Related Elements: Technical paper, "Iterative State-Space Reduction for Flexible Computation," Artificial Intelligence, February, 2001
Advertisements:
February 14, 2001
Page One
Quantum effect moves machine
Software speeds gene comparison
Agents learn from traveling salesman
Harder chips make more sensitive sensors
Silver atoms shine red and green
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
