John-Jules Ch. Meyer and Jan Treur
A currently popular definition of artificial intelligence (AI) is: ‘the study of agents that exist in an environment and perceive and act’. Agents, often referred to as intelligent agents, are (hardware or software) entities that act on the basis of a ‘mental state’. They possess both informational and motivational attitudes, which means that while performing their actions they are guided by their knowledge and beliefs as well as their desires, intentions and goals, and, moreover, they are able to modify their knowledge, intentions, etc. in the process of acting as well.
Clearly the description of agent behaviour involves reasoning
about the dynamics of acting, and if agents are supposed to be deliberative, they should also themselves be able to do so. Furthermore, since the actions of agents may - apart from actions that change the external world directly - also include reasoning as a special kind of mental action (for example, performing some belief-revising action or an action comprising of reasoning by default), it may be clear that in the context of agent systems the dynamics of reasoning and reasoning about dynamics go hand in hand.
One of the recognized problems in AI is the gap between applications and formal foundations. This sixth volume, as well as the following one in the DRUMS series, does not present the final solution to this problem, but at least does an attempt to reduce the gap by bringing together state-of-the-art material from both sides and by clarifying their mutual relation. One of the areas where the application-foundation gap is deeply felt is the area of reasoning processes as they occur within agents.
In practical applications complex (expert) reasoning processes are modelled, both in the context of knowledge-based systems for complex tasks and in the context of intelligent agents. In such practical reasoning processes it is often important, given the aims of the reasoning, to minimize the amount of information needed, and thus make (rational) decisions about the focuses of the reasoning process. Therefore models of such practical reasoning processes, have to address complex dynamics, including automated solutions for
For example, in models for diagnostic reasoning processes almost all of these aspects of dynamics often occur. But also for information gathering agents these dynamic aspects play an important role. From the side of foundations of reasoning processes, since 1980 a lot of work has been done, in particular on logics for nonmonotonic reasoning. However, very few contributions have addressed the dynamics of these reasoning processes, and no contribution at all has covered all aspects listed above.
More recently, the area of agent models has been addressed. For example, in order to formalize agents with belief, desires and intentions (BDI-agents), specific logics have been developed. However, the architectures for BDI-agents that have been developed for practical applications are not related in a clear manner to these logics. In particular, although some degree of dynamics is captured by them, BDI-logics lack a clear relationship to the internal dynamics of the reasoning in applications of BDI-agents: e.g., the revision of beliefs, desires and intentions under the appropriate circumstances, have not been sufficiently addressed in the foundational approaches. In applications of BDI-agents, this rather complex issue of revision of beliefs, desires and/or intentions has to be addressed, and actually has been addressed; e.g., when to revise only an intention and not the underlying desire, when to revise both, when to revise a desire and still keep a (committed) intention which was based on the desire?
In a comparable manner, existing theories of diagnosis from first principles address diagnosis from a static perspective, but do not cover process-oriented questions such as, on which hypothesis should the process be focused, and which observations should be done at which moment. Similarly, most contributions in the area of logics for nonmonotonic reasoning only offer a formal description of the possible conclusions of such a reasoning process, and not of the dynamics of the reasoning process itself.
In conclusion, as far as the relation to applications is concerned, within these foundational approaches especially the dynamic aspects of the agent's internal (reasoning)processes are often not, or at least not fully covered. The areas of models for reasoning patterns and agents, show a gap between applications and foundations in which the lack of adequate dynamics incorporated in the foundations plays an important role. For this reason in this volume the main theme is dynamics of reasoning processes. In the next volume, also dynamics of the external world is addressed. Agents often reason about both types of dynamics.
In this book we will consider various formal means regarding the topics reasoning and dynamics, mostly from an intelligent agent perspective. By formal means we mean formal logics / calculi as well as formal specification languages together with their formal semantics. We will see how in particular temporal and dynamic logic / semantics are useful means to perform this formal analysis. (Since these frameworks play such a prominent role in this book, we have included a separate ‘Basic Concepts’ chapter following this introduction, where these are explained succinctly.)
Formal foundations of reasoning models are of importance for different reasons. First, by defining semantics in a formal manner, a precise and unambiguous meaning of the syntactical constructs is obtained, which may help designers. This requires that designers are familiar with the formal techniques used to define such formal semantics. Unfortunately, this requirement is often not fulfilled for application developers in practice, and there is no reason to expect that this will change in the short term. However, more realistically, those who develop a modelling technique often have more knowledge of formal methods. Therefore they can benefit a lot from knowledge of formal foundations during development of their modelling technique, and use that also as a basis to informally or semi-formally describe the semantics for others (application developers using the modelling technique) with a less formal background.
Secondly, formal foundations are especially important to obtain the possibility of verification of a design or verification of requirements. Verification is usually a rather technical and tedious matter, only feasible for specialists (‘verification engineers’). They need to know about the formal foundations, including formal semantics and proof systems.
In this volume the emphasis is on the investigation of the dynamics of reasoning processes within an agent. Reasoning takes (place in) time, so, for example, it is natural to view the behaviour of reasoning processes from a temporal perspective, and consider a temporal semantics of these processes. For example, in meta-level architectures the reasoning may switch from object level to meta-level, and one may describe such behaviour by means of temporal models. Furthermore, to reason about this temporal behaviour it is very natural to employ temporal logic of some kind. But, of course, taking a temporal stance is possible for the analysis of any reasoning process or system, like (multi-)agent systems.
A large variety of reasoning patterns is presented in this volume: from dynamic generation and retraction of assumptions and dynamic control of reasoning in meta-level architectures to diagnostic reasoning processes and non-monotonic reasoning processes. All these reasoning processes have in common that they are defeasible in some sense, that is, it is possible (or perhaps even typical) that at a certain stage of the reasoning process certain conclusions may be (tentatively) arrived at, which possibly should be abandoned at a later stage. This type of reasoning is generally called defeasible reasoning. In the first two papers meta-level reasoning is exploited to focus the object level reasoning process, either by dynamically focusing on a set of goals for the object level reasoning, or on a set of assumptions used as premises in the object level reasoning. The other papers in this book address the dynamics of different variants of nonmonotonic reasoning such as reasoning by default. Here ‘nonmonotonic reasoning’ means a form of (nonstandard) logical reasoning in which adding assumptions to a set of premises may have loss of derivable conclusions as a result. This is, of course, nonstandard in the sense that classical first-order logic is ‘monotonic’ (not nonmonotonic). On the other hand a common sense reasoning method like reasoning by default is typically nonmonotonic: conclusions may be drawn on the basis of a set of premises, inclusing tentative ones on the basis of lack of information, while adding information to the premises may result in not having certain conclusions derivable any more. Clearly, a form of nonmonotonic reasoning in the above sense is also defeasible: if one considers the reasoning process in time clearly it may be the case that as more information comes available as time progresses, tentative conclusions (e.g., default conclusions) have to be retracted. Due to the emphasis of DRUMS on nonmonotonic reasoning this type of reasoning patterns is discussed quite extensively.
In the first paper of this book temporal semantics is defined for a goal-directed reasoning process in which explicit reasoning about the goals of reasoning takes place, using a meta-level architecture. By this approach it is possible to dynamically determine the goals of the reasoning by meta-reasoning. The semantics makes use of combined linear time temporal models for object level and meta-level.
The second paper addresses the dynamics of reasoning processes in which assumptions can be added and retracted dynamically, on the basis of meta-level reasoning. One of the applications of this approach is reasoning by indirect proof. Another application, addressed in the paper, is diagnosis based on causal knowledge. The semantics is based on branching time temporal models over epistemic states.
The third paper addresses the dynamics of reasoning in a generic model for a diagnostic task, which has been applied, among others, to chemical Nylon production processes. It is shown how a temporal semantics approach to these diagnostic reasoning processes can be used to verify dynamic properties of the reasoning process.
The following nine papers address the dynamics of nonmonotonic reasoning patterns such as default reasoning.
The fourth paper presents a general (temporal) semantic framework for nonmonotonic reasoning processes. Within this framework it is possible to specify the dynamics of a large class of nonmonotonic reasoning patterns.
The fifth, sixth and seventh paper address the dynamics of nonmonotonic reasoning based on default logic.
The fifth paper defines a temporal semantics for default reasoning processes. An interpretation mapping of Reiter's default logic into linear time temporal epistemic logic is defined. According to this interpretation, the antecedent of a default rule refers to the past, the justification refers to the future of the reasoning process, and the consequent to the current time point.
In the sixth paper, the KARO framework (here to be considered as a form of doxastic dynamic logic) is used to formalise (a particular type of) default reasoning processes. The dynamics of reasoning by default is considered from the viewpoint of an agent which performs default reasoning steps as particular actions, and is thus analyzed by using the dynamic logic operators together with the doxastic ones in the KARO framework.
In the seventh paper another dynamic logic approach is used to describe the dynamics of default reasoning processes. In this approach also a blend of epistemic/doxastic and dynamic logic operators is employed. The treatment of default reasoning is more general than in the previous approach. (In some sense it is reminding of the use of dynamic logic for describing reasoning steps in more general reasoning systems by Sierra et al. that we will encounter in Volume 7.) On the other hand the actions are confined to the application of default rules, which is thus not integrated into a general framework of actions performed by agents as in the previous approach.
An operational problem with default logic is that in the reasoning, also the context of the future of the reasoning processes has to be taken into account. Therefore, other, more constructive variants have been proposed. Two of them, Temporal Epistemic Default Logic (TEDL), and Constructive Default Logic (CDL) are presented in paper eight and nine.
The eighth paper addresses a variant of default logic which is defined in a temporal context. The logic TEDL is introduced in which default reasoning steps can be specified based on a branching time temporal logic.
The ninth paper presents Constructive Default Logic and specifies the control of default reasoning processes based on this logic. It exploits selection knowledge to specify conflict resolution in case of conflicting defaults.
The tenth paper addresses a situation calculus approach to the dynamics of logic program execution.
In the eleventh paper a natural-deduction-based approach to non-monotonic reasoning is presented. In this approach aspects of the dynamics of the (nonmonotonic) reasoning process are incorporated into the logic itself by means of so-called ‘contexts’, which, at any stage of the deduction, contain the premises used sofar. Contexts thus are updated during the reasoning process, and (nonmonotonic) conclusions must always be viewed with respect to the context at hand.
In the twelfth paper in this part we encounter a slightly different approach of dealing with the dynamics of a reasoning process: instead of using an explicit temporal logic Veltman-style update semantics is used to model the reasoning process (here applied to normative or deontic reasoning). The basic idea behind update semantics is that the processing of assertions in a (here deontic) logic causes an update of the (deontic) state of the processing agent, and as such this approach is another good example of analyzing the dynamics of reasoning.
The thirteenth paper addresses an application, viz. that to cooperative information gathering agents. In this paper it is shown how properties such as succesfulness of the cooperation depend on dynamic properties (such as reactiveness and pro-activeness) of the agents participating in the cooperation. The agents reason about the control of dynamics of a number of aspects of the cooperative process of information gathering. In particular, reasoning is performed about when observations are to be performed, when available information has to be communicated to other agents, when requests have to be communicated, and when conclusions have to be drawn on the basis of acquired information. Although the information states and reasoning processes of the agents are dynamic, the actual world is assumed to be not dynamic in this applications.
The fourteenth paper shows a model for the internal dynamics of an agentbreasoning and acting on the basis of beliefs, desires and intentions. This type of agent is able to reason about dynamics of the world, but also about the dynamics of its own reasoning processes, for example, about when to retract a desire, or an intention. Within this model (a formal specification of a design), in particular, it is specified how the agent should revise in an appropriate manner not only beliefs, but also desires, intentions and commitments, on the basis of specific characteristics such as blind commitment, single-mindedness or open-mindedness. Semantics of the model are inherited of the generic semantics of the formal specification language in which it is specified. However, the question how specific, dedicated semantics for this type of reasoning processes can be obtained is left open, as a challenge for further research. Only very recently some preliminary and partial results on this issue are found in the literature.
The fifteenth paper addresses a model for deliberative evolution in an agent society. An agent in this society is able to deliberatively generate the goal to create a new agent with certain desired (behavioural) properties. Moreover, the agent can deliberatively design a new agent architecture that satisfies these properties, and after this deliberation process is finished, it is able to plan and perform a creation action in the material world by which the designed agent actually is created and starts functioning in the society. In the first place reasoning about desires, goals, intentions and actions takes place. Within this reasoning process, a particularly complex pattern occurs: the design of an agent model that satisfies the requirements. In the second place, to manufacture an agent based on the generated design, reasoning about dynamics of the world is involved. Here reasoning about the dynamics of the world is related to the creation of new entities that perform themselves reasoning processes. As in the previous chapter, also in this case semantics of the model are inherited of the generic semantics of the formal specification language in which it is specified. Also here, the question how specific, dedicated semantics for this type of integrated reasoning and acting processes can be obtained is left open, as a challenge for further research.