Monthly Archives: August 2016
Every other year, the International Conference on Automated Planning and Scheduling hosts a competition in which computer systems designed by conference participants try to find the best solution to a planning problem, such as scheduling flights or coordinating tasks for teams of autonomous satellites.
On all but the most straightforward problems, however, even the best planning algorithms still aren’t as effective as human beings with a particular aptitude for problem-solving — such as MIT students.
Researchers from MIT’s Computer Science and Artificial Intelligence Laboratory are trying to improve automated planners by giving them the benefit of human intuition. By encoding the strategies of high-performing human planners in a machine-readable form, they were able to improve the performance of competition-winning planning algorithms by 10 to 15 percent on a challenging set of problems.
The researchers are presenting their results this week at the Association for the Advancement of Artificial Intelligence’s annual conference.
“In the lab, in other investigations, we’ve seen that for things like planning and scheduling and optimization, there’s usually a small set of people who are truly outstanding at it,” says Julie Shah, an assistant professor of aeronautics and astronautics at MIT. “Can we take the insights and the high-level strategies from the few people who are truly excellent at it and allow a machine to make use of that to be better at problem-solving than the vast majority of the population?”
The first author on the conference paper is Joseph Kim, a graduate student in aeronautics and astronautics. He’s joined by Shah and Christopher Banks, an undergraduate at Norfolk State University who was a research intern in Shah’s lab in the summer of 2016.
The human factor
Algorithms entered in the automated-planning competition — called the International Planning Competition, or IPC — are given related problems with different degrees of difficulty. The easiest problems require satisfaction of a few rigid constraints: For instance, given a certain number of airports, a certain number of planes, and a certain number of people at each airport with particular destinations, is it possible to plan planes’ flight routes such that all passengers reach their destinations but no plane ever flies empty?
A more complex class of problems — numerical problems — adds some flexible numerical parameters: Can you find a set of flight plans that meets the constraints of the original problem but also minimizes planes’ flight time and fuel consumption?
Finally, the most complex problems — temporal problems — add temporal constraints to the numerical problems: Can you minimize flight time and fuel consumption while also ensuring that planes arrive and depart at specific times?
For each problem, an algorithm has a half-hour to generate a plan. The quality of the plans is measured according to some “cost function,” such as an equation that combines total flight time and total fuel consumption.
Shah, Kim, and Banks recruited 36 MIT undergraduate and graduate students and posed each of them the planning problems from two different competitions, one that focused on plane routing and one that focused on satellite positioning. Like the automatic planners, the students had a half-hour to solve each problem.
Is the Internet old or new? According to MIT professor of mathematics Tom Leighton, co-founder of Akamai, the internet is just getting started. His opinion counts since his firm, launched in 1998 with pivotal help from Danny Lewin SM ’98, keeps the internet speedy by copying and channeling massive amounts of data into orderly and secure places that are quick to access. Now, the National Inventors Hall of Fame (NIHF) has recognized Leighton and Lewin’s work, naming them both as 2017 inductees.
“We think about the internet and the tremendous accomplishments that have been made and, the exciting thing is, it’s in its infancy,” Leighton says in an Akamai video. Online commerce, which has grown rapidly and is now denting mall sales, has huge potential, especially as dual screen use grows. Soon mobile devices will link to television, and then viewers can change channels on their mobile phones and click to buy the cool sunglasses Tom Cruise is wearing on the big screen. “We are going to see [that] things we never thought about existing will be core to our lives within 10 years, using the internet,” Leighton says.
Leighton’s former collaborator, Danny Lewin, was pivotal to the early development of Akamai’s technology. Tragically, Lewin died as a passenger on an American Airlines flight that was hijacked by terrorists and crashed into New York’s World Trade Center on Sept. 11, 2001. Lewin, a former Israeli Defense Forces officer, is credited with trying to stop the attack.
According to Akami, Leighton, Lewin, and their team “developed the mathematical algorithms necessary to intelligently route and replicate content over a large network of distributed servers,” which solved congestion that was then becoming known as the “World Wide Wait.” Today the company delivers nearly 3 trillion internet interactions each day.
The NIHF describes Leighton and Lewin’s contributions as pivotal to making the web fast, secure, and reliable. Their tools were applied mathematics and algorithms, and they focused on congested nodes identified by Tim Berners-Lee, inventor of the World Wide Web and an MIT professor with an office near Leighton. Leighton, an authority on parallel algorithms for network applications who earned his PhD at MIT, holds more than 40 U.S. patents involving content delivery, internet protocols, algorithms for networks, cryptography, and digital rights management. He served as Akamai’s chief scientist for 14 years before becoming chief executive officer in 2013.
Lewin, an MIT doctoral candidate at the time of his death, served as Akamai’s chief technology officer and was an award-winning computer scientist whose master’s thesis included some of the fundamental algorithms that make up the core of Akamai’s services. Before coming to MIT, Lewin worked at IBM’s research laboratory in Haifa, Israel, where he developed the company’s Genesys system, a processor verification tool. He is named on 25 U.S. patents.
“It is a special honor to be listed among so many groundbreaking innovators in the National Inventors Hall of Fame,” says Leighton. “And I am very grateful to Akamai’s employees for all their hard work over the last two decades to turn a dream for making the Internet be fast, reliable, and secure, into a reality.”
The butt of jokes as little as 10 years ago, automatic speech recognition is now on the verge of becoming people’s chief means of interacting with their principal computing devices.
In anticipation of the age of voice-controlled electronics, MIT researchers have built a low-power chip specialized for automatic speech recognition. Whereas a cellphone running speech-recognition software might require about 1 watt of power, the new chip requires between 0.2 and 10 milliwatts, depending on the number of words it has to recognize.
In a real-world application, that probably translates to a power savings of 90 to 99 percent, which could make voice control practical for relatively simple electronic devices. That includes power-constrained devices that have to harvest energy from their environments or go months between battery charges. Such devices form the technological backbone of what’s called the “internet of things,” or IoT, which refers to the idea that vehicles, appliances, civil-engineering structures, manufacturing equipment, and even livestock will soon have sensors that report information directly to networked servers, aiding with maintenance and the coordination of tasks.
“Speech input will become a natural interface for many wearable applications and intelligent devices,” says Anantha Chandrakasan, the Vannevar Bush Professor of Electrical Engineering and Computer Science at MIT, whose group developed the new chip. “The miniaturization of these devices will require a different interface than touch or keyboard. It will be critical to embed the speech functionality locally to save system energy consumption compared to performing this operation in the cloud.”
“I don’t think that we really developed this technology for a particular application,” adds Michael Price, who led the design of the chip as an MIT graduate student in electrical engineering and computer science and now works for chipmaker Analog Devices. “We have tried to put the infrastructure in place to provide better trade-offs to a system designer than they would have had with previous technology, whether it was software or hardware acceleration.”
Price, Chandrakasan, and Jim Glass, a senior research scientist at MIT’s Computer Science and Artificial Intelligence Laboratory, described the new chip in a paper Price presented last week at the International Solid-State Circuits Conference.
The sleeper wakes
Today, the best-performing speech recognizers are, like many other state-of-the-art artificial-intelligence systems, based on neural networks, virtual networks of simple information processors roughly modeled on the human brain. Much of the new chip’s circuitry is concerned with implementing speech-recognition networks as efficiently as possible.
But even the most power-efficient speech recognition system would quickly drain a device’s battery if it ran without interruption. So the chip also includes a simpler “voice activity detection” circuit that monitors ambient noise to determine whether it might be speech. If the answer is yes, the chip fires up the larger, more complex speech-recognition circuit.