(19)
`
`(12)
`
`Europaisches Patentamt
`European Patent Office
`een des brevets
`Office europeen des brevets
`
`EUROPEAN PATENT APPLICATION
`
`E P 0 8 4 5 7 4 8 A 2
`
`(43) Date of publication:
`03.06.1998 Bulletin 1998/23
`
`(21) Application number: 97309215.8
`
`(22) Date of filing: 17.11.1997
`
`(84) Designated Contracting States:
`AT BE CH DE DK ES Fl FR GB GR IE IT LI LU MC
`NL PT SE
`Designated Extension States:
`AL LT LV MK RO SI
`
`(30) Priority: 28.11.1996 GB9624711
`
`(71) Applicant: INTERNATIONAL BUSINESS
`MACHINES CORPORATION
`Armonk, NY 10504 (US)
`
`(51) |nt CI.6: G 06 F 17/60
`
`(72) Inventor: Carter, John Mervyn
`Chilworth, Hampshire S016 7LL (GB)
`
`(74) Representative: Moss, Robert Douglas
`IBM United Kingdom Limited
`Intellectual Property Department
`Hursley Park
`Winchester Hampshire S021 2JN (GB)
`
`(54)
`
`A method and apparatus for performing computer-based on-line commerce using an
`intelligent agent
`
`A method, computer program product and sys-
`(57)
`tem, for performing computer-based on-line commerce
`in which a client computer issues a commercial request
`and a plurality of server computers is available to service
`said request, said method, performed by an intelligent
`agent, comprising steps of: receiving said request from
`said client computer; reviewing content-related informa-
`tion and business policies of each server computer of
`said plurality of server computers; and making decisions
`as to which server should serve the request based on
`said content-related information and said business pol-
`icies.
`
`CM
`<
`00
`^>
`Is-
`
`^ -
`00
`o
`a .
`LU
`
`( START )
`
`Receive request from client
`
`.201
`
`Review service details and business policies
`of restaurant and Theatre servers
`
`202
`
`Make preliminary decisions as to
`which restaurant and which Theatre
`best suits clients request
`
`203
`
`Review cancellation business policy of
`each server selected at step 203
`
`Place servers in a queue according to
`cancellation policy serverity
`
`204
`
`205
`
`Make final decision as to restaurant
`
`Make final decision as to Theatre
`
`207
`
`stoF)
`
`FIG. 2
`
`Printed by Jouve, 75001 PARIS (FR)
`
`Starbucks Corp. Exhibit 1052
`
`

`

`1
`
`EP 0 845 748 A2
`
`2
`
`Description
`
`Field of the Invention
`
`The present invention relates to computer-based
`on-line commerce, where a computer user buys goods
`or services through his computer by linking his computer
`with that of a plurality of sellers through a computer net-
`work.
`
`Background of the Invention
`
`As networks of linked computers become an in-
`creasingly more prevalent concept in everyday life, so-
`called "on-line" interactions between computer users
`has begun to spread into many different areas of our
`lives. One of these areas is the marketplace for goods
`and services.
`In the past couple of years there has been an ex-
`plosive growth in the use of the globally-linked network
`of computers known as the Internet, and in particular of
`the worldwide Web (WWW), which is one of the facilities
`provided on top of the Internet. The WWW comprises
`many pages or files of information, distributed across
`many different server computer systems. Information
`stored on such pages can be, for example, details of a
`company's organization, contact data, product data and
`company news. This information can be presented to
`the user's computer system ("client computer system")
`using a combination of text, graphics, audio data and
`video data. Each page is identified by a Universal Re-
`source Locator (URL). The URL denotes both the server
`machine, and the particular file or page on that machine.
`There may be many pages or URLs resident on a single
`server.
`In order to use the www, a client computer system
`runs a piece of software known as a graphical Web
`browser, such as WebExplorer (provided as part of the
`OS/2 operating system from IBM Corporation), or the
`Navigator program available from Netscape Communi-
`cations Corporation. "WebExplorer", "OS/2" and "IBM"
`are trademarks of the International Business Machines
`Corporation, while "Navigator" and "Netscape" are
`trademarks of the Netscape Communications Corpora-
`tion. The client computer system interacts with the
`browser to select a particular URL, which in turn causes
`the browser to send a request for that URL or page to
`the server identified in the URL. Typically the server re-
`sponds to the request by retrieving the requested page,
`and transmitting the data for that page back to the re-
`questing client computer system (the client/server inter-
`action is performed in accordance with the hypertext
`transport protocol ("HTTP")). This page is then dis-
`played to the user on the client screen. The client may
`also cause the server to launch an application, for ex-
`ample to search for WWW pages relating to particular
`topics.
`Most WWW pages are formatted in accordance with
`
`a computer program written in a language known as
`HTML (hypertext mark-up language). This program con-
`tains the data to be displayed via the client's graphical
`browser as well as formatting commands which tell the
`5 browser how to display the data. Thus a typical Web
`page includes text together with embedded formatting
`commands, referred to as tags, which can be used to
`control the font size, the font style (for example, whether
`italic or bold), how to lay-out the text, and so on. A web
`10 browser "parses" the HTML script in order to display the
`text in accordance with the specified format. HTML tags
`are also used to indicate how graphics, audio and video
`are manifested to the user via the client's browser.
`Most Web pages also contain one or more referenc-
`es es to other Web pages, which need not be on the same
`server as the original page. Such references may gen-
`erally be activated by the user selecting particular loca-
`tions on the screen, typically by clicking a mouse control
`button. These references or locations are known as hy-
`20 perlinks, and are typically flagged by the browser in a
`particular manner (for example, any text associated with
`a hyperlink may be in a different colour). If a user selects
`the hyperlink, then the referenced page is retrieved and
`replaces the currently displayed page.
`Further information about HTML and the www can
`be found in "World wide Web and HTML" by Douglas
`McArthur, p18-26 in Dr Dobbs Journal, December 1994,
`and in "The HTML SourceBook" by Ian Graham, (John
`Wiley, New York, 1995).
`Enterprises (companies) are considering their us-
`age of the World wide Web. The first phase, namely the
`publicity of the company in whatever form, has already
`occurred. Home pages are commonplace, an essential
`ingredient for any company which wishes to maintain
`itself in line with current business practices. The public-
`ity material contains marketing information, product
`brands and, in some cases, product catalogues.
`The second phase, namely to conduct commerce,
`is emerging. Enterprises are poised to conduct business
`
`sales of their products and services, by way of the world
`Wide Web.
`Software infrastructure is coming into existence to
`enable the progress of this trend. Secure financial pro-
`tocols have been defined and are being implemented.
`The provision of firewall technologies offer safeguards
`to the enterprise, without which the enterprise would not
`contemplate permitting access to its critical data. Gate-
`way products are becoming available to facilitate con-
`so nection between the World wide Web and the server ma-
`50
`chines of the enterprise.
`Thus, many suppliers have begun to sell their goods
`and services over the World wide Web by placing their
`catalogues on their Web pages, such catalogues listing
`55 content-related information (e.g. product description,
`price, availability) about the various goods and services
`offered for sale. They also list their business policies
`concerning, for example, their cancellation policy. That
`
`
`
`25 25
`
`30
`30
`
`35
`35
`
`40 by way of the world wide Web. They are seeking to make 40
`
`45
`45
`
`2
`
`Starbucks Corp. Exhibit 1052
`
`

`

`3
`
`EP 0 845 748 A2
`
`4
`
`is, the cancellation policy specifies what will happen if a
`customer decides to buy something and later changes
`his mind.
`If the buyer tries to do this on his own without any
`help, this can be a frustrating and confusing experience
`as many different competing suppliers must be contact-
`ed to determine who can supply the correct product/
`service at the best price. This problem is compounded
`when a group of inter-related requests are being simul-
`taneously coordinated. For example, a buyer may wish
`to book a theatre reservation, restaurant reservation as
`well as parking.
`So-called intelligent agents are available to help an
`"on-line" buyer in these situations. Intelligent agents are
`computer programs that simulate a human relationship
`by doing something that another person could otherwise
`do for you. For example, the Telescript agent software
`developed by General Magic, a Silicon Valley start-up
`company, supports the deployment of software agents
`to act as personal delegates across a computer network
`("Telescript" is a trademark of General Magic company).
`The agent performs various tasks at electronic venues
`(servers) called "places" which include electronic mail-
`boxes, calendars and marketplaces.
`The Telescript agents gather information resource-
`fully and negotiate deals on behalf of the client buyer
`(the principal for whom the agent is working). The agent
`can be customized by each individual buyer/user so that
`the agent reflects the choices and desires of the buyer/
`user. The agents are intelligent in the sense that they
`can execute contingency plans if the most preferred
`plan is not feasible given the supplier resources and the
`general server environment at the time of the agent's
`dispatch. The Telescript agent can be sent to an elec-
`tronic florist, ticket seller and restaurant to perform a
`shopping trip for the client on the other side of the com-
`puter network. The details of such software agents are
`well known and are explained, for example, in Internet
`Agents, Spiders, Wanderers, Brokers, and Bots, Fah-
`Chun Cheong, New Riders Publishing, Indianapolis, In-
`diana, USA, 1 996. Further details can be found on Gen-
`eral Magic's World wide web site (http://www.genmagic.
`com).
`When an intelligent agent such as Telescript con-
`tacts appropriate suppliers (servers) of the same good
`or service in order to determine which of the plurality of
`competing suppliers to choose to supply a particular
`good or service requested by the client, the agent uses
`only "content-related" information provided by the sup-
`pliers in order to make a decision. That is, the agent
`looks only at whether the supplier can supply the re-
`quired content of the request. For example, if the client
`requests a particular videotape to be rented the intelli-
`gent agent electronically "goes" to a plurality of on-line
`videotape rental companies and checks each company
`to see if they have the particular videotape in stock. The
`agent also looks at other content-related information
`such as rental price. However, the agent does not take
`
`5
`
`is
`
`20
`
`25
`
`other considerations into account beyond such content-
`related information.
`Since known software agents use only content-re-
`lated considerations in deciding amongst a plurality of
`competing suppliers, a request is processed in such a
`way that the agent expends the least effort in making a
`decision as to which of a plurality of competing suppliers
`to use. while the agent is relieved from having to perform
`extra processing steps, this least effort approach does
`10 not always result in the best possible solution for the
`client. For example, the agent may choose a particular
`supplier because of price but not take into account the
`supplier's cancellation policy which may prove detri-
`mental to the client should the client wish to cancel.
`Also, known intelligent agents have not taken into
`account implications resulting from the order in which
`portions of a multi-portion request are booked. That is,
`if a theatre ticket is booked before a restaurant reserva-
`tion, and an appropriate restaurant is not available for
`the night in which the theatre is booked, it will be nec-
`essary to cancel the theatre reservation which could
`mean losing the funds expended, as most theatres will
`not give a refund for cancellations (while most restau-
`rants do not even require advance payment at all).
`As another example, a buyer may be trying to co-
`ordinate a group of interrelated "on-line" purchase relat-
`ed to a two-week trip overseas. The buyer may wish to
`book not only the airline reservation but also the parking
`at the airport (or bus/train reservations), hotel, rental car
`30 and restaurant reservations. If the agent books the air-
`line reservation, hotel and rental car it may then turn out
`that airport parking (and bus/train reservations) is either
`unavailable ortoo inconvenient to match up with the oth-
`er booked reservations. This would require having to re-
`35 contact the suppliers of the booked reservations and try-
`ing to renegotiate a new booking. In the case of the air-
`line, this is oftentimes difficult to impossible without in-
`curring substantial financial losses.
`With this booking approach currently used by intel-
`ligent agents, there is a good chance that it will be very
`difficult to recover expended funds made for booked
`transactions in the event a cancellation must occur.
`
`40
`
`Disclosure of the Invention
`
`45
`
`The present invention provides a method of per-
`forming computer-based on-line commerce in which a
`client computer issues a commercial request and a plu-
`rality of server computers is available to service said re-
`50 quest, said method, performed by an intelligent agent,
`comprising steps of: receiving said request from said cli-
`ent computer; reviewing content-related information
`and business policies of each server computer of said
`plurality of server computers; and making decisions as
`to which server should serve the request based on said
`content-related information and said business policies.
`In a preferred embodiment, the request issued by
`the client computer is made up of a group of inter-related
`
`55
`
`3
`
`Starbucks Corp. Exhibit 1052
`
`

`

`5
`
`EP 0 845 748 A2
`
`6
`
`sub-requests, and said intelligent agent decides which
`server should serve each sub-request based on said
`content-related information and said business policies.
`Further, said business policies of each server include
`cancellation conditions concerning consequences of
`cancelling service by that server once a decision is
`made by the intelligent agent to use that server to serve
`a particular sub-request, said conditions ranging from a
`first extreme where cancellation is most difficult to a sec-
`ond extreme where cancellation is easiest; and further
`wherein, after making preliminary decisions as to which
`server should serve which request based on said con-
`tent related information, said intelligent agent makes fi-
`nal decisions on said group of requests in the order such
`that a sub-request matched with a server with a cancel-
`lation condition closest to or at said second extreme is
`decided upon first.
`According to other aspects of the invention, the in-
`vention is drawn to an intelligent agent for performing
`the above method steps, and to a computer-based on-
`line commerce system using an intelligent agent which
`performs the above method steps.
`According to a preferred embodiment, final deci-
`sions on remaining requests of said group are made in
`a descending order from said second cancellation con-
`dition extreme to said first cancellation condition ex-
`treme. Also, said first cancellation policy extreme is one
`where no recovery of any expended funds is allowed
`and said second extreme is one where total recovery of
`any expended funds is allowed.
`According to the preferred embodiment, once a pre-
`liminary decision is made as to which server should sat-
`isfy which request based on content-related considera-
`tions, the decision is not made final at that point and no
`final commitment with any server has yet been made.
`Instead, the commitments are made in a certain order.
`First, the commitments which are most easily cancelled
`are made. Lastly, after the easily cancelled commit-
`ments are made, the commitments which are more dif-
`ficult to cancel are made. Therefore, the difficulties of
`having to go back and try to unbook a commitment in
`order to accommodate other commitments is mini-
`mized. If an easily cancelled commitment is not conven-
`ient with respect to a later considered more difficult to
`cancel commitment, the easily cancelled commitment
`can be simply cancelled and rebooked by the intelligent
`agent, without any loss being incurred.
`
`Brief Description of the Drawings
`
`Preferred embodiments of the invention will be de-
`scribed in detail below with reference to the following
`figures:
`
`Figure 1 shows a basic system configuration in
`which the present invention operates, according to
`a preferred embodiment;
`
`55
`
`4
`
`5
`
`Figure 2 is a flow chart showing the steps performed
`by an intelligent agent illustrating a specific example
`of on-line commerce according to a preferred em-
`bodiment of the present invention; and
`
`Figure 3 is a flow chart showing the steps performed
`by an intelligent agent according to a preferred em-
`bodiment of the present invention.
`
`10 Detailed Description of the Preferred Embodiments of
`the Invention
`
`is
`
`As shown in Fig. 1 , a preferred embodiment of the
`present invention involves a client computer system 1
`running a Web browser and connected to the Internet
`2. A plurality of server computer systems 3a-3n are also
`connected to the Internet and run Web server software
`in a well known manner. Another computer system 4 is
`provided for running the intelligent agent software. This
`20 software can be stored, for example, on the hard drive
`or in semiconductor memory of system 4. The client sys-
`tem 1 communicates first with the agent system 4 which
`in turn contacts the servers 3a to 3n. It should be noted
`that the agent software does not have to be running on
`25 a separate computer system 4 but can be run on the
`25
`client system 1 or alternatively on one of the servers 3a
`to 3n.
`The agent software running on computer system 4
`performs a group of related business transactions for its
`30 client computer system 1 . The client computer system
`30
`1 makes a request of its agent system 4 and this request
`causes the agent to access the servers 3a to 3n, review
`their services, price structures and business policies
`and perform the group of business transactions on be-
`35 half of the client system 1 .
`Business Transactions
`
`Business Transactions are characterised by: multi-
`40 pie, yet separate, traditional transactions (local and/or
`distributed),
`
`* which gives rise to the potential for time windows,
`during which some part(s) of the overall business
`transaction can be observed to be complete,
`
`45
`
`*
`
`not uncommonly they are of long duration (even
`weeks or months),
`
`so *
`50
`
`and involve a wide distributed environment.
`
`The business transaction is exemplified by the long-
`term car parking scenario, with its several time inde-
`pendent phases, namely:
`
`*
`
`*
`
`initiating the service (entering the car park),
`
`terminating the service (leaving the car park, and
`
`Starbucks Corp. Exhibit 1052
`
`

`

`7
`
`EP 0 845 748 A2
`
`8
`
`initiating payment, for example by cheque or credit
`card),
`
`*
`
`*
`
`settling the payment (though the client's bank), and,
`
`accounting reconciliation (within the car parking
`business).
`
`This example also shows the separation of the main
`interactions, firstly between the customer and the sup-
`plier to request and obtain the product or service, and
`secondly, between the financial bodies representing the
`customer and the supplier in order to transfer the appro-
`priate payment.
`It is worth noting that, at least in theory, this second
`stage does not necessarily involve either the customer
`or the supplier.
`If the car parking scenario was a "stand alone" busi-
`ness transaction, then the "requesting the product"
`phase involves a straightforward interaction between
`only the consumer and the supplier. However, it is very
`conceivable that this activity is just a part of some larger
`business transaction, such as involving the reservation
`of flights, hotels and other travel related commodities.
`An individual consumer might choose to undertake
`each of the various and separate interactions with the
`autonomous suppliers in order to arrange all the ele-
`ments needed to meet the specification of the complete
`package. However as the complexity of the package in-
`creases, so it is more likely that the individual will wish
`to delegate some, or all, of the organisation to an agent.
`As we shall see, whether or not an individual or an
`agent is responsible for assembling the various ele-
`ments, the business policies of the suppliers influence
`the strategy by which the complete package is con-
`structed.
`
`Agent strategy
`
`Consider a scenario in which an individual wishes
`to organise an evening out, including say, reservations
`for a theatre and a restaurant. This implies the conflu-
`ence of three conditions, namely:
`
`a) the availability of the individual,
`b) the availability of a seat in the (desired) theatre
`(at the right price), and,
`c) the availability of a place at the (desired) restau-
`rant (again at right price).
`
`However, the theatre has a business policy which
`requires payment with the order and does not make any
`refund on a ticket once it is sold. On the other hand, the
`restaurant business only charges its customers once it
`knows what they have consumed, and therefore ac-
`cepts cancellations (since these are preferable to "no-
`shows"). Under these circumstances what strategy
`should the organiser adopt?
`
`5
`
`10
`
`is
`
`If there are more appropriate restaurants than the-
`atres, it would seem natural to reserve the theatre first
`and then to book one of the several possible restau-
`rants. However, such an approach is based on the sta-
`tistical chances of success. This may be warranted in
`practice, but it is a policy of risk, because if none of the
`possible choices of restaurant can accept the reserva-
`tion, then the organiser now has a theatre booking which
`is no longer required and for which it is difficult to recover
`the financial commitment. Therefore in terms of reduc-
`ing the effort for recovery, Applicant has found that it is
`better if the reservation for the theatre is made after the
`reservation for the restaurant. This is because the the-
`atre is the party imposing the most severe conditions on
`the organiser.
`Fig. 2 shows an example of the software program
`steps which the agent computer system 4 would exe-
`cute in order to minimize the costs of totally cancelling
`a booked group of business transactions related to an
`20 evening out at the theatre. The client request would in-
`clude, for example, whether the client wishes to view a
`particular show at a particular theatre or a particu lar type
`of show (e.g. a comedy) at any theatre etc. The request
`could also inform the agent of the type of restaurant de-
`25 sired. The request also has a day or range of days which
`25
`the client would find most acceptable.
`In response to receiving the client request, the
`agent begins its routine. At step 201 the agent receives
`the request from the client and analyzes its details. As
`30 part of this review, the days of the individual's availability
`30
`may be checked, for example, by examining the individ-
`ual's electronic diary stored via a personal information
`manager software program on the client computer sys-
`tem 1, to make sure the individual is indeed available
`35 on the days specified. At step 202, the agent 4 checks
`35
`the various servers 3a to 3n which represent companies
`dealing in theatre and restaurant services, and exam-
`ines their service details and business policies. The pur-
`pose is to check each server's service details and poli-
`40 cies to see how well that server could satisfy the appro-
`40
`priate part of the client's request. For example, the the-
`atre servers would be examined to see if they had the
`requested show type and theatre type, and if they were
`available on the days in which the client is available. The
`restaurant servers are similarly checked. The agent also
`checks the business policies to determine which server
`is giving the best deal in terms of price, quality etc.
`Then, at step 203, based on the data collected in
`the previous steps, the agent chooses the most appro-
`50 priate restaurant and theatre servers which are availa-
`50
`ble on a day which is acceptable to the client. A prelim-
`inary decision is made, at this point, as to which servers
`will be used. The selected servers and date are stored
`in memory without making a final commitment with re-
`55 spect to any server.
`At step 204, the agent 4 reviews a specific one of
`the business policies of each server, the cancellation
`business policy. Usually, for the theatre, the policy will
`
`45
`45
`
`5
`
`Starbucks Corp. Exhibit 1052
`
`

`

`9
`
`EP 0 845 748 A2
`
`10
`
`fort of recovery, then it will pursue a strategy of obtaining
`the commitment of the required services, in the order of
`increasing effort of change, that is starting with the serv-
`ice for which the effort of rework is the least and finishing
`5 with that for which that effort is the most.
`Applicant has found that the cancellation policies of
`the various suppliers should be taken into account in or-
`der to eliminate the problems of having to recontact a
`supplier of a booked request in order to try to unbook
`the request and obtain a refund in situations where other
`requests can not be conveniently matched with the
`booked request.
`Some examples of commands which an agent
`would make to a server while carrying out the review of
`is content-related information and business policies of
`each server (as in steps 202 and 204 of the above ex-
`ample) are as follows.
`
`10
`
`*
`
`*
`
`*
`
`*
`
`lnquire_Server_Capabilities
`To determine the functions supported by a server.
`
`lnquire_Server_Policies
`To identify the business policies of the server, for
`example does the server provide "credit on cancel-
`lation". This information would enable the agent to
`determine its strategy for handling this server.
`
`lnquire_Goods/Services/ Availability/Cost
`To provide details concerning goods/services of-
`fered by a server and the availability and/or cost of
`a good or service.
`
`lnquire_Booking/Reservation/Waitlisted_Reserva-
`tion
`To return the current status of a specified order.
`
`* Make_Reservation
`To prepare the server for an order, which will be can-
`celled or confirmed subsequently. There is an im-
`plied timeout for a reservation established by the
`business terms and conditions of the server.
`
`* Cancel_Reservation
`To cancel a reservation (equivalent to a "rollback"
`against a prepared server).
`* Confirm_Reservation
`To finalize a reservation (equivalent to a "commit"
`against a prepared server).
`* Cancel_Booking
`To cancel a confirmed order.
`* Make_Booking
`To establish a confirmed reservation. This is logical-
`ly equivalent to a Make_Reservation with an imme-
`diate Confirm_Reservation, the difference being
`that it is an atomic action (i.e. there is no time win-
`
`be that there is no refund available in case of a cancel-
`lation. The money is simply kept by the theatre. On the
`other hand, the restaurant would usually have a policy
`of not requiring money in advance, so there is no loss
`to the client (or agent) upon cancellation of that part of
`the overall group of transactions. The selected servers
`are placed in a queue according to the severity of their
`cancellation policies at step 205. The restaurant would
`be first in the queue as it has the least severe cancella-
`tion policy. The theatre would be last in the queue as it
`has the most severe cancellation policy.
`At step 206, the restaurant server preliminarily se-
`lected at step 203 is now booked, as this server has the
`least severe cancellation policy as compared to the oth-
`er preliminarily selected servers at step 203 (the theatre
`in this example). Then, at step 207, the theatre server
`which was selected at step 203 is now booked.
`Obviously, this is rather "pure" logic, and in practice
`an organiser would make some optimisations, such as
`dealing only with the theatre based on the days