Nav: Home

Researchers add human intuition to planning algorithms

February 07, 2017

CAMBRIDGE, Mass. -- 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.

"By choosing MIT students, we're basically choosing the world experts in problem solving," Shah says. "Likely, they're going to be better at it than most of the population."

Encoding strategies

Certainly, they were better than the automatic planners. After the students had submitted their solutions, Kim interviewed them about the general strategies they had used to solve the problems. Their answers included things like "Planes should visit each city at most once," and "For each satellite, find routes in three turns or less."

The researchers discovered that the large majority of the students' strategies could be described using a formal language called linear temporal logic, which in turn could be used to add constraints to the problem specifications. Because different strategies could cancel each other out, the researchers tested each student's strategies separately, using the planning algorithms that had won their respective competitions. The results varied, but only slightly. On the numerical problems, the average improvement was 13 percent and 16 percent, respectively, on the flight-planning and satellite-positioning problems; and on the temporal problems, the improvement was 12 percent and 10 percent.

"The plan that the planner came up with looked more like the human-generated plan when it used these high-level strategies from the person," Shah says. "There is maybe this bridge to taking a user's high-level strategy and making that useful for the machine, and by making it useful for the machine, maybe it makes it more interpretable to the person."

In ongoing work, Kim and Shah are using natural-language-processing techniques to make the system fully automatic, so that it will convert users' free-form descriptions of their high-level strategies into linear temporal logic without human intervention.
-end-
ADDITIONAL BACKGROUND

ARCHIVE: Robot helps nurses schedule tasks on labor floor

http://news.mit.edu/2016/robot-helps-nurses-schedule-tasks-on-labor-floor-0713

ARCHIVE: Enabling human-robot rescue teams

http://news.mit.edu/2016/human-robot-rescue-teams-0217

ARCHIVE: Computers that teach by example

http://news.mit.edu/2014/pattern-recognition-systems-convey-learning-1205

Massachusetts Institute of Technology

Related Competition Articles:

Aging and nutrients competition determine changes in microbiota
Two studies with surprising discoveries: in the elderly, the bacterium E. coli evolves in a way that can become potentially pathogenic and increase the risk of disease and, according to data obtained in another study, the metabolism of the same bacterium present in the microbiota evolves differently if it is alone or accompanied by other bacteria.
Is human cooperativity an outcome of competition between cultural groups?
A study by ASU researchers looks at how culture may have fueled our capacity to cooperate with strangers.
Location and competition
Those of us who drive regularly are keenly aware of gas prices and their daily fluctuations.
Political competition is hurting our charitable giving
As the midterm election heats up and the fallout of the Supreme Court nomination rings across the political divide, a new study presents a unique angle of American politics: how party affiliation affects charitable donations.
For wineries, competition boosts profits from sustainability
An international study of small- to medium-sized wineries and vineyards finds that the more sustainability practices a winery has in place, the better its financial performance -- and the effect is enhanced when a winery perceives significant pressure from competitors.
Outside competition breeds more trust among coworkers: Study
Working in a competitive industry fosters a greater level of trust amongst workers, finds a new study from the University of British Columbia, Princeton University and Aix-Marseille University, published today in Science: Advances.
Step aside Superman, steel is no competition for this new material
When it comes to materials, there is no question as to who wins the strongman competition.
Competition between males improves resilience against climate change
Animal species with males who compete intensively for mates might be more resilient to the effects of climate change, according to research by Queen Mary University of London.
International competition benchmarks metagenomics software
Communities of bacteria live everywhere: inside our bodies, on our bodies and all around us.
Can aromatherapy calm competition horses?
Although studies suggest that inhaling certain scents may reduce stress in humans, aromatherapy is relatively unexplored in veterinary medicine.
More Competition News and Competition Current Events

Trending Science News

Current Coronavirus (COVID-19) News

Top Science Podcasts

We have hand picked the top science podcasts of 2020.
Now Playing: TED Radio Hour

Listen Again: Meditations on Loneliness
Original broadcast date: April 24, 2020. We're a social species now living in isolation. But loneliness was a problem well before this era of social distancing. This hour, TED speakers explore how we can live and make peace with loneliness. Guests on the show include author and illustrator Jonny Sun, psychologist Susan Pinker, architect Grace Kim, and writer Suleika Jaouad.
Now Playing: Science for the People

#565 The Great Wide Indoors
We're all spending a bit more time indoors this summer than we probably figured. But did you ever stop to think about why the places we live and work as designed the way they are? And how they could be designed better? We're talking with Emily Anthes about her new book "The Great Indoors: The Surprising Science of how Buildings Shape our Behavior, Health and Happiness".
Now Playing: Radiolab

The Third. A TED Talk.
Jad gives a TED talk about his life as a journalist and how Radiolab has evolved over the years. Here's how TED described it:How do you end a story? Host of Radiolab Jad Abumrad tells how his search for an answer led him home to the mountains of Tennessee, where he met an unexpected teacher: Dolly Parton.Jad Nicholas Abumrad is a Lebanese-American radio host, composer and producer. He is the founder of the syndicated public radio program Radiolab, which is broadcast on over 600 radio stations nationwide and is downloaded more than 120 million times a year as a podcast. He also created More Perfect, a podcast that tells the stories behind the Supreme Court's most famous decisions. And most recently, Dolly Parton's America, a nine-episode podcast exploring the life and times of the iconic country music star. Abumrad has received three Peabody Awards and was named a MacArthur Fellow in 2011.