Individualized Learning Stories
Problem-solving Programmers
Watch a short video as the students explain the project!
Sam Estrem ’12 and Colin Potts ’13 are conducting separate, but closely related, research projects this summer with Associate Professor of Computer Science Kurt Krebsbach ’85. Their research explores ways to improve heuristic search techniques applicable to a wide variety of problems, including areas as diverse as generating driving directions, scheduling package deliveries, planning Hubble Space Telescope observations and even generating candidate answers for IBM’s Jeopardy-playing Watson.
The two mathematics-computer science majors are attempting to develop programs — or more generally, “algorithms” — that plan sequences of actions to achieve specific goals that are faster or require less memory than methods other researchers have devised. A computer then uses these more efficient techniques to solveany number of different problems without changing the algorithm at all.
“We’re giving the computer a way to think about a problem to see if that’s an efficient or inefficient way of solving that,” said Potts, a junior from Berkeley Lake, Ga. “I’m sure companies like Google would be very interested in new techniques that would be faster for solving search problems in their specific domain.”
“What we’re doing is so abstract,” added Estrem, a senior from Newberg, Ore., who presented some of his research last year at an undergraduate research symposium in St. Louis. “To visualize any of this stuff — programming is just lines and words — to really get a grasp on it, we end up drawing a whole bunch of ‘trees’ and graphs to visualize how these algorithms work.”
Their problem-solving research dovetails nicely with Krebsbach’s own research interests in automated planning.
“Initially my goal was to have a part that I could carve off and let these guys loose on, supervise their progress and maybe be able to transfer some of their results to my research area,” said Krebsbach, who returned to his alma mater as a faculty member in 2002. “But they’re doing such a good job, they’re as good as many of the graduate students I encountered when I was at the University of Minnesota. They’ve exceeded my expectations. We’re hoping we can do some published work between the three of us before Sam and Colin graduate.”
Estrem and Potts often work on their projects at all hours of the day and night, regularly updating the research team on their progress, and meeting with Krebsbach often for strategy and critique sessions.
“It’s invaluable having the face-to-face meetings,” said Krebsbach. “Just having other people who are familiar with what’s going on, but maybe are not doing that exact thing, to look at it alongside you, and to critique and give you suggestions is helpful. We give each other a hard time about every detail on the slides and choice of colors on the graphs. But it’s fun. It gets us thinking about all the same related things and leads to hours of useful technical discussion.”
Estrem began working on his research — “AIRS: Anytime Incremental Refinement of a Solution” — in early 2010. His approach is to have the computer generate a “bad” but valid solution very quickly and use remaining computational time to incrementally improve the solution until time runs out. Complemented by several tutorials and independent studies classes, he plans to fold it into a Senior Experience and perhaps an Honors Project as well.
Potts is developing a variation of the IDA* algorithm he is calling “Iterative Expansion A*”, which exploits available memory to reduce search time. The experience, Potts says, has helped him focus on different career paths after Lawrence.
“A lot of the stuff we’re doing really gives you a good idea and exposure as to what your life would be like if you chose to do this kind of work. It’s really invaluable to your life to just jump into it this early and know what’s going on.”
