MIT researchers are turning to human intuition to improve planning algorithms.
The International Conference on Automated Planning and Scheduling holds a competition every other year in search of the best computer systems for addressing planning problems such as coordinating activities for satellites or scheduling flights. Unfortunately, even the best of planning algorithms already developed are still aren't as effective as people who are particularly skilled to solve problems.
In a paper to be presented at the annual conference of the Association for the Advancement of Artificial Intelligence, researchers from the Computer Science and Artificial Intelligence Laboratory at MIT sought to improve planning systems by incorporating human intuition into automated algorithms. After encoding strategies from real human planners into a form readable by machines, they recorded an improvement of between 10 and 15 percent in planning algorithms that had already gone on to win at the competition, depending on the problems being solved.
"[W]e'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 MIT assistant aeronautics and astronautics professor Julie Shah.
Planning Algorithms At Work
Planning algorithms are designed to solve problems with varying levels of difficulty, with the easiest problems having to meet the fewest parameters, which will depend on the problem. For example, a problem calling for planning flight routes such that all passengers arrive at their destination with not one plane flying empty will have parameters such as the number of airports, the number of passengers at a certain airport, and the number of planes available.
Numerical problems are more complex as they add numerical parameters, while temporal problems are deemed the most difficult as they add temporal constraints on top of numerical problems.
For every problem, 30 minutes is allocated for an algorithm to get to work.
Adding Human Intuition
Shah and colleagues recruited 36 graduate and undergraduate students from MIT and gave them planning problems to work on. According to the researchers, participants were pooled from MIT because they believe the school's students as problem-solving experts. And they were right, because the students did better than automatic planners in solving the problems they were presented with.
A large portion of the strategies the students used could be defined with the use of linear temporal logic, a formal language that can then be utilized to add parameters to problem specifications. Each strategy used was tested separately and produced varying results, although only slightly.
For satellite-positioning and flight-planning problems, the researchers recorded an improvement of 16 and 13 percent on problems categorized as numerical, while those classified as temporal problems logged an improvement of 10 and 12 percent, respectively.
"There is maybe this bridge to taking a user's high-level strategy and making that useful for the machine," said Shah.
In an ongoing work, Shah and colleagues are looking to turn their algorithm fully automatic by using techniques to process language naturally, converting descriptions of high-level strategies in free form into linear temporal logic, all without intervention from people.
Aside from Shah, Joseph Kim and Christopher Banks also contributed to the research.
