Trip Report - Aug/Sep 1994

Trip Report - Europe, August and September 1994


1 Lausanne Trip Notes

This was the AI in Design '94 conference located in Lausanne, Switzerland at the Swiss Federal Institute of Technology (EPFL). I gave the keynote at the workshop on Conflict Management on 13 August. I have not only the proceedings but notes on the papers for anyone interested in the details. Ian Smith < >, convener of the workshop and head of the AI Group at the EPFL, is editing a special edition of AIEDAM. and has invited me to contribute my workshop paper.

I also participated in the workshop on Design Rationale. And I gave a paper at the main conference on 18 August. There is interest in using my Redux system in Lausanne. One of Ian Smith's students, Esther Gelle <> is working with a civil engineering student, Sylvie Boulanger <>, on bridge design. I spent the afternoon with them one day discussing how constraint propagation could be done in Redux or consistent with Redux based on the bridge design constraints they showed me. This turns out to fit with work being done at the University of Kaiserslautern. In any case, Esther Gelle would like a copy of the Redux' server with which to experiment. I also spent time with other students discussing constraint satisfaction in general. Several of these students had already read my papers for the last three years.

There is a group from the university of Amsterdam that would also like to collaborate with me on using Redux to manage design rationales in combination with their design tool for developing banking processes. This group consists of Jan Treur <>,
Frances Brazier <>, and Pieter van Langen <>. Jan and Frances are professors and Pieter is a student. They are proceeding to read my papers and would like to work out a plan of collaboration, perhaps involving exchanging personnel.

I have a copy of the workshops and the conference proceedings. I have more detailed notes on the Conflict Management workshop papers as well as informal notes on extensions to Redux inspired by various papers.

2 Kaiserslautern Trip Notes

I arrived at the University of Kaiserslautern on Monday 22 August, gave a talk on Thursday 25 Aug to a group of about 40 people from the Computer Science department here.

While here this week, I consulted with various projects in two main groups. The first is the AG Künstliche Intelligenz : the AI group within the CS department of the university. The second is the Kaiserslautern branch of the DFKI: the German National AI Institute. Both are located in the same building on the campus and are both led by Prof. Dr. rer. nat. Michael M. Richter

2.1 AG Künstliche Intelligenz

Software Engineering Project They have a nice Smalltalk implementation with windows for different agents allowing them to accept tasks and monitor progress. (Lots of windows that could be displayed in gifs on WWW.) They recommend Smalltalk as an easy way to implement H/I.

They also have an implementation that allows a display of TMS dependencies directly. The trick is to use the static dependency structure of Redux. May be able to carry out idea for Next-Link decision graph. I have hard copy of the latter as well as an extended dependency graph and a draft paper.

We worked on understanding, correcting, and renaming the extended dependencies. I have the notes for use at Stanford. We also worked on a problem with the current dependencies. It turns out they were representing inputs to tasks. What they need instead is inputs to decisions, because different methods applied to the same task may have different inputs. Once I understood their object model, this was easy since I have already implemented dependent assignments as decision inputs and we are using these in Next-Link.

2.2 City Planning Project (Der Intelligente Bebauungsplan)

Dr. Richter has various students working on general idea of a Design Manager. This is an elaboration on the Next-Link architecture. DM not only resolves global constraints, but perhaps changes all of the decisions involved. An example is wing + fusalage + motor violates weight requirements. Rejection of each should be treated as single constraint violation. But also may have a sensitivity analysis. If the fusalage should be changed more rather than the wing, should make rejection a metadecision with the rationale of the analysis. Also look for indivual agent landmarks. If an agent's design is not near a landmark, the DM is free to change the design to resolve a global problem. If near a landmark, must look at detail. General problem is to have enough expertise/experience at the right level of abstraction to know what is important and who to change by how much. Ultimately, perhaps the AG will produce DM technology we can use in Next-Link.

2.3 Constraint Propagation versus DDB

There was much discussion with Jürgen Paulokat < > on his dissertation project: what can be done to integrate a ``black-box'' continuous infinite constraint propagation system with Redux, which is based on dependency-directed backtracking (DDB)? The problem is that only chronological history is preserved in constraint propagation. So a decision produces a subgoal of a special kind: to assign a variable a value from a domain. The initial domain is handed off to the Constraint Propagation System. If the CPS only performs arc consistency, inconsistencies may be generated as decisions are made.

So subsequent similar decisions may activate constraints over the variables. This results in reductions of the intervals for the numbers in the domain. However, which other decisions/variables are responsible for this reduction? Right now, this information is not available. In the original configuration system, the CSP simply puts or removes a premise justification under the rejection node. That is, rejection is not cached by Redux, but rather recomputed by the CSP.

So can a sufficiently small set of decisions/assignments be isolated to construct a partial justification - one that does not omit any necessary decision and does not contain too many extraneous ones?

Idea 1: Certainly the set of decisions made since the original one and before the reduction (requested by the problem solver) includes the responsible ones. Idea 2: This set can be further pruned by eliminating decisions/assignments not in the domain of the constraint violated. Is there any further pruning that can be achieved?

This is partial DDB. What caching/messages by the CPS would make this set more specific? How to handle that the rejection of a decision from this set may not resolve the constraint violation? (I don't think the latter is hard.) Jürgen will visit the CDR in October and work with me further on this dissertation topic. But then, he will also contrast the nature of constraint propagation with the partial propagation available in Redux, show the conceptual gaps, and evaluate the complexity of the alternatives for generating rejection justifications.

Jürgen's work coincides with the needs of Esther Gelle who is working the application of bridge design in civil engineering - she would like to use Redux but needs continuous variable constraint propagation. I have put Esther and Jürgen in touch with one another and they have started to exchange interests. Jürgen will visit me for two weeks in October of this year and give a talk on his results.

2.4 DFKI - Deutsches Forschungszentrum für Künstliche Intelligenz

Holger Wache <> is working on TMS-based constraint propagation. This is based on a new form of TMS. The report is forthcoming. I have hard-copy of notes from discussion with Holger and Jürgen. This sort of system can tell Redux' the reasons for rejection of values of the domain of a variable. This is a discrete propositional system. May be useful in Next-Link as a default CPS. The original paper (in German) and the system in LISP is forthcoming.

Bernd Bachmann <> is working on semantic unification techniques for knowledge sharing using mode-theoretic techniques used in mathematical theorem proving for the unification of theories. He may use a suggestion of mine for supporting the user in unifying heterogeneous knowledge-system ontologies. He will try to have a paper to submit to IJCAI by January. He will visit Stanford on December 5th and 6th.

Donald Steiner < > heads the Cooperative Man-Machine Architectures (CoMMA) project. This includes three subprojects: MAPS, Plat, CoMoves, and is a large project between Siemens and the DFKI at both Kaiserslautern and Saarbrücken. The general topic of the project is distributed problem solving with multi-agents in the real world. One current application is truck scheduling. A future application is a hand-held personal travel agent. I have a paper that describes the general planning approach, which involves both planning and reactive approaches. There is also a set of cooperation performatives. Of special note is the goal to attempt to develop ways in which the set of performatives can be dynamically enlarged by the agents. I noted to Donald that there is a potential synergy between the cooperation performatives of this project and the task delegation performative of Maurer's software engineering project.

I am invited back in March (all expenses paid) to give an invited talk at a German national conference on knowledge-based systems: XPS-95. This is equivalent to a ACM/IEEE AI conference such as CAIA. The conference is one day of workshops and two of sessions. There are two invited speakers; one from industry and the other from research. I am the latter. The dates are 1-3 March. All expenses will be paid.

3 Vienna Trip Notes

Traveled all day Tuesday 30 August to Vienna where I gave a talk on Wednesday 31 August to a combination of the Vienna Technical University and the Austrian Research Institute for AI (OFAI) at the invitation of Robert Trappl < >, Director of OFAI. It was well-attended (>15 people) given that it was in between semesters. There were good questions and I had a long visit with Dr. Trappl afterwards. He liked the Next-Link/Redux work very much and offered me a guest professorship on the strength of it. We also discussed common problems with funding and technology transfer.

Thursday, 1 September, I spent about seven hours discussing and citiquing an approach to constraint satisfaction done here and reported in a paper draft, titled "Solving the Dynamic Shift-Scheduling Problem with a `Projections First Strategy'" that I have been reviewing while traveling. This is a joint paper by Prof. Johannes Gärtner < > of the TU and Dr. Silvia Miksch < > of the OFAI. While I had a large number of specific citicisms and suggestions, I thought the paper had enough insights to merit more work.

The paper has a domain of application: generating annual worker shift schedules for large companies. The essential idea implicit in the work, which I made explicit in discussions, is that the paper discribes one way in which humans can work with an algorithmic process to greatly simplify an NP-hard problem. The paper describes at what points in the process, and how, the human should intervene to simplify the problem.

I also found in this paper other ideas that have general applicability. One is the idea of using metavariables in constraints that can be expressed as relations over the instances of types or sets. Another is the idea of finding aggragations of units of domain variables that can be used to make part of the problem solving repetitive. A really nice feature of the problem solving process described is that though it only allows chronological backtracking, the decision process moves through levels of abstraction rather than at the same level. So one backtracks to the most specific level of abstraction for which the partial solution is consistent with the constraints or new conditions.

The process currently has no provision for Redux-like control of thrashing. There is interest in determining whether a Redux' server could be useful. My preliminary thought is that it could because the user process decisions can be expressed at a fairly coarse level of granularity: e.g., choose "SHIFT" as a metavariable, use "180" as the minimum "shift-group" size. Johannes and Silvia plan to rewrite the paper using my suggestions and investigate this use of Redux with me later in the year.

At the Vienna Technical University, I also visited with Markus Stumpner < > and briefly discussed his work. I have the following papers from him:

Finally, I recommend trying out the OFAI Library Services on the web.

4 Berlin Trip Notes

From Vienna, I took the overnight train to Berlin where I visited and gave talks at two places.

4.1 Humbolt University

I visited the Information Science department at the Humbolt (Institut fuer Wirtschaftsinformatik Humboldt-Universität zu Berlin), which is being completely overhauled after the fall of East Germany. My host was the department chair, Prof. Dr. Oliver Guenther < >. I gave a talk and then attended project reviews of the current projects there. My notes have been lost in transit but I can remember that the major project there is to create a suite of services that can be accessed over the Internet to solve problems. While the domain of these services are technical business problems (such as statistical analysis), it can be seen that this work has much in common with Next-Link. Oliver and I will stay in touch (he will visit early next year) and as this work progresses, we will explore our approaches to this common problem of Internet-based services.

The following paper is available in German: Wirtschaftlichkeit von Workflowsystemen - Ein Ansatz zur Modellierung von Kontexainderungen in Gesheftsprozessen.

4.2 DaimlerBenz

My host was Dr. Kurt Sundermeyer <>, director of the AI group at the Dailer-Benz research group in Berlin (Forschung und Technik Berlin). His position was unclear because he was in the process of being promoted. to the position held by Dr. E. W. Jüngst, whom I also met. While these relativel technical management positions were changing, Dr. Sundermeyer was kind enough to give me the over-all organization chart of information research at D-B. One of the interesting features of this chart is Dr. Barth, whom I have previously met in 1986 when he assumed the technical directorship of the DFKI from which he recently resigned.

In addition to giving a talk, I review several projects. A major project is the MDS-Projekt on model-based diagnosis. This project is not particularly relevant to Next-Link and I will only say that it is well done and I have the names of the researchers if anyone is interested.

I spent quite a bit of time with Afsaneh Haddadi <> who is doing her Ph.D. thesis on multi-agent systems. We had some interesting discussions on the nature of mult-agent systems versus cooperative problem-solving that helped me better position the Next-Link work, but there was little technical contribution since Afsaneh's work concentrates on agent beliefs, which seem to be unnecessary in Next-Link.

However, Afsaneh's work is a small part of a larger project called COSY. I have a copy of an overview paper called COSY: towards Agent Oriented Techniques. In this general architecture for cooperating agents, agents are characterized by the quadruple:

These map to an architecture consisting of sensors, intention, cognition, actuators, and communication. Cognition is further composed of a knowledge base, an inference mechanism, and mechanisms for executing scripts. It is interesting that reception of messages from other agents is handled directly by the inference mechanism while sending of messages is done by the script execution mechanism. The latter is directed by the inference mechanism, but the important point is that there is presumed to be some script for each outgoing message, but not necessarially for every incoming message.

This is important because this overview paper otherwise explicitly notes the importance of using generic cooperation protocols based on domain-independent speech acts. This is a common idea in AI agents now. The performatives of COSY (Informaing, Querying, Commanding, and Offering) are impoverished wrt KQML, though more performatives are planned. But it is interesting that the architecture does not seem to expect that all agents will use this protocol and that the inference mechanism will need to decipher messages. This is likely an incorrect interpretation as I did not ask this question at the time.

The really important comparison to Next-Link is that the COSY protocol is similar to KQML's in that it only provides a substructure for the service-level protocol of Redux' and other Next-Link generic services.

I also spent time reviewing the configuration software that Helmuth Ritzer <> essentially brought with him when he completed his masters work at the U. of Kaiserslautern. This work is interesting to me because it is based upon the Redux model of design. However, while Helmuth is keeping it alive at Daimler, it remains to be seen whether it will find its way into any of the mainstream projects.

This chance is not vanishingly small and there was some serious talk by Dr. Sundermeyer of me visiting Berlin to collaborate on Redux-oriented projects in the future. We had a technical discussion about the COSMOS configuration shell that has been used in D-B to configure Programmable Logic Controllers. We discussed how the resource model used in COSMOS maps into the Redux decision model. A copy of a paper published in the 1991 IEEE Conf. on AI Applications is available: A Resource-Based Paradigm for the Configuring of Technical Systems from Modular Components.

Finally, I visited briefly with Rudolf Müller about his work on scheduling. However, his approach is completely that of traditional operations research and so this work is of little interest to our group. However, I have several of his papers if anyone is interested.

The most important fact I learned while visiting D-B was the establishment of a Palo Alto DB research office with the purpose of tracking research relevant to D-B. The head of this office is Paul Mehring <> with whom we need to meet in the near future (and have since the trip).

German Research

In general, German research in computer science is starting to feel the pressure of less government funding and the need to produce applicable technology. AI in particular is starting to feel the pinch, just as it did here in the states in the late '80s. A review in German of the AI work at the DFKI and other places by Arthur D. Little and rebuttals by Prof. Wahlster and others are available as published in the KI in Deutschland magazine.

Charles J. Petrie
Stanford Center for Design Research