Researchers adding human intuition to planning algorithms

Researchers at MIT are encoding the strategies of high-performing human planners in a machine-readable algorithm form and improving overall performance by 10 to 15%.

02/16/2017


Researchers from MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) 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-readabEvery 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.

Researchers from MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) 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% on a challenging set of problems.

"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," said 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 (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.

Encoding strategies

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% and 16%, respectively, on the flight-planning and satellite-positioning problems; and on the temporal problems, the improvement was 12% and 10%.

"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 said. "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.

Massachusetts Institute of Technology (MIT)

www.mit.edu 

- Edited by Chris Vavra, production editor, Control Engineering, CFE Media, cvavra@cfemedia.com. See more Control Engineering asset management stories.



The Engineers' Choice Awards highlight some of the best new control, instrumentation and automation products as chosen by...
The System Integrator Giants program lists the top 100 system integrators among companies listed in CFE Media's Global System Integrator Database.
Each year, a panel of Control Engineering and Plant Engineering editors and industry expert judges select the System Integrator of the Year Award winners in three categories.
This eGuide illustrates solutions, applications and benefits of machine vision systems.
Learn how to increase device reliability in harsh environments and decrease unplanned system downtime.
This eGuide contains a series of articles and videos that considers theoretical and practical; immediate needs and a look into the future.
Women in engineering; Engineering Leaders Under 40; PID benefits and drawbacks; Ladder logic; Cloud computing
Robotic integration and cloud connections; SCADA and cybersecurity; Motor efficiency standards; Open- and closed-loop control; Augmented reality
Controller programming; Safety networks; Enclosure design; Power quality; Safety integrity levels; Increasing process efficiency
This article collection contains several articles on how advancements in vision system designs, computing power, algorithms, optics, and communications are making machine vision more cost effective than ever before.
Featured articles highlight technologies that enable the Industrial Internet of Things, IIoT-related products and strategies to get data more easily to the user.
This digital report will explore several aspects of how IIoT will transform manufacturing in the coming years.

Find and connect with the most suitable service provider for your unique application. Start searching the Global System Integrator Database Now!

Cloud, mobility, and remote operations; SCADA and contextual mobility; Custom UPS empowering a secure pipeline
Infrastructure for natural gas expansion; Artificial lift methods; Disruptive technology and fugitive gas emissions
Mobility as the means to offshore innovation; Preventing another Deepwater Horizon; ROVs as subsea robots; SCADA and the radio spectrum
Automation Engineer; Wood Group
System Integrator; Cross Integrated Systems Group
Jose S. Vasquez, Jr.
Fire & Life Safety Engineer; Technip USA Inc.
This course focuses on climate analysis, appropriateness of cooling system selection, and combining cooling systems.
This course will help identify and reveal electrical hazards and identify the solutions to implementing and maintaining a safe work environment.
This course explains how maintaining power and communication systems through emergency power-generation systems is critical.
The Engineers' Choice Awards highlight some of the best new control, instrumentation and automation products as chosen by...
The System Integrator Giants program lists the top 100 system integrators among companies listed in CFE Media's Global System Integrator Database.
Each year, a panel of Control Engineering and Plant Engineering editors and industry expert judges select the System Integrator of the Year Award winners in three categories.
This eGuide illustrates solutions, applications and benefits of machine vision systems.
Learn how to increase device reliability in harsh environments and decrease unplanned system downtime.
This eGuide contains a series of articles and videos that considers theoretical and practical; immediate needs and a look into the future.
Women in engineering; Engineering Leaders Under 40; PID benefits and drawbacks; Ladder logic; Cloud computing
Robotic integration and cloud connections; SCADA and cybersecurity; Motor efficiency standards; Open- and closed-loop control; Augmented reality
Controller programming; Safety networks; Enclosure design; Power quality; Safety integrity levels; Increasing process efficiency
This article collection contains several articles on how advancements in vision system designs, computing power, algorithms, optics, and communications are making machine vision more cost effective than ever before.
Featured articles highlight technologies that enable the Industrial Internet of Things, IIoT-related products and strategies to get data more easily to the user.
This digital report will explore several aspects of how IIoT will transform manufacturing in the coming years.

Find and connect with the most suitable service provider for your unique application. Start searching the Global System Integrator Database Now!

Cloud, mobility, and remote operations; SCADA and contextual mobility; Custom UPS empowering a secure pipeline
Infrastructure for natural gas expansion; Artificial lift methods; Disruptive technology and fugitive gas emissions
Mobility as the means to offshore innovation; Preventing another Deepwater Horizon; ROVs as subsea robots; SCADA and the radio spectrum
Automation Engineer; Wood Group
System Integrator; Cross Integrated Systems Group
Jose S. Vasquez, Jr.
Fire & Life Safety Engineer; Technip USA Inc.
This course focuses on climate analysis, appropriateness of cooling system selection, and combining cooling systems.
This course will help identify and reveal electrical hazards and identify the solutions to implementing and maintaining a safe work environment.
This course explains how maintaining power and communication systems through emergency power-generation systems is critical.
The Engineers' Choice Awards highlight some of the best new control, instrumentation and automation products as chosen by...
The System Integrator Giants program lists the top 100 system integrators among companies listed in CFE Media's Global System Integrator Database.
Each year, a panel of Control Engineering and Plant Engineering editors and industry expert judges select the System Integrator of the Year Award winners in three categories.
This eGuide illustrates solutions, applications and benefits of machine vision systems.
Learn how to increase device reliability in harsh environments and decrease unplanned system downtime.
This eGuide contains a series of articles and videos that considers theoretical and practical; immediate needs and a look into the future.
Women in engineering; Engineering Leaders Under 40; PID benefits and drawbacks; Ladder logic; Cloud computing
Robotic integration and cloud connections; SCADA and cybersecurity; Motor efficiency standards; Open- and closed-loop control; Augmented reality
Controller programming; Safety networks; Enclosure design; Power quality; Safety integrity levels; Increasing process efficiency
This article collection contains several articles on how advancements in vision system designs, computing power, algorithms, optics, and communications are making machine vision more cost effective than ever before.
Featured articles highlight technologies that enable the Industrial Internet of Things, IIoT-related products and strategies to get data more easily to the user.
This digital report will explore several aspects of how IIoT will transform manufacturing in the coming years.

Find and connect with the most suitable service provider for your unique application. Start searching the Global System Integrator Database Now!

Cloud, mobility, and remote operations; SCADA and contextual mobility; Custom UPS empowering a secure pipeline
Infrastructure for natural gas expansion; Artificial lift methods; Disruptive technology and fugitive gas emissions
Mobility as the means to offshore innovation; Preventing another Deepwater Horizon; ROVs as subsea robots; SCADA and the radio spectrum
Automation Engineer; Wood Group
System Integrator; Cross Integrated Systems Group
Jose S. Vasquez, Jr.
Fire & Life Safety Engineer; Technip USA Inc.
This course focuses on climate analysis, appropriateness of cooling system selection, and combining cooling systems.
This course will help identify and reveal electrical hazards and identify the solutions to implementing and maintaining a safe work environment.
This course explains how maintaining power and communication systems through emergency power-generation systems is critical.
click me