Method, apparatus, and system for distributed meeting scheduling based on autonomous multi-agent

According to one aspect of the invention, a method is provided in which a scheduling agent is assigned to each user in a system. Each scheduling agent is responsible for coordinating meeting activities for its associated user. Each user in the system is allowed to specify preferences for meeting scheduling based upon his corresponding calendar. In response to a meeting request initiated by one of the users, the scheduling agent for the meeting initiator and the scheduling agents for the attendees negotiate with each other to schedule the requested meeting at a most suitable time that is accepted by all attendees through their associated scheduling agents, based upon a set of scheduling criteria including the meeting timing information and the attendees preferences for meeting scheduling.

FIELD OF THE INVENTION

The present invention relates to the field of computer processing. More specifically, the present invention relates to a method, apparatus, and system for distributed meeting scheduling based on autonomous multi-agent.

BACKGROUND OF THE INVENTION

In the current office environment, meetings have taken people a lot of time and energy. An executive will often spend a much larger percentage of his/her work time on meetings. Therefore the efficiency of the scheduling process used and the quality of the schedules generated affect the working of an organization to a large extent. Typically, the initiator of a meeting will have to negotiate with every attendee to arrange the meeting at such time that is acceptable to all the attendees in order to make sure that all attendees will be available to attend the meeting. Especially when a meeting has many attendees, the discourse of negotiation will often go on several rounds before reaching an agreement of the appropriate meeting time. Even when everyone involved in a meeting has available times to meet, the process for searching for a commonly available time, in the presence of communication delays (e.g., either through electronic mail or contacting by phone) and in the presence of other meetings being scheduled concurrently, can be frustrating and lead to less than satisfactory results.

Most of the commercially available software for scheduling over computer networks have been personal computer-based systems. Similarly, there have been a number of research projects that assist a human user in meeting scheduling process. However, there are severe drawbacks in the current commercial products and research systems. First, the scheduling discourse still needs user's interference. There are disadvantages with the user's interference: it takes a lot of the user's time and energy, and it can produce errors that might be introduced by human users due to the routine and tedious nature of the meeting schedule. Second, the scheduling activity is static. The dynamic nature of the users' calendars cannot be considered in time, which often leads to the failure of meeting scheduling. Third, there is a lack of privacy and security. The user must open his/her calendar to others, the necessary privacy cannot be guaranteed. The openness of the user's calendar also facilitates the malicious scheduling and attack. In addition, most current systems are the centralized ones in which the request for meeting scheduling must be sequenced and multiple meetings cannot be scheduled concurrently, which severely affects the throughput of the scheduling process.

DETAILED DESCRIPTION

In the following detailed description numerous specific details are set forth in order to provide a thorough understanding of the present invention. However, it win be appreciated by one skilled in the art that the present invention may be understood and practiced without these specific details.

In the discussion below, the teachings of the present invention are utilized to implement a method, apparatus, system, and machine-readable medium for distributed meeting scheduling based on autonomous multi-agent. According to the teachings of the present invention, autonomous scheduling capabilities are provided through information exchange between intelligent meeting scheduling agents. In a meeting scheduling environment according to one embodiment, each user has one agent on acting on behalf of the user to take part in the negotiation of meeting scheduling according to the current dynamic user calendar. Not only that this configuration can save time and effort on the part of the human users, it also can lead to more efficient schedules and to changes in how information is exchanged within organizations. The distributed nature of the scheduling process allows for better throughput through concurrent negotiation on multiple meetings. Moreover, the user's preference(s) for the meeting scheduling are also taken into consideration. For example, when a meeting has several scheduling options, the agents will negotiate to reach an agreement of meeting scheduling based on all attendees' global preferences. In addition, since all meeting requests and calendar accesses are routed through the meeting scheduling agent, it can protect the privacy of its associated user while satisfying preferences of this individual. In one embodiment, a scheduling agent is assigned to each user in a system. Each scheduling agent is responsible for coordinating ands scheduling meeting activities for its associated user. In one embodiment, each user in the system may specify his/her preferences for meeting times and scheduling based upon his/her corresponding calendar. In one embodiment, in response to a meeting request initiated by one of the users, the scheduling agent for the meeting initiator and scheduling agents for the attendees negotiate with each other to schedule the requested meeting at a most suitable time that is accepted by all attendees through their corresponding scheduling agents, based upon a set of scheduling criteria including the meeting timing information and the attendees' preferences for meeting times. In one embodiment, the meeting timing information includes a set of possible start times for the requested meeting and an expected duration for the requested meeting. In one embodiment, each scheduling agent is assigned a network address and the addresses for the scheduling agents are maintained by a facilitator. Based upon the meeting timing information and the attendees' preferences, a list meeting suggestions is determined. Each meeting suggestion is assigned a relative score. A meeting suggestion with a higher score is considered more preferable than a meeting suggestion with a lower score. Based upon this list of meeting suggestions starting with the meeting suggestion that has the highest score, the scheduling agents will negotiate to obtain a consensus from all attendees with respect to a specific meeting suggestion until a consensus is obtained from all attendees or until all meeting suggestions have been exhausted. If a consensus can be obtained from all attendees for at least one meeting suggestion, a meeting notice is sent to the meeting initiator and the attendees. If a consensus cannot be obtained for any meeting suggestion, the meeting initiator is notified of a failure to schedule the requested meeting. In one embodiment, the list of meeting suggestions is determined as follows. Upon the initiation of the meeting request, a list of candidate suggestions is created based upon the meeting timing information. Each candidate suggestion includes a possible start time and the expected duration of the requested meeting. The list of candidate suggestions is then sent to the scheduling agents of the meeting attendees. The list of meeting suggestions is then formed based on the feedback received from the attendees' scheduling agents. The feedback received, in one embodiment, includes individual scores given to each candidate suggestion by the corresponding scheduling agents based upon the attendees' preferences. A list of optional suggestions is then formed by removing from the list of candidate suggestions those candidate suggestions that are not feasible based upon the feedback received from the attendees' scheduling agents. Each optional suggestion is assigned a corresponding global score based upon the individual scores given by the attendees' scheduling agents. The list of optional suggestions is then sorted in a specified order based upon the global score of each optional suggestion to form a list of reserving suggestions. Starting with the reserving suggestion that has the highest global score, a meeting scheduling negotiation process is performed to determine whether a particular reserving suggestion is acceptable to all meeting attendees. In one embodiment, the meeting scheduling process is performed as follows. The scheduling agent for the meeting initiator checks with the attendees' scheduling agents in a specified order to determine whether a particular reserving suggestion is acceptable to the attendees. If that particular reserving suggestion is acceptable to all attendees, then the requested meeting is scheduled according to the timing of that particular suggestion. If that particular reserving suggestion is not acceptable to any attendee, it is discarded and the meeting scheduling negotiation process is continued with the next reserving suggestion in the list.

FIG. 1shows a block diagram of one embodiment of a system framework100according to the teachings of the present invention. As shown inFIG. 1, the system framework100includes a facilitator110and a set of scheduling agents120(1–N) each of which acts on behalf of its associated user. In one embodiment, each individual or user in the organization is provided with an autonomous meeting scheduling agent120. The network addresses of the agents120are registered with the facilitator110. In one embodiment, when a user joins the organization, the corresponding agent120will register its network address with the facilitator automatically. Likewise, if the network address of a user's agent is changed, the corresponding agent120will request the facilitator110to update its address. If the user leaves, the agent120will request the facilitator to remove its network address. The inclusion of the facilitator110in the system framework100is very helpful to adapt the scalability and dynamics of the organization because the agents120can easily contact with each other through the addresses obtained from the facilitator110.

In one embodiment, if a user wants to schedule a meeting with other users, he/she informs his/her associated agent of the meeting request. The agent gets the addresses of all the attendees' agents from facilitator, and then negotiates with the attendees' agents to determine whether the requested meeting can be scheduled successfully based on the preferences that are predefined by the users and the timing constraints specified by the meeting request. The scheduling discourse is asynchronous and autonomous. The scheduling result will be sent out by the agent acting on behalf of the initiator. In one embodiment, if the scheduling of the requested meeting is successful, the agent will send a meeting notice to all the attendees and the meeting initiator. If the scheduling fails, a notice of failure will be sent out only to the initiator. Under this condition, it is often that the constraint of the requested meeting is too strict to be met by all the attendees (e.g., the meeting time is constrained to only one option, 2:00–3:00 p.m, etc.). In this instance, the initiator can modify the meeting constraint and begin a new round of scheduling. According to the teachings of the present invention, multiple requests of meeting scheduling can be processed concurrently. Although the capability of concurrent scheduling makes the system more complicated, it allows high throughput and more efficiency in the meeting scheduling process.

FIG. 2illustrates a block diagram of one embodiment of the architecture of the scheduling agents, according to the teachings of the present invention. As shown inFIG. 2, a scheduling agent includes a user interface210, a scheduler manage unit220, a user preference unit230, a mailbox240, a communication control unit250, and a calendar manage unit260. In the present embodiment, the scheduler manage220is considered the core unit or core module of the scheduling agent, which takes charge in the meeting scheduling activities for the user and negotiates with other agents on the basis of the user's dynamic calendar and preference. A user can utilize the user interface210to request the meetings, define or edit the meeting timing information and/or his/her preference for the meeting scheduling. In one embodiment, the information exchange between agents or between agent and facilitator is controlled by the communication control unit250. In one embodiment, the user preference unit230is used to store the user preference(s) for the meeting scheduling based on his/her calendar. Calendar manage unit260records, among other things, the user's daily activities which include meetings with other users and his personal activities. In one embodiment, the result of the meeting scheduling will be sent to the users through the mailbox240in the manner of email. It should be appreciated and understood by one skilled in the art the agent's architecture shown inFIG. 2is for illustration and explanation purposes and does not limit the scope of the present invention which includes other types of agent's architecture and configurations that may or may not have all the components or units shown inFIG. 2. Similarly, depending upon the specific implementations and/or applications of the present invention, the function(s) of the various units or components shown inFIG. 2may be configured differently and each unit may perform its corresponding function in a different manner. For example, the result of meeting scheduling may be sent to the users in another form or manner (e.g., network broadcasting or other types of message communication, etc.).

The Global Preferences of Users

Meeting scheduling is a kind of social or business activity that involves multiple human users. Since the agents will act on behalf of the users to negotiate with each other to schedule meetings, it is important to integrate the users' preferences (e.g., preferences for meeting timing and scheduling) into the decision-making of the agent. However, different users may have different preferences for the meeting scheduling. Especially when there are many feasible suggestions for a meeting request, it is meaningful to schedule the meeting so that it will fit all the attendees' preferences. The following discussion explains how the meeting scheduler in accordance with the teachings of the present invention uses the user preferences to schedule meetings in a manner that will satisfy the user.

In a multi-agent model described herein, each user can express or specify his or her preferences over all the available time slots in the user's calendar. Through the associated agent, the user can predefine or modify his/her preferences over the time slots. In one embodiment, the preferences will be quantitated as a positive number and stored in the user preference unit or module of the corresponding agent. A user can express the preferences in the periodic way or just for a special day or time. For a time slot that has been occupied, the agent will update the user's preference for the respective time slot as zero. When the time slots that involve in a meeting suggestion are all free, the user's preference for a meeting suggestion will be the sum of the preference points for the individual timeslots divided by the duration of the meeting. If the meeting suggestion involves a busy timeslot (e.g., the user's preference for the timeslot has been updated as zero), the user's preference for the meeting suggestion will also be zero, which means that the suggestion is not an option.

In the discourse of multi-agent negotiation, the global preference will be emphasized for the meeting scheduling. However, when there are multiple options for a meeting, there is a question of how to decide or select the best one based on the global preference of users? A simple strategy is to select the one that has the maximal sum of preferences that the users define. But this solution cannot meet the different users' preferences for the following reasons. Suppose that user A and user B will be the attendees of a meeting and two options meeting time T1and T2are available. User A has a preference point1for T1and user B has a preference point7for T1However, user A has a preference point3for T2and user B has a preference point4for T2. It is not correct to say that T1is more suitable or more preferable than T2,although the sum of the preference points for T1is 8 which is larger than that for T2. Actually, T2is more preferable under many conditions due to the nature of the meeting scheduling activity. The meeting scheduling is a negotiating activity, so it is more important to reach a consensus from different users with respect to the scheduling. In one embodiment, based on this reason, the outcome that maximizes the product of all the meeting attendees' preference points is chosen as the most suitable option for all meeting attendees. This approach guarantees a relatively fair distribution of the individual preferences and narrows the space of feasible consensus states.

The Solution for the Conflict for Concurrent Meeting Scheduling

The distributed meeting scheduling process described herein works in a asynchronous and distributed manner, and permits multiple meeting scheduling activities to be processed concurrently. Therefore it is possible that a user may act as the initiator and attendee, or as the attendee of different meetings at the same time. This brings more flexibility and higher throughput. But it also gives rise to the conflict of concurrent scheduling. The following example is used to explain this condition.

Supposed that there are two meeting requests M1and M2initiated in the current scheduling environment. M1is initiated by user u1, and attendees are user u1, u2, u3(note that the initiator of a meeting does not always attend the meeting. For example, a secretary can schedule meetings for his/her boss but may not be required to attend the meetings). M2initiated by user u4, and u2, u3, u4,are the attendees. The meeting times for both meetings are 2:00–3:00 p. m. on the same day. In this example, the associated agents are named after the users. Accordingly, the agent u1will send its request to agents u1, u2, u3. At the same time agents u2, u3, u4may possibly get a request from agent u4. It is therefore possible that the following conflict condition will take place as illustrated inFIG. 3.

Continuing with present discussion, it is assumed that the agent u2has accepted the request from agent u1and agent u3has accepted the request from agent u4. Consequently, the agent u3win decline the request from agent u1, and agent u2will decline the request from agent u4. Thus neither of the two scheduling activities can be successful. In one embodiment, to avoid this conflict, a global order of the users is predefined (e.g., the alphabetical order of attendees' names). The agent of the meetings initiator will query the attendees' agents according to the predefined global order. In the present example, it is assumed that the global order of users is u1, u2, u3, u4. Then agent u1will send out the meeting request in the order of u1, u2, u3and agent u2will send out request in the order of u2, u3, u4. For the two requests from the agents u1and u4respectively, the request that is first accepted by the agent u2will continue to be sent to the next attendee's agent, and the other request will be declined.

FIG. 4shows a flow diagram of one embodiment of a method for distributed meeting scheduling according to the teachings of the present invention. At block410, a scheduling agent is assigned to each user in a system. Each scheduling agent, as described above, is responsible for coordinating meeting activities for its associated user. At block420, each user in the system is allowed to specify or express preferences for meeting scheduling based upon his/her calendar. At block430, in response to a meeting request initiated by a user, the scheduling agent for the meeting initiator and the scheduling agents for the attendees negotiate with each other to schedule the requested meeting at a most suitable time that is accepted by all attendees through their associated agents, based upon a set of scheduling criteria including the meeting timing information and the attendees' preferences for meeting scheduling as described above.

FIG. 5shows a flow diagram of one embodiment of a process for meeting scheduling in accordance with the teachings of the present invention. The following discussion provides in details the scheduling process taken into consideration the global users' preferences and the conflict of concurrent scheduling as described above. First, the related formal description for meetings are described below. Given a typical meeting schedule environment, which consist a set of p users. A meeting request can be defined as:
R=(H,A,S,ST,L),
where:
H is the user who requests the meeting, called initiator. The associated agent of the meeting initiator is designated as the initiator agent (AGh) for the requested meeting;
A| U(U={1,2, . . . , p}, is the set of users to attend the meeting, called attendees, the corresponding associated agents for the attendees are called attendee agents (A Gi, iεA). It's possible that HεA or not (H may or may not be one of the attendees). In one embodiment, if HεA and |A|=1, it means that the initiator reserves the times for himself/herself on the calendar;
S is the subject of the requested meeting;
ST is a set of possible start times for the meeting;
L is the desired length that the meeting will last (also called the anticipated or expected duration for the meeting).
The following assumptions and definitions are also provided:

Candidate suggestions are the meeting suggestions that meet the requirements or constraints of the meeting request (R). These candidate suggestions are proposed by the initiator agent (AGh) before the negotiation and can be described as a set of pair {t, L}, where tεST, is a possible start time for the meeting, L is the length that the meeting will last (also called anticipated or expected duration of the meeting);

Optional suggestions are a subset of the candidate suggestions which are feasible for all the meeting attendees (A). However, the optional suggestions have not been considered on the basis of the global users' preferences;

A reserving suggestion is one of the optional suggestions that is considered the most optimal or suitable suggestion at the present based on the above-discussed approach for the global users' preferences.

It is assumed that the calendar of the user is divided into some basic time slots (e.g., 30 minutes each).

The method illustrated inFIG. 5works as follows:

At block510: the initiator of the meeting H gives his/her associated agent (initiator agent, AGh) the meeting request (R). AGhproduces all the candidates suggestions and send them to all attendees' agents (AGi, iεA);

At block520: each AGithat receives the candidate suggestions will give each candidate suggestion suitable points (also called score), based on the predefined preference of its associated user and then sends out the feedback to AGh;

At block530: when AGhgets all the feedback from all the AGi, it forms a list of optional suggestions by removing those infeasible candidate suggestions. The initiator agent then calculates the global preference points (score) for each optional suggestion, sorts them in a list according to a specified order (e.g., descending order) of the global reference scores. This sorted list of optional suggestions based on the global reference scores is also called the list of reserving suggestions. The initiator agent then selects the first reserving suggestion in the list;

At block540: the AGhwill send the selected reserving suggestion to all the AGi, one after another in the global order of all the users. After getting the selected reserving suggestion, AGifirst checks its calendar to decide whether its time slot involved in the reserving suggestion is still free. If the time slot is free, it will accept the meeting request and update its calendar with the meeting, then send out the “acknowledge” (also called acceptance) information to AGh. If the time slot is not free, it will send out “decline” to the AGh;

At block550: AGhwaits for the feedback from the AGi. If it gets the “acknowledge” from the AGi, it will send the selected reserving suggestion to the next attendee agent in the global order of users. Once AGhgets a “decline” message (e.g., which may indicate that the previously available time of that attendee user is not available now), it will stop sending the selected reserving suggestion to the remaining attendee agents. Instead, AGhsends out a “cancel” message to the AGiwho has accepted the reserving suggestion. AGhthen selects the next one from the list of reserving suggestions (the sorted optional suggestions) as the new reserving suggestion and begins a new round of scheduling.

At block560: when the AGhgets the acknowledge message from all the attendee agents (i.e., the selected reserving suggestion is accepted by all attendees), it sends out a meeting notice to all the attendees and the initiator. If the AGhhas tried all the reserving suggestions but none is accepted by all attendees (e.g., it gets a decline message for each of the reserving suggestions), which indicates that there no longer available time slots that can meet the constraint of the meeting request R that is proposed by H. In this case, AGhwill send out a notice of failure only to the initiator H. The initiator H can modify the meeting constraint and reschedule the meeting or just cancel the meeting.

The invention has been described in conjunction with the preferred embodiment. It is evident that numerous alternatives, modifications, variations and uses will be apparent to those skilled in the art in light of the foregoing description.