[ Top ] [ Previous Section ] [ Next Section ]

A Heterogeneous Reasoning and Mediator System

3. Applications

In this section, we will present two case studies that have/are being developed as applications on top of HERMES.

3.1. Case Study: Integrating Terrain Maps, Relational Databases, and Planning

In this section, we will describe an application of our work to intelligent terrain reasoning that involves integrating terrain map data, relational data, and planning packages (developed at the US Army Corps of Engineers). The purpose of such an integrated system is many-fold. It can be used as a basis for vehicular navigation in disaster relief situations (e.g. floods, earthquakes, volcanic disasters, etc.), as well as in military mission planning applications. In these applications, a user, who may either be a human or may be an autonomous vehicle, may be interested in posing queries of the following types:

A route planner (which we will call RP) has been implemented at the US Army Topographic and Engineering Center. Given two points, this route planner will find an optimal, least-cost path between these two points (if one exists). Thus, for instance, the query

returns the set of least-cost paths from the origin point, (35,70) to the destination point (200,98) that are found by the Army's route planner.

We illustrate how this example may be solved within the HERMES framework, using RP as a domain. For this, let us suppose that we have a relational (PARADOX) database containing a relation called facilities having the schema (Name,Facility). Thus, this relation may contain a tuple of the form (awasa,airport) denoting that the place, Awasa, has an airport. Other tuples in the relation facilities may be similarly interpreted. Suppose there is another (DBASE) database containing a relation called supplies having the schema (Place,Item) -- an example tuple in this relation is (awasa,gas) specifying that gas is available at Awasa (In practice, these relations will contain much more detail, but we keep them simple here in order to facilitate presentation.).

Using HERMES, we have integrated the following four domains -- RP, DBASE, and PARADOX -- along with a spatial database that identifies points (xy-coordinates with place names). We have written a mediator that may be used to solve this example using the rule given below.

Query 1: Let rte1 be a ternary predicate such that rte1(O,D,R) is satisfied iff R is a route from the origin to an unspecified destination such that the destination has an airfield as well as certain types of ammunition. For this, we may define the following clause in the mediator:

rte1(O,D,R) <-
in(P1,PARADOX:select=(facilities,facility,``airfield'')) &
in(P2,DBASE:select=(supplies,item,``ammunition'')) &
=(P1.place,P2.place) &
in(D,SPATIAL:findpt(P1.place)) &

To obtained the result from a given location l, we can pose the query

This is then processed as follows: PARADOX is invoked which SELECTs all tuples from the facilities relation that have the an airfield facility. P1 is then instantiated to one of the selected tuples. Next DBASE is then queried to SELECT all tuples from the supplies relation that have the item field set to ammunition. P2 is instantiated to one such tuple. A check is made to see that P1 and P2 have the same place field. In other words, this ensures that single place is found with both ammunition and an airfield? If not, the HERMES inference engine looks for other possible instantiations of P1 and P2 that satisfy these constraints. Finally, the xy-location of the place P1.place is computed using the spatial domain, instantiating D, and RP is called to find a route from the origin l to D.

Solving the second query is somewhat more complicated because of the additional requirement that no enemy outpost lies within 4 miles of any point on the route. Let us suppose that the SPATIAL domain contained in our solution to Query 1 above has a special function called range that takes a point P and a radius Rad as inputs and returns all enemy outposts within Rad units of P.

Query 2: We define a new predicate called rte2 as follows.

Note the use of the special HERMES predicate ${\tt is}$ described earlier.

3.2. Case Study: Face Recognition for Law Enforcement Applications

We have also been developing a mediator in HERMES for law enforcement applications. The general problem is best illustrated with an example. Consider the problem of identifying all people P who have been recorded, by surveillance cameras, as having met with an individual X (for instance, X may be a Mafia chief like Don Corleone), who live within a hundred mile radius of Washington DC, and who work for a suspected front company ``ABC Corp.'' Solving this problem may require access to a wide variety of data sources and furthermore, require recourse to diverse reasoning paradigms as well. For example, it may be necessary to

We define the following three mediating rules.

seenwith(X,Y) <-
in(P1,facextract:segmentface('surveillancedata')) &
in(P2,facextract:segmentface('surveillancedata')) &
=(P1.origin,P2.origin) &
P1 <> P2 &
in(P3,facedb:findface(X)) &
in(true,facextract:matchface(P1,P3)) &
swlndc(X,Y) <-
seenwith(X,Y) &
in(A,PARADOX:select_eq('phonebook',"name",X)) &
in(Pt1,SPATIAL:locateaddress(A.streetnum,A.streetname,A.cityname) &
A.statename, A.zipcode)) &
suspect(X,Y) <-
swlndc(X,Y) &

The seenwith predicate access a domain called faceextract that we assume is a pattern recognition package, and that it uses the function segmentface to locate the faces in a set of photographs. The output of the function contain mugshots that can be stored. The extraction procedure returns a list of pairs of the form (<resultfile,origin>) specifying which image in the surveillance data, a given face was extracted from (the origin) and where the mugshot is now stored. The faceextract domain also contains a function called matchface that takes a face (such as those extracted by the faceextract domain) and checks if this face is identical to another face in the mugshot library. Likewise, the seenwith predicate access a domain called facedb containing a function called findface which determines, given a person's name, whether his or her face is in a mugshot library. The facedb domain also contains a function called findname which, given a mugshot in the mugshot library, returns the name of the person involved.

Given that a person Y has been seenwith X, swlndc (for ``seen with and lives near DC''), accesses a relational database to find the address of Y, and then accesses a spatial data management system to determine what (x,y) coordinates, on a map of the DC area, this address corresponds to (using a function called locateaddress). It then determines, using a function called range, whether this address lies within the specified distance from DC.

Finally, a person Y is a suspect just in case swlndc(``Don Corleone'',Y) is true and if he is an employee of ``ABC Corp.'' For this, a DBASE relation called empl_abc is accessed. The above three clauses express the mediator for this example in its entirety (though the individual domains are not completely shown).

3.3. System Usage

Figure 4. HERMES: Mediator Selection and Predicate Listing Screens

When the user brings up HERMES under Unix, the first screen shown in Figure 4, appears. The top window in this screen contains a list of available mediators. The user may select a mediator by clicking on it with the mouse button. To select the terrain mediator, the user clicks on terrain. The second screen in Figure 4 shows the screen that results -- the top screen contains various predicates defined within the terrain mediator. The buttons in the command bar at the top are suitably modified as well. The bottom window brings up a description of the mediator. The user may scroll through either the top window or the bottom window by using the scroll bar on the left. If the user wishes to find help information on a particular predicate, then s/he may click on that predicate with the mouse button.

Figure 5. HERMES: Query Articulation Screen and Screen after Query Execution

The first screen in Figure 5 shows the result of clicking on the routeToFacility predicate. At this stage, the second window from the bottom shows the usage of the predicate routeToFacility together with a help string explaining the utility of the predicate. The figure shows the screen after the user has keyed in a specific query

The new screen that pops up with the answer is shown in the second screen of Figure 5, The second window from the bottom contains the desired solution. Also observe that the top window now contains the statement

indicating that the file 2.scr is available for viewing. This is a script file. If the user wishes to view this file, then he may click on it -- doing so generates a pictorial version of the actual path generated (see Figure 6 where the red path denotes the desired route to the facility in question. In general, the files shown in response to a user query may themselves be heterogeneous files such as .GIF files of .SCR files, plain text files, or hypermedia documents. The display of these files requires the use of the action module to ``bring up'' the files in the desired format.

Figure 6. HERMES: Screen after Action Module's Intervention

3.4. Related Work

Following Wiederhold's pioneering paper on mediators [24,25], there have been several efforts to develop general-purpose methods of integrating multiple databases. In contrast to approaches that specifically deal with integrating multiple databases, we emphasize that our system and framework are applicable to the integration, not only of multiple databases, but also to the integration of multiple software packages (e.g. spreadsheets), and also multiple reasoning paradigms (e.g. path planning, face recognition, terrain reasoning, etc.).

Multidatabases and federated databases form a well-known family of database integration paradigms. In such frameworks, an attempt is made to create a ``global'' integrated scheme from a number of local schema -- then the global schema is queried. Most of the works in this arena are used to integrate multiple relational databases (and in some cases, object oriented databases), identifying schema mismatches, and eliminating them as part of the query processing procedures. Some elegant pieces of work on multidatabases are those due to Litwin et. al. [6,13,14]. In addition, Krishnamurthy, Litwin and Kent [11] define criteria that a language that a language that integrates multiple databases must satisfy. They show how to handle schematic discrepancies. Intuitively, two databases may contain the semantic information, but this information may be represented in different ways (e.g. in one database, all the information may be contained in one relation, while in the other, the same information may be spread over two relations). They define a query language that takes such schematic mismatches into account when handling queries. In a similar vein, Spaccapietra and Parent [21] structural conflicts that arise when multiple databases contain similar, but structurally different data. They show how data across multiple databases can be ``linked'' or ``tied together'' based on common attribute values (even though the attribute names may be different across different databases). Similarly, Bright et. al. [5] and Sciore et. al. [18] develop an array of methods to automatically resolve (using different techniques) semantic conflicts in multidatabases. Their work can be used to contribute to the conflict resolution toolkit that forms part of the HERMES architecture.

Generally speaking, the HERMES system applies to a wide diversity of domains with very different aspects to them such as the path planning domain, the face recognition domain, etc., that are not handled by multidatabases. As such, the types of software packages and the kinds of reasoning performed in systems like HERMES are broader than those in multidatabases. Other recent efforts that are proceeding synchronously with ours, are the SIMS/LOOM effort at ISI [2] and efforts to develop a language called KQML [12]. SIMS is a system that uses an object-oriented language called LOOM to integrate information from multiple databases. Objects in the world are classified into classes and a set of relations that link objects and classes are also stored. Various types of inheritance properties can be expressed in LOOM. Both HERMES and SIMS can benefit from one another in a variety of ways -- for instance, HERMES' generalized domain integration method is applicable to the SIMS model as well. As mentioned, in our Heterogeneous User Interface, the LOOM query language could form an important component therein, allowing users who prefer LOOM's LISP-flavored syntax to express their queries in it. KQML, in contrast, provides a method for communication requests to be made between a mediator and various software packages. Various KQML primitives like ask-if, ask-all, etc. may be used to manipulate belief-states that an agent may have (for example, this agent may a communications module that controls a communication channel). HERMES could benefit from KQML by using KQML agents in order to effect communications across the network. In contrast, KQML could benefit from HERMES by using HERMES' query language to identify and extract relevant information from different data sources, pool them together after identifying/resolving conflicts. We see rich potential interactions with both SIMS and KQML/LOOM.

[ Top ] [ Previous Section ] [ Next Section ]

Click here to go back to the Hermes homepage .

Web Accessibility