\documentclass{llncs} \usepackage{epsfig,times,html} \newcommand{\ob}{\allowbreak} % for bibtex and Web refs %"ob" for optional break \begin{document} \newlength{\fred} \setlength{\fred}{\textwidth} \addtolength{\fred}{-2\fboxsep} % -2 x \fboxsep \addtolength{\fred}{-2\fboxrule} % -2 x \fboxrule \addtolength{\fred}{-0.5mm} %\addtolength{\fred}{-1em} %\addtolength{\fred}{-12pt} % - \tabcolsep \title{An Agent-based Architecture for\\Software Tool Coordination} \author{Stephen Cranefield and Martin Purvis} \institute{Computer and Information Science, \\ University of Otago, \\ PO~Box~56, Dunedin, New Zealand\\ \{scranefield,mpurvis\}@commerce.otago.ac.nz} \maketitle \begin{abstract} This paper presents a practical multi-agent architecture for assisting users to coordinate the use of both special and general purpose software tools for performing tasks in a given problem domain. The architecture is open and extensible being based on the techniques of agent-based software interoperability (ABSI), where each tool is encapsulated by a KQML-speaking agent. The work reported here adds additional facilities for the user to describe the problem domain, the tasks that are commonly performed in that domain and the ways in which various software tools are commonly used by the user. Together, these features provide the computer with a degree of autonomy in the user's problem domain in order to help the user achieve tasks through the coordinated use of disparate software tools. This research focuses on the representational and planning capabilities required to extend the existing benefits of the ABSI architecture to include domain-level problem-solving skills. In particular, the paper proposes a number of standard ontologies that are required for this type of problem, and discusses a number of issues related to planning the coordinated use of agent-encapsulated tools. \end{abstract} \bibliographystyle{unsrt} \section{Introduction} Every computer user must at some time have wished their machine was more ``intelligent'' and could reason about the task being performed by the user and the steps that must be performed to achieve that task. In particular, for many computer users, their day-to-day work involves the use of a variety of different software tools, developed independently and using different data representations and file formats. Coordinating the use of these tools, remembering the correct sequence of commands to apply each tool to the current problem and incorporating new and modified tools into their work patterns adds additional demands on the user's time and memory. This paper discusses an agent-based architecture designed to remove this drudgery from the user. The paper also includes a discussion of related planning and ontological issues. The architecture combines the techniques of agent-based software interoperability (ABSI) \cite{facilitator_manual} with a planning agent and facilities for the user to describe the problem domain, the tasks that are commonly performed in that domain and the ways in which various software tools are commonly used by the user. Together, these features provide the computer with a degree of autonomy in the user's problem domain. The user can request the initiation of domain-level tasks and the system will plan and execute the appropriate sequence of tool invocations. If a task is not completed in one session, the system will remember the current state of the task and how any intermediate data files relate to the overall task. By simply requesting the continuation of the task, the user can cause the planner to begin from where it left off previously. Providing these abilities has implications for the nature of the planning agent and also suggests the necessity of developing ontologies for certain standard information storage formats. This work places no requirements on the internal structure of agents in the system (which, apart from specialised planning and console agents, are simply encapsulations of existing software tools). Instead it focuses on the representational and planning capabilities required to extend the existing benefits of the ABSI architecture to include domain-level problem-solving skills. \section{Agent-based Software Integration} In today's heterogeneous software environments, with tools written at different times for various specific purposes, there is an increasing demand for interoperability among these tools \cite{Genesereth}. While distributed object models such as CORBA \cite{CORBA} are currently gaining widespread industrial acceptance as standards for sharing data and exchanging services amongst distributed applications, research is underway towards finding higher-level, declarative models of communication and cooperation. Progress in this area has been made in the field of ``Agent-Based Software Interoperability'' (ABSI) \cite{facilitator_manual}, also known as ``Agent-Based Software Engineering'' \cite{Genesereth}. This involves the encapsulation of software tools and information servers as ``agents'' that can receive and reply to requests for services and information using a declarative knowledge representation language, {\it e.g.}\ KIF (Knowledge Interchange Format), a communication language, KQML (Knowledge Query and Manipulation Language) and a library of formal ontologies defining the vocabulary of various domains. The agents are connected in a ``federation architecture'' which includes special `facilitator' agents such as the one developed by the Stanford University Computer Science Department's Logic Group \cite{facilitator_manual}. Facilitator agents receive messages and forward them to the most appropriate agent depending on the content of the message (this is known as ``content-based routing''). Agents are responsible for registering the type of message they can handle with the facilitator. Tools can be spread across different platforms to form an open and extensible agent system: a new tool can be added to the system by providing it with a `transducer' program (that translates between KQML and the tool's own communications protocol) or a `wrapper' layer of code (a KQML interface written in the tool's own command or scripting language) and registering its capabilities with a facilitator agent. \section{Desktop Utility ABSI} ABSI projects discussed in the literature have to date largely focused on domains where the software tools to be integrated are complex and/or expensive to develop, {\it e.g.}\ concurrent engineering of a robotic system \cite{PACT}, civil engineering \cite{civil_eng}, electronic commerce \cite{commerce_net}, and distributed civic information systems \cite{knowledgeable_community}. In contrast with these large-scale integration efforts, the problem addressed in this paper is how to support interoperation among an evolving workbench or toolkit of general purpose utilities and special-purpose tools. Working with such a toolkit can typically be characterised as follows: \begin{itemize} \item A number of tasks are performed in sequence, possibly over an extended period of time and with significant time intervals between some of the tasks. \item Information recording the current state of the problem domain must be kept and updated as each task is performed. \item A variety of data formats and software tools are used to perform the different tasks. Relevant new tools may appear and existing tools may be replaced or upgraded over time. \item Some general-purpose tools may be used to support work in a number of different problem domains. \end{itemize} Typically, the problem domain is relatively simple and can be adequately defined using standard data modelling representations ({\it e.g.}\ the relational data model). Also, as some of the tools used may be general purpose utilities such as relational database management systems, programmable text editors and spreadsheets, for maximum reusability these should be encapsulated by agents that communicate in terms of the data formats the tools operate on. An architecture to support this type of tool interoperation must therefore include ontologies describing low-level data formats and how these can be related to higher-level representations of the domain. As each of the tools used may only perform a small part of the overall task, the overhead of coordinating the use of different tools into a coherent sequence represents a significant overhead. Thus planning support is needed to help the user select the appropriate sequence of tools to be used. We will refer to this type of ABSI problem as ``Desktop utility ABSI'' to distinguish it from the large scale interoperability projects referenced above. One application area that falls into this area is administrative work involving the management of information stored in common data formats such as text files, spread sheets and relational databases. \section{The Architecture} \begin{figure}[htbp] \centerline{\epsfig{file=small-arch-pic.eps,width=15pc,height=7.8pc}} %\centerline{\epsfig{file=arch.eps,width=65mm,height=33.8mm}} %\centerline{\epsfig{file=arch.ps,width=15pc,bbllx=164pt,bblly=524pt,bburx=415pt,bbury=723pt,clip=}} \caption{The desktop utility agent system architecture} \label{arch_fig} \end{figure} Figure~\ref{arch_fig} shows our architecture for Desktop Utility ABSI \cite{Baltimore}. This is based on the federation architecture with the addition of two specialised agents: a planning agent and a console agent. \subsection{The Planning Agent} For interoperating systems involving a few complex agents (large scale ABSI) the patterns of interaction between the agents are likely to be known in advance and limited in scope. In contrast, for desktop utility agent systems, there may be many simple agents each encapsulating a number of operations performed by various general-purpose tools. To achieve a user's high-level goal in the problem domain, it may be necessary for a number of different agents to perform actions in an appropriate sequence. It would be tedious if the user were required to specify this sequence of agent invocations. However, deducing an appropriate sequence of agent actions to achieve a goal is an AI planning problem and facilitators whose is knowledge is expressed using KIF ({\it e.g.}\ the Stanford facilitator \cite{facilitator_manual}) do not support planning well as they have no notion of state and time. Rather than attempting to extend the function of a facilitator to perform planning, our architecture contains a specialised planning agent. Each agent is required to register with the planning agent by sending specifications of the actions it can perform (consisting of the actions' preconditions and effects). \begin{figure}[htbp] \fbox{ \parbox{\fred}{ \rule{\fred}{0pt} \begin{tabbing} {\bf Action: } \= \kill {\bf Agent: } \> {\tt dbase-agent} \\ {\bf Action: } \> {\tt (add-marks ?f ?ass ?db)} \\ {\bf Description: } \\ {\tt\ }Add marks for assignment {\tt ?ass} in file {\tt ?f} to the database {\tt ?db}.\\ \\ {\bf Preconditions: } \\ {\tt\ (database-matches-datamodel ?db info202-dm) }\\ {\tt\ (file-format ?f (delim \#\char92, (listof string string number))) }\\ {\tt\ (file-represents-relation ?f }\\ {\tt\ \ \ \ (select ASSESS (= cmptid ?ass))}\\ {\tt\ \ \ \ info202-dm }\\ {\tt\ \ \ \ (stuid cmptid mark)}\\ {\tt\ \ \ \ ?state)}\\ \\ {\bf Postconditions: } \\ {\tt\ (database-includes-relation ?db }\\ {\tt\ \ \ \ (select ASSESS (= cmptid ?ass)) }\\ {\tt\ \ \ \ info202-dm}\\ {\tt\ \ \ \ (do (add-marks ?f ?ass ?db) ?state))} \end{tabbing} }} \caption{Specification for a database agent action} \label{action_spec} \end{figure} Figure~\ref{action_spec} shows a specification\footnote{In this case no preconditions are retracted by the action, although in general this is possible.}\ for an action performed by a database agent as part of a university course administration process (the predicates appearing in the specification are explained in Sect.~\ref{ontologies}). This describes an ability of the database agent to read in a specially formatted marks file (as produced by a utility used to systematically mark student's electronically submitted programming assignments) and to update the student marks database. Note that an explicit state variable appears in some of the pre- and post-conditions. The reason for this is explained in Sect.~\ref{state_variables}. This agent action is designed for a specialised problem domain: its specification contains terms from the problem domain ontology. Agents may also encapsulate the general-purpose data manipulations of desktop utilities. For example, an agent might encapsulate the ability of the Excel spreadsheet to take as input a text file containing a column of numbers and produce a printed histogram of these numbers. In general, one agent wrapper must be provided for each application, and this will register with the planning agent all the functionalities of the underlying application that have been encoded in the agent. It is not envisaged that the full functionality of general packages such as spreadsheet or word processing applications could be expressed declaratively in a single specification. However, it should be possible to provide specifications for various simple computations that the application can perform. \subsection{The Console Agent} In the desktop utility agent architecture the user interacts with a console agent that accepts requests expressed using the ontology of the user's various problem domains. In particular, the user can issue a request \verb|(perform ?task)| where {\it task} is the (possibly parameterised) name of a problem-domain level task that the user wishes to be performed. This request is packaged up as a KQML message and sent to the facilitator, which will forward it to the planning agent. Once an appropriate sequence of agent actions has been planned it is sent back to the console agent which is then responsible for invoking agents to perform these actions for the user. The console agent also keeps track of the current state of the system ({\it i.e.}\ what information is currently recorded and what it represents). \subsection{Using the Architecture} The initial step in using the architecture involves defining a problem domain (which need only be done once for each domain). The user must define a data model defining the entities of interest in the domain. This is done by asserting facts (using the console agent) defining the relations in the domain. It is also necessary to assert facts describing the initial state of the system, {\it i.e.}\ what information is recorded in data files or databases and how it relates to the domain-level data model. In conjunction with an existing ontology defining the terminology of relational data models, this defines an ontology for the user's domain. The various domain-related tasks to be performed are specified by declaring their names and parameters and their precondition and goal states (in terms of the information recorded before and after the task is performed). The user may also provide a specification of possible expansions of each task into an ordered set of subtasks (see Sect.~\ref{planning_issues}). In addition it is assumed that the user has previously developed or acquired agent wrappers for the various general or special-purpose tools used to support work in this domain. These wrappers must be equipped with planning operator style specifications of (a subset of) the possible actions these tools can perform. These specifications describe the actions' preconditions and effects in terms of the domain ontology or standard data storage ontologies as described in Sect.~\ref{ontologies}. When the user requests a task to be performed via the console agent, the planner generates a sequence of agent actions that can satisfy the task specification. These actions are then invoked by the console agent. Note that while these actions are considered to be atomic by the planner they may involve the invocation of an agent-encapsulated tool which may possibly require a series of user interactions. During execution the console agent keeps track of the current state of the system (in terms of the facts asserted and retracted by the actions' planning operators). \section{Required Ontologies} \label{ontologies} %\subsection{States and actions} %\label{state_assertions} %Very simple ontology -- nothing as complicated as what is being %developed by the ARPA/Rome Laboratory Planning Initiative (ARPI) %Planning Ontology Construction Group (POCG) \cite{POCG}. \subsection{File Formats} In large scale ABSI projects, where there are a fixed number of interoperating tools that are specialised for a particular domain, it makes good sense to encapsulate each tool within an agent that speaks a high-level domain-related ontology. In contrast, in desktop utility ABSI there may be agents controlling various general-purpose tools that act at a relatively low data representation level ({\it e.g.}\ by performing manipulations on files). As these tools could be used in various problem domains it would limit their reusability in an ABSI framework if their agent wrappers could only declare their abilities in terms of a single high-level domain. Although for a general purpose tool it would be possible to generate separate agent wrappers corresponding to different domain ontologies, this would clearly be a duplication of effort. Instead, a generic tool should be described at the level at which it operates. Thus a utility that can manipulate text files should be described in terms of an ontology of text files. There are a number of different levels at which the contents of text files are typically viewed, {\it e.g.}\ as a sequence of characters, a sequence of lines or a sequence of records. Figure~\ref{file_ontologies_fig} shows a hierarchy of ontologies being constructed for representing the contents of a text file in a declarative fashion, along with the type of facts used to describe the file contents at each level. \addtolength{\fred}{0.5mm} \addtolength{\fred}{-1em} \addtolength{\fred}{-2\tabcolsep} % - \tabcolsep \begin{figure}[htb] \fbox{ \begin{tabular}{ll} {\bf Conceptual level} & {\bf Fact schema} \\\hline & \\ {\bf Relational} & {\tt (tuple ?pairs ?rel ?dm)}\\ & {\em pairs\/} is the set of attribute-value pairs in relation {\em rel\/} of data\\ & model {\em dm}\\ \multicolumn{1}{@{\hspace{1.5em}}l}{$\Uparrow$} & \\ \multicolumn{2}{@{\hspace{0.5em}}l}{\hbox{ \begin{minipage}[t]{\fred} An ontology relating lists of records to sets of tuples, using facts asserting which relation and data model a file corresponds to and which fields correspond to which attributes. \end{minipage}}} \\ \multicolumn{1}{@{\hspace{1.5em}}l}{$\Downarrow$} & \\ & \\ {\bf Records and fields}& {\tt (field ?i ?n ?f ?v)} \\ & Field {\em i\/} of record {\em n\/} in file {\em f\/} has value {\em v\/}\\ \multicolumn{1}{@{\hspace{1.5em}}l}{$\Uparrow$} & \\ \multicolumn{2}{@{\hspace{0.5em}}l}{\hbox{ \begin{minipage}[t]{\fred} An ontology for string parsing, based on facts describing the record format. \end{minipage}}} \\ \multicolumn{1}{@{\hspace{1.5em}}l}{$\Downarrow$} & \\ & \\ {\bf Seq.\ of lines} & {\tt (line ?n ?f ?s)} \\ & Line {\em n\/} of file {\em f\/} is the string {\em s}\\ \multicolumn{1}{@{\hspace{1.5em}}l}{$\Uparrow$} & \\ \multicolumn{2}{@{\hspace{0.5em}}l}{\hbox{ \begin{minipage}[t]{\fred} An ontology describing newline terminated strings. \end{minipage}}} \\ \multicolumn{1}{@{\hspace{1.5em}}l}{$\Downarrow$} & \\ & \\ {\bf Seq.\ of chars} & {\tt (char ?n ?f ?c)}\\ & Character {\em n\/} in file {\em f\/} is {\em c\/}\\ \end{tabular} } \caption{A hierarchy of text file ontologies and how they relate facts at different levels of abstraction } \label{file_ontologies_fig} \end{figure} \addtolength{\fred}{1em} \addtolength{\fred}{2\tabcolsep} % - \tabcolsep To relate the different viewpoints the ontologies also need to describe how to translate information between the different representational levels. For instance, the information that the file named ``students.dat'' is a text file with three string-valued fields delimited by commas might be represented by the following fact: \begin{verbatim} (file-format "students.dat" (delim #\, (list-of string string string))) \end{verbatim} This predicate would be defined in an ontology by a formula stating how facts about records and fields can be inferred from facts about lines in files. For instance, the fact \begin{verbatim} (line 10 "students.dat" "9601234,Joe Smith,A0100001") \end{verbatim} would allow the following three facts to be deduced: \begin{verbatim} (field 1 10 "students.dat" "9601234") (field 2 10 "students.dat" "Joe Smith") (field 3 10 "students.dat" "A0100001") \end{verbatim} Thus the \verb|file-format| fact above provides the information needed to translate between the line-based view of a file and the record-based view. Similarly, facts of the following form could be used to link the record-based and the relational views of a file: \begin{verbatim} (file-represents-relation ?file ?rel ?data-model ?att-list ?state) \end{verbatim} As tuples in relations are {\em sets\/} of attribute-value pairs, whereas the fields in a record are ordered, the argument {\tt ?att-list} is required to specify the order in which the attributes appear in the file\,---\,this is a list which is some permutation of the attributes of the relation {\tt ?rel}. \label{state_variables} The explicit mention of a state in this fact is necessary because in the type of tool use supported by this architecture, domain-level tasks may not be completed in a single session and there may be information stored in temporary files that are more up-to-date than other information sources. For example, in the university course administration domain, the user may run a marking utility to mark student assignments and then go home for the day before updating the course database with the marks recorded in the file that was output by the marking utility. At this point the database and the text file contain information relating to different stages of the high level ``mark assignment'' task: the database does not reflect the fact that the latest assignment has been marked, whereas the text file does. The final argument in the fact above specifies which (possibly earlier) state in the plan the information in the file represents. It will be an expression of the form $({\tt do}$ $a$ $s)$ representing the state resulting from performing action $a$ in a state $s$ (which may itself be represented by an expression of this form). It is important to note that the ontologies described above are only {\em specifications\/} of standard terminologies that may be used by agents. While some agents may perform inference using the formulae in an ontology, all that is {\em required\/} of an agent is that its use of the terminology in an ontology be consistent with the ontology's logical theory. Defining ontologies describing different conceptual views of files, and how to translate between these levels of abstraction, does not imply that all file processing will be performed using an inference system. In practice, these ontologies\,---\,particularly at the lower levels\,---\,might be implemented by `procedural attachment', so that telling a file manager agent a \verb|file-format| fact such as the one above would result in that agent reading and parsing the file and sending a stream of {\tt field} facts to all interested agents. \subsection{Data Models and Databases} \label{rel_data_ont} In any ABSI project there needs to be at least one high-level ontology describing the problem domain (in some cases there may be several due to different agents having different views of the domain). In the example domain described above, the problem area involves student details, assignments and marks. An ontology for this domain can be created in various ways, {\it e.g.}\ an object-oriented model could be based on the Stanford ontology library's frame ontology \cite{KSL-Ontology-Server}. However, like all applications involving a relational database, a domain model already exists: the relational data model developed for the database application. This could be easily described as an ontology if a standard ontology of relational data models were available. Such an ontology would define the concepts of base relations and their attributes and attribute domains, as well as a way of naming relations derived from the base relations. The discussion in this paper assumes the existence of such an ontology (which is currently under development) with relations described using the relational algebra, {\it i.e.}\ relations can be built from the base relations using operations such as select, join and project. Users will define the relational data models for their problem domains by asserting facts naming the model and describing its base relations. The relational data model ontology will also allow the user to declare semantic information such as candidate keys, foreign keys, foreign key rules and default attribute values, thus supporting agents that can update derived relations (``view updates''). For the course administration example, using a domain ontology based on a relational data model, a tuple in a base relation STUDENT (recording student ID numbers, names and Novell NetWare IDs) could be represented by the following KIF fact: \begin{verbatim} (tuple (setof (stuid "9601234") (stuname "Joe Smith") (nw_id "A0100001")) student info202-dm) \end{verbatim} where {\tt student} names the relation and {\tt info202-dm} names the particular relational data model (there could be more than one problem domain, and hence more than one data model in use at a time). The relational data model ontology discussed above describes a conceptual model of a domain, whereas the text file ontologies discussed in the previous section describe the physical representations of data. Just as the text file ontologies refer to files, we need an ontology in which there is a concept of a database (as opposed to the conceptual model implemented by it). A database is a separate concept from a relational data model: a database could represent information from several relational models; conversely the information pertaining to a single data model could be split (or duplicated) across several databases. Therefore it is necessary to have an ontology for actual databases, defining (amongst others) the predicate: \begin{verbatim} (database-matches-datamodel ?database ?data-model) \end{verbatim} This declares that the tables in the database match the relational data model specified (including any integrity checks implied by the foreign key information in the data model). This predicate can be implemented by procedural attachment to the database query language. \section{Planning Issues} \label{planning_issues} \subsection{Hierarchical Task Network Planning} The nature of desktop agent interoperation imposes a number of demands on the planner. The aim of this architecture is to remove as much manual coordination of tool use as possible from the user. For this multi-agent system to be as autonomous as possible, facilities need to be provided to assist the user in providing as much information about the problem domain as possible. In particular, the user may have common patterns of tool use that could improve the performance of the planner if it could make use of them. Such a facility is provided by hierarchical task-network (HTN) planners such as UMCP \cite{UMCP}. With this type of planner, the user can provide the planner with declarations describing possible decompositions of tasks into ordered networks of subtasks. The basic planning step involves expanding a task into one of its possible networks of subtasks and then attempting to resolve any unwanted interactions between steps in the plan that were introduced by this expansion. A task expansion can also include subtasks of the form ${\mit achieve}(g)$ where $g$ is a goal. By providing methods for expanding `achieve' tasks, the user can also provide the planner with (domain-specific) goal-directed planning capabilities. \subsection{Ontologies and Abstraction} An important characteristic of desktop utility ABSI is the mix of domain-specific and general-purpose tools. To use the information output by general-purpose tools as input to domain-specific tools, it is necessary to store facts stating how these low-level representations relate to the problem domain's data model. For example, Fig.~\ref{action_spec} shows the specification for an action that can be performed by a database-encapsulating agent in the university course administration domain: to update a student record database from a specially formatted text file. The action specification contains some pre- and post-conditions that are inherently related to the problem domain (university course administration). Other conditions are expressed using the lower level ontologies of file formats and databases. The planner may need to switch back and forth between these different levels of description as the following example shows. Before the {\tt add-marks} action can be performed a marking utility must be run to allow the tutor to systematically mark each student's electronically submitted programming assignment and create a file containing the marks. When encapsulated by an agent, the postconditions for this ``mark assignments'' action are as follows: \begin{verbatim} (file ?f (delimited #\, (listof string string string number))) (file-represents-relation ?f (join STUDENT (project (select ASSESS (= cmptid ?ass)) (stuid mark))) info202-dm (stuid stuname nw_id mark) (do (mark ?ass ?f) ?state)) \end{verbatim} The format of the output file, and the relation it represents differ from that required by the {\tt add-marks} action. The planner must find a way to achieve the preconditions of the {\tt add-marks} action starting from the postconditions shown above. This is a text file manipulation process that takes the file produced as a result of running the marking program and converts it into a format suitable for adding information to the ASSESS table in the database. This can be performed by two operations at the text file level: deleting two fields of the file and then adding a new field containing the assignment name in each row. Figure~\ref{step3_fig} shows how these two file-level operations can be used to achieve the preconditions of the {\tt add-marks} action starting with the postconditions of the {\tt mark} action (the state expressions are not given in full). \addtolength{\fred}{-0.5mm} \begin{figure}[htbp] \fbox{ \parbox{\fred}{ \rule{\fred}{0pt} \begin{tabbing} {\tt\ (file ?f }\\ {\tt\ \ \ \ (delimited \#\char92, (list-of string string string number))) }\\ {\tt\ (file-represents-relation ?f }\\ {\tt\ \ \ \ (join STUDENT (project (select ASSESS (= cmptid ?ass)) }\\ {\tt\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (stuid mark))) }\\ {\tt\ \ \ \ info202-dm }\\ {\tt\ \ \ \ (stuid stuname nw\char95 id mark) }\\ {\tt\ \ \ \ }{\it state1}{\tt )} \end{tabbing} }} \vspace{1.5\baselineskip} {\Huge\quad\quad $\Downarrow$\quad} Delete columns 2 and 3 from file {\tt ?f} \vspace{1.5\baselineskip} \fbox{ \parbox{\fred}{ \rule{\fred}{0pt} \begin{tabbing} {\tt\ (file ?f (delimited \#\char92, (list-of string number))) }\\ {\tt\ (file-represents-relation ?f }\\ {\tt\ \ \ \ (project (select ASSESS (= cmptid ?ass)) }\\ {\tt\ \ \ \ \ \ \ \ \ \ \ \ \ (stuid mark)) }\\ {\tt\ \ \ \ info202-dm }\\ {\tt\ \ \ \ (stuid mark) }\\ {\tt\ \ \ \ }{\it state2}{\tt )} \end{tabbing} }} \vspace{1.5\baselineskip} {\Huge\quad\quad$\Downarrow$\quad} Insert new column 2 with value of {\tt ?ass} in every row \vspace{1.5\baselineskip} \fbox{ \parbox{\fred}{ \rule{\fred}{0pt} \begin{tabbing} {\tt\ (file ?f (delimited \#\char92, (list-of string string number))) }\\ {\tt\ (file-represents-relation ?f }\\ {\tt\ \ \ \ (select ASSESS (= cmptid ?ass))}\\ {\tt\ \ \ \ info202-dm }\\ {\tt\ \ \ \ (stuid cmptid mark)}\\ {\tt\ \ \ \ }{\it state3}{\tt )} \end{tabbing} }} \caption{The file manipulation process} \label{step3_fig} \end{figure} To infer that this sequence of file manipulations can be used as a link in a plan involving higher level concepts requires the planner to drop down a level in the hierarchy of ontologies, generate a subplan at that level and then produce a specification of that subplan at the higher conceptual level. This translation process could be defined as a HTN planner `task'; however, it would also be useful if the planner could solve this problem without such presupplied help from the user. Existing hierarchical planning techniques may be applicable to this problem. This is an issue requiring further investigation. \subsection{Incorporating Run-Time Information} \label{planning_and_execution} In some domains, the planning agent may not be able to expand a task in a plan network until it has information that may only be available at run time. For example, in the university course administration domain, the task of marking every student's submitted work for a given assignment can be broken into two subtasks: first to invoke the marking utility for some subset of the students and then (sometime later) to mark the assignments for the rest of the students (a compound task to be expanded further). The subset of students whose assigments are marked during the first subtask can not be known at run time\,---\,it depends on how much time the tutor has. The expansion of the second subtask will also depend on this information. To address situations such as this, the planner's action description language must have a formalism for representing information that will become available during the execution of a plan. The planner must also be capable of interleaving planning and execution, and instantiating the run-time information. These capabilities have been provided in previous planning research by allowing special ``run-time variables'' to appear in action preconditions and effects \cite{ambros-ingerson} and this work has been extended to address other issues related to planning in the absence of complete information about the world \cite{golden,knoblock95}. The formalism of ``provisions'' \cite{williamson} was introduced to generalise the role that parameter instantiation and run-time variables play in the flow of information between actions in a plan. This is also the only work in this area to address HTN planning. The notion of a provision is powerful but seems unintuitive as a primitive concept in a planning formalism. There is much scope for further research in this area to clarify how information flow in plans can best be modelled. \subsection{Planning to Communicate} Planners traditionally model actions by the changes they make to a world state. In the ABSI framework, agents communicate by sending messages in KQML to each other and these communications do not directly change the state of the world. However, if the world model includes facts describing the planner's knowledge of the knowledge of other agents appearing in the plan, planning operators for different types of KQML messages can be specified in terms of the changes they make to these facts. This approach would require the planner to include at least some of the inference capabilities of epistemic logic and may introduce needless complexity. An alternative approach is for the planner to specify agent actions and generate plans under the hypothesis that a global shared knowledge base is available to all agents. The resulting plan could then be transformed into one including communication acts, in the same way that a program for a shared-memory parallel process can be translated into a program for a message-passing architecture. These two approaches for planning to communicate will be investigated and compared in future work. \section{Related Work} As discussed earlier, this work builds upon the ABSI federation architecture \cite{Genesereth,KSL-Ontology-Server}. SRI's Open Agent Architecture \cite{Cohen} allows agent-encapsulated desktop tools to interoperate in a distributed heterogeneous environment. Agents communicate via a distributed blackboard. User interface considerations are a focus of this work, while ontological issues and planning for high-level tasks are not addressed. The SIMS architecture \cite{SIMS} is specialised for agents encapsulating distributed information sources. The agents are relatively complex, containing planning and learning components, and use domain and information source models developed using specialised knowledge representation tools. Softbots \cite{Etzioni} are complex stand-alone agents that can invoke various tools on behalf of the user. However, there is no facility for users to extend or alter a softbot's functionality. %\section{Further Work} %Implementation, data model, database and spreadsheet (refs) ontologies. \section{Conclusion} This paper has presented an agent-based architecture for a type of software interoperability problem (desktop utility ABSI) different from the large scale ABSI projects discussed in the literature. In particular the use of a planning agent to automate the selection of actions to jointly achieve domain tasks has been discussed. It has been suggested that hierarchical task-network planning techniques be used so the user can provide guidance on how different tools can be combined for particular tasks. Combining the use of special-purpose tools with general-purpose utilities means that at times during the performance of a task, information corresponding to different stages of the task may be stored in different formats and the implications of this on the planner has been discussed. Standard ontologies for data formats are required to facilitate the use of general-purpose tools with this architecture and the design of database and text file format ontologies have been outlined. A prototype implementation \cite{Our-Web-page} of the architecture has been developed using the Java Agent Template \cite{JAT} to build the console agent, the facilitator (with help from Amzi! Prolog and its Java interface \cite{Amzi}) and KQML-speaking agent ``transducers'' for tools running under Windows NT and Unix. The Common Lisp HTN planner UMCP \cite{UMCP} is currently being used with a KQML interface provided by the KAPI software \cite{KAPI}. Currently work is continuing on the implementation of this architecture and example software agents to encapsulate the tools of the course administration domain. Further work involves elaborating the planning requirements for this architecture (as outlined in Sect.~\ref{planning_issues}) and the ontologies discussed above. Also, ontologies for other common tools such as spreadsheets will be required (\cite{Spreadsheet} may provide a useful starting point). A user interface will be developed to help non-sophisticated users compose their problem domain description, the specifications of the tasks to be performed in that domain and create agent wrappers for their existing software tools. At present our research assumes that all agents share the same ontologies for the domain description and the data formats they operate on. This work should eventually address the problem of interoperation between agents with different ontologies for the same domain \cite{SIMS,wiederhold}. \section*{Acknowledgements} This research is supported by an Otago Research Grant. Thanks to Aurora Diaz for her ongoing work in implementing this architecture. \bibliography{workshop} \end{document}