INET Conferences

Conferences

INET


NDSS

Other Conferences

[INET'98] [ Up ][Prev][Next]

A New Time Scheduler Application on Web Using Logic Programming and Agents

Amrudee SUKPAN <g3922061@maliwan.psu.ac.th>
Duenpen SANTHITITHAM <g3922013@maliwan.psu.ac.t>
Ajin JIRACHIEFPATTANA <ajin@ratree.psu.ac.th>
Andrew DAVISON <ad@ratree.psu.ac.th>
Prince of Songkla University
Thailand

Abstract

Our aim is to develop a Web-based diary system which uses logic programming for storing the structured server-side data required in a diary, and for specifying high-level client-side queries upon that data.

Logic programming has allowed us to develop deductive databases for our diaries, and to formulate queries using unification and backtracking search. This permits us to represent information in a very succinct manner, and to retrieve it in a variety of ways impossible with simpler relational databases.

A drawback of logic programming is the difficulty that nontechnical users can have with the paradigm. Consequently, we have tried to simplify the interface to our diaries using Web-based graphics and forms; indeed, many users may not realize they are using a Prolog server-side application and writing Prolog queries.

An important strand of this work is the inclusion of agent helpers, which can monitor changes within a diary, and between diaries. The monitoring conditions (e.g., alert the user when the 2:00-2:59 p.m. time slot becomes free in Amrudee's diary) are defined with logic programming facts and rules. This makes the heuristics concise, while retaining flexibility and generality.

Contents

1. Introduction

This work investigates the potential for using logic programming within a Web-based diary application. This domain contains many interesting problems, including how to structure diary information and how to devise high-level queries over diaries without making the system too difficult for nontechnical users. We contend that logic programming, with its support for deductive databases, inference, unification, and backtracking search, offers excellent solutions to these problems. However, some care must be taken to design the user interface to reduce the surface complexity of the logic programming techniques.

We chose the Web as the support layer for our system due to its network-wide accessibility and its graphical and forms-based features which are required for a friendly user interface. In addition, the Web is not proprietary, is supported by all the major platforms, and has sufficient security measures for our needs.

A second element of our system is the use of agents to monitor changes within a diary and between diaries. We are considering these two types of agents in order to supply ourselves with a wider range of design problems, which we are addressing with logic programming. Our work illustrates that logic programming is an ideal mechanism for expressing agent behavior in terms of relations composed of facts and rules. In particular, these relations are easy for novice users to write, due to pattern matching and the intuitive if-then terminology of Prolog.

In section 2, we outline the diary system with its forms-based Web interface. In section 3, we consider how agent helpers are incorporated into the system. Section 4 looks at related work, and section 5 concludes.

2. The diary system

Figure 1 gives a simplified functional overview of the system:


Figure 1: The diary system

The server side system consists of CGI scripts coded in BinProlog [Tarau 1997]. Web pages containing forms are used to interact with the various scripts, which return answers as Web pages. We use the logic programming PiLLoW Web library to process forms input and generate the answer pages [Cabeza et al. 1997].

There is a diary database for each user, with access controlled by the password mechanism built into the Apache Web server [Apache Group. 1998]. A new user must register a user ID and password, which will subsequently permit him to access other parts of the system and cause the initialization of his diary database.

2.1. The diary database data structures

Each user has his or her own diary database, which typically consists of three predicates: diary/3, invisible/2, and reserved/1.The diary/3 predicate hold the diary information for the user. It consists of facts of the form 

        diary(Name, TimePeriod, Item).

Name is the name of the person whom the diary owner is meeting. Currently, we restrict this to one person, but plan to expand it to be a list of names, one for each participant in the meeting.

TimePeriod has the form 

        time(StartSlot, EndSlot, date(Day,Month, Year))

StartSlot and EndSlot are integers in the range 1, 2, ..., 24. For a start slot, the integer denotes the start of the hour (1 stands for midnight, 2 for 1 a.m., and so on). For an end slot, the integer denotes the end of the hour (1 stands for 0:59 a.m., 2 for 1:59 a.m., and so on). This is somewhat inflexible and may be extended.

Item has the format 

        item(topic(TopicTitle, Comments), Where, Importance)

TopicTitle, Comments, and Where are strings. TopicTitle holds the meeting title, Comments holds extra details related to the meeting, and Where gives the location of the meeting. Importance is an integer used to rate the significance of the meeting: A higher value denotes higher importance. Some example diary/3 facts follow: 

        diary('John',time(10, 10, date(2, 2, 1998)),item(topic("Project",
                "Coding Discussion"), "Rm400",1)).
        diary('Mary',time(13, 14, date(3, 2, 1998)),item(topic("Lunch",
                "Discuss widgets"), "JB Hotel", 5)).

The first fact records a meeting with John on February 2 between 9 a.m. and 9:59 a.m. to discuss coding in a project. The meeting is in room 400 and is low priority.

The second fact describes a lunch meeting with Mary on February 3 between noon and 1:59 p.m. to discuss widgets. The meeting is at the JB Hotel and is at a higher priority.

The invisible/2 predicate is used to hide parts of the owner's diary from other users. In particular, this information is used to filter the diary/3 facts before they are displayed by the "view a diary" CGI script (see section 2.5).

invisible/2 clauses have the form 

        invisible(UserID,TimePeriod) :- /* extra conditions */ .

UserID is the ID of the person whose viewing is being restricted, or can be the word all to mean all users (except the diary owner).The user ID is obtained when a user enters the system. TimePeriod has the same format as in diary/3. The extra conditions usually relate to values inside the TimePeriod term, in order to generalize the invisibility range. Some examples 

        invisible(ad,time(10, 12, date(1, 2, 1998))).
        invisible(all, time(1, 24, date(X, 2, 1998))) :-X >= 5, X =< 12.

These clauses state that user ad cannot see this diary's details for meetings between 9 a.m. and 11:59 a.m. on February 1, while everyone (except the diary owner) is prevented from seeing diary information concerning February 5 to 12.

A more advanced use of invisible/2 is to link invisibility to the presence (or absence) of diary/3 and reserved/1 clauses in the database. For instance, 

        invisible(ajin,TimePeriod) :-diary(Name,TimePeriod, _), Name \== ajin.

This states that user ajin cannot see diary information for users other than himself. The reserved/1 predicate "reserves" time slots in the owner's diary so that no other users can make appointments. reserved/1 clauses have the form 

        reserved(TimePeriod)  :- /* extra conditions */ .

As with invisible/2, the extra conditions allow the time period to be generalized or made dependent on diary/3 or invisible/2 clauses. For example, 

        reserved(time(16,16, date(7, 2, 1998))).
                reserved(time(13,13, _)).
        reserved(time(1,24, Date)) :-date2day(Date,Day), Day \== "Saturday", Day \=="Sunday".

The first fact states that the 3 p.m. to 3:59 p.m. slot on February 7 is reserved. The second fact uses an uninstantiated date variable to reserve every day between noon and 12:59 p.m. (for lunch presumably). The final clause uses the built-in predicate date2day/2 to reserve every Saturday and Sunday.

2.2. Querying a diary

A diary is queried via the interface shown in Figure 2.


Figure 2 : Querying a diary

The form supplies the name of the diary database to be examined (the DiaryName field), the fields of interest in the diary/3 predicate in that database, and any extra conditions. The fields can contain "diary variables" (words beginning with "dv"), which become logic variables in the constructed Prolog query. When a field is left empty, the corresponding diary/3 data is not considered by the query.

The results page for the query in Figure 2 is shown in Figure 3.


Figure 3: Results for the query given in Figure 2.

The constructed Prolog goal uses findall/3 to return all possible answers at once. For the query in Figure 2, the following (somewhat simplified) goal would be evaluated: 

        ?- findall( result(Who, Date, Month, Year, T1, T2, Topic),
                ( diary(Who, time(T1, T2, date(Date, Month, 1998)),item(topic(Topic, _), _, _)),
                        member(Who, ['John', 'Jim', 'Mary']),Month \== 1,
                        contains("student", Topic)), Results
                ).

This searches for details on meetings with John, Jim, or Mary, any time in 1998 apart from January, where the topic title contains the string "student." member/2 and contains/2 are built-in predicates.

2.3. Changing a diary

Diary facts can be added, deleted, or updated. The user utilizes the forms interface shown in Figure 4.


Figure 4: Changing a diary

When the user adds a diary fact, JavaScript is used to check for simple input error, saving the expense of invoking a server-side CGI script [Reynolds and Wooldridge 1996].The user can delete facts by filling in any of the form fields. For example, the date and time period fields can be used to remove diary/3 facts spanning several days. A planned extension is to include a conditions field, similar to the one on the "Query a Diary" page. This would allow more complex deletion expressions to be specified.

Updating a diary fact requires the Who, DatePeriod, and TimePeriod fields to be filled in and only occurs if a single existing diary fact can be found. It is then altered by changing its Where, Topic, Comments, and Importance fields according to the information entered by the user.

2.4. Changing reserved and invisibility information

The addition and deletion of reserved/1 and invisible/2 data are achieved in a similar way to changing diary/3, except that the form includes an extra field so that conditions can be included with the added facts. At present it is not possible to update information except by using deletion followed by addition.

2.5. Viewing a diary

Figure 5 shows how a diary can be viewed.


Figure 5: Viewing a diary.

The left-hand frame holds the form for entering the name of the diary to be viewed, along with the month and year of interest. Currently, the system only displays a month of diary information at a time. The information presented is based on the diary/3 and reserved/1 clauses. A reserved time is denoted with a "r*", as seen in Figure 5. In addition, the diary information is filtered through the invisible/2 clauses, based on the ID of the user. Only those facts that are still "visible" after the filtering are displayed.

3. Agent helpers

The agent helpers shown in Figure 1 illustrate how monitoring is integrated into the system. Each agent examines a diary by periodically downloading its "visible" details by accessing the CGI script for viewing a diary. An agent does this by sending a POST query to the script [Berners-Lee et al. 1996] and by supplying a user ID and password to access the system.

When an agent gets back a Web page of details, it extracts the diary/3 facts, which are included in the page but commented out so that browsers do not display them. The extracted facts are stored locally by the agent, as are later diary downloads (of the same diary or of other diaries). The resulting collection of databases is analyzed by the agents using logic programming techniques.

Our agents are coded using BinProlog, although the page downloading subsystem is written in C. We plan to reimplement this in Prolog.

We are investigating two types of agent helper: agents which monitor a single diary, looking for additions, deletions, or updates, and agents which monitor several diaries. We have specialized the second category to concentrate on agents that examine several diaries for free times which are "near" to each other. This kind of information is extremely useful when someone is trying to organize a meeting involving several people.

Both types of agent notify their users by sending e-mail to specified addresses.

3.1. The "diary changes" agent

The "diary changes" agent monitors a specified diary for any changes. It does this by regularly downloading the visible diary/3 facts from the specified user's diary and storing them in a database (which we call Dcurrent). This database is compared with the last download of the same database (called Dprevious) using comparison rules written in Prolog by the agent's user.

The agent is initialized with the user ID of the diary of interest, the download frequency (e.g., 24 times/day), a start and termination time for the agent's monitoring, and a user name and password for accessing the diary system. The user must also supply an e-mail address where the agent can send change announcements.

The comparison rules are given as changed/2 clauses, of the form 

        changed(<deleted diary/3 fact>,<added diary/3 fact>) :- 
            /* extra conditions */ .

Following are two examples: 

        changed( diary(Name, time(_, _, date(X, 2, 1998)), Item),
                    diary(Name, time(_, _, date(Y, 2, 1998)), Item)) :-
                     X > 11, Y =< 11.
        changed( diary(Name, Time, item(Topic, OldWhere, _)),
                     diary(Name, Time, item(Topic, NewWhere, _))) :-
                     OldWhere \== NewWhere.

The first rule causes the user to be alerted when an appointment with Name about Item scheduled after February 11 is moved to the 11th or before. The second rule triggers a message if an appointment has its location changed.

changed/2 clauses can be used to detect deletions by leaving the second argument unbound. For example, 

        changed( diary(Name, time(14,15, date(_, 2, 1998)), _), _).

This will cause an e-mail message to be sent when any diary entry between 1 p.m. and 2:59 p.m. in February is deleted.

In a similar way, changed/2 can be employed to monitor only additions by leaving the first argument unbound. For example, 

        changed(_, diary(_, _, item(topic(Title,_), _, _))) :-
            contains("salary", Title).

This rule will trigger a message if the diary owner makes an appointment which involves the string "salary" in its title.

The collection of user-defined changed/2 clauses is utilized by the agent in the following manner. First, two sets of diary/3 facts are extracted from Dprevious and Dcurrent. The deleted facts are 

        Ddeleted = Dprevious - (Dcurrent Ç Dprevious)

The new, additional diary facts are 

        Dadded = Dcurrent - (Dcurrent Ç Dprevious)

These two collections are searched with changed/2 inside a findall/3 query. A simplified version of that query is 

        ?- findall( change(Dd, Da),
                ( member(Dd, Ddeleted), member(Da, Dadded),
                  changed(Dd, Da) ),
                Changes).

The list of changes collected in Changes are subsequently reformatted and sent as an e-mail message to the specified address.

3.2. The "diary changes" agent

The "free time" agent monitors a series of specified databases, looking for free time common to all the diaries. The rules to decide if free times in different diaries are "near" to each other are coded by the user with logic programming clauses.

The current system is only able to monitor two diaries, but the techniques outlined below can be scaled to deal with any number of diaries.

The two diaries (D1 and D2) are regularly downloaded by accessing the "view a diary" CGI script for the diaries under study. The agent removes the diary facts from the retrieved pages and places them in local databases. These extracted facts have already been filtered on the server-side so that facts not visible to the agents have been removed. However, reserved/1 clauses are not currently downloaded, which means that the agent cannot discern which free times are actually reserved.

The agent is initialized in a similar, but slightly more complex, way to the "diary changes" agents. The user IDs of the diaries of interest are given, as well as the downloading frequency, a start and termination time for the agent's monitoring, the user ID and password for accessing the diary system, and an e-mail address for notifications. The additional input is a period of interest in the diary, which consists of a date range (e.g., February 1 to 14).

The user-specified rules are given as near/2 clauses of the form 

        near( <a time period in a D1 diary/3 fact>, 
              <a time period in a D2 diary/3 fact>) :- 
                    /* extra conditions */ .

The intention of near/2 is to define the meaning of "near" free times between the two diaries. When two free times in the diaries are near to each other (e.g., when both diaries have the same time period free), then that is reported to the user.

Two examples 

        near(TimePeriod, TimePeriod) :-
               TimePeriod = time(_, EndSlot, _), EndSlot =< 11.
        near(time(SS1, ES1, Date), time(SS2, ES2, Date)) :-
               (SS1 =< SS2, SS2 =< ES1) ; (SS2 =< SS1, SS1 =< ES2).

The first rule specifies that a "near" free time occurs in both diaries when they contain the same free time period (TimePeriod), and that time slot ends before or at 10:59 a.m.. The second rule defines a "near" free time as being when two time periods in the diaries overlap. There are two possible cases, which are shown in Figure 6.

Figure 6: Overlapping free times in two diaries

The order of the near/2 facts is important, due to the evaluation strategy of Prolog. More precise notions of nearness should be placed before more vague ones so that the system will report those times first. For instance, if near/3 was defined for three diaries, then the following facts specify an "all three, best of any two" strategy: 

        near(T, T, T). /* all
        three */
        near(T, T, _). /* best of any two */
        near(T, _, T).
        near(_, T, T).

The first clause considers near free times as occurring when all three diaries have the same free time period. A more relaxed notion of nearness follows in the second, third, and fourth clauses which permit near free times to occur in any two diaries with the same time.

The collection of near/2 clauses is utilized by the agent in an analogous way to the "diary changes" agent. A simplified version of the top-level query for near/2 is 

        ?- free_times(D1, Fts1), free_times(D2, Fts2),
                findall ( nr(Ft1, Ft2),
                        ( member(Ft1, Fts1), member(Ft2, Fts2), near(Ft1, Ft2) ),Nears).

free_times/2 extracts the free times from a diary, resulting in a list of time period terms. These are tested with a findall/3 call which collects all the matching "near" times in Nears. Nears is subsequently reformatted and sent in an e-mail message to the specified user address.

The interface to free_times/2 is more complex than shown here since it also employs the user's initialization data about the "dates of interest" in order to narrow the search for free times.

4. Related work

Our diary system, with its focus on the utilization of logic programming for structuring diary information and for specifying queries on that data and its use of logic programming-based agents for monitoring diaries, is dissimilar to other applications in the spheres of groupware or distributed meeting scheduling.

Groupware applications have been developed in response to the needs of the business community for electronic data management, office productivity aids, and other team coordination tools [Schlosberg 1995]. Most diary scheduling applications of this kind are not Web-based, are specific to particular systems and/or platforms, utilize relational database techniques (typically some form of SQL), and do not employ agents (for example, Blue Cannon Software 1996; EuroSoft 1997; Sheridan Software 1997). However, Web-centric tools are becoming available, including Lotus Organizer Web Calendar [Lotus Corp. 1997] and Lotus Internotes which is a Web-publishing package with access to Lotus Notes [Engler 1995]. Even so, these tools still rely on traditional database structuring and search.

Distributed meeting scheduling is one of the favorite problem domains of the distributed AI and agents communities, primarily as a means of investigating how scheduling agents can cooperate/negotiate within the remit of user-specified constraints [Sen 1997; Steiner 1997]. Problems include the choice of negotiation protocol (often derived from contract nets), the specification of relationships between meetings, and the representation of agent knowledge and user constraints [Schmeier and Schupeta 1996; Wada et al. 1996; Brancaleoni et al. 1997].

Our work does not address all of these concerns. In particular, our agents do not interact with each other, only with the diary software, and they are not mobile. Our research has concentrated on the formulation of agent knowledge (as deductive databases) and the user's constraints (as relations such as near/2 and changed/2). As far as we know, our work is the only one to explicitly represent monitoring agent behavior as logic programming facts and rules, although IntelliDiary [Wada et al. 1996] is implemented in April, a language with several features borrowed from logic programming [McCabe 1996].

5. Conclusions

Our Web-based diary system is a testbed for the use of logic programming in three related areas: the representation of highly structured server-side information as deductive databases, the encoding of complex client-side queries over those databases using logic programming techniques such as backtracking and unification, and the formulation of agent heuristics ("rules of thumb") as logical relations. Our system, although still at a prototype stage, highlights the benefits of using logic programming in these ways.

The databases, as represented with diary/3, reserved/1, and invisible/2, are concise while retaining expressiveness. diary/3 contains the diary meeting and appointment details, reserved/1 extends the diary with the notion of "reserved" times, while invisible/2 controls the user's access to a diary.

Very complex queries can be readily devised and have proven to be useful for searching for data, restricting the user's view of the database, and for deleting ranges of information. An oft-stated problem is that such queries are too complex for a novice, or even average, user to write. We have addressed this with a forms-based interface and the automatic generation of queries.

The heuristics utilized by the agents, which are encoded with the changed/2 and near/2 predicates, give the user a great deal of leverage for encoding monitoring behavior. However, the clauses themselves are easy to write and understand. This is partly due to the availability of pattern matching and inference inherent in the logic programming paradigm, but is also helped by the design of the agents which hide the full complexity of the queries posed against the databases.

References

Apache Group. 1998. Apache Web Server, http://www.apache.org/ABOUT_APACHE.html

Berners-Lee, T., Fielding, R., and Frystyk, H. 1996. "HyperText Transfer Protocol (HTTP/1.0) Specification (RFC 1945)," http://ds.internic.net/rfc/rfc1945.txt

Blue Cannon Software. 1996. Calendar Wise, http://www.softwarelabs.com/business/business126.htm

Brancaleoni, R., Cesta, A., and D'Aloisi, D. 1997. "MASMA: A Multi-Agent System for Scheduling Meetings," PAAM 97: Proc. of the 2nd Int. Conf. on the Practical Application of Intelligent Agents and Multi-Agent Technology, London, UK, April, pp. 31-49.

Cabeza, D., Hermenegildo, M., and Varma, S. 1997. "The PiLLoW/CIAO Library for Internet/WWW Programming," http://www.clip.dia.fi.upm.es/miscdocs/pillow/pillow.html

Engler, N. 1995. "The Politics of Trust," Open Computing, Vol. 12, No. 9, September, pp. 39-44.

EuroSoft. 1997. Calendar Magic, http://www.focusmm.co.uk/products/productivity/calendar.html

Lotus Corp. 1997. Lotus Organizer Web Calendar, http://www.lotus.com/home.nsf/tabs/calendar

McCabe, F.G. 1996. "April: An Agent Programming Language for the Internet", Tutorial at INAP'96: Proc. of the Symp. on Industrial Applications of Prolog, Hino, Tokyo, Japan, October, pp. 25-34.

Reynolds, M.C. and Wooldridge, A. 1996. Special Edition using JavaScript, QUE

Schlosberg, J. 1995. "Where is the Elusive Groupware Payoff?", Open Computing, Vol. 12, No. 9, September, pp. 31-36.

Schmeier, S., and Schupeta, A. 1996. "PASHA II - Personal Assistant for Scheduling Appointments," PAAM 96: Proc. of the 1st Int. Conf. on the Practical Application of Intelligent Agents and Multi-Agent Technology, London, UK, pp. 523-542.

Sen, S. 1997. "Developing an Automated Distributed Meeting Scheduler," IEEE Expert, July/August, pp. 41-45.

Sheridan Software. 1997. Calendar Widgets, http://www.shersoft.com/products/calendar/calgen.htm

Steiner, D. 1997. "Issues in Agent Interaction," PAAM 97: Proc. of the 2nd Int. Conf. on the Practical Application of Intelligent Agents and Multi-Agent Technology, London, UK, April, pp. 23-27.

Tarau, P. 1997. BinProlog 5.75, http://clement.info.umoncton.ca/~tarau

Wada, Y., Kawamura, A., McCabe, F.G., Shiouchi, M., Teramoto, Y., and Takada, Y. 1996. "An Agent Oriented Schedule Management System: IntelliDiary," PAAM 96: Proc. of the 1st Int. Conf. on the Practical Application of Intelligent Agents and Multi-Agent Technology, London, UK, pp. 655-667.

[INET'98] [ Up ][Prev][Next]