Description of Research Areas Logic Programming Systems Parallel Logic Programming Systems

L
ogic Programming Systems

A number of Abstract Machines and Architectures has been designed to implement several resolution algorithms in order to exploit both OR and AND parallelism of logic programs. Our current research is concentrated towards a distributed memory architecture, named OASys, in which the processing elements performing the OR-parallel computation, posess their own address space while other simple processing units are assigned with AND-parallel computation and share the same address space. OASys execution is based on distributed scheduling which allows either environment copying or recomputation of paths depending on an estimated cost before the distribution of work. Currently a prototype implementation is in progress, based on a network of workstations.

Our main objective is to extend the basic Resolution Principle of logic programs in order to exploit both OR and AND parallelism. We have been investigating a number of resolution algorithms for logic programs which would facilitate the use of distributed computer architectures. In order to combine these two types of parallelism, we consider each alternative path of the resolution tree as a totally independent computation. This gives rise to OR-parallel execution. In addition, the conjunction of subgoals of each deterministic path can be resolved in parallel, giving in effect AND-parallelism.

Recent work also describes the separation of logic programs from the control over them. We have been testing a number of search algorithms used in Artificial Intelligence in order to provide a meta-language in which someone could express guidance of search as a separate programming activity. We adopt a notation in form of meta-directives which would give the user all the necessary features to express search by only changing the meta-program while keeping the same underlying logic program.

The goal of the research in constraint logic programming is to improve the efficiency of logic programming systems at combinatorial problems, by combining parallel execution of logic programs and supporting constraints in logic. The focus of the research is on extending logic programming to support constraints and parallelism at the same time. Various applications are also developed to study specific requirements from the CLP system for various different problems, such as:

• 
  timetabling
  
• 
  workforce scheduling
  
• 
  production line optimization
  
• 
  traffic lights control
  

K
nowledge Base Systems

The research resulted in an active object-oriented knowledge base system, called DEVICE, that efficiently integrates active or event-driven (ECA), production and deductive rules into a single Object-Oriented Database system.

More specifically, the active OODB EXACT has been extended with production and deductive rules using the DEVICE compilation method which compiles the declarative condition of a high-level rule into a network of complex events that incrementally matches the condition at run-time. The network is similar to the RETE discrimination network, appart from two optimizations for saving space: the event object re-usability, when multiple rules have common conditions, and the virtual alpha node optimization, which does not store tokens in the network when they originate from a non-selective condition.

The last event in the event network acts as a trigger of an ECA rule that hosts the original high-level rule. The action of the ECA rule depends on the type of the high-level rule. Production rules' actions are procedural specifications of the host database language, while deductive rules' conclusions are more cumbersome. When the condition of a deductive rule is confirmed the action is to insert in the database the object described in the conclusion (derived data). On the other hand, the falsification of a previously true condition denotes that the derived object should not be in the database, therefore an anti-action deletes the object.

The DEVICE system has been implemented on the EXACT system, which is an extensible active OODB, that is itself an extension of ADAM OODB, which is built in Prolog. Currently DEVICE runs on ECLiPSe and SICStus Prolog. It is ported to a parallel/distributed version of Prolog, called CS-Prolog, in order to be executed in parallel (see below). Furthermore, DEVICE is being used as an expert system shell for developing a distributed expert system for managing a national WAN (ExperNet).

Furthermore, we explore ways to enhance the performance of active OODB systems through efficient complex event handling and/or use of parallelism in event detection and condition evaluation. Consequently, deductive and production rules will also be executed efficiently on top. All these facilities will be integrated in the PRACTIC parallel OODB system.

Research is focused on the development of a parallel knowledge base system. So far, a parallel active Object-Oriented Database (OODB) model, named PRACTIC, has been defined and its abstract machine has been studied. PRACTIC is based on the inter-class and intra-class parallel query processing of queries. A hierarchical multi-processor architecture and various data and knowledge declustering schemes have been studied, in order to increase the speed-up and scalability of OO query processing. A prototype has been implemented on a transputer network and a Unix workstation using CS-Prolog. In the future, it will also be ported to a cluster of workstations.

Furthermore, the algorithms for distributing the event and rule objects of the DEVICE system onto the abstract PRACTIC machine have been developed, along with parallel rule matching and asynchronous execution schemes, for all three rule types.




I
ntelligent Systems

Knowledge-based Systems

The goal is to develop intelligent applications for solving non-trivial problems using the expertise knowledge acquired by human experts. The group has been involved in the development of various expert systems, such as:

• 
  Expert system for software evaluation (ESSE)
  
• 
  Distributed expert system for managing a national network (ExperNet)
  
• 
  Various intelligent systems for searching in a database using incomplete, insufficient, incorrect information
  
• 
  Expert system for land evaluation
  
• 
  Expert system for detecting problems in a Novell LAN
  
• 
  Expert system for drug consultation
  

The goal of the research in intelligent real-time systems is to develop autonomous systems that are able to work in complex environments, taking decisions and acting in limited time periods. The following topics are studied:

• 
  Intelligent real-time systems architecture
  
• 
  Development of scheduling algorithms that support Artificial Intelligence techniques
  
• 
  Representation and reasoning about time
  

The goal of the research in data mining is to develop methods and tools for detecting patterns and useful correlations in raw data (observation data, commercial transactions, etc.) using machine learning techniques. The following topics are studied:

• 
  Discovery of Association Rules
  
• 
  Mining Sequential Patterns
  
• 
  Knowledge discovery in non-structured data (free text, multimedia, etc)
  
• 
  Distributed Data Mining