Research Activities

The research within TOSCA is mainly concerned with theoretical aspects on various types of temporal systems, currently within the following topic areas.

Algorithmics of Action Planning

Since 1989, we have worked on identifying restrictions that make action planning computationally tractable, as well as studying the sources of intractability when such restrictions are not present. To the best of our knowledge, we presented in 1990 the first restrictions in the literature allowing for polynomial-time planning (defining the tractable SAS-PUBS class), along with a polynomial-time algorithm for this class. Taking a bottom-up approach from the SAS-PUBS class we have then incrementally removed and replaced restrictions to get larger classes of tractable planning problems. All since the beginning, this research has been carried out in close cooperation with the division of automatic control at the department of electrical engineering, Linköping University, and our primary target application area is problems in sequential control (within automatic control).

For a recent summary of our results, see

Bäckström, C. (1995), Five Years of Tractable Planning
In Ghallab, M. and Milani, A., editors, New Directions in AI Planning: EWSP'95---3rd European Workshop on Planning, Frontiers in AI and Applications, Assisi, Italy. IOS Press.
Invited paper.

Temporal Constraint Reasoning

Recent results on algorithmics of temporal constraint reasoning to appear here soon.

Diagnosis of Dynamical Systems

TOSCA participates in ISIS---a cross-disciplinary research programme financed by NUTEK, Linköping University and the Industry, with the purpose of integrating automatic control and information technology. Within ISIS we collaborate with the divisions of vehicular systems and automatic control at the department of electrical engineering, Linköping University, Sweden to combine methods from automatic control and computer science for fault detection and diagnosis in dynamical systems. Automatic control offers methods for detecting faults in continuous systems (eg. system identification, residual generators) and computer science offers methods for reasoning about faults and events in discrete systems (eg. temporal reasoning, model-based diagnosis). However, diagnosis of dynamical systems probably requires that we combine methods for reasoning about continuous and discrete systems, which is the purpose of our project. To start with, we concentrate on diagnosing car engines, which provides rich opportunities for practical experiments in the engine laboratory at vehicular systems. However, we aim at developing general methods for a broader range of applications.

Modelling and Verification of Hybrid Systems

The work in this area concerns modelling and verification of reactive systems interacting with a physical environment. Correctness in such an embedded system entails that the system has certain safety properties, and that its reactions to developments in the outside world are generated at the right time.

Mathematical models for such systems can be derived using two different approaches. In the first approach, discrete models of the environemnt are derived from the physical models and composed with the models of the reactive system for the purpose of analysis. Appropriate semantics for the discrete languages (e.g. Esterel, statecharts, rule-based languages) and the derivation of the environment models are the main areas subject to study within this approach.

Although the above approach suffices for analysis of safety properties in certain applications, proofs of timeliness requirements require explicit representation of the "rate of change" in the system and its environment. In the hybrid approach, we derive models in which both the continuous and the discrete elements are represented explicitely. In this area our main concern is to generate hybrid mathematical models from engineering languages and physical models systematically. Also, we study the translation of the hybrid models generated as above to models where formal analysis is facilitated. Our interests span both deductive proof techniques and algorithmic methods.

These problems are closely related to the problems of requirements capture and formal languages for design and requirements specifications in the context of software engineering.

Next: Graduate-student Positions (Doktorandtjänster) Up: No Title Previous: Members

---

---

Christer Backstrom
torsdag, 30 oktober 1997 kl 13:08:54 MET