Software that can’t crash.
PROBLEM: To test the reliability of software that controls embedded chips in medical devices and vehicles, computer scientists have relied on trial-and-error methods that can miss bugs.
SOLUTION: By using mathematical analysis to prove that a piece of software is reliable, June Andronick can take into account all possible inputs to the software, and all the possible ways the software could process those inputs.
Working at Australia’s national IT research center (NICTA), Andronick and colleagues in Gerwin Klein’s lab were able to use this analytical technique to write a small operating system that will always behave exactly as intended, never crashing (barring incorrect assumptions about the hardware).
Because the OS acts as the gatekeeper to the hardware, it can block instructions that would cause a crash—say, instructions coming from the application software that makes decisions about how an engine should be throttled. Some computer scientists predict that mathematically verifying the reliability of critical software components will become the norm in certain systems.
The technology could also help protect against cyber-attacks, Andronick says. The operating system could block unauthorized actions that are issued by software that has been hacked through some point of vulnerability, such as a Web browser. “The attack on the untrusted part can’t keep the trusted part from functioning correctly,” she says.
Robots that learn from people.
Instead of programming robots to handle each step of a new job, Pieter Abbeel, an assistant professor at UC Berkeley, has created robots that can observe humans demonstrating a task and then mimic them, or learn from pictures how to handle a piece of flexible material they’ve never seen before. His robots have learned to perform flying acrobatics, tie surgical sutures, and neatly sort socks.
Abbeel’s key innovation was to program the robots so that they can reliably infer the underlying intent of their instructors, filtering out the “noise”—irrelevant variations, or even slight mistakes, in the instructors’ demonstrations. Each robot is usually shown around 10 demonstrations before it can extract general rules of behavior. Even without an instructor, it can sometimes work out what to do. For example, Abbeel taught one robot how to fold laundry by giving it some general rules about how fabric behaves, and then showed it around 100 images of clothing so it could analyze how that particular clothing was likely to move as it was handled. After that, the robot could fold towels and sweaters without further instruction.
Speeding up simulations of complex objects.
Engineers and animators use computer simulations to model the ways objects bounce, bump, and change shape under external forces. Until now, these simulations were too complex to run in real time, but Jernej Barbič has developed a way to make them run tens of thousands of times faster than previously seemed possible—fast enough for engineers to be able to interact with a model and see it respond instantly, allowing them to experiment with designs as never before.
Barbič translates models with millions of parameters into versions that have just tens or hundreds but are still accurate. He created software that can automatically identify which parameters are the most important and determine how these can be combined to reduce their number.
His latest experiments connect models to haptic interfaces that allow a user to literally feel what’s happening in the virtual world. Producing a realistic physical sensation of movement takes approximately 1,000 updates per second. “That’s infeasible without Jernej’s approach,” says Adrien Treuille (a member of the 2009 TR35), a professor at Carnegie Mellon University. Barbič is now in talks with the French company Haption to commercialize the technology. He says that because his techniques make it easier to quickly test and revise designs, products could “be made faster and turn out cheaper and safer.”
Cheaper satellite pictures.
Dan Berkenstock, cofounder and chief product officer of Skybox Imaging, wants to let “anyone know what’s happening anywhere in the world at any time.” Next year the company plans to launch the first of what it hopes will be a constellation of 12 to 24 satellites taking high-resolution pictures of Earth. Each satellite should cost about a tenth as much as the $250 million to $500 million imaging satellites operated by companies like DigitalGlobe and GeoEye.
Currently, so few commercial imaging satellites are in orbit that it can take days or even weeks to get pictures of a location—and there will be only one per day. By placing multiple satellites in multiple orbits for the cost of a single traditional satellite, Skybox plans to realize something closer to Berkenstock’s vision of anywhere, anytime coverage: it could photograph nearly any spot on the planet up to three or four times a day, weather permitting. (Skybox’s license from the U.S. government takes security and privacy concerns into account: the satellites will have one-meter resolution—enough detail to identify a crowd but not an individual.)
The secret to the low cost of Skybox’s satellites is their size: each one is about as big as a large trash can, rather than a minivan. With smaller, more modern components than those typical in the conservative aerospace industry, they’re cheaper to build, and less expensive rockets can be used to launch them. Skybox is hoping to recoup the cost of the constellation by expanding the market for fresh satellite imagery beyond the government and the military. Berkenstock is working on tools for storing and classifying petabytes of data–tools that financial analysts, for example, could use to get daily counts of the cars in the parking lots at thousands of retail location.
A common language for robots.
PROBLEM: People who want to program robots have had to either write software from scratch or purchase proprietary software that is hard to modify.
SOLUTION: Brian Gerkey has developed open-source platforms, called Player and ROS, that standardize the basic software used to control a robot. Both have been adopted by thousands of companies, universities, and governments around the world.
Gerkey believes the software will allow entrepreneurs to create new commercial applications for robots even if they don’t have extensive robotics expertise. The goal is to help “people who have ideas for what robots can do in the marketplace,” he says. Much of the development of ROS is happening at Willow Garage, a robot technology incubator, where Gerkey is the director of open-source development. The first full version of ROS, which can handle more complex robots than Player, was released in 2010. By encouraging the adoption of ROS, Willow Garage is also increasing the market for its own robots, which it hopes will become the de facto hardware standard for would-be robot entrepreneurs.
Managing huge data sets.
In 2006, as Facebook was starting to accumulate information about its users faster than the data could be analyzed and stored, Jeff Hammerbacher was brought in to deal with the problem. A former Wall Street number cruncher, he soon developed techniques for handling and mining unprecedented amounts of data.
Realizing that the company needed entirely new technology to handle the information overload, Hammerbacher threw Facebook’s muscle behind a relatively new open-source database project called Hadoop, which allows nearly real-time processing of data in quantities that had previously been impossible. Hadoop enabled Hammerbacher to create the suite of analytics that underpins Facebook’s targeted advertising system—the key to the company’s profitability.
Though much of the technology he constructed is still in use at Facebook, Hammerbacher left in 2008 to found a company called Cloudera, where he is now chief scientist. Cloudera is devoted to developing Hadoop and related open-source technologies. Hammerbacher points out that industries including oil and gas, retail, and life sciences are all dealing with increasing amounts of data. They could use such technology to extract valuable insights from the deluge.
Teaching computers to classify music.
Is Lady Gaga’s “Born This Way” a happy song? Is “Bohemian Rhapsody” sad? Gert Lanckriet wants computers to be able to tell. Then people could search for tunes that match a particular mood or instrumental style, and an online store could make better recommendations.
Lanckriet, an associate professor in the Department of Electrical and Computer Engineering at the University of California, San Diego, started by having his computers analyze a collection of 500 popular songs that human judges had categorized in six ways—by genre and tempo, for example. When fed a new piece of music not in the database, the computer uses that training to infer how a human would characterize it. Lanckriet continues to train the system through a Facebook game called Herd It, launched in 2009. Players listen to snippets of music and win points if they agree with the majority of their fellow users; the results are fed into Lanckriet’s software.
After the software gets some more fine-tuning, Lanckriet plans to let it crawl the Web like a search engine, automatically classifying the huge amount of music available online. He’s also exploring how to use the sensors in smart phones to cue up exactly the sort of music someone is in the mood for. If the phone’s accelerometer detects that the user is exercising, it could choose something energetic, while sitting in a quiet room at night might lead it to choose something mellower.
Guaranteeing cloud security.
PROBLEM: Cloud computing offers numerous advantages to businesses and individuals by enabling them to store data and run websites on remote computers rather than ones they own. But many hesitate to use the technology for fear of what might happen if a cloud provider’s systems aren’t secured properly or break down.
SOLUTION: Software created by Alina Oprea, a researcher at RSA Laboratories in Cambridge, Massachusetts, can guarantee users that their data hasn’t been tampered with and won’t become inaccessible. For her 2007 PhD thesis, she developed a digital fingerprint capable of quickly verifying that data stored in the cloud hasn’t been maliciously altered or accidentally corrupted. Then, at RSA, Oprea helped create HAIL, a technology that lets users divide data among multiple cloud providers in such a way that if one provider goes offline, the missing information can be reconstructed from the data stored by the others.
Next she helped lead the development of HomeAlone, which guards against an insidious threat in cloud computing: when users buy remote computing power, they often share server space with other customers, offering an opportunity for potential hackers. Many cloud providers let customers pay extra for their own private servers to avoid this risk. HomeAlone lets customers who choose that option verify that the data is indeed isolated and no one is snooping on their space in the cloud.
Converting paper records to digital in real time.
Beginning in 2009, while working with Microsoft Research India, Aishwarya Ratan spent 15 months figuring out how to help local microcredit co-ops, which often struggle with handwritten entries that are illegible, incorrect, or incomplete. Her solution combines digital technology with the familiar paper notebooks that villagers prefer. Co-op members use an electronic ballpoint pen to write in ledgers placed on a slate equipped with software that recognizes handwritten numbers. The slate provides feedback on whether the records are complete and legible, stores them in a database, and gives real-time balance updates, both on a screen and verbally in the local language. The database can be shared with the nongovernmental organizations and banks that back each co-op.
In field tests, the hybrid slate yielded entries that were 100 percent complete and made record keeping faster while letting co-op members retain the paper records they are comfortable with. The potential of the system is tremendous: microfinance co-ops serve 86 million Indian households. High-quality record keeping could make them more efficient, helping members save more and repay faster, and it could allow the co-ops to borrow more easily from banks.
In June, Ratan became the director of the Microsavings and Payments Innovation Initiative at Yale University, which as part of its mission studies how technologies can help the poor financially. Meanwhile, the NGO that Ratan was partnering with continues to test the slate in villages.
Synthesizing 3-D models from 2-D photographs.
Every snap of a shutter—be it the subtle click of a DSLR or the artificial ka-chak of a smart phone-—turns three-dimensional reality into a two-dimensional image. Noah Snavely is taking those images and using them to create 3-D digital models of structures ranging from individual houses to entire cities.
In 2006, as part of his PhD studies at the University of Washington, Snavely created a system that could assemble such models using an unstructured assortment of images from different cameras and viewpoints. “If we can find matching points between views,” he says, “we can reason about where each image was taken and what the 3-D shape of the scene is.” In 2008 his work was commercialized as Microsoft’s Photosynth service, which allows users to upload photo collections and view them in a 3-D reconstruction of the space where they were taken. Snavely has even used his technology to reconstruct the city of Rome from the wealth of amateur images available online.
Snavely, now an assistant professor at Cornell, is trying to assemble a “distributed camera” composed of all the individual cameras whose pictures are shared online. He hopes to use those photos to construct a street-level digital model of much of the globe.
Software that can be localized to teach taboo topics.
Despite considerable educational efforts by experts and organizations alike, public awareness in India about the growing HIV epidemic has remained low. So Piya Sorcar, founder and CEO of TeachAIDS, has developed interactive software to educate children about HIV in a way that’s sensitive to the country’s cultural mores.
When Sorcar traveled to India in 2005, she found that even children and young adults who received training on HIV didn’t learn much: cultural taboos prevented educators from speaking frankly about how the virus is transmitted. As she designed her software, she took pains to ensure that it didn’t run afoul of those taboos. She analyzed cultural responses to every image used. She recorded narration with correct local accents, created gender-specific versions of each program, enlisted local celebrities for voice acting, and tested to see how much information children retained, even long after the lessons were over.
The cultural sensitivity has paid off: Sorcar’s software has been approved and distributed by states in India where other sex education is banned. The software has been designed to be modular, so that it’s easy to swap in locally appropriate elements. The country of Botswana has approved it for every school in the nation, and Sorcar hopes to distribute it to countries around the world within five years.
Creating movie-quality graphics in real time.
Thanks to Kun Zhou, computer games will become more realistic and animated movies will reach cinemas faster. The Zhejiang University computer science professor has released software capable of rendering movie-quality scenes using graphics chips of the sort that most PCs use to create comparatively crude images.
These chips, known as GPUs, perform many relatively simple computations in parallel. While this design is adequate to synthesize images for today’s computer games, it wasn’t seen as a good fit for the complex algorithms required to create the truly photorealistic images produced by animation and special-effects studios. But in 2009 Zhou developed a programming language that could efficiently break up these algorithms in a way that suited GPUs. He used this language as the foundation of a rendering system called RenderAnts, which generates images more than 10 times as fast as traditional software. A Chinese animation studio is already using an early commercial version of the software to increase the quality of its television productions, and Zhou is collaborating with the Frankfurt-based gaming studio Crytek—maker of the popular Crysis series of games, which are often used to benchmark the graphics performance of PCs—to improve the realism of its products.
Making games more realistic while keeping them fast enough to respond instantaneously to a player’s actions is a personal goal for Zhou. He says he got hooked on games as a young engineering student and has been trying to overcome their limitations ever since.