 |
 |
|
|
Issue of
|
 |
Rapid advances in algorithms, the mathematical nuts and bolts of computer simulation technology, are allowing programmers to create increasingly realistic computer models of rigid objects colliding or avoiding collisions in near approaches and soft objects being dented and squished by impact, Latombe noted in kicking off the workshop. |
Computer modeling of soft objects has important applications in fields like medicine, said Joel Brown, a Stanford computer science graduate student working under Kevin Montgomery and Michael Stephanides, respectively the technical and medical directors of the National Biocomputation Center at the Stanford Medical School. In the field of microsurgery, which involves the suturing of small blood vessels under a microscope, training is crucial. "Well-trained microsurgeons enjoy close to a 100 percent success rate," Brown said. In contrast to non-recyclable lab rats, he continued, computer simulations allow surgeons to practice an operation again and again. Brown reported that his group's efforts to mathematically model blood-vessel surgery were proceeding apace although, he allowed, "if anybody has any idea about a realistic model of tying a knot with needle and thread, we'd love to hear about it."
Rigid objects are easier to model than soft ones. But simulating the behavior of many rigid objects on collision courses (as on a bad day, in the sky above San Francisco International Airport) is difficult, all the more so if you want to manipulate these objects' trajectories in real time. Brian Mirtich of Mitsubishi Electric Research Labs described new algorithms for detecting collisions in virtual environments and showcased them with a video representation of hundreds of variously shaped simulated gemstones colliding repeatedly as they tumbled down an inclined tray. The virtual gemstones, albeit more slow-moving then their actual counterparts would be, appeared exceptionally realistic. Mirtich acknowledged that bringing the speed up to real time requires more work.
 |
Even stationary structures, when they get complex enough, can be difficult and expensive to model. It might not seem worth it to generate a $100-million simulated mock-up of a nuclear submarine, with all its 20 million parts. |
A realistic simulation of these subs requires the generation of 850,000 polygons, observed Dinesh Manocha, a University of North Carolina computer scientist. But when the actual subs cost $2 billion apiece, he said, the notion of creating them virtually first in order to check out their functionality and manufacturability starts to make sense.
An automobile has about 20,000 parts, a commercial airplane 5 million, Manocha said. In each case, there's a benefit to modeling the item virtually before assembling the infrastructure to build it. Newer and more powerful algorithms are being developed that will make virtual simulations practical for other less demanding applications as well.
Computer simulations have a number of benefits. For example, they make the assembly of big parts like wings more predictable, said Raju Mattikali of Boeing Corp. Big, flat things tend to flex a lot just from gravity alone. Further uncertainties in final shape are introduced by tool inaccuracies, deformations accruing from assembly-tool impact and sometimes-surprising effects of the nuts and bolts used to fasten the wing sections together. "When you connect two big, long, flat sheets in one spot," Mattikali explained, "you may introduce stresses that lead to an unexpected new gap somewhere else. Such a gap may be permissible in one place, but not in another." Simulations also help determine the best place to position the bolts, he said.
Access to digital representations of manufactured items opens the door to their placement in virtual installations. "You can bring an escalator or elevator into an architectural model and see if it fits before you buy it," or drive a virtual new car over a test track to see how it responds, said Ron Watson of Centric Software in Los Gatos. Digital representations aid in disassembly as well as in construction. To wit: There are times when you don't want to get too close to a nuclear power plant component. The first of France's numerous nuclear power plants is being decommissioned now, said Jean-Francois Rit of Electricite de France, necessitating the disassembly and relocation of highly radioactive materials and components. Rit's group is working on simulations for planning the trajectory of a robot that will be used to help remove a steam generator and for training workers in routines choreographed to minimize their exposure to radiation.
 |
In industrial settings robots have to do more than simply avoid collisions. Robots in the automotive industry perform 4,000 precision spot welds per body at a rate of 80 bodies per hour. |
When you "build a car," you don't build just one car. You build a million of them, using millions of each part. Each car must look and work exactly the same, yet no two parts are precisely the same. Even the tools used to make them subtly change with use. "You can never manufacture a part exactly equal to another," said Ralf Schultheiss of Ford's German affiliate, "so you have to make a design tolerant to these differences." In the past, it was common to laboriously hand-build 10 prototypes, then test each one in several ways. Computer simulations that generate millions of such test situations stand to save companies (and, presumably, consumers) serious money as cycle times shrink and accuracy and flaw detection improve.
Approaching the collision-avoidance issue from the theoretical end, Texas A&M computer scientist Nancy Amato amused the audience by passing around a puzzle consisting of two longish metal nails that had been identically twisted into loops, now intertwined. The challenge was to separate the two nails -- which, Amato assured participants, could be accomplished, but only through a single set of proper motions. While the puzzle circulated, Amato talked about her group's efforts to speed computer solutions of a common bugaboo, called the "narrow passage problem" -- simply put, the need to get one object (say, a robot) to move along the shortest possible path to a location without bumping into anything. (They're still working on it, although Amato herself had no difficulty proving that the two nails could indeed be physically separated -- and rather gracefully so, without even scraping against each other -- without the assistance of teeth or sulfuric acid.)
James Kuffner, a graduate student in the Latombe group who also works for a company called the Motion Factory in Fremont, showed how a collision-avoidance algorithm can be combined in a virtual robot with algorithms that convey lifelike motion, memory and the ability to adapt quickly to change. In a demonstration, an animated character is trapped in a labyrinth. The character is programmed to see and run rapidly through . . . virtual environment, at all times avoiding contact with the constraining walls looming up around him and remembering from past forays what avenues not to try again. When the character is stymied by a perverse programmer's repositioning of the obstructions, the character adapts in real time, revising his "mental map" of the terrain and tirelessly pursuing a sole objective: escape.
 |
Reacting to this technology, MIT computer scientist Ken Salisbury commented, "Today, when we think about pulling a movie down off the Internet, we assume we'll download the whole video intact. Tomorrow, maybe we'll think in terms of downloading the characters and the script independently, and let the characters act the script out for us." |
Dinesh Pai, a computer science professor at the University of British Columbia, discussed the requirements for adding more of what might be called cinéma vérité to simulations: attributes such as visual squishiness (rather than rigidity) in an object and improved sound. Pai demonstrated a computer simulation of a bell being hit alternatly by a sharp metal object and a felt-covered mallet. He predicted that by 2002, computer users will start to see real-time representations of deformable, rather than just rigid, bodies. They may see significant improvements in simulated representations of texture by that time as well, he said.
Yet another gripping concept -- in more ways than one -- reported on at the workshop was haptics. A haptic device operates in three dimensions instead of the usual two that a mouse can handle. Imagine grasping a bar mounted on a jointed stem -- when you move the bar toward or away from you, the cursor on the screen "moves" in and out. Move it up or down, and the cursor goes up or down. Move it left and right, and the cursor goes left or right.
More important, a haptic device's force feedback allows its user to experience the shape, texture, heft and solidity of a three-dimensional object displayed on a computer screen, as well as to apply force to that object. The principle of force feedback is simple: The harder you push on a stationary object, the stronger the force with which it resists; if the object is movable, the heavier it is . . . the more force it takes to push it around.
Imagine that a brick wall is displayed on the screen, with the cursor visually displayed as a little ball poised in front of the wall. As you move the bar away from you, you feel no resistance while the cursor-ball approaches the wall until it actually gets there. Then the ball abruptly stops, and the bar won't go any further. (If you push hard enough, you can force the bar, acknowledged Diego Ruspini, a graduate student working under Computer Forum director and associate professor of computer science Oussama Khatib, but then you'll break the device's motor.) By pushing gently and moving the bar up against this perceived force field, however, you can roll the ball up the wall's side and onto its flat top. Now, while the ball is sitting on the top of the wall, you feel resistance only when you try to push down on the bar.
MIT's Salisbury is the inventor of such a haptic device, called the Phantom. Haptic devices show promise for surgery, said Salisbury, now an adviser to Mountain View-based Intuitive Surgical Inc. Robotic joints permit much more rotation than human knuckles or wrists can, allowing surgical procedures to commence with a much smaller incision than would be the case if the same operations were performed manually.
"I had the opportunity to show the Phantom to Bill Gates a while back," Salisbury told the audience. "It was at a meeting, and he seemed pretty bored the entire time. Then he stuck his finger in a Phantom that was on exhibit and said, 'Hey! This is cool!' So I asked him, 'Do you think this is going to become important in computing over the next few years?' He said, 'No.' And I breathed a big sigh of relief," Salisbury said to the laughter of the crowd. No worries about competition from Microsoft for the time being.
 |
During a wrap-up tour of the Stanford Robotics Laboratory, participants were treated to some haptic simulations including a virtual amusement park rocket ride, a roller coaster and a windmill, all produced by Ruspini and featuring the Phantom. |
Visitors
also got to see a video of two distinctly
non-anthropomorphic robots nicknamed Romeo and Juliet
(it's hard to tell gender if you don't know where to
look) ironing shirts, erasing a blackboard and
slow-dancing with a glum-looking graduate student. SR
Bruce Goldman is a freelance science writer
