Logic Programming with Temporal Constraint Graphs
by
Sergei Bogomolov
LGTCM Soft Lab

Logic Programming with Temporal Constraint Graphs Presented by Sergei Bogomolov LGTCM Soft Lab The aim of this paper is to present an approach based on conception of constraint logic programming. Temporal constraints are concerned that lie in the class of closed linear inequalities involving no more than two temporal variables. This restriction allows to propose effective procedure of computation of answer to temporal constraints query. The temporal reasoning scheme combines the temporal constraints consistency procedure based on transitive closure and non-deterministic choice procedure based on SLD-resolution.

The consistency procedure allows to cut off non-promise ways of search. The size of search space is cut down much more large if there are more accurate temporal constraints in initial query and rules from temporal constraint logic program. The logic programs with temporal constraints (TC) enable to use new flexible computation strategies based on analysis of accuracy of temporal constraints of TC-rules and TC-query. The computation strategy defines an order of round of search tree and includes a selection step of active atom from current query and a suitable rule choice from admissible rule list. For selection of suitable rule a more compound strategy may use the ordering of admissible rules set based on analysis of accuracy of temporal constraints.

The effective reasoning system above assertions with time binding and temporal constraints allows to give new flexible tools for processing and analysis of systems behaviour.

The well-known formalisms for temporal reasoning are Allen's interval algebra, time maps of Dean and McDermott, temporal constraint networks of Dechter, Meiri and Pearl, T-Prolog of Futo and Szeredi, calculus of events of Kowalski and Sergot, temporal logic of Shoham, logics of real time systems. Part of above given formal schemes is supported by constraint-directed reasoning procedures. Another part of formalisms is based on logical approach that uses the inference search and model checking procedures. The conception of constraint logic programming (CLP) developed by J.Jaffar and J.-L.Lassez allows to connect the paradigms of constraints solving and logic programming. The assertions of logic program are complemented by constraints presented as equalities and inequalities over real, integer or boolean numbers. In this case, each computation step includes constraints consistency test and non-deterministic choice. For linear inequalities over real numbers, the consistency test is based on well-known in the operations research simplex-method with exponential complexity. This method have been used in the known CLP(R)-scheme.

The relative arrangement of temporal intervals corresponding to predicate atoms is seen as loaded oriented graph named TC-graph. The edges of TC-graph can be related to the elementary temporal constraints in the terms of closed linear inequalities over temporal intervals boundaries. The logic program with temporal constraints constitutes a set of pairs ''Horn formulae + TC - graph''. Given paper is an extension of results of early investigations of author.

The temporal constraints logic program is defined by set of the rules with temporal con-straints (named the TC-rules) in the form A0<=A1,...,Am || G[A0,A1,...,Am] , where A0<=A1,...,Am is a standard rule of classic logic programming (logical component), G[ A0,A1,...,Am] is a temporal constraints system of the rule represented as TC-graph. For m=0 we have a special case of the TC-rules called the TC-facts. The temporal constraints system of TC-fact is either of two types: with or without time binding. The first type of temporal constraints system of TC-fact is used for time binding of temporal interval boundaries of predicate atom. Another type is used if we are in the dark about the time binding of predicate atom temporal interval.

Also we define the query with temporal constraints named TC-query and presented as pair <=C1,...,Ck || G[C1,...,Ck,B1,...,Bn], where <= C1,...,Ck is a typical query of classic logic programming (logical component of TC-query), C1,...,Ck are the predicate atoms named active ones and included in logical component , B1,...,Bn are the predicate atoms named passive ones and excluded in logical component, G[C1,...,Ck,B1,...,Bn] is a temporal con-straints system involving active and passive predicate atoms. If the TC-query is free from passive atoms, then one is said to be initial. If the TC-query is free from active atoms (logical component is empty query, so one is named final. With the availability of passive and active atoms the TC-query is said to be intermediate. We suppose that the temporal con-straints systems for any TC-rules, TC-facts and TC-query are temporal consistent.

The successful computation of answer to initial query Q0 is a finite sequence of queries Q0,Q1,...,QN, so that query QN is final query and query Qi+1 is derived from query Qi by using the computation step (inference rule). The computation step converts query Qi to query Qi+1 through the application of TC-rule (or TC-fact). By this means the logical component of new query Qi+1 is derived from logical component of current query Qi by application of standard SLD-resolution procedure. The second component corresponding to temporal constraints system is constructed by combination of the temporal constraints system of current query Qi and the temporal constraints system of applied TC-rules.

The condition of using TC-rule is an existence of unification for terms and consistent temporal constraints system for union of temporal constraints systems of current query and rule. The temporal consistency checking is based on temporal graph way closure with cubic complexity. Computational complexity of consistancy procedure can be decreased by using decomposition of temporal constraints graph to square one in some cases.

The search of successful computation is performed by back-tracking method. But the use of temporal constraints consistency procedure with cubic complexity allows to cut off non-promise ways of search. The size of search space is cut down much more large if there are more accurate temporal constraints in initial TC-query and TC-rules from temporal con-straint logic program. The accuracy of temporal constraints depends on length of intervals loads of TC-graph. The best (absolute) accuracy of temporal constraints system takes place when all interval loads are degenerated into point loads. Then the system of closed linear inequalities corresponding to temporal constraints system transformed into system of equalities. The logic programs with temporal constraints permit to use new flexible computation strategies based on analysis of accuracy of temporal constraints systems. The computation strategy defines an order of round of search tree and includes a selection step of active atom from current query and a suitable rule choice from admissible rule list REFERENCES [1] J.F. Allen, `Towards a general theory of action and time', Artificial Intelligence, 23(1), 123-154, (1984).

[2] T.L. Dean, D.V. McDermott, `Temporal data based managment', Artificial Intelligence, 32(1), 1-555, (1987).

[3] R.Dechter, I.Meiry and J.Pearl, `Temporal constraint networks', Artificial Intelligence, 49(1), 61-95, (1991).

[4] I.Futo and P.Szeredi, T-Prolog user manual. Version 4.2. SZKI, Budapest, 1983.

[5] R.Kowalski and M.Sergot, `A logic-based calculus of events', New generation computing, 4, 67-95, (1986).

[6] Y. Shoham, `Temporal logics in artificial intelligence: semantical and ontological con-siderations', Artificial Intelligence , 33(1), 89-104, (1987).

[7] R. Alur and T.A.Henzinger, Logics and models of real time: a survey, in: Lecture Notes in Computer Science, 74-106,(1992).

[8] J.Jaffar and J.-L.Lassez, Constrained logic programming, in: Proceedings 14 th ACM Symposium on Principles of Programming Languges, Munich, Germany, 111-119,(1987).

[9] J.Jaffar and J.-L.Lassez, From unification to constraints, Logic Programming'87, ed., K.H.Tanaki, Lecture Notes in Computer Science, 315 , 1-18, 1987.

[10] J.Jaffar and S.Michaylov, Methodology and implementation of CLP system, in: Pro-ceedings of Fourth International Conference on Logic Programming, Melbourn, Austra-lia,(1987).

[11] S.Ye.Bogomolov and A.G.Yankovsky, Temporal constraint logic programming in modelling of distributed real-time systems, in: Proceedings of the first international Workshop on High Speed Networks of Open Distributed Platforms, St.-Petersburg, Rus-sia, 195-198, (1995).

[12] J.W.Lloyd, Foundations of Logic Programming, Springer Verlag, Berlin, 1984.

[13] C.Brzoska, Temporal logic Programming and its relation to constraint logic program-ming. In Proc.of the 1991 Logic Programming Symposium, San Diego, 1991.

Date received: March 18, 1999