Ioannis Refanidis
Abstract
The goal of helping to automate the management of an individual's time is ambitious in terms both of knowledge engineering and of the quality of the plans produced by an AI system. Modeling an individual's activities is itself a challenge, due to the variety of activity, constraint, and preference types involved. Activities might be simple or interruptible; they might have fixed or variable durations, constraints over their temporal domains, and binary constraints between them. Activities might require the individual being at specific locations in order, whereas traveling time should be taken into account. Some activities might require exclusivity, whereas others can be overlapped with compatible concurrent activities. Finally, while scheduled activities generate utility for the individual, extra utility might result from the way activities are scheduled in time, individually and in conjunction.
This article presents a rigorous, expressive model to represent an individual's activities, that is, activities whose scheduling is not contingent on any other person. Joint activities such as meetings are outside our remit; it is expected that these are arranged manually or through negotiation mechanisms and they are considered as fixed busy times in the individual's calendar. The model, formulated as a constraint optimization problem, is general enough to accommodate a variety of situations. We present a scheduler that operates on this rich model, based on the general squeaky wheel optimization framework and enhanced with domain-dependent heuristics and forward checking. Our empirical evaluation demonstrates both the efficiency and the effectiveness of the selected approach. Part of the work described has been implemented in the SelfPlanner system, a Web-based intelligent calendar application that utilizes Google Calendar.
- Aickelin, U., Burke, E. K., and Li, J. 2009. An evolutionary squeaky wheel optimization approach to personnel scheduling. IEEE Trans. Evolut. Comput. 13, 2, 433--443. Google Scholar
Digital Library
- Alexiadis, A. and Refanidis, I. 2009. Defining a task's temporal domain for intelligent calendar applications. In Proceedings of the 5th IFIP Conference on Artificial Intelligence Applications and Innovations (AIAI). L. Iliadis et al. Eds., Spinger, 399--406.Google Scholar
- Baptiste, P., Pape, C. L., and Nuijten, W. 2001. Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems. Kluwer, Boston, MA. Google ScholarDigital Library
- Berry, P. M., Donneau-Golencer, T., Duong, K., Gervasio, M., Peintner, B., and Yorke-Smith, N. 2009. Evaluating user-adaptive systems: Lessons from experiences with a personalized meeting scheduling assistant. In Proceedings of the 21st Conference on Innovative Applications of Artificial Intelligence (IAAI). K. Haigh and N. Rychtyckjy Eds., AAAI Press, 40--46.Google Scholar
- Feng, G. and Lau, H. C. 2008. Efficient algorithms for machine scheduling problems with earliness and tardiness penalties. Ann. Oper. Res. 159, 1, 83--95.Google ScholarCross Ref
- Freed, M., Carbonell, J., Gordon, G., Hayes, J., Myers, B., Siewiorek, D., Smith, S. F., Steinfeld, A., and Tomasic, A. 2008. RADAR: A personal assistant that learns to reduce email overload. In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI). D. Fox and C. P. Gomes Eds., AAAI Press, 1287--1293. Google ScholarDigital Library
- Gallagher, A., Zimmerman, T. L., and Smith, S. F. 2006. Incremental scheduling to maximize quality in a dynamic environment. In Proceedings of the 16th International Conference on Automated Planning and Scheduling (ICAPS), D. Long, et al. Eds., AAAI Press, 222--232.Google Scholar
- Joslin, D. and Clements, D. P. 1999. Squeaky wheel optimization. J. Artif. Intell. Res. 10, 365--397. Google ScholarDigital Library
- Joslin, D., Frank, J., Jónsson, A. K., and Smith, D. E. 2005. Simulation-Based planning for planetary rover experiments. In Proceedings of the 37th Winter Simulation Conference, M. E.Kuhl et al., Eds. 1049--1058. Google ScholarDigital Library
- Kramer, L. A. and Smith, S. F. 2003. Maximizing flexibility: A retraction heuristic for oversubscribed scheduling problems. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI). G. Gottlob and T. Walsh, Eds., Morgan Kaufmann, 1218--1223. Google ScholarDigital Library
- Laborie, P. 2009. IBM ILOG CP optimizer for detailed scheduling illustrated on three problems. In Proceedings of the 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR). W.-J. van Hoeve and J. N. Hooker Eds., Springer, 148--162. Google ScholarDigital Library
- Lim, A., Rodrigues, B., And Song, L. 2003. Manpower scheduling with Time Windows. In Proceedings of the 18th ACM Symposium on Applied Computing. G. B. Lamont et al. Eds., ACM, New York, 741--746. Google ScholarDigital Library
- Modi, P. J., Veloso, M. M., Smith, S. F., and Oh, J. 2004. CMRadar: A personal assistant agent for calendar management. In Proceedings of Conference on Agent-Oriented Information Systems. P. Giorgini et al. Eds., Springer, 169--181. Google ScholarDigital Library
- Myers, K., Berry, P., Blythe, J., Conley, K., Gervasio, M., Mcguinness, D., Morley, D., Pfeffer, A., Pollack, M., and Tambe, M. 2007. An intelligent personal assistant for task and time management. AI Mag. 28, 2, 47--61.Google Scholar
- Palen, L. 1999. Social, individual and technological issues for groupware calendar systems. In Proceedings of the ACM SIGCHI Conference on Human Factors in Computing Systems (CHI). M. G. Williams and M. W. Altom Eds., ACM, New York, 17--24. Google ScholarDigital Library
- Payne, S. J. 1993. Understanding calendar use. Hum.-Comput. Interact. 8, 2, 83--100. Google ScholarDigital Library
- Refanidis, I. 2007. Managing personal tasks with time constraints and preferences. In Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS). M. Boddy et al. Eds., AAAI Press, 272--279.Google Scholar
- Refanidis, I. and Alexiadis, A. 2008. SELFPLANNER: Planning your time! In Proceedings of ICAPS Scheduling and Planning Applications Workshop (SPARK). L. Castillo et al. Eds.Google Scholar
- Refanidis, I., Gemitzis D., and Stephanides, G. 2006. Scheduling personal time using squeaky wheel optimization. In Proceedings of the ECAI Workshop on Modelling and Solving Problems with Constraints. S. Prestwich and B. Hnich, Eds., 17--24.Google Scholar
- Refanidis, I., McCluskey, T. L., and Dimopoulos, Y. 2004. Planning services for individuals: A new challenge for the planning community. In Proceedings of the ICAPS Workshop on Connecting Planning Theory with Practice. S. Biundo and P. Jarvis Eds., 56--61.Google Scholar
- Refanidis, I. and Yorke-Smith, N. 2009. On scheduling events and tasks by an intelligent calendar assistant. In Proceedings of the ICAPS Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems. M. A. Salido and R. Bartak Eds., 43--52.Google Scholar
- Smith, S. F. 2003. Is scheduling a solved problem? In Proceedings of the 1st Multi-Disciplinary International Conference on Scheduling: Theory and Applications (MISTA). G. Kendall et al. Eds., Springer, 3--18.Google Scholar
- Varakantham, P. and Smith, S. F. 2007. Linear relaxation techniques for task management in uncertain settings. In Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS). M. Boddy et al. Eds., AAAI Press, 272--279.Google Scholar
- Varakantham, P. and Smith, S. F. 2008. Advising busy users on how to cut corners in uncertain settings. In Proceedings of the ICAPS Workshop on Oversubscribed Planning and Scheduling. L. Barbulescu et al. Eds.Google Scholar
- Verfaillie, G. and Jussien, N. 2005. Constraint solving in uncertain and dynamic environments — A survey. Constraints 10, 3, 253--281. Google ScholarDigital Library
- Zabala, L., Perfecto, C., Unzilla, J., and Ferro, A. 2001. Integrating automatic task scheduling and Web-based agenda in a virtual campus environment. In Proceedings of the 2nd International Conference on Information Technology Based Higher Education and Training (ITHET). H. Akiyama, Ed.Google Scholar
Index Terms
- A constraint-based approach to scheduling an individual's activities
Recommendations
Marketing implications of traditional and ICT-mediated leisure activities
This study investigates the role of traditional and information and communication technology ICT-mediated leisure activities in consumer behaviour. An online survey of 558 members and 1319 ex-members of an Australian DVD rental company gathered ...
Modeling human activity semantics for improved recognition performance
UIC'11: Proceedings of the 8th international conference on Ubiquitous intelligence and computingActivity recognition performance is significantly dependent on the accuracy of the underlying activity model. Therefore, it is essential to examine and develop an activity model that can capture and represent the complex nature of human activities ...
An Adaptive Rule-Based Approach to Classifying Activities of Daily Living
ICHI '15: Proceedings of the 2015 International Conference on Healthcare InformaticsThe need for a human activity recognition system arises when designing a "health smart home" which monitors its occupants to assess their health status. In this work, a rule-based system was constructed to classify the common activities of daily living ...
Comments