Deploying Information Agents on the Web

1 Introduction

There is a tremendous amount of information available on the Web, but the access to this information is largely dependent on the information providers. The individual web sites de­ cide what information to provide to the visitors to their site and how a visitor will access that information. There is little in the way of capabilities to combine information across sites and only the most primitive capabilities to monitor informa­ tion on individual sites. Of course, sites may provide inte­ grated access to specific data sources or sophisticated mon­ itoring capabilities on their data, but users of the Web are dependent on a site to make these capabilities available.

In contrast, imagine a world where access to information is driven by the consumers of the data. Where it is not only possible, but simple to task your own personal information agents to gather specific information, monitor for changes in the gathered data, and to notify you of important information or changes. The challenges are that the required information is often embedded in HTML pages, the data is organized in different ways on different sites, there are a huge number of ways the information could be combined, and it can be slow and cumbersome to combine the information.

We have developed a set of core technologies to simplify the task of building intelligent agents for gathering and mon­ itoring information on the Web .[Knoblock et al., 2003; 200 I; Barish and Knoblock, 2002a]. The technologies include the ability to gather information from the Web, to link that infor­ mation with related information, to build plans to integrate the various sources of data, and to efficiently execute these plans in the Web environment. We have applied these tech­ nologies to build agents for a variety of applications [Barish et al., 2000; Am bite et al., 2002], including an application for monitoring travel plans from online sources.

Researchers have developed a variety of agents that have been deployed on the Web over the years. Some notable sys­ tems include the Internet Softbot [Etzioni and Weld, 1994], an agent that interacts with a range of Internet resources, Bar·· gainFinder [Krulwich, 1996], a comparison shopping agent for CDs, ShopBot [Perkowitz et a/., 1997], a system for au­ tomatically locating and incorporating new stores into a com­ parison shopping agent, and Warren [Decker et al., 1997], a system for gathering data on a financial portfolio. There has also been a significant amount of research on the underly­ ing technologies required for developing agents on the Inter­ net [Levy and Weld, 2000]. As noted by Etzioni [1996], the Web provides a tremendous opportunity for building intelli­ gent software agents. Yet, surprisingly few have seized this opportunity. This is almost certainly because there are many technical issues that must be addressed to build such agents. Our work is designed to address these issues and simplify the task of building agents for the Web.

In this paper I first describe an example set of agents for monitoring travel plans. Then I will briefly describe the tech­ nologies that we have developed to gather data from web sources, link data across sources, generate plans to integrate the data, and efficiently execute these plans. Finally, I present directions for future research and conclusions.

2 Information Agents for Monitoring Travel

As part of the Electric Elves project [Chalupsky et al., 2001; Ambite et al., 2002] we have applied our agent technologies to build a set of agents for various tasks including tracking visitor schedules, monitoring meeting schedules, and moni­ toring a user's travel plans. In the case of monitoring travel plans, this task is particularly well-suited for applying agent technology for several reasons: a) this is a fairly complicated task with many possible forms of failure ranging from flight cancellations and schedule changes to hotel rooms be­ ing given away when a traveler arrives late at night, b) there are a large number of online resources that can be exploited to anticipate problems and keep a traveler informed, and c) these tasks would be tedious and impractical for a human to perform with the same level of attention that could be pro­ vided by a set of software agents.

To deploy a set of agents for monitoring a planned trip, the user first enters the travel itinerary and then specifies which aspects of the trip she would like to have the agents monitor. A set of information agents are then spawned to perform the requested monitoring activities. For the travel planning appli­ cation, we developed the following set of agents to monitor a trip:

• A airfare-monitoring agent that tracks the current price of a flight itinerary. The agent sends a notification on price increases and/or decreases. A traveler might con­ sider reticketing if the price drops significantly below what they paid.
• A schedule-change agent that keeps track of the pub­ lished schedule for a given flight itinerary and notifies a traveler of any change to this itinerary. Small sched­ ule changes occur quite frequently, especially if one pur­ chases tickets well in advance of a flight. Travel agents are supposed to notify their customers of changes, but one usually arrives at the airport before discovering that the scheduled departure time has changed.
• A flight-status agent that continually monitors the status of a flight. When a change of status or cancellation is detected, the traveler is immediately notified. This agent also sends a fax to the hotel if the flight arrival is de­ layed past 5pm in order to ensure that the hotel room is held for the traveler. This agent differs from what is available from commercial sites, such as ual.com, which simply check the status a fixed period of time prior to the flight. In contrast, our agents maintain state and can no­ tify the user of multiple status changes without sending messages that provide no new information.
• An earlier-flight agent that checks for flights that leave before the scheduled flight. It also checks the status of these flights to avoid suggesting delayed or cancelled flights . This agent is particularly handy when one fin­ ishes a meeting early or one wants to skip out of a par­ ticularly boring meeting.
• A flight-connection agent that monitors a users sched­ uled flights and if there is a connecting flight it wakes up a few minutes before the projected landing time, checks the status and gate information of the connecting flight and also searches for any earlier flights to the same des­ tination that the user might be able to take instead. This agent is particularly useful when there are only a few minutes to make an earlier connection that is about to depart.
• A restaurant-finding agent that locates the nearest restau­ rant based on the user's GPS location. On request, it sug­ gests the five closest restaurants providing cuisine type,

price, address, phone number, latitude, longitude, and distance from the user's location.

These agents are scheduled to run at regular intervals, where the agents are woken up to perform their task. The agents can cancel their own task once it is complete and can change the interval in which they are run based on the in­ formation from other agents. The agents often invoke other agents to help them perform their tasks. For example, the flight-status agent calls another agent that extracts the flight status information directly from a web site and it invokes the hotel notification agent, which in turn sends a message to the fax agent.

Figure I shows the messages that various agents generated during actual use of the system. The original set of agents were in use for about a year and then based on feedback and requests from the users we recently developed a new set of agents that provide improved capabilities.

3 Gathering Data from Web Sources

A key capability for information agents is the ability to reli­ ably access information. As the Web moves towards XML and Web Services, accessing data could become greatly sim­ plified. However, movement in this direction has been quite slow and for various reasons many sources will remain avail­ able only in HTML, so there is still a critical need to tum HTML sources into agent-enabled sources.

The challenge in building wrappers for online sources is how to achieve broad coverage and high accuracy with min­ imal user input. The two general approaches to this problem are supervised machine learning techniques [Kushmerick, 1997; Muslea et al., 200 I; Hsu and Dung, 1998] and unsu­ pervised grammar induction techniques [Lerman et al., 200 I ; Crescenzi et al., 200 I; Hong and Clark, 200 I]. The unsuper­ vised grammar induction techniques have the advantage of no user input, but they are not able to handle the full range of semistructured sources. In contrast, the supervised learn­ ing techniques apply to a wider set of sites, but can require a signifi(.;ant amount of labeled data to achieve high accuracy.

We developed an machine learning algorithm called Stalker [Muslea et al., 2001] that requires labeled data, but attempts to minimize the amount of information that must be provided by a user. Given labeled data, the system employs a greedy set covering algorithm to learn extraction rules that define a wrapper for a source. We minimize the amount of labeled data required by decomposing the learning problem into a number of simpler subproblems, which require fewer examples to learn. The decomposition is based on the hier­ archical structure of the information in a web source. This approach allows Stalker to learn how to extract data from complicated sites that involve lists of information and even arbitrary nesting of embedded lists.

An issue for any learning system, even Stalker, is that to achieve high accuracy the system must see the right set of ex­ amples. Since the expectation in a wrapper is to extract the data with 100% accuracy, finding a representative set of ex­ amples is a critical part of the problem. Rather than relying on the user to identify these examples, we developed an active learning technique called Co-Testing [Muslea et al., 2000; Muslea, 2002; Muslea et al., 2003] that selects the most in­ formation examples to label. Co-Testing works by learning multiple classifiers using different views of the same problem. In the case of wrapper learning, the system exploits the fact that it can learn equally well a classifier by finding landmarks from the beginning of the page or by finding landmarks from the end of the page. The system can then exploit the fact that both classifiers should agree if they have learned the same concept and any disagreement provides a source of training examples. Both classifiers are applied to the unlabeled exam­ ples and the user is asked to label the examples where there is disagreement. This allows the system to quickly identify the unusual cases in the data set to rapidly converge on an accurate set of extraction rules.

Another important challenge building wrappers is to ensure that they continue to work properly over time. This problem has not received much attention. The exception is the work by Kushmerick [2000] who developed an approach that uses the global properties of a page, such as the density of HTML tokens on a page, to determine when the page or even the spe­ cific information being extracted has changed. The limitation of this approach is that it is too coarse to detect some sites that have changed [Lerman et al., 2003] .

We developed a wrapper maintenance system that can repair wrappers by learning a description of the content ex­ tracted by a wrapper [Lerman et al., 2003]. This approach learns a pattern by using a hierarchy of pattern types, such as number or capitalized word, and then learning a description of the beginning and ending of the information that is being extracted. The resulting description or learned patterns are then stored and compared to the information being extracted. The patterns are compared statistically to avoid false positives due to examples that have not been seen before. In a large test set, this approach was able to identify 95% of the Web sites that had changed.

Once the system has identified a source that has changed, the learned patterns can then be used to automatically rela­ bel the site and run the labeled examples through Stalker, the wrapper learning system. The wrapper learning, validation, and reinduction process are illustrated in Figure 2.

4 Linking Information

Once data has been extracted from a web site, then one fre­ quently needs to combine it with other information in order to perform some task. For example, if one wants to build an agent for recommending nearby restaurants, then one might want to combine the data on a restaurant review site with the department of health site to ensure that the restaurant has an adequate health rating. The problem is that the information on these two distinct sites will often refer to the restaurants in different ways - the name, address, and phone number may all have slight variations that preclude simply joining the two sites across a single attribute.

To address this problem, we developed a machine learn­ ing approach to record linkage [Tejada et al., 2002; 2001]. In this approach the system, called ActiveAtlas, compares the attributes that are shared across the two data sets and learns two things. First, it uses a committee of decision tree learn­ ers to decide whether two records are matched based on the strength of the match of the various attributes (Figure 3). Sec­ ond, it improves the accuracy of these matches by learning an appropriate set of weights on a library of transformation rules (Figure 4). ActiveAtlas takes an active learning approach to select examples for the user to label in order maximize the ac­ curacy of the matches and minimize the amount of user input. Compared to other approaches to this problem [Cohen, 2000; Sarawagi and Bhamidipaty, 2002], the combination of the transformation weight learning and the active learning of the rules allows the system to achieve very high accuracy in matching entities.

5 Planning to Integrate Sources

Once an agent has access to the sources and can link the data across sources, the problem remains how to compose a set of information sources to perform some task. We developed an approach to automatically planning the integration of these sources to answer queries. In this approach, which is im­ plemented in the Ariadne information mediator [Knoblock et al., 1998; 2001], the contents of the sources available to the system are described using a common model [Ambite et al., 2001]. The system uses this model to create a plan that spec­ ifies both the data sources and the specific operations to be performed to satisfy a request.

One of the interesting problems is that due to the large search space and the need to optimize the plans, traditional planning techniques do not scale. To overcome this problem we developed a general-purpose planning approach, called Planning by Rewriting [Ambite and Knoblock, 2001], and we use it as the planner for Ariadne [Ambite and Knoblock, 2000]. In Planning by Rewriting, the system starts with an initial, but suboptimal plan, and then the planner performs a local search through the space of plan transformations to maximize the given evaluation criterion. In the query plan­ ning application, the planner searches through the space of sources and the operations on these sources to find an effi­ cient way to process a query. Figure 5 shows a simple exam­ ple of how Planning by Rewriting searches through the space of plan transformations. Researchers have explored a variety of approaches to this general problem of planning for infor­ mation gathering (see [Lambrecht and Kambhampati, 1997] for a summary of this work).

We are currently exploring planning techniques for com­ posing Web Services [Thakkar et al., 2003]. The Web Service infrastructure provides access to online sources in a form with which agents can interact without having to construct a wrapper for a site. In addition, the Semantic Web provides semantic-level descriptions of the services that are available [Ankolenkar et al., 2002]. Our approach to integration plan­ ning builds on previous work on data integration [Levy, 2000] and applies the inverse rules approach of Duschka [ 1997].

One challenge is that the sources available online often have restrictions on how they can be accessed in that cer­ tain inputs may be required to access a source. In the in­ verse rules framework this means that computing a complete set of answers to a query may require recursion. Since it can be expensive to execute integration plans in a language such as Datalog, we have developed an approach to automatically convert the recursive plans produced by the inverse rules al­ gorithm into a streaming dataflow execution framework that can efficiently execute these plans [Thakkar and Knoblock, 2003]. This execution framework is described next.

6 Executing Plans

Given a plan for performing some task on the Web, an agent needs to be able to efficiently execute this plan. In the Web environment, sources can be quite slow and the latencies of the sources are also unpredictable since they can be caused by heavy loads on both servers and networks. Since the primary bottleneck of most agent plans on the web is retrieving data from online sources, we would like to execute information requests as early as possible. To address these issues, we have developed a streaming dataflow language and executor, called Theseus [Barish and Knoblock, 2002a], which is optimized for the Web environment in the following three ways. First, since the executor is based on a dataflow paradigm, actions are executed as soon as the data becomes available. Second, Theseus performs the actions in a plan in separate threads, so they can be run asynchronously and in parallel. Third, the system streams the output from one action to the next so that sequential operations can be executed in parallel.

Theseus is similar to network query engines, such as Tele­ graph [Hellerstein et al., 2000] or Tukwila [Ives et al., 2002], in that they are also streaming dataflow execution systems. However, the network query engines focus on the efficient execution of of XML queries, while Thesues provides an ex­ pressive language for expressing information gathering and monitoring plans. The Theseus language supports capabili­ ties that go beyond network query engines in that it supports recursion, notification operations, and writing and reading from databases to support monitoring tasks.

Recently we developed an approach to increase the po­ tential parallelism in a streaming dataflow execution sys­ tem. This optimization technique, called speculative execu­ tion [Barish and Knoblock, 2002b; 2003], attempts to predict the results of an operation based on data and patterns that it has seen in the past. The predicted results can then be used to speculate about the operations that will need to be performed later in the plan. The system decides where to speculate by analyzing a plan and determining the critical paths. On these paths it then inserts a "speculate" operation, which uses in­ put to earlier operations to predict the input to later opera­ tions. The system also inserts a "confirm" operation, which ensures that the final result is correct regardless of whether the prediction is correct. This approach to optimizing streaming dataflow plans can achieve arbitrary speedups by speculating on the speculations. If the system is able to make accurate predictions, the executor could speculate on all of the input, execute the entire plan in parallel , and then confirm all of the results.

Figure 6 shows an example agent plan for integrating car­ related data from three online sources. This plan first uses the Edmunds.com site to find the midsize cars priced between $4000 and $12000. Next it selects out those cars made by Oldsmobile. Then for each of those cars, in parallel it calls both the NHTSA site to get safety reports and the Consumer Guide site to retrieve car reviews. Finally, all of this infor­ mation is combined into a single report. Figure 7 shows an abstract version of the same plan with the speculation opera­ tions inserted into the plan. The use of speculative execution in this plan makes it possible to invoke all three web sites in parallel.

The effectiveness of the speculation technique depends on making accurate predictions. We have developed a learning system that uses decision tree learning to make predictions on similar inputs and transducer learning to discover patterns in Web navigation paths. The learning system is described in more detail in [Barish and Knoblock, 2003].

Figure 7: Augmented plan for speculative execution

7 Future Directions

Given the growing interest in both Web Services and the Se­ mantic Web [Hendler, 200 I], we believe it will become easier to rapidly create and deploy agents on the Web. As more se­ mantic information becomes available about online sources, we plan to exploit this information to automatically discover and integrate new sources of information. Similarly, as web services become available that can support transactions, we plan to move beyond gathering and monitoring of online sources to build agents that perform more complex tasks, such as not just finding the lowest price ticket, but also purchasing it.

There are many possible uses of agents for retrieving and monitoring data from online sources. Ideally, users could de­ fine their own tasks that they want an agent to perform. For example, I might want an agent that monitors airfares and no­ tifies me the moment I can buy a ticket to Hawaii for less then $300. Someone else might want an agent to monitor for travel delays in their connecting airport and notify them when the average delay exceeds 30 minutes. The possibilities are endless. We are currently working on what we call an Agent Wizard, which allows the user to define new agents for mon­ itoring tasks simply by answering a set of questions about the task. The resulting system will work similar to the Excel Chart Wizard, which converts numerical data into charts by asking the user a set of questions. The Agent Wizard will au­ tomatically build the corresponding Theseus plan and sched­ ule the monitoring task for the user.

Another exciting direction is to deploy agents to collect and learn about online data and then use the results to make pre­ dictions about the world. For example, we recently developed a system called Hamlet that advises a user about whether they should immediately buy a ticket on a particular flight or wait for a possible drop in the price [Etzioni et al., 2003] . Hamlet makes these recommendations by collecting data on the cur­ rent pricing of flights on a particular route and then learning a model of the pricing in order to make predictions about fu­ ture price behavior. In a simulation using real data, Hamlet was able to save 607 simulated passengers $283,904, which was 88.6% of the savings possible with complete knowledge of the future price changes. Hamlet provides a compelling example of the potential of information agents.

8 Conclusion

The World Wide Web provides a tremendous opportunity for AI researchers to build, deploy and test software agents. The Web provides a real world environment that sidesteps many of the difficult issues of sensing and control and makes it pos­ sible to explore higher level capabilities. We have developed the tools and infrastructure for rapidly constructing agents on the Web for performing various types of information gather­ ing and integration tasks.

While the agents we have developed are extremely useful, there are many interesting and challenging problems that re­ main to be solved in order to widely deploy agents on the Web. Agents need to be able to robustly accomplish their tasks, responding appropriately to failures of various types. They must be able to communicate flexibly with people and other software agents, ideally in natural language. They need the ability to explain their behavior, especially as the tasks they perform become more complex. And, of course, we want agents that can learn from their past experience to both broaden their capabilities and improve their performance.

Acknowledgments

I want to thank my collaborators for their many contribu­ tions to the projects described in this paper. Steve Minton has worked closely with me on defining, building, and executing many of the research projects described here. Jose Luis Am­ bite, Greg Barish, Maria Muslea, Jean Oh, Snehal Thakkar, and Rattapoon Tuchinda all helped build the travel applica­ tion of the Electric Elves. Ion Muslea developed the wrap­ per learning systems, Kristina Lerman developed the wrapper maintenance and repair techniques, Sheila Tejada developed the record linkage approach, Snehal Thakkar and Jose Luis Am bite developed the various query planning algorithms, and Greg Barish built the Theseus executor and speculative ex­ ecution techniques. I also want to thank both Doug Dyer and Robert Herklotz for their support of my research over the years.

This research was supported in part by the Air Force Of­ fice of Scientific Research under grant numbers F496200 1-1-0053 and F49620-02-l-0270, in part by the Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory under contract/agreement num­ bers F30602-0 1-C-0 197 and F30602-00-l-0504, in part by the United States Air Force under contract number F4962002-C-0103, and in part by a gift from the Microsoft Corpora­ tion.

The U.S.Government is authorized to reproduce and dis­ tribute reports for Governmental purposes notwithstanding any copy right annotation thereon. The views and conclu­ sions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of any of the above organizations or any person connected with them.