3/16/2009 Tom Moone, ECE ILLINOIS
In the search for improved scheduling algorithms, ECE Professor Benjamin Wah and his student Chih-Wei Hsu could be a source of important breakthroughs. They recently received the Best Temporal Satisficing Planner Award in the Deterministic Track of the Sixth International Planning Competition.
Written by Tom Moone, ECE ILLINOIS
Satisficing is a term that combines the words satisfying and suffice. It refers to a decision-making strategy whose goal is not necessarily to find a perfect solution, but to develop a solution that is guaranteed to be correct and that meets most of the soft criteria most efficiently.
This is a specialized word that is used in the world of scheduling. At any large institution such as an airport or a train station, arrival and departure schedules for the planes or trains is a major component. The number of planes or trains that are arriving and leaving, without colliding with each other, as well as the task of actually keeping straight which vehicle is doing what and when, is staggering. Scheduling is also used in developing space missions, organizing telescope operations, and a host of other engineering applications.
In the search for improved scheduling algorithms, ECE Professor Benjamin W Wah and his student Chih-Wei Hsu could be a source of important breakthroughs. They recently received the Best Temporal Satisficing Planner Award in the Deterministic Track of the Sixth International Planning Competition. A planner creates a schedule to optimize completion time of a number of large-scale activities.
“This project started six years ago when we had a contract with NASA,” said Wah, the Franklin W. Woeltge Professor of Electrical and Computer Engineering. Since that original work designing planners for NASA, the study of planners has been extensively developed.
As Hsu explained, their approach to scheduling was to exploit the localities of constraints in these problems and to partition a problem into multiple subproblems that are loosely related by a few common constraints. Each subproblem is significantly less complex because it has fewer variables and constraints and can be solved much faster than the original problem.
The benchmarks of the competition come from large-scale industry applications on scheduling operations in airports, satellites, storage depots, mobile channels, Mars rovers, oil refineries, and many others. “So, for instance, in scheduling trains, we allowed a train to change its direction from the inbound direction to the outbound direction in order to move it to another track and to create space for an incoming train,” said Hsu.
The competition involves applications with many constraints on operations that could not happen at the same time. In the algorithm they developed, Wah and Hsu exploited the localities of these constraints, breaking the problem into subproblems that could be clustered according to the strong localities.
“People knew about these localities,” said Wah, “but they did not have a method of resolving the inconsistencies of the global constraints in general cases after they solved the subproblems.” Together with Yixin Chen, a former doctoral student in the group, Wah and Hsu have developed some necessary and sufficient conditions on guaranteeing the consistency of the solutions in the global constraints, which lead to effective methods for resolving the inconsistencies.
The algorithm that they have developed has proven successful. In fact, they have won the biennial competition the last three times it has taken place. In the competition held in 2006, they achieved a success rate of 91 percent. The team that came in second achieved 44 percent success rate. They are awaiting the specific results of this most recent competition.
The competition is not held in any particular location. Benchmarks to be solved were released online at regular intervals for participants to test whether their program was correct. “Then you submit your code, and then they run them on new benchmarks that you haven’t seen before,” said Wah. “This is to make sure that it is not specially tailored to each application.” The entire competition was run over several months.
Hsu, who is a graduate student in Computer Science, will be using his experience with this competition for his dissertation, in which he will refine the method developed for this competition, making it more mathematically elegant and theoretically sound.