Human-Guided Search
Interactive, or human-in-the-loop, optimization systems leverage people's abilities in areas in which they outperform computers, such as visual and strategic thinking. Users can steer interactive optimization systems towards solutions which satisfy real-world constraints. Furthermore, people can better understand, justify, and modify solutions if they have participated in their construction. We have developed the Human-Guided Search (HuGS) framework and Java toolkit for rapidly developing interactive optimization systems. The framework and code include visual metaphors for focusing and constraining optimization algorithms. The user can select from different algorithms, including a human-guidable version of a powerful heuristic, called tabu search. We have developed a wide variety of applications with the HuGS toolkit, including interactive systems to solve scheduling, vehicle routing, layout, and protein-folding problems.
Background & Objective: This work represents a multi-person, multi-year, ongoing effort to develop experience, techniques, and generic software to produce interactive optimization systems. Our goal is to overcome many limitations of almost all current optimization systems. Current optimization systems typically solve an oversimplified formulation of the real-world problem and produce solutions which are difficult for users to understand or trust. In contrast, interactive optimization allows users to explore many possible solutions in order to better understand the tradeoffs between possible solutions and then choose a solution based on their rich understanding of the domain.
Technical Discussion: Our framework provides the user a greater degree of control than previous interactive optimization approaches. Users can manually modify solutions, backtrack to previous solutions, and invoke, monitor, and halt a variety of search algorithms. More significantly, users can constrain and focus the search with a visual metaphor that we have found effective on a wide variety of problems. Our experiments have shown that human guidance can improve the performance of the exhaustive search algorithm on thecapacitated-vehicle-routing-with-time-windows problem to the point where the interactive algorithm is competitive with the best previously reported algorithms. Further experiments on other problems has shown that 10 minutes of guided tabu search is comparable to, on average, 70 minutes of unguided tabu search.
Outside Collaborations: We are actively collaborating with researchers at Harvard University, Vienna University of Technology, and McGill University.
Contact: Joseph Katz
Publications:
Anderson, D., Anderson, E., Lesh, N.B., Marks, J.W, Mirtich, B., Ratajczack, D.; Ryall, K., "Human-Guided Simple Search", National Conference on Artificial Intelligence (AAAI), ISBN 0-262-5112-6, August 2000 (AAAI Press, TR2000-016)
| Technical Reports: | |
| Human-Guided Tabu Search | |
| The HuGS Platform: A Toolkit for Interactive Optimization | |
| Investigating Human-Computer Optimization | |
| Interactive Partitioning | |
Technology Areas:
Sensor and Data Systems
Artificial Intelligence
Modification Date: September 12, 2007
