Investigating human-computer optimization

ABSTRACT

Scheduling, routing, and layout tasks are examples of hard optimization problems with broad application in industry. Past research in this area has focused on algorithmic issues. However, this approach neglects many important human-computer interaction issues that must be addressed to provide people with practical solutions to optimization problems. Automatic methods do not leverage human expertise and can only find solutions that are optimal with regard to an invariably over-simplified problem description. Furthermore, users must understand the generated solutions in order to implement, justify, or modify them. Interactive optimization helps address these issues but has not previously been studied in detail. This paper describes experiments on an interactive optimization system that explore the most appropriate way to combine the respective strengths of people and computers. Our results show that users can successfully identify promising areas of the search space as well as manage the amount of computational effort expended on different subproblems

REFERENCES

• 1: David Anderson , Emily Anderson , Neal Lesh , Joe Marks , Brian Mirtich , David Ratajczak , Kathy Ryall, Human-Guided Simple Search, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.209-216, July 30-August 03, 2000
• 2: S. Chien , G. Rabideau , J. Willis , T. Mann, Automating planning and scheduling of shuttle payload operations, Artificial Intelligence, v.114 n.1-2, p.239-255, Oct. 1999 [doi>10.1016/S0004-3702(99)00069-7]
• 3: Cohen, P.R., Oates, T., and St. Amant, R. (1996). Plan Steering and Mixed-Initiative Planning. In A. Tate, ed. ARPI Supplement to Proc. 3rd Intl. Conf. on AI Planning Systems, pp. 105--112.
• 4: Colgan, L., Spence, R., and Rankin, P. (1995). The Cockpit Metaphor. Behaviour & Information Technology, 14(4), pp. 251--263.
• 5: Michael T. Cox , Manuela M. Veloso, Supporting Combined Human and Machine Planning: An Interface for Planning by Analogical Reasoning, Proceedings of the Second International Conference on Case-Based Reasoning Research and Development, p.531-540, July 25-27, 1997
• 6: Do Nascimento, H.A.D, and Eades, P. (2002). To appear in Proc. of Graph Drawing '02.
• 7: George Ferguson , James F. Allen, TRIPs: an integrated intelligent problem-solving assistant, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.567-572, July 1998, Madison, Wisconsin, United States
• 8: Michael Gleicher , Andrew Witkin, Drawing with constraints, The Visual Computer: International Journal of Computer Graphics, v.11 n.1, p.39-51, 1994 [doi>10.1007/BF01900698]
• 9: Sandeep Kochhar , Mark Friedell, User control in cooperative computer-aided design, Proceedings of the 3rd annual ACM SIGGRAPH symposium on User interface software and technology, p.143-151, October 03-05, 1990, Snowbird, Utah, United States [doi>10.1145/97924.97941]
• 10: Greg Nelson, Juno, a constraint-based graphics system, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.235-243, Jul. 1985
• 11: Kathy Ryall , Joe Marks , Stuart Shieber, An interactive constraint-based system for drawing graphs, Proceedings of the 10th annual ACM symposium on User interface software and technology, p.97-104, October 14-17, 1997, Banff, Alberta, Canada [doi>10.1145/263407.263521]
• 12: Kamran E Shahroudi, Design by continuous collaboration between manual and automatic optimization, CWI (Centre for Mathematics and Computer Science), Amsterdam, The Netherlands, 1997
• 13: Karl Sims, Artificial evolution for computer graphics, ACM SIGGRAPH Computer Graphics, v.25 n.4, p.319-328, July 1991
• 14: Smith, S.F., Lassila, O., and Becker, M. (1996). Configurable, Mixed-Initiative Systems for Planning and Scheduling. In A. Tate, ed. Advanced Planning Technology, AAAI Press.
• 15: M. M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, v.35 n.2, p.254-265, March-April 1987 [doi>10.1287/opre.35.2.254]
• 16: Stephen Todd , William Latham, Evolutionary Art and Computers, Academic Press, Inc., Orlando, FL, 1994
• 17: Waters, C.D.J. (1984). Interactive vehicle routeing. J. of the Operational Research Society, 35(9), pp. 821--826.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human factors

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: User interfaces

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.5 Implementation
          Subjects: Interactive systems

General Terms:
Design, Human Factors, Performance, Theory

Keywords:
human-in-the-loop, interactive optimization, semi-automatic optimization, tabletop interfaces, training systems, user study