HomeDigital EditionSys-Con RadioSearch Java Cd
Advanced Java AWT Book Reviews/Excerpts Client Server Corba Editorials Embedded Java Enterprise Java IDE's Industry Watch Integration Interviews Java Applet Java & Databases Java & Web Services Java Fundamentals Java Native Interface Java Servlets Java Beans J2ME Libraries .NET Object Orientation Observations/IMHO Product Reviews Scalability & Performance Security Server Side Source Code Straight Talking Swing Threads Using Java with others Wireless XML
 

Almost every working professional has experienced the tedium and frustration that results from scheduling a meeting for multiple attendees with potentially conflicting schedules plus additional constraints imposed by the meeting rooms and other resources. This problem deserves serious attention as many people in typical organizations have to spend a large portion of their working time in scheduling and attending meetings. With autonomous agents [1], which can schedule meetings and manage calendars on behalf of their users, the savings in time and effort can be tremendous. Users can then be relieved for more creative and productive tasks.

In this article, we introduce a Java-based multi-agent meeting organizer that requires multiple personal assistants (i.e., software agents) to collaborate with each other for automated meeting scheduling and calendar management. The prototype, known as AMEETZER (multi-Agent MEETing organiZER) represents and reasons with soft constraints related to the meeting attendees and meeting resources. Each AMEETZER interacts with its user, Registry, Room Manager and other AMEETZERs to schedule or negotiate meetings for its user. Using soft constraints allows tedious negotiations to be simplified into one-shot constraint satisfaction to arrive at an optimal meeting time, respecting all hard and soft constraints with graceful degradation. Internally, an AMEETZER is decomposed into four subagents - Receptionist, Scheduler, Messenger and Dispatcher. Inter- and intra-agent communications are realized in a uniform manner with KQML-like messages.

Overview
AMEETZER is a multi-agent meeting organizer that assists its user to manage his or her calendar and to call for meetings with other users. Upon accepting a call-for-meeting request from its user (host), an AMEETZER communicates with other AMEETZERs of the proposed attendees and the agent managing the meeting rooms (i.e., Room Manager) to arrive at some commonly free time slot, taking into account the pre-specified and dynamically created hard and soft constraints of all attendees and meeting resources. Users only decide on the final scheduling outcome and are reminded of forthcoming appointments. For users who are comfortable with full delegation to agents, AMEETZERs can be modified to skip the meeting confirmation process.

A typical meeting scheduling process consists of the following three phases:

  • Phase 1: Call for Meeting - a user (i.e., host of a meeting) wishes to initiate a meeting and sends a meeting request to his or her AMEETZER.
  • Phase 2: Scheduling - AMEETZER solicits necessary calendar and preference information from other AMEETZERs and performs constraint satisfaction to arrive at a scheduling decision.
  • Phase 3: Confirmation - The scheduling outcome of the requested meeting is decided upon, by either the user or the AMEETZER and the necessary information recorded or preparation carried out.
In short, AMEETZER has the following novel features :
  1. An Iterative Reservation withOut Commitment (IROC) scheduling protocol that achieves soundness and flexibility in utility-based scheduling [2,3] and negotiation [4] respectively among autonomous agents without forcing the user to commit a meeting [3] unless he or she is notified and wishes to do so.
  2. A uniform fuzzy constraint satisfaction framework to represent and reason with both hard and soft meeting constraints, be it a user's preference (goal) or a situation to be prevented (constraint). Potentially this would enable constraint satisfaction in a richer inference framework [5] and in a massively parallel computational paradigm [6].
  3. A two-layer (macro and micro) multi-agent architecture with inter- and intra-agent communications respectively to achieve high modularity and concurrency. Distributed networked AMEETZERs interact with each other with the support of the name service agent, Registry, and room management agent, Room Manager. Within an AMEETZER, Receptionist, Scheduler, Messenger and Dispatcher cooperate to fulfill a user's meeting scheduling requirements.
In this article, we focus on the software architecture. In particular, we see how to structure both multi-agent and agent architectures as Java processes and threads respectively. Consequently, we illustrate how to realize inter- and intra-agent communications using Java sockets and built-in synchronization mechanisms with object serialization, which is crucial to achieve high-level agent message passing. Last but not least, this article also touches on issues of registry implementation.

Software Architecture and Java Implementation
Macro-Architecture
As shown in Figure 1, AMEETZERs are designed as distributed personal software agents that interact with their users and collaborate with each other and the system agents across the network to schedule meetings automatically.

Figure 1
Figure 1:

With distributed architecture, meeting requests that involve disjoint sets of attendees and resources can be scheduled concurrently, in contrast to a centralized approach where all meetings are scheduled by a central scheduling agent. Not only will the latter approach be subject to communication and processing bottlenecks, it will also face fault tolerance and complex schedule maintenance issues.

The IROC scheduling protocol is shown in Figure 2. It is carried out in three stages:

Stage 1: Calendar Query
The host AMEETZER requests the calendars within a specified range (i.e., meeting the time horizon as specified by the user) from the attendee AMEETZERs and Room Manager, instantiated with their preferences.

Stage 2: Iterative Reservation
With all retrieved calendars, the host AMEETZER infers the optimal meeting time using a uniform fuzzy inference framework. In the case where the scheduling problem is not over-constrained, a valid optimal meeting time, respecting various hard and soft constraints, will be found. The host AMEETZER then requests the attendee AMEETZERs and Room Manager to reserve the scheduled time. If an attendee's (or Room Manager's) calendar is still available (i.e., has not been reserved by other concurrently scheduled meetings), the corresponding time slot is marked and its status replied to the host AMEETZER. The host AMEETZER may have to iterate this reservation process for $K$ times, each with the $k^{th}$ optimal time, or until all reservations within a single iteration are successful, whichever is earlier.

Stage 3: User Confirmation
When the calendars of all attendees (including host) and Room Manager are reserved successfully with some (sub-)optimal time, the host AMEETZER initiates a user confirmation process. Each AMEETZER notifies its user about the scheduled meeting and seeks his or her acceptance, which is replied to the host AMEETZER.

Within the IROC scheduling protocol, there are four situations where a meeting scheduling can fail (indicated by asterisk ($*$) in Figure 2):

  1. During Stage 1, some attendee(s) is not contactable.
  2. After inference, no commonly free time slot is available.
  3. After Stage 2, some reservation(s) is still not possible after $K$ attempts.
  4. During Stage 3, some user(s) rejects the meeting.
Whenever one of the above situations arises, the host AMEETZER broadcasts a meeting cancellation message to the relevant AMEETZERs and Room Manager to cancel a meeting. The message passing for these meeting cancellations is not shown in Figure 2 for readability.

AMEETZERs and system agents (Registry, Room Manager) are implemented as Java processes running on different hosts.

Registry
As a user is allowed to run his or her AMEETZER on any host at any time, the only way to cope with dynamic user mobility is to have a name service agent to maintain and provide the most up-to-date host and port information to any AMEETZER when agent communication is required. Thus, a Registry is necessary. The Registry should also be responsible for registration and unregistration of an AMEETZER, to assign an available port number to an AMEETZER newly activated on a host and to be notified of a terminated AMEETZER respectively. We will discuss Registry's implementation in greater detail later.

Room Manager
This is an agent to manage the calendars of meeting places. The calendar of a meeting place will be treated uniformly as that of an attendee though specific constraints such as room size and location can be incorporated. Thus, this single agent provides centralized control over calendars of all possible meeting rooms as contrast to one AMEETZER per attendee. This conceptual framework can be generalized for any kind of Resource Manager.

Other Agents
Depending on the application domain, more service agents (e.g., Refreshment Catering Agent) can be added to the AMEETZER system to enrich the services provided by the whole system.

Micro-Archiecture
To further increase the concurrency of the system, we propose multiagent (or multi-subagent) architecture within each AMEETZER, as shown in Figure 3.

Figure 3
Figure 3:

Each AMEETZER is decomposed into four subagents -- Receptionist, Scheduler, Messenger and Dispatcher. Personal user data comprise a Calendar to record scheduled meetings and a set of Preferences to capture user's constraints on meetings to be scheduled. The functions of the subagents are :

  1. Receptionist - interacts with the user to manage his or her Calendar and Preferences, accepts his or her requests (e.g., call-for-meeting), presents scheduling results for confirmation and reminds him or her about forthcoming meetings.
  2. Scheduler - implements the IROC scheduling protocol and the fuzzy constraint satisfaction framework.
  3. Messenger - forwards outgoing messages to other AMEETZERs, using the name service of Registry when necessary.
  4. Dispatcher - distributes incoming messages to the right subagent.
In implementation, an Ameetzer class (main program) contains the start-up and clean-up codes for AMEETZER (Listing 1). Upon activation by the user,

marten% java Ameetzer <config_path>

where <config_path> is the path where the configuration file resides, Ameetzer carries out the following initialization steps,

  • reads in the configuration parameters from a file,
  • identifies the user from System.getProperty( "user.name" ),
  • registers with Registry (more details later),
  • reads in user's calendar and preferences from files,
  • creates its four subagents, providing the data pathname and abbreviated names, as well as a communication Channel object [7] for inter-agent communication (discussed below), and waits for the four subagents to join when the user exits via the Receptionist subagent. Before exit, Ameetzer will perform some clean up operations, such as saving the user's data and mailboxes.
The four subagents inherit common variables and methods from the Subagent class (Listing 2). Each subagent (thread) executes in a perpetual loop to provide appropriate services based on the message retrieved from its own mailbox. Listing 3 shows skeletonal codes of the Dispatcher subagent.

Agent Communication
Recently, KQML [8] has gained popularity as an agent communication language without alternative with similar elaboration. We adopted a subset of KQML's performatives and adapted its communication format and content language for meeting scheduling domain and purpose. In AMEETZER, an Agent Communication Message, shown in Listing 4, has the following constituents :

  1. Intention - agent's intention of sending the message. It implements the performatives in KQML. We feel that intention is a more appropriate term as an agent message only conveys a sender agent's intended request for the receiver agent which may or may not fulfil the request in general.
  2. Sender - the agent (could be human agent) who sends the message.
  3. Receivers - a list of agents to receive the message.
  4. Content - message content, implemented as an array of Java Objects.
Subagents within an AMEETZER communicate with each other by message passing in mailboxes which support synchronization mechanism via semphores. The MessageQueue and Semaphore classes are given in Listings 5 and 6. The codes for the Queue object can be found in [7].

For communication among agents running on different hosts, a communication channel that encapsulates generic message sending and receiving behaviors built upon Java sockets and Java Object Serialization has been proposed [7]. Object serialization is necessary to support agent communication messages whose contents are of generic Object type. An item in the message content can range from a Date object (e.g. meeting date and time) to a multi-dimensional array of floating points (e.g. preference values).

To send a message to another AMEETZER, a Receptionist or Scheduler subagent sends a "forward" message to the Messenger subagent. Listing 7 shows an example where the Scheduler subagent of a meeting host's AMEETZER intends to retrieve the relevant parts of calendars from the attendee AMEETZERs.

The Messenger subagent will then "unwrap" this message when it is retrieved from its mailbox, look up the hostnames and port numbers of the respective recipient AMEETZERs and send out the message (i.e., fw_msg.content[0]) via the send() method of the Channel object [7] which receives incoming messages intended for the AMEETZER in Dispatcher subagent's mailbox (i.e., Dispatcher subagent's mailbox accepts external messages). The Messenger subagent may consult the Registry for the latest whereabouts of a recipient AMEETZER when necessary via another Channel object created by itself.

AMEETZER in action
We have tested AMEETZER's effectiveness under different scenarios. Scheduling a meeting that involves fourteen attendees (i.e., from call-for-meeting request to result reporting) requires not more than twenty seconds. Listing 7 depicts the text output of an operational AMEETZER and Figures 4-8 show some of the sample screen shots of AMEETZER during operation.

Figure 4
Figure 4:
Figure 5
Figure 5:
Figure 6
Figure 6:
Figure 7
Figure 7:
Figure 8
Figure 8:

Registry
To track the whereabouts of AMEETZERs for peer-to-peer agent communications and to resolve communication port allocation conflict for AMEETZERs running on the same host, the Registry provides name service and registration function to the AMEETZERs using Channel object [7] via its well-known port (Listing 9).

When an AMEETZER comes alive, it needs to contact Registry to request a pair of port numbers (to be used by two Channel objects) for future agent communication (with other AMEETZERs) and name service (with Registry). However, to carry out this registration request an AMEETZER needs a prior communication port. This chicken-and-egg problem is resolved by using an initial well-known port (i.e. AMZ_INIT_PORT in Listing 9).

Upon receiving a "register" request from an AMEETZER, the Registry creates a new entry in its look-up tables (i.e., uid_host_map, ses_port_map) and replies with a pair of allocated port numbers if the requester is the only AMEETZER for its user. Otherwise, a sorry message will be replied, which will cause the AMEETZER to notify its user of pre-existing AMEETZER (at any time, only one AMEETZER is allowed per user). In the rare case of more than one AMEETZER attempting to register simultaneously, only the first AMEETZER will be granted and the rest will catch a Socket exception and request its user to start AMEETZER again later before exiting itself.

When the request is "unregister", the Registry simply removes the requester's entry in look-up tables and frees the port numbers held by it.

Last but not least, the Registry responds to an "ask-all" query request by looking up its tables and replying with a corresponding list of hostnames and port numbers for the given list of user names. Null values are replied for users who have no active AMEETZER running.

Conclusion and Future Outlook
In this article, we have described the design and implementation of a Java-based multi-agent meeting organizer, AMEETZER. We are collaborating with Tsukuba Research Center, RWCP, Japan to enhance AMEETZER's user interface with speech and gesture recognition technologies. Users will use voice and gestures to interact with their AMEETZER, which will respond with a synthesized voice which supplements the existing visual output. System integration can be achieved in a seemless and loose manner via socket communication. Briefly, the Channel object [7] in AMEETZER is modified to receive keywords produced after speech and gesture recognition and to send speech synthesized text to the new interface module (currently implemented in C).

We are also looking into transforming the standalone AMEETZERs for the World Wide Web platform. With Internet, we can extend the Registry to support inter-organization meetings and meetings among home users. A mobile computing and communication platform is another possible area for investigation.

References

  1. Maes, P. (1994). "Agents that reduce work and information overload." Communications of the ACM, 37(7): 30-40, July 1994.
  2. Ephrati, E., Zlotkin, G., & Rosenschein, J.S. (1994). "A non-manipulable meeting scheduling system." In Proc. of the 13th International DAI Workshop, Seattle, Washington, July 1994, pp. 105-125.
  3. Yamaki, H., Kajihara, M., Nishimura, T., & Ishida, T. (1995). "Socia: an agent-based meeting support system." Technical Report ILTR-95-01. Dept. of Information Science, Kyoto University.
  4. Sen, S. (1996). "An automated distributed meeting scheduler." To appear in IEEE Expert.
  5. Lim, J.H. (1995). "Fuzzy constraint logic programming: a proposal." In Proc. of FUZZ-IEEE/IFES'95, Yokohama, Japan, Mar. 20-24, 1995, pp. 2305-2310.
  6. Lim, J.H. (1991). "A constraint satisfaction neural network applied to timetable scheduling." In Proc. of Neuro-Nimes'91, Nimes, France, Nov. 4-8, 1991, pp. 761-764.
  7. Lai, S.L. & Lim, J.H. (1996). "Channel: a communication component." Java Developer's Journal, Volume 1, Issue 3, December 1996, pp. 16-.
  8. Finin, T. et al. (1993). Draft specification of the KQML agent communication language. http://www.cs.umbc.edu/kqml/.
About the Authors
Ms. Siet-Leng Lai has developed a concurrent object-based language on parallel machine as well as clustered workstation environment and a multi-tasking operating system on DOS. She has more than four years of IT industrial experiences. . She is now conducting research into Internet/Intranet middlewares using Java.

Mr. Joo-Hwee Lim proposed novel neural networks techniques for timetabling and developed execution monitoring engine for a complex planner. He is now a senior software engineer leading an Agent Engineering Team researching agent-based software engineering and multi-agent systems using Java. The project is funded by Japan's Real World Computing Partnership.

	

Listing 1

/**
 * AMEETZER main program
 */
public class Ameetzer {

	public static Config cfg;

	/* other variable definitions */
	.....

	public static void main( String[] args ) {

		/* read in configuration file */
		.....

		/* get user's identity */
		.....

		/* register with Registry */
		.....

		/* read in user's calendar and preferences */
		.....

		/* create subagent threads */
		cfg.sa_gui = new Receptionist( cfg.data_path, "gui" );
		cfg.sa_sch = new Scheduler( cfg.data_path, "sch" );
		cfg.sa_msg = new Messenger( cfg.data_path, "msg" );
		cfg.sa_dsp = new Dispatcher( cfg.data_path, "dsp" );
		cfg.channel = new Channel( cfg.assigned_port, cfg.sa_dsp.mailbox );

		/* wait for subagents to join (die) */
		try {
			cfg.sa_gui.join();
			cfg.sa_sch.join();
			cfg.sa_msg.join();
			cfg.sa_dsp.join();
		} catch (InterruptedException e) {
			e.printStackTrace();
		}

		/* save user's data */
		.....
	}
}

// Listing 2

/**
 * Subagent object defines a subagent as a thread 
 *  with name, path, filename and mailbox fields.
 */
public class Subagent extends Thread {

	protected String myName;
	protected String myPath;
	protected String filename;
	protected MessageQueue mailbox;

	public Subagent( String path, String name ) {

		myPath = path;
		myName = name;
		filename = path+name+"_mbox.dat";

		// no existing mailbox, create new one
		if (mailbox == null)
			mailbox = new MessageQueue();
	}

	/**
	 * read and enqueue messages from file (if any)
	 */
	public void read_mbox() {
		.....
	}

	/**
	 * dequeue and write messages to file
	 */
	public void write_mbox() {
		.....
	}
}

Listing 3

public class Dispatcher extends Subagent {

	public Dispatcher( String path, String name ) {
		super( path, name );
		this.start();
	}

	public void run() {

		Message msg;

while (Ameetzer.cfg.exit_status != true) {

// get a message from mailbox
msg = (Message)mailbox.get();

// dispatch message according to intention 
//  and content
if (msg.intention.compareTo("ask-one") == 0
&& ((String)msg.content[0]).compareTo(
"schedule") == 0 || ..... ) {

// dispatch to Receptionist subagent
try { 
Ameetzer.cfg.sa_gui.mailbox.put( msg );
} catch (QueueException e) {
return;
	}

	} else if ( ..... ) {

// dispatch to Scheduler subagent
.....

	} // end of message-matching
		} // while (true)
	} // run
}

Listing 4

/**
 * Message object defines a agent communication 
 *  message
 */
public class Message extends Object {

	protected String intention;

	protected String sender;

	protected String receiver[];

	protected Object content[];

	public Message() {
		// super();
	}
}

Listing 5

/**
 * MessageQueue object provides messaging via
 *  mailbox
 */
public class MessageQueue extends Queue {

	// synchronization primitives
	private Semaphore empty, full;

	/**
	 * create queue and semaphores
	 */
	public MessageQueue() {
		empty = new Semaphore( super.qsize );
		full  = new Semaphore( 0 );
	}

	/**
	 * create queue and semaphores
	 */
	public MessageQueue( int size ) {
		super( size );
		empty = new Semaphore( super.qsize );
		full  = new Semaphore( 0 );
	}

	/**
	 * remove message from queue 
	 */
	public Message get() {

		full.down();
		Message msg = (Message)super.remove();
		empty.up();
		return( msg );
	}

	/**
	 * append message to queue
	 */
	public void put( Message new_msg ) 
		throws QueueException {

		empty.down();
		super.append( new_msg );
		full.up();
	}
}

// Listing 6

/**
 * Semaphore object for synchronization
 */
public class Semaphore {

// semaphore value
private int count;

/**
 * initialize semaphore value
 */
public Semaphore(int value) {
count = value;
}

/**
 * V() operation
 */
public synchronized void up() {
count++;
if (count <= 0) 
notify();
}

/**
 * P() operation
 */
public synchronized void down() {
count--;
if (count < 0) {
try {
wait();
} catch (InterruptedException e) {}
		}
	}
} 

Listing 7

Message query_msg = new Message();
query_msg.intention = "ask-one";
query_msg.sender = Ameetzer.cfg.userid;
query_msg.content = new Object[3];
query_msg.content[0] = "schedule";
query_msg.content[1] = mtg_id;
query_msg.content[2] = meeting;

Message fw_msg = new Message();
fw_msg.intention = "forward";
fw_msg.sender = myName;
fw_msg.receiver = new String[meeting.attendees.
length];
for (int i = 0; i < meeting.attendees.length; 
			i++) {
	fw_msg.receiver[i] = meeting.attendees[i].name;
}
fw_msg.content = new Object[2];
fw_msg.content[0] = query_msg;
fw_msg.content[1] = mtg_id;
try {
	Ameetzer.cfg.sa_msg.mailbox.put( fw_msg );
} catch (QueueException e) {
	e.printStackTrace();
}

Listing 8

marten% java Ameetzer .        
Configuring myself ..... done.
Registering myself ..... done.
Hmm ... looking for your data ..... done.
Now ... sharpening my senses for you ..... done.
[email protected] started.
[email protected] started.
[email protected] started.
[email protected] started.

[email protected] exits now.
[email protected] exits now.
[email protected] exits now.
[email protected] exits now.
Ameetzer exits.
marten%

Listing 9

/**
 * Registry: registration and name services 
 */
public class Registry {

public final static int WELL_KNOWN_PORT = 9999;
public final static int AMZ_INIT_PORT = 9988;

/* other variable definitions */
.....

public static void main( String[] args ) {

Message msg;
MessageQueue mailbox = new MessageQueue();
Channel channel = new Channel( 
WELL_KNOWN_PORT, mailbox );

// map: userid --> hostname
Hashtable uid_host_map = new Hashtable();

// map: userid+hostname --> port number
Hashtable ses_port_map = new Hashtable();

System.out.println("## Registry started.");

while (true) {
// get a message from mailbox
msg = (Message)mailbox.get();
// provide service based on message 
//  intention
// registration
if (msg.intention.compareTo("register")
== 0) {

String userid = msg.sender;
String hostname = 
(String)uid_host_map.get( userid );

if (hostname != null) {
// user's AMEETZER already active

// reply with [sorry] message
.....

} else { // user's AMEETZER is new

// create new entry and reply with
//  allocated port numbers
.....

}

// unregistration
} else if
(msg.intention.compareTo("unregister")
== 0) {

// remove entry from look-up tables
	.....

// query
} else if
(msg.intention.compareTo("ask-all")
== 0) {

// look up the hostnames and port numbers
//  and reply
.....

	}
} // while (true)
} // run
}
 

 

All Rights Reserved
Copyright ©  2004 SYS-CON Media, Inc.
  E-mail: [email protected]

Java and Java-based marks are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries. SYS-CON Publications, Inc. is independent of Sun Microsystems, Inc.