Human-Guided Search

Speaker
Joe Marks

When
-

Where
Newell-Simon Hall 1305 (Michael Mauldin Auditorium)

Description

Most previous research on scheduling, routing, and layout problems has focused on the development of fully automatic, batch-process algorithms. However, people often have a superior understanding of the amorphous real-world constraints that apply to a particular problem. Moreover, humans have abilities, such as visual perception, learning from experience, and strategic assessment that cannot (currently) be emulated by computer. So why not put a person in the loop for optimization tasks where human abilities may complement and enhance the computer’s?

In this talk, I will present visualization and interaction techniques that allow human users to guide and focus simple search heuristics, such as hill climbing and tabu search. We have applied our approach to several problems, including vehicle routing and rectangular strip packing. Our results show that human input can greatly improve the performance of simple search heuristics. Using our prototype system, human test subjects have achieved results that match or exceed those achieved by the best known batch algorithms on benchmark academic problems.

Joint work with: D. Anderson, E. Anderson, G. Klau, N. Lesh, A. McMahon, M. Mitzenmacher, B. Mirtich, D. Ratajczak, K. Ryall, S. Scott, and S. Whitesides.

Speaker's Bio

Joe Marks grew up in Dublin, Ireland, before emigrating to the U.S. to attend college. He holds three degrees from Harvard University. His areas of interest include computer graphics, human-computer interaction, and artificial intelligence. He has worked previously at Bolt Beranek and Newman and at Digital’s Cambridge Research Laboratory. He was Research Director at Mitsubishi Electric Research Labs (MERL) from 2000–2006. He is the recent past chair of ACM SIGART, and the conference chair for SIGGRAPH 2007.

Host
Dan Siewiorek