# A Temporal Description Logic For Reasoning About Actions And Plans

Alessandro Artale ITC-IRST, Cognitive and Communication Technologies Division I-38050 Povo TN, Italy ARTALE @IR ST . IT C . IT
Enrico Franconi Department of Computer Science, University of Manchester Manchester M13 9PL, UK
FRANCONI@CS.MAN.AC.UK

## Abstract

A class of interval-based temporal languages for uniformly representing and reasoning about actions and plans is presented. Actions are represented by describing what is true while the action itself is occurring, and plans are constructed by temporally relating actions and world states. The temporal languages are members of the family of Description Logics, which are characterized by high expressivity combined with good computational properties.

The subsumption problem for a class of temporal Description Logics is investigated and sound and complete decision procedures are given. The basic language TL-F is considered first: it is the composition of a temporal logic TL   able to express interval temporal networks together with the non-temporal logic F a Feature Description Logic. It is proven that subsumption in this language is an NP-complete problem. Then it is shown how to reason with the more expressive languages TLU-FU and TL-ALCF . The former adds disjunction both at the temporal and non-temporal sides of the language, the latter extends the non-temporal side with set-valued features (i.e., roles) and a propositionally complete language.

## 1. Intro Duction

The representation of temporal knowledge has received considerable attention in the Artificial Intelligence community in an attempt to extend existing knowledge representation ssssems to deal with actions and change. At the same time, many logic-based formalisms were developed and analyzed by logicians and philosophers for the same purposes. In this class of logical formalisms, properties such as expressive power and computability have been studied as regards typical problems involving events and actions.

This paper analyzes from a theoretical point of view the logical and computational properties of a knowledge representation system that allows us to deal with time, actions and plans in a uniform way.  The most common approaches to model actions are based on the notion of state change   e.g., the formal models based on the original situation calculus c arthy ayes, andewall hoham, or the Strips-like planning in which actions are generally considered systems ikes Nilsson, ifschitz, instantaneous and defined as functions from one state to another by means of pre- and post-conditions. ere, an explicit notion of time is introduced in the modeling language and actions are defined as occurring over time intervals , following the Allen proposal Allen,