Analyzing Dynamics That Can Choke Supercomputers

http://www.computerworld.com/printthis/2005/0,4814,106722,00.html

Getting Real:

Analyzing Dynamics That Can Choke Supercomputers

Researchers find ways to tame the complexity in real-world reasoning

Future Watch by Gary H. Anthes , DECEMBER 05, 2005 (COMPUTERWORLD) -

It is surely one of the more mind-blowing PowerPoint slides ever created. It's a graph, and one of the smallest numbers, near the bottom of the vertical axis, is 10¹⁷, the number of seconds from now until the sun burns up. Then comes 10⁴⁷, the number of atoms on Earth. After that, the numbers get really big, topping the scale at 10 ^301,020.

This graph, from the Defense Advanced Research Projects Agency, shows the exponential growth in possible outcomes for a range of activities, from a simple car engine diagnosis with 100 variables to war gaming with 1 million variables (that's what the 10^301,020 represents).

The point DARPA is trying to make in explaining its Real-World Reasoning Project is that computers will never be able to exhaustively examine the possible outcomes of complex activities, any more than a roomful of monkeys with typewriters would ever be able to re-create the works of Shakespeare. But in the recently completed Phase I of the Real Project, as it's called, the agency did discover shortcuts that can tame the punishing combinatorial complexity that for decades has stymied efforts to model the real world.

Beyond Brute Force

Bart Selman, a computer science professor at Cornell University and one of three DARPA contractors on the project, points out that for a decade there have been automated reasoning tools that can discover defects in chip or software designs. These tools can "prove" the correctness of a specification without exhaustively testing every situation the chip or software might encounter.

But those tools can do only what's called single-agent reasoning. Selman is extending the concepts to a much harder class of problem -- multiagent scenarios in which there's one or more opposing forces -- and he's developed chess-playing software to test his ideas. The best chess programs today, such as IBM's Deep Blue, excel by brute-force trials of moves, analyzing millions of board positions per second. "Deep Blue explores hundreds of millions of strategies, but most of them are very dumb," Selman says. "Grandmasters only explore three or four possible lines of play."

The Cornell chess program works more like a grandmaster, he says. "It might exploit certain strategies, then find they are not successful. It learns from that and adds that to its knowledge base. It gets better the more games it plays, even during a single game," Selman explains. It develops a conceptual view of the board and seeks out overall positions that will give it strength.

By applying these learning techniques and other improvements over traditional reasoning tools, Selman's team has so far achieved a 10⁹ speed improvement over those tools, he says.

While Selman works on two-agent systems like chess, researchers at SRI International in Menlo, Park, Calif., are looking at games with four or more agents. That lets them include the dynamics of partnerships and coalitions often found in real-world conflicts.

Patrick Lincoln, director of the nonprofit's Computer Science Laboratory, has applied a "model checker" that's normally used to prove out semiconductor designs to a four-player variant of chess and to Diplomacy, a seven-player board game set in Europe just before World War I.

Lincoln developed an algorithm that can find the "Nash equilibrium" in a game, a point at which no player can deviate from his strategy without harming his outcome. Once that's been determined and the strategies of all the players are known, the model checker can find the best tactical moves given the various partnerships that have evolved. "This is a major computational challenge," Lincoln concedes.

Like Selman at Cornell, Lincoln has used model-checking techniques to mathematically prune the combinatorial tree. "We are doing it symbolically, in a way we don't have to exhaustively look at all the cases," he says.

Meanwhile, researchers at the University of California, Berkeley, are introducing notions of uncertainty into automated reasoning. They are modeling Kriegspiel chess, a variant of the game that the Prussian army used in the 19th century to train its officers. In Kriegspiel chess, neither opponent sees the pieces or the moves of the other, so each works only with information that's been inferred from the consequences of his own moves.

Stuart Russell, a computer science professor at Berkeley, says his team has come up with search algorithms that are 100 to 1,000 times faster than earlier methods for this kind of problem. Some can find solutions directly, without trying all possibilities. He says his techniques could one day be used in applications dealing with real-world situations whose dynamics are only partially observable, such as negotiations, management of traffic flows or supply distribution systems.

"With these technologies, one might create a logistics decision-support system that could, for instance, consider the likelihood of future events such as a natural disaster, and factor the event, and its implications, into the logistics process," says Tom Wagner, DARPA's program manager for the Real Project. "That same logistics system could also reason about the value of forming a relationship with another company, possibly even a competitor, as a way to improve the response to that disaster."

In the next phase of the project, not yet approved by DARPA, SRI will scale up the tools to handle more complex games with more players, Lincoln says. "The exponentials are so terrifying," he says. "The only way to make progress is to tame them algorithmically."

http://www.msnbc.msn.com/id/11829347/

DNA folded into a world of patterns

Origami method could be used for nano-computers and more

Slide show

• DNA origami A new molecular-scale construction technique can be used to create some pretty funny nano-shapes.

By Alan Boyle

Science editor

MSNBC

Updated: 1:17 p.m. ET March 15, 2006

Alan Boyle Science editor • Profile • E-mail

A computer scientist has developed a method to weave stringy DNA molecules into nanometer-scale, two-dimensional patterns ranging from smiley faces to a map of the Americas.

Experts say the "DNA origami" procedure laid out by Paul Rothemund of the California Institute of Technology could be adapted to create nano-computers, new drug delivery systems or even molecular-scale chemical factories.

"We are arriving at a new frontier in our pursuit of ever-smaller structures," Lloyd Smith, a chemist at the University of Wisconsin at Madison, said in Thursday's issue of the journal Nature, where Rothemund's research was published.

In a news release, Rothemund said the process is so simple that high-school students should be able to design woven DNA patterns, but so versatile that scientists could build complex structures for a wide variety of nanotechnology applications.

"A physicist, for example, might attach nano-sized semiconductor 'quantum dots' in a pattern that creates a quantum computer," he said. "A biologist might use DNA origami to take proteins which normally occur separately in nature, and organize them into a multi-enzyme factory that hands a chemical product from one enzyme machine to the next in the manner of an assembly line."

Rothemund's technique uses chemicals to twist a long, single-stranded DNA molecule into a predetermined shape, then "staples" the scaffolding together with crossover strands. For the experiments reported in Nature, Rothemund used the genome from a bacteria-destroying virus called M13 — well-suited as weaving material because its 7,000-nucleotide sequence has been fully decoded.

An army of smileys
To demonstrate the technique's versatility, Rothemund created a variety of fanciful shapes, including stars, tilelike octagons that look like lace doilies, and squares of carpet with the letters "DNA," a double helix or the rough shapes of North and South America woven into it. The shapes range around 100 nanometers wide, about 1,000 times smaller than the diameter of a human hair.

One atomic-force microscopy image shows myriads of smiley faces bunching up under the microscope — which Smith called "a disconcerting sight."

Smith noted that the technique could allow for dyes or attachment points to be woven into the patterns. That could turn the origami patterns into "nano-breadboards" that would serve as the basis for molecular-scale circuitry.

Rothemund and other researchers are working to extend the 2-D origami technique to 3-D structures as well. If they're successful, that could lead to the development of 3-D molecular "cages" to hold enzymes or drug molecules. The tiny cages could be flipped open chemically when the material is needed.

Decades of research
Rothemund's work builds on decades of research into using DNA as a molecular-scale construction kit — a pursuit pioneered by New York University's Nadrian Seeman.

Seeman and his colleagues have been working with even smaller DNA structures in three dimensions, measuring mere nanometers in width rather than the tens of nanometers spanned by Rothemund's structures.

Seeman told MSNBC.com that he was enthusiastic about Rothemund's work because it adds another level of scale to nano-construction processes.

"On a slightly larger scale, he's added a huge amount of convenience, and there's something to be said for that," Seeman said. The two techniques both take a "bottom-up" approach to creating small-scale structures, but Rothemund's origami method "might ultimately be easier to interface with the top-down world than ours."

Seeman emphasized that a variety of methods on a variety of scales will come into play as researchers develop nanostructures — just as tweezers, pliers and pipe wrenches are all useful at larger scales.