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. Anderson, D., Anderson, E., Lesh, N., Marks, J., Mirtich, B., Ratajczak, D., and Ryall, K. (2000). Human-guided simple search. Proc. of pp. 209--216.
2. Chien, S., Rabideau, G., Willis, J., and Mann, T. (1999). Automating planning and scheduling of shuttle payload operations. J. of Artificial Intelligence, 114, pp. 239--255.
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. Cox, M.T., and Veloso, M.M. (1997). Supporting Combined Human and Machine Planning: An Interface for Planning by Analogical Reasoning. Proc. 2nd Intl. Conf. on Case-Based Reasoning, pp. 531--540.
6. Do Nascimento, H.A.D, and Eades, P. (2002). To appear in Proc. of Graph Drawing '02.
7. Ferguson, G. and Allen, J. (1998). Trips: an integrated intelligent problem-solving assistant. Proc. 15th National Conf. of Artificial Intelligence, pp. 567--572.
8. Gleicher, M. and Witkin, A. (1994). Drawing with constraints. Visual Computer, 11, 39--51.
9. Kochhar, S. and Friedell, M. (1990). User control in cooperative computer-aided design. Proc. of UIST '90, pp. 143--151.
10. Nelson, G. (1985). Juno, a constraint based graphics system. Computer Graphics, 19(3) (Proc. of SIGGRAPH '85), pp. 235--243.
11. Ryall, K., Marks, J., and Shieber, S. (1997). Glide: an interactive system for graph drawing. Proc. of UIST '97, pp. 97--104.
12. Shahroudi, K.E. (1997). Design by continuous collaboration between manual and automatic optimization. Centrum voor Wiskunde en Informatica Technical Report SEN-R9701.
13. Sims, K. (1991). Artificial evolution for computer graphics. Computer Graphics, 25(3) (Proc. of SIGGRAPH '91), pp. 319--328.
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. Solomon, M.M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), pp. 254--265.
16. Todd, S. and Latham, W. (1992). Evolutionary Art and Computers. Academic Press.
17. Waters, C.D.J. (1984). Interactive vehicle routeing. J. of the Operational Research Society, 35(9), pp. 821--826.

Index Terms

• Human-centered computing

  • Human computer interaction (HCI)

    • Interactive systems and tools

• Software and its engineering

  • Software notations and tools

    • Development frameworks and environments

      • Integrated and visual development environments