Students Publish Temporal Planning Research

Student researchers at Harvey Mudd aren’t exactly on a mission to Mars, but their work could lead to red planet rovers learning some new tricks. In a computer science/mathematics collaboration, Amy Huang ’18 and Liam Lloyd ’18 use geometry to seek ways to embed time management and efficiency into artificial intelligence technologies, aiming to produce a set schedule that’s flexible enough to accommodate unexpected events.

Huang’s and Lloyd’s project is described in their paper, “New Perspectives on Flexibility in Simple Temporal Planning,” which was accepted for publication and presentation at the International Conference on Automated Planning and Scheduling this summer in Delft, Netherlands.

“The project explores geometric interpretations of scheduling problems,” says computer science professor Jim Boerkoel. “The set/space of schedules that are valid possibilities can be represented using something called a simple temporal network (STN), which is a network of constraints of the form. For example, ‘Activity A must start between 8 a.m. and 10 a.m.’”

Mars rovers appear in the paper as one example of the challenge presented by inflexible schedules, which, in the rover’s case, is exacerbated by the eight-minute lag for all communication links to and from Earth. Because of this, to be efficient, rovers need autonomous schedules that can be flexible when unexpected events occur.

Other potential applications for the work are somewhat more terrestrial. “Our work could be applicable to almost any system where STNs are used,” says Lloyd. “STNs are popular on systems with low computation power, which range from Roombas to satellites.”

The researchers explored the idea that temporal networks of constraints could also be interpreted as geometric shapes, where each event that needs scheduling adds a new dimension. “These n-dimensional interpretations are actually geometric shapes, but they become very hard to visualize as we extend beyond two or three dimensions,” Boerkoel says.

That’s where the students’ diversity of knowledge, interests and experience come in. “A project like this highlights the value of a cross-disciplinary core that prepares students with a broad base of STEM knowledge,” says Boerkoel, whose Human Experience and Agent Teamwork Laboratory at Harvey Mudd joined forces with Huang, Lloyd and mathematics professor Mohamed Omar on the project. “We were able to push insights further than if we had attacked the problem from a computer science perspective alone.”

Omar agrees, noting that this type of collaboration gives mathematics and computer science more capability than either has alone. “In this project, we were interested in finding a way to quantify the inherent flexibility of an STN,” he says. “In order to do that, we noticed that STNs could be modeled geometrically, and the mathematics of these geometric figures gave us a natural way to quantify what flexibility could be for an STN. This allowed us to use quite theoretical mathematics in a robotics setting, having potential for greater social impact.”

Indeed, with this research, Huang and Lloyd have begun to define what a flexibility metric should be, offering new metrics that are closer to the ideal than previous ones were.

“While the flexibility of STNs has been written about for decades, it has always been defined in terms of some particular metric,” Huang says. “The field has not settled on a canonical metric, suggesting that measuring flexibility is difficult. We determined that the further search for flexibility metrics will benefit from a clearer target, and thus defined a set of desiderata that we feel flexibility metrics should have.”