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 <gelle@lia.di.epfl.ch> is working with a civil engineering student, Sylvie Boulanger <sylvie.boulanger@icom.dgc.epfl.ch>, 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 <treur@cs.vu.nl>,
Frances Brazier <frances@cs.vu.nl>, and Pieter van Langen
<langen@cs.vu.nl>. 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.
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
<richter@informatik.uni-kl.de>.
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.
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.
Bernd Bachmann <bachmann@dfki.uni-kl.de> 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 < steiner@dfki.uni-kl.de > 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.
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 < jgaertner@email.tuwien.ac.at > of the TU and Dr. Silvia Miksch < silvia@ai.univie.ac.at > 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 < mst@vexpert.dbai.tuwien.ac.at > and briefly discussed his work. I have the following papers from him:
Finally, I recommend trying out the OFAI Library Services on the web.
The following paper is available in German: Wirtschaftlichkeit von Workflowsystemen - Ein Ansatz zur Modellierung von Kontexainderungen in Gesheftsprozessen.
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 <afsaneh@DBresearch-berlin.de> 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:
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 <ritzer@DBresearch-berlin.de> 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 <mehring@rtna.daimlerbenz.com> with whom we need to meet in the near future (and have since the trip).
