Sulla - A User Agent for the Web
David Eichmann and Jun Wu(1)
Research Institute for Computing and Information Systems
University of Houston - Clear Lake
Houston, TX 77058
{eichmann, jwu}@ricis.cl.uh.edu
Table of Contents
1 - Introduction
2 - Background and Related Work
3 - Design Goals
4 - Architecture
5 - Current Features
6 - Related Work
7 - Conclusions and Future Work
8 - References
As the World Wide Web [2] grows in scale and complexity, it will be increasingly difficult for end users to track information relevant to their interests. The transaction rates reported by major Web search engines bears out the increasing dependency upon such resources. However, as the novelty of the Web fades, users will also increasingly demand efficient access to information. Agent technology offers an excellent means to release users of the Web from lengthy and tedious tasks. This paper lays out the design and development of the Sulla user agent,(2) an intermediary software system with responsibility for tracking Web information and relating to its user information which is relevant to the user's interests. In particular, Sulla supports the ability to:
- acquire and retain an interest profile of its user and act upon one or more goals based upon that profile;
- act autonomously, pursuing the goals posed to it by its user, irrespective of whether the user is connected to the system where the agent is based;
- apprise its user of progress towards outstanding goals, and present preliminary results; the ability to access a variety of information sources, both via direct access to those sources (e.g., HTML documents, FTP files, WAIS databases, articles posted to newsgroups, etc.) and those referenced by service agents; and
- act ethically, exemplified by the guidelines proposed our WWW Fall `94 paper [8], in particular, moderation in the acquisition of information during the satisfaction of a goal.
The ease of construction and potential Internet-wide impact of autonomous software agents on the World Wide Web has spawned a great deal of discussion and occasional controversy [8, 12, 13]. Based upon our experience in the design and operation of the RBSE Spider [9], such tools can create substantial value to users of the Web. Unfortunately, agents can also be pests, generating substantial loads on already overloaded servers, and generally increasing Internet backbone traffic. A principal design goal in our work on Sulla is building a personal agent that is both a good Web citizen and a provider of a useful resource.
An agent is a program which interacts and assists an end user. Research in this area has been driven primarily by the artificial intelligence research community. The special issue of Communications of the ACM edited by Riecken [19] provides a good overview of the area. The nature of the Web supports a distinction between agents whose primary function is the provision of a service to the Web community at large, a service agent, and an agent whose primary function is the support of an individual user of the Web, a user agent. Scope of effect is a critical aspect of consideration when evaluating agents operating on a network. A limited scope agent is one which operates on information present only on the computer upon which it resides. A global scope agent is one which operates on information present not only of the local system, but also on information found on a potentially large fraction of the overall network. An additional distinction between mobile and stationary agents is also necessary the rapid growth in popularity of client-server application languages such as Java offers renewed interest in the notion of a remotely executable agent.
Maes' electronic mail agent [14] is an excellent example of a stationary, limited scope agent, operating only on the user's workstation and only upon the incoming mail queue for that single user. Many multi-agent projects [1, 7, 20] also presume a stationary, limited scope architecture, usually constrained by the need to efficiently share information (e.g., through a blackboard [11]).
The agents currently on the Web are largely service agents, stationary and of global scope, and involve Web spiders, which traverse the interlinked documents making up the Web, constructing an index of the information thus discovered. The difficulty with relying solely upon service agents to access relevance to a user's interest profile is that none of the service agents provide any persistence of state concerning what the user has already been presented with. (Note that a distinction is made here between a service agent that presents its results as a sequence of Web pages, as is the case with Alta Vista, Inktomi, and others, and the retention of information across an extended period of time.) It is the responsibility of each user to periodically poll a given user with a query, and then filter that which is new from that which has already been seen. A user agent's architecture should reflect the concerns of the individual, rather than the concerns of the community (w.g., a service agent's focus on authoritativeness).
A user agent for the web is used by one or more users to facilitate Web information search and retrieval. Derived in part from our work in Web agent ethics [8], we conceived Sulla having the following characteristics:
- Personalizability: Different users may have different tasks, or they may share the same task but do it in different ways. A user agent need to have the ability to catch the profile of its users' interests and preferences, and then act upon goals created by these profiles.
- Autonomy: An agent should act independently of or preemptively for the benefit of its user. Autonomous actions can be classified as periodic actions, spontaneous execution, and initiative.
- Discourse: An agent should have the ability to communicate with its user suggestions relating to a task and notification of accomplished tasks.
- Flexibility: An agent should have the ability to access a variety of information sources, both via direct access to those sources (e.g., HTML documents, FTP files, WAIS databases, articles posted to newsgroups, etc.) and those referenced by service agents, as well as a variety of information consumers in the form of browsers.
- Ethics: An agent should act moderately in the acquisition of information to achieve a goal.
- Privacy: An agent should give no indication to a user (other than perhaps by faster-than-normal access times) that some other user has similar goals or is accessing the same information resources.
Note that the goals listed here are primarily architectural in nature. Sulla is an stationary, global scope agent framework supporting a wide variety of user services, initially focussed upon enhancing user access to the Internet. The resulting architecture is shown in Figure 1, where the use employs an unmodified Web client from an arbitrary host to interact with the agent, which resides on a particular host (typically the user's desktop system). This scheme uses a feature already present in most browsers, support for a proxy server, to decouple user interaction from long-lived goal satisfaction and Web monitoring. Work towards goal satisfaction will sometimes best be handled in periods of light network load, requiring the retention of goals for later execution. This also makes the historical retention of goals for later reevaluation or refinement straightforward to implement. The user agent will also act as a "personal proxy" server, employing a spool area to cache relevant documents to avoid re-retrieval.
Figure 1: The Sulla Architecture
Sulla further decomposes into a number of major subsystems:
- proxy: This persistent process is a traditional Web server modified to intercept specific URLs for internal execution within Sulla and to track and log all user activity for subsequent goal analysis. The proxy also wraps all HTML documents forwarded to the browser with a containing frame that also references the status display (mentioned below)
- search processes: Intercepted URLs involving the formation of new searches cause the spawning of new search processes that will execute either through a single completion of a multiple engine search or through an indefinite number of search completions, each occurring at an interval specified by the user at the time of the initial request.
- search interfaces: Scripts parameterized with a search string and the number of desired hits that is executed by a search process to access a specific Web search engine. Search interfaces are only lightly bound to Sulla. Definition of a new interface entails the placement of a script with a specific name in the interface directory and the inclusion of that name as the returned value of a checkbox on the engine preference page. Submission of a new preference page results in the storage of engine values in a preference relation for that user which search processes pick up at execution time.
- retrieval processes: Intercepted URLs involving a request for the current overall state of Sulla or for the current state of a particular search process cause the creation of a transient CGI execution that interrogates the goal/result database.
- status process: Sulla can asynchronously notify the user of newly available information through the status display included in the wrapping frame generated by the proxy process. The status process is also responsible for refreshing access timestamps for URLs that are visited by the user and accepting requests for change notification monitoring.
Sulla development is scheduled as a three year effort, with the first year resulting in an initial goal storage/execution scheme based upon natural language search and the second year involving the design and implementation of a knowledge representation scheme. The second and third years will also include the integration of the knowledge representation scheme with the RBSE Spider [9] and the MORE repository system [10]. For normal URL browsing, Sulla acts as a proxy with a cache, with explicit status information if requested by the user, or silent activity tracking if not. In interface agent mode, Sulla dynamically generates virtual HTML pages corresponding to its search and retrieval entry points. The current prototype has the following features:
- Multi-tasking: The user can browse and keyword search simultaneously.
- Interval search: Searches can be scheduled through the search engines currently available on the web such as Lycos, Web Crawler, Spider etc., at a constant interval set by the user.
- Asynchronous notification: Sulla optionally reports to its user if a specific search is fulfilled or in progress through the inclusion of a footer to pages currently displayed on the user's browser. The footer refreshes with every URL accessed and can be suppressed so as not to interfere with printing documents, etc.
- Differential notification: Sulla reports to a user if a specific search has new search result since last database retrieval
- Persistence: Retrieval of information obtained by previous searches is supported through caching of search results.
- User authentication: To avoid the need to run multiple Sulla instances (and hence multiple database instances) on a single shared server, Sulla uses HTTP user authentication to distinguish users in the multi-user / single agent environments.
Autonomy is a basic but important property of an agent. An agent must be able to operate without the direct intervention of humans or others, and have some kind of control over their actions and internal state to facilitate its user [5]. For an agent to behave autonomously in a dynamic real-world domain, goal creation is an important issue [16]. Our initial work has been limited to relevance-feedback based natural language search to allow us to stabilize the overall system architecture and to provide a comparison framework for the second prototype.
In the current implementation of Sulla, each search carried out by a user the search configuration is saved in a relational database. The search interface page, shown in Figure 2,has the following contents: keyword(s) for search, interval (in days) between subsequent searches (if not set by user, the default is 0 which means no interval search), the number of hits to acquire from each engine, and domain over which to do the search (the preferred set of search engines or the preferred set of news groups). When interval search is specified by a user, a child process is spawned which is tasked with sending the query to the remote engines. Upon the receipt of search results from remote engines, the information is processed and saved in the database. If this is a new result, a status message is added to the status display at the next request for a document (presuming that notification is enabled).
Figure 2: The Sulla Search Page
Sulla classifies search results by different search engines. Retrieval of data from the database is by the keyword(s) corresponding to a search, as shown in Figure 3. A user has the choice to retrieve the most recently obtained data only (useful for browsing only new information contained in large search responses) or the entire result stored in the database. New search results are stored in a separate database relation and are deleted after a user has retrieved the recently obtained data. Note that this interface only retrieves information already returned by the search engines the search processes execute transaction commits following every returned hit, allowing incremental display of search results as they arrive. A sample result page is shown in Figure 4. Users having searched the same keyword can share the same information obtained by Sulla without Sulla indicating that the results derive from another Sulla user. The current prototype limits processing of obtained information from searches to the subtraction of title and corresponding wrapper text from a result page obtained from some remote search engine. Redundancy may exist among results from different search engines.
Figure 3: The Sulla Stored Query Page
Figure 4: A Sulla Query Result Page
One of the challenges in collating responses from a diverse (and extensible) collection of search engines is the corresponding diversity in retrieval and scoring algorithms that those search engines employ. Rather than take an approach similar to that of MetaCrawler [21], which rescores each search hit based upon its own evaluation scheme, Sulla merely tags each hit from each engine with the rank order that the hit was returned in. This allows for easy extension of the engine set, since each engine is allowed to use its own scoring scheme to order results and no presumption is made about the relative effectiveness or coverage of the engines.
We have experimented with how to aggregate results for user inspection, considering both averaging the combined ranking for all engines identifying the document as a hit and summing the combined rankings. We have noted an interesting phenomenon in using the current suite of search engines low hit request values (e.g., 10-25 hits) rarely result in hits that are common across engines. Even raising the hit request value to 100 per engine typically only increases common hits to a dozen or so per search. We've found that summing the rankings accentuates the common hits, which are frequently those we have been seeking, and rarely accentuates a spurious hit.
Users must be able to select the degree of intrusiveness that they allow an agent. We have configured Sulla with ability for the user to toggle the status display on and off as desired. Sulla is browser sensitive, using HTML frames when available for the presentation of the status display. With other browsers, the status information is appended to the end of every HTML document retrieved by a user. A user again may turn off the status information by setting the appropriate preference toggle. Additional preference features will be added as the underlying data model is enhanced. These will include a profile link field to point to a document a standing search profile and the knowledge structure manipulation interface planned for the second prototype.
Sulla's user authentication facility is supported by the CERN library. Before a search is executed, a tuple comprised of userid and search keyword is written into the database for later user authentication. To protect each user's search history, user identity is checked during the retrieval of status information and search results. The use of the existing authentication facility implies that a user only need to login once when they first use Sulla with any given browser session, since browsers support automatic userid and password responses to authentication challenges.
Silk [6] is the project most related to Sulla of which we're currently aware. Silk is a browser extended with the notion of Uniform Resource Agents (URAs), which extend the browser with expertise in interacting with a given Web resource. The search interfaces described earlier comprise a very limited form of URA. However, Silk differs from Sulla significantly in the nature of interaction with its user. Silk operates as a sophisticated browser, but a browser none-the-less. Sulla, on the other hand, was designed from inception for informed, but autonomous, operation.
Infoharness [22] is an open, extensible system designed to provide access to large amounts of heterogeneous information through encapsulation of these information resources in meta-data objects. The system architecture is comprised of a HTTP gateway, one or more InfoHarness servers, one or more InfoHarness collections, a meta-data generator which populates the collections, and a set of access tools (e.g., WAIS, relational databases, etc.). Users interact with the system through the gateway, which transforms requests into a form acceptable to the servers, which then act upon the request by returning portions of the meta-data, or by routing appropriate requests on to the access tool (which are responsible for manipulation of actual data). While the Infoharness architecture bears some resemblance to that of Sulla, the design goals are quite different.
Harvest [3, 4] supports "gathering, indexing, caching, replicating, and accessing Internet information" [3]. It was designed for scalability and customization through the separation of gatherers, responsible for the acquisition of information, and brokers, responsible for collection, index generation and dissemination of that information. Gatherers run at provider sites, and transmit information thus acquired back to one or more brokers using a "summary object interchange format" [3]. This allows for a significant reduction in network overhead when the transmitted information is heavily summarized or when there are many documents involved. Brokers interact with one or more gatherers for initial acquisition and with other brokers where useful to further filter information already collected by those brokers. Harvest is hence a service agent with similar architecture to Sulla's, but without any support for user or search profiling, and limited intelligence.
PAINT (Personalized Adaptive Internet Navigation Tool) [17] supports hierarchical hotlists in conjunction with Mosaic. This distinguishes it in that it is intended to support a single individual user, rather than a community of users. PAINT supports the creation of hierarchical clusters of Web resources as name spaces. The principle design goal was to simplify the comprehension of hotlist elements. Based upon the number of hotlist manipulation schemes springing up to support Mosaic, this is a significant problem for serious users of the Web. PAINT has formed much of our thinking with regard to information clustering
The Lycos system [15] employs a Gnu DBM file to store the information discovered during its exploration. The information stored for a given document includes: the title, headings, the 100 most weighty words, the first 20 lines of the document and the size of the document, both in bytes and in words. The rationale behind these choices is the creation of a scheme that is finite in scope the information concerning a document is not dependent upon the size of that document. Lycos caches the first twenty lines of the document for display as part of the results of a user search of the index, providing a limited context for the user without the need to access the matched documents.
WebCrawler [18] full-text indexes the documents encountered, operating with multiple retrieval agents in a server-breadth-first approach. The rationale behind the notion of a bread-first search with respect to servers rather than documents is that most servers currently have many related documents in a single subject area, rather than multiple subject areas. Skipping from server to server ensures broader coverage in results at the cost of requiring users to explore particular servers that seem to be relevant to see if they truly contain what is sought. Of course, subsequent passes by WebCrawler can reduce this coverage gap by eventually indexing the full set of documents on a given server.
The RBSE Spider [9] retains both the structure of the Web as a graph representation in a relational database and a full text index of the HTML documents encountered. Searches can thus be specified either as SQL queries against the database, resulting in information concerning the nature of the Web itself, or against the full text index, resulting in information concerning the contents of documents that make up the Web. The full text index is currently supported through a slightly modified WAIS server.
Each of the three search engines just discussed take very different approaches to the discovery, indexing and retrieval of Web resources. The difficulty in doing serious cross comparison due to the differences in scope and coverage of the Web that each has drove much of our initial thinking in the desirability of a user agent that could be tasked with the responsibility of interrogated potentially large numbers of search engines.
A user agent's architecture should reflect the concerns of the individual, rather than the concerns of the community. We have described Sulla, a user agent that supports long-lived, goal-oriented Web activity. Our current approach to agent interaction entails Sulla mimicking the behavior of a human interacting with each service agent. This approach suffers from the ambiguities of natural language and the limitations of interaction through simplistic query interfaces.
Creating a knowledge representation scheme for agent interaction will allow for more sophisticated interactions between a user agent and the service agents to which it appeals for information. A preliminary approach to a representation scheme for such a protocol, based upon a thesaurus, is currently under develop for MORE, the RBSE project's Web-based repository system [10]. This work will extend our current approach with richer representations, and will be validated using Sulla, the RBSE Spider and MORE.
There are few practical information retrieval systems that operate with anything other than a simple textual representation of a user query. Recent work in the area of knowledge engineering has led to significant, reusable environments for the construction of ontologies - models of the world that comprehend the relationships and terminologies used by humans in their reasoning and discourse. Representing such an ontology, and relating one system's ontology to another system's ontology is the critical factor for moving beyond ambiguous natural language as a means for users or agents to share information and goals. The ARPA Knowledge Sharing project has generated a prototype for just such a representation in KIF, the Knowledge Interchange Format. We intend to assess KIF for its strengths and implement a limited version that is focussed directly on our particular problem domain. This approach will form the core of the representation scheme for the second prototype.
- [1]
- Baclace, P. E., "Competitive Agents for Information Filtering," Communications of the ACM, v. 35, n. 12, December 1992, p. 50.
- [2]
- Berners-Lee, T., R. Cailliau, A. Loutonen, H. F. Nielsen and A. Secret, "The World-Wide Web," Communications of the ACM, v. 37, n. 8, August 1994, p. 76-82.
- [3]
- Bowman, C. M., P. B. Danzig, D. R. Hardy, U. Manber and M. F. Schwartz, "The Harvest Information Discovery and Access System," Proceedings of the Second International Conference on the World Wide Web, Chicago, IL, October 19-21, 1994.
- [4]
- Bowman, C. M., P. B. Danzig, D. R. Hardy, U. Manber and M. F. Schwartz, Harvest: A Scalable, Customizable Discovery and Access System, University of Colorado, Boulder, CO, August 26, 1994.
- [5]
- Castelfranchi, C., "Guarantees for Autonomy in Cognitive Agent Architectures," in Intelligent Agents: Theories, Architectures, and Languages, M. Wooldridge and N. R. Jennings (eds.), LNAI vol. 890, Springer-Verlag, 1995, p. 56-70.
- [6]
- Daigle, L. L., and P. Deutsch, "Agents for Internet Information Clients," CIKM'95 Intelligent Information Agents Workshop, Baltimore, MD, December 1-2, 1995.
- [7]
- Dunin-Keplicz, B. and J. Treur, "Compositional Formal Specification of Multi-Agent Systems," in Intelligent Agents, M. Wolldrige and N. R. Jennings (eds.), Springer-Verlag, Berlin, 1995, p. 102-117.
- [8]
- Eichmann, D., "Ethical Web Agents," Proc. Second International World-Wide Web Conference: Mosaic and the Web, Chicago, IL, October 17-20, 1994, pages 3-13. To appear in Computer Networks and ISDN Systems.
- [9]
- Eichmann, D. "The RBSE Spider Balancing Effective Search Against Web Load," First International Conference on the World Wide Web, Geneva, Switzerland, May 25-27, 1994, p. 113-120.
- [10]
- Eichmann, D., T. McGregor and D. Danley, "Integrating Structured Databases Into the Web: The MORE System," Computer Networks and ISDN Systems, v. 24, n. 2, 1994.
- [11]
- Engelmore, R and T. Morgan (eds.), Blackboard Systems, Addison-Wesley, Reading MA, 1988.
- [12]
- Koster, M., "List of Robots," Nexor Corp., http://web.nexor.co.uk/mak/doc/robots/active.html.
- [13]
- Koster, M., "A Standard for Robot Exclusion," Nexor Corp., http://web.nexor.co.uk/mak/doc/robots/norobots.html.
- [14]
- Maes, P., "Agents that Reduce Work and Information Overload," Communications of the ACM, v. 37, n. 7, July 1994, p. 31-40.
- [15]
- Mauldin, M. L. and J. R. R. Leavitt, "Web Agent Related Research at the Center for Machine Translation," Proceedings of the ACM Special Interest Group on Networked Information Discovery and Retrieval (SIGNIDR-94), August 1994
- [16]
- Norman, T. J. and D. Long, "Goal Creation in Motivated Agents," in Intelligent Agents: Theories, Architectures, and Languages, M. Wooldridge and N. R. Jennings (eds.), LNAI vol. 890, Springer-Verlag, 1995, p. 277-290.
- [17]
- Oostendorp, K. A., W. F. Punch and R. W. Wiggins, "A Tool for Individualizing the Web," Proceedings of the Second International Conference on the World Wide Web, Chicago, IL, October 19-21, 1994.
- [18]
- Pinkerton, B., "Finding What People Want: Experiences with the WebCrawler," Proceedings of the Second International Conference on the World Wide Web, Chicago, IL, October 19-21, 1994.
- [19]
- Riecken, D., "Intelligent Agents: Introduction to Special Issue," Communications of the ACM, v. 37, n. 7, July 1994, p. 18-21.
- [20]
- Riecken, D., "An Architecture of Integrated Agents," Communications of the ACM, v. 37, n. 7, July 1994, p. 107-116.
- [21]
- Selberg, E. and O. Etzioni, "Multi-Service Search and Comparison Using the MetaCrawler," Fourth World Wide Web Conference, Boston, MA, December 11-14, 1995.
- [22]
- Shklar, L., S. Thatte, H. Marcus and A. Sheth, "The "Infoharness" Information Integration Platform," Proceedings of the Second International Conference on the World Wide Web, Chicago, IL, October 19-21, 1994.
Footnotes
- (1)
- This work is supported in part by a grant from Texas Instruments, Inc. and in part by NASA as part of the Repository Based Software Engineering program, Cooperative Agreement NCC-9-30, research activity RB-02A.
- (2)
- Sulla was the robotic secretary to Harry Domain, General Manager of Rossum's Universal Robots, in Karel Capek's 1921 play R.U.R., where the term robot was first coined. Helena Glory, a visitor to the Rossum factory, initially refused to believe that Sulla was a robotess because she behaved perfectly normally for a human, with one rather notable exception. She didn't seem to be overly concerned about being dismantled... a property we have found very useful for a research prototype.
