Home' Trinidad and Tobago Guardian : February 10th 2017 Contents A24 body & soul
guardian.co.tt Friday, February 10, 2017
Every other year, the International Confer-
ence 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, how-
ever, 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 Ar-
tificial Intelligence Laboratory are trying to improve
automated planners by giving them the benefit of
By encoding the strategies of high-performing
human planners in a machine-readable form, they
were able to improve the performance of competi-
tion-winning planning algorithms by ten to 15 per
cent on a challenging set of problems.
The researchers presented 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
optimisation, 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 first author on the conference paper is Jo-
seph Kim, a graduate student in aeronautics and
astronautics. He's joined by Shah and Christopher
Banks, an undergraduate at Norfolk State Univer-
sity who was a research intern in Shah's lab in the
summer of 2016.
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 prob-
lems 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 con-
straints of the original problem but also minimises
planes' flight time and fuel consumption?
Finally, the most complex problems---temporal
problems---add temporal constraints to the numer-
ical problems: Can you minimise 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 undergrad-
uate 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.
Certainly, they were better than the automatic plan-
ners. 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
The results varied, but only slightly. On the numer-
ical problems, the average improvement was 13 per
cent and 16 per cent, respectively, on the flight-plan-
ning and satellite-positioning problems; and on the
temporal problems, the improvement was 12 per cent
and ten per cent.
"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
"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.
(Massachusetts Institute of Technology)
are trying to
Human intuition added to planning algorithms
Our Company is recruiting for a dynamic individual to accept the role of Operations Manager to
Company proprietary technology
The Human Resource Department
P.O. Box 25 San Fernando.
50-54 Duke Street
Port of Spain
Links Archive February 9th 2017 February 11th 2017 Navigation Previous Page Next Page