[full paper] |
Takuo Tsuruta, Toramatsu Shintani
Scheduling meetings is generally difficult in that it attempts to satisfy the preferences of all participants. However, all participants can agree to a schedule in which a portion of their preferences are not satisfied, since preferences are regarded in terms of their relative importance. In this paper, we formalize a meeting scheduling as a Distributed Valued Constraint Satisfaction Problem (DVCSP) and propose an algorithm for solving over-constrained problems formalized as a DVCSP by means of constraint relaxation based on importance. Our algorithm can relax lower priority constraints and schedule meetings that satisfy as many of the important constraints as possible under over-constrained conditions. We show a group schedule management system, consisting of multiple agents, and COLS which can concretely specify users' preferences as constraints. Our experiments show that our algorithm can discover a semi-optimal solution to over-constrained meeting scheduling problem in practical time. We can conclude that our algorithm is cost effective in comparison to another method that can find an optimal solution.
Keywords: Multi-Agent Systems, Constraint Satisfaction, Scheduling
Citation: Takuo Tsuruta, Toramatsu Shintani: Scheduling Meetings Using Distributed Valued Constraint Satisfaction Algorithm. In W.Horn (ed.): ECAI2000, Proceedings of the 14th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2000, pp.383-387.