Search

We study a propositional variant of Hoare logic that can be used for reasoning about programs that exhibit both angelic and demonic nondeterminism. We work in an uninterpreted setting, where the meaning of the atomic actions is specified axiomatically using hypotheses of a certain form. Our logical formalism is entirely compositional and it subsumes the non-compositional formalism of safety games on finite graphs. We present sound and complete Hoare-style (partial-correctness) calculi that are useful for establishing Hoare assertions, as well as for synthesizing implementations. The computational complexity of the Hoare theory of dual nondeterminism is investigated using operational models, and it is shown that the theory is complete for exponential time.

Much of the existing work on plan recognition assumes that actions of other agents can be observed directly. In continuous temporal domains such as traffic scenarios this assumption is typically not warranted. Instead, one is only able to observe facts about the world such as vehicle positions at different points in time, from which the agents' plans need to be inferred. In this paper we show how this problem can be addressed in the situation calculus and a new variant of the action programming language Golog, which includes features such as continuous time and change, stochastic actions, nondeterminism, and concurrency. In our approach we match observations against a set of candidate plans in the form of Golog programs. We turn the observations into actions which are then executed concurrently with the given programs. Using decision-theoretic optimization techniques those programs are preferred which bring about the observations at the appropriate times. Besides defining this new variant of Golog we also discuss an implementation and experimental results using driving maneuvers as an example.

The method of modeling concurrent programs is introduced. The basic framework of MPI programs are modeled by Petri net structures. On the one hand, the atomic actions of statements’ execution are represented by the transition firing, on the other hand, properties such as Orphan Message, Lack of Message, Deadlock and Livelock Subnet of concurrent programs are analyzed and verified.

We introduce an atomic action based features and demonstrate that it consistently improves performance on human activity recognition. The features are built using auxiliary atomic action data collected in our lab. We train a kernelized SVM classifier for each atomic action class. Then given a local spatio-temporal cuboid of a test video, we represent it using the responses of our atomic action classifiers. This new atomic action feature is discriminative, and has semantic meanings. We perform extensive experiments on four benchmark action recognition datasets. The results show that atomic action features either outperform the corresponding low level features or significantly boost the recognition performance by combining the two.

In safety-critical and in space applications, high demands are made on the reliability of the involved systems. As autonomy could increase both the efficiency and the reliability of such systems, a reliable autonomous system could be beneficial for several robotic scenarios. In this paper, the concept of a biologically inspired, robust behaviour control system is presented. The system includes components for prediction of actions to be executed and the evaluation of the action consequences. In its design process, particularly the occurence of unexpected situations was taken into account. The paper concludes with a presentation of preliminary simulation results and the evaluation setup that will be used in future tests to demonstrate the model properties.

The dynamic description logic DDL provides a kind of action theories based on description logics (DLs). Compared with another important DL-based action formalism constructed by Baader et.al., a shortcoming of DDL is the absence of occlusions and conditional post-conditions in the description of atomic actions. In this paper, we extend atomic action definitions of DDL to overcome this limitation. Firstly, we introduce extended atomic action definitions in which the occlusions and conditional post-conditions are incorporated. Secondly, for each atomic action specified by an extended atomic action definition, a function named Expand is introduced to transform it into a choice action which is composed of atomic actions defined by ordinary atomic action definitions. Finally, based on the Expand function, the satisfiability-checking algorithm of DDL is extended to support occlusions and conditional post-conditions.

Some time ago, Computer Vision has passed the stage where it detected changes in image sequences, estimated Optical Flow, or began to track people and vehicles in videos. Currently, research in Computer Vision has expanded to extract descriptions of single actions or concatenations of actions from videos, sometimes even the description of agent behavior in the recorded scene. This transition from treating mostly quantitative, geometric descriptions to becoming concerned with more qualitative, conceptual descriptions creates contacts between Computer Vision, Computational Linguistics, and Computational Logic. The latter two disciplines have studied the analysis and combination of conceptual constructs already for decades. Based on selected examples, attention will be drawn to the potential which can be tapped if the emerging thematic overlap of research in these three disciplines is investigated collaboratively. This applies in particular to the development of encompassing systems which rely on methods from all three disciplines, for example by providing Natural Language interfaces to more generally applicable combinations of Knowledge Bases with Computer Vision systems.

The quest for modular concurrency reasoning has led to recent proposals that extend program assertions to include not just knowledge about the state, but rights to access the state. We argue that these rights are really just sugar for knowledge that certain updates preserve certain invariants.

This paper presents a method of how to simulate various human actions. Actions are formed in the Action Hierarchy, and are reified in terms of expanding the hierarchy. While inheritance, super classes provide overall information of actions, and sub classes are used as the actual functions of actions. Primitive actions as leaves of the action hierarchy are proposed for an atomic action to be shared in several actions, and used as key frame. The Action Generator guarantees to return accurate primitive actions to an agent based on the Action Library and the Action Hierarchy, and also provides individual patterns of actions.

We propose complementing tabular notations used in requirements specifications, such as those used in the SCR method, with a formalism for describing specific, useful, subclasses of computations , i.e., particular combinations of the atomic transitions specified within tables. This provides the specifier with the ability of driving the execution of transitions specified by tables, without the onerous burden of having to introduce modifications into the tabular expressions; thus, it avoids the problem of modifying the object of analysis, which would make the analysis indirect and potentially confusing. This is useful for a number of activities, such as defining test harnesses for tables, and concentrating the analyses on particular, interesting, subsets of computations. Unlike previous approaches, ours allows for the description of a wider class of combinations of the transitions defined by tables, by means of a rich operational language. This language is an extension of the Alloy language, called DynAlloy, whose notation is inspired by that of dynamic logic. The use of DynAlloy enables us to provide an extra mechanism for the analysis of tabular specifications, based on SAT solving. We will illustrate this and the features of our approach via an example based on a known tabular specification of a simple autopilot system.

Emotional-BDI agents are BDI agents whose behaviour is guided not only by beliefs, desires and intentions, but also by the role of emotions in reasoning and decision-making. The $\mathcal{E}_{\rm BDI}$ logic is a formal system for expressing the concepts of the Emotional-BDI model of agency. In this paper we present an improved version of the $\mathcal{E}_{\rm BDI}$ logic and show how it can be used to model the role of three emotions in Emotional-BDI agents: fear , anxiety and self-confidence . We also focus in the computational properties of $\mathcal{E}_{\rm BDI}$ which can lead to its use in automated proof systems.

A typical present-day virtual actor is able to store episodes in an ad hoc manner, which does not allow for reconstructing the actor's personal stories. This paper proposes a virtual RPG actor with a full episodic memory, which allows for this reconstruction. The paper presents the memory architecture, overviews the prototype implementation, presents a benchmark for the efficiency of the memory measurement, and details the conducted tests.

Graphical level of detail (LOD) is a set of techniques for coping with the issue of limited computational resources by reducing the graphical detail of the scene far from the observer. Simulation LOD reduces quality of the simulation at the places unseen. Contrary to graphical LOD, simulation LOD has been almost unstudied. As a part of our on-going effort on a large virtual-storytelling game populated by tens of complex virtual humans, we have developed and implemented a set of simulation LOD algorithms for simplifying virtual space and behaviour of virtual humans. The main feature of our technique is that it allows for several degrees of detail, i.e. for gradualvarying of simulation quality. In this paper, we summarise the main lessons learned, introduce the prototype implementation called IVE and discuss the possibility of scaling our technique to other applications featuring virtual humans.

We present a dynamic description logic for representation and reasoning about actions, with an approach that embrace actions into the description logic ALCO@. With this logic, description logic concepts can be used for describing the state of the world, and the preconditions and effects of atomic actions; Complex actions can be modeled with the help of standard action operators, such as the test, sequence, choice, and iteration operators; And both atomic actions and complex actions can be used as modal operators to construct formulas. We develop a terminable and correct algorithm for checking the satisfiability of formulas. Based on the algorithm, many reasoning tasks on actions are effectively carried out, including the realizability, executability, projection and planning problems.

When modeling concurrent or parallel systems, we must be aware that basic activities of each system may be constituted by smaller activities, i.e. transitions may be conceptually refined into transactions. Nevertheless, the Unified Modeling Language seems to lack compositional constructs for defining atomic actions/activities/operations. We discuss proper extensions for UML behavioral diagrams that are able to cope with the concept of transaction. Transactions are formally defined through a special morphism between automata in a semantic domain called Nonsequential Automata.

In this chapter we review some issues of research in intelligent agents and particularly some logical theories that have been proposed in the literature to describe aspects of intelligent agents.

This paper discusses automated reasoning in the KARO framework. The KARO framework accommodates a range of expressive modal logics for describing the behaviour of intelligent agents. We concentrate on a core logic within this framework, in particular, we describe two new methods for providing proof methods for this core logic, discuss some of the problems we have encountered in their design, and present an extended example of the use of the KARO framework and the two proof methods.

This paper proposes a formal framework for modelling the interaction of concurrent items of equipment in real-time safety-critical systems and reasoning about their behaviour abstractly. The framework is based on the concept of Coordinated Atomic (CA) actions, an approach widely used for structuring complex activities in fault-tolerant computer systems. It advocates a hierarchical approach and begins with the construction of a mathematical model of the behaviour of an individual item of equipment. Later on, the model is extended to incorporate the concept of a CA action. In the final stage, a formal representation of the ideal behaviour of an abstract CA action is provided. The framework uses Timed CSP - a well-established formalism used for representation and reasoning in real-time systems.

In this paper, we propose a new way of considering reasoning about action and change. Rather than placing a preferential structure onto the models of logical theories, we place such a structure directly on the semantics of the actions involved. In this way, we obtain a preferential semantics of actions by means of which we can not only deal with several of the traditional problems in this area such as the frame and ramification problems, but can generalize these solutions to a context which includes both nondeterministic and concurrent actions. In fact, the net result is an integration of semantical and verificational techniques from the paradigm of imperative and concurrent programs in particular, as known from traditional programming, with the AI perspective. In this paper, the main focus is on semantical (i.e. model theoretical) issues rather than providing a logical calculus, which would be the next step in the endeavor.

The concurrency facilities within Ada 95 are more comprehensive than in any other language. Through a discussion of three case studies, this paper shows how the language abstractions supported by Ada can be combined to build effective higher-level abstractions. The three examples concern a concurrency problem, a fault tolerance requirement and a scheduling (real-time) issue. Together they illustrate that many of the criticisms that were rightly focused on Ada 83 have been addressed by the language revision.

This paper deals with a multiple planning problem, which is a collection of planning problems defined for the same partial transition system and have the same set of goal states. It is shown that a solution to the multiple planning problem can be written in procedural (imperative) languages like Pascal. The formal definition of the syntax and semantics of conditional-iterative actions is provided. It is proven that a multiple plan can be generated by a conditional-iterative action. A language of formal representation of partial transition systems with a vector-state space is proposed.

This paper reviews the development of error recovery structures that support general fault tolerance, and describes a new object-oriented scheme for error recovery in concurrent systems that generalizes existing schemes based on either conversations or transactions. This new scheme, which is based on what we term a Coordinated Atomic Action, is intended to facilitate the provision of means of tolerating hardware and software faults, and faults that have affected the environment of the computer system — and to do so for programs that involve cooperating concurrent processes, and the use of shared resources.

In this paper we investigate non-atomic actions and changes in the framework of the situation calculus. We classify non-atomic actions into three types: simultaneous actions, inclusive selective actions, and exclusive selective actions. We show that the extended situation calculus with non-atomic actions has the same expressive power as the basic situation calculus. We identify a problem, called composition problem, which relates effects of non-atomic actions to those of their component actions. A defeasible solution to the composition problem is proposed. The believability of some choices of default rules for the composition problem are discussed. We also provide some simple examples to illustrate the usefulness of our default rules.

TINA provides an architecture to support the Telecommunication Services of the future [2,3]. This architecture consists of a number of Service Managers (e.g. Service Session Manager, User Service Manager) that co-operate to provide Telecommunication Services to the users. In certain cases, complex interactions are required and this paper suggests the use of Atomic Action (AA) transaction principles to provide the required co-operation mechanisms.

Arjuna is an object-oriented programming system implemented in C++ that provides a set of tools for the construction of fault-tolerant distributed applications. This paper reports on the experience gained by building and using the system. It then describes how in light of this experience, a new version of the system is being designed.

We study a problem of actions with typical, but not certain effects. We show how this kind of actions can be incorporated in a dynamic/epistemic multi-agents system in which the knowledge, abilities and opportunities of agents are formalized as well as the results of actions they perform. To cope with complexity of a rational agent behaviour, we consider scenarios composed of traditionally viewed basic actions and atomic actions with typical effects. We focus on a specific type of scenarios reflecting a “typical” pattern of an agent's behaviour. Adopting a model-theoretic approach we formalize a nonmonotonic preferential strategy for these scenarios in order to reason about the final results of their realizations.

A method for making aspects of a computational model explicit in the formulas of a programming logic is given. The method is based on a new notion of environment -an environment augments the state transitions defined by a program''s atomic actions rather than being interleaved with them. Two simple semantic principles are presented for extending a programming logic in order to reason about executions feasible in various environments. The approach is illustrated by (i) discussing a new way to reason in TLA and Hoare-style programming logics about real-time and by (ii) deriving the first TLA and Hoare-style proof rules for reasoning about schedulers.

In this paper we define a framework designed to formalize certain aspects of the behaviour of rational agents. To this end we start by defining a language L in which not only knowledge and actions of a set of agents can be expressed, but also their abilities. A semantics for the language L is defined; a sound and complete axiomatization with regard to the class of models used to define this semantics is given. We define the notion of action transformation, a function that transforms actions into other actions. The semantics that we define is such that two actions that can be transformed into one another have equivalent results and that the abilities of an agent are closed under the action transformations. We also consider the Can-predicate and the Cannot-predicate that formalize the knowledge of agents about the (in)correctness and (un)feasibility of their plans.

In a flowchart scheme an atomic action is modelled as a vertex (box), while in a process graph an atomic action is modelled as an edge. We define translations between these two graphical representations. By using these translations, we show that the classical bisimulation equivalence on process graphs coincides with the natural extension of the classical step-bystep flowchart equivalence to the nondeterministic case. This result allows us to translate axiomatisation results from flowcharts to processes and viceversa.

We propose a programming formalism that provides multiprocess synchronization and priorities. As in CCS and CSP, processes communicate by executing pairs of complementary actions. Processes are labelled transition systems, where the labels are formed by combining atomic actions with the operators Λ, ⌝. Intuitively, a Λ b expresses multiple synchronization on actions a,b, while ⌝e expresses that the actions specified by e cannot be performed in the current environment.

Conversations were proposed as a means of organizing fault tolerance by coordinated backward recovery in a set of communicating processes, avoiding the domino effect and allowing diversity in the retries. The general concept of conversations is susceptible to many different detailed implementations. We review and discuss the problems of implementation and of practical use of conversations, comparing and generalizing the solutions offered in the different existing proposals, and suggesting some useful extensions. We discuss limits to the complexity of implementations that can be exploited in practice, and to the applications that can be programmed using the conversation scheme.

This paper gives a reconstruction of the classical pre- and postcondition technique from its roots and extends it with several features. A number of problems in connection with pre- and postcondition specifications are discussed and solutions presented. Problems that are discussed include: framing, dynamic object creation, non-atomic actions and user-friendly syntax. The technique as described is part of the specification language COLD-1 and has been used in several industrial applications.

We investigate equivalence notions for concurrent systems. We consider “linear time” approaches where the system behaviour is characterised as the set of possible runs as well as “branching time” approaches where the conflict structure of systems is taken into account. We show that the usual interleaving equivalences, and also the equivalences based on steps (multisets of concurrently executed actions) are not preserved by refinement of actions. We prove that “linear time” partial order semantics, where causality in runs is explicit, is invariant under refinement. Finally, we consider various bisimulation equivalences based on partial orders and show that the strongest one of them is preserved by refinement whereas the others are not.

The construction of models for distributed computations plays a very important role in designing and developing parallel computing systems. Various algebraic approaches have been proposed in the past as, for instance, the communicating computing agents of [Mil80], [BeK85], and [BHR84].

These notes describe a method for specifying concurrent and distributed systems, and illustrate it with a number of examples, mostly of storage systems. The specification method is due to Lam-port (1983, 1988), and the notation is an extension due to Nelson (1987) of Dijkstra’s (1976) guarded commands.

A database can be seen as a set of entities which satisfy certain assertions called integrity constraints. A database is simultaneously accessed by numerous transactions. Each transaction is composed of a sequence of atomic actions and performs a set of operations. In order to guarantee the good execution of all the operations and the integrity of the database, it is necessary to limit the simultaneous execution of transactions.

Two design rules which aid the construction of distributed computing systems and the provision of fault tolerance are described, namely that: (i) a distributed computing system should be functionally equivalent to the individual computing systems of which it is composed, and (ii) fault tolerant systems should be constructed from generalised fault tolerant components.

Using structured occurrence graphs, we present an operational characterisation of the atomicity of activities. Broadly, activities are defined to occur atomically if they do not interleave with each other. We discuss our characterisation and use it as a starting point for the discussion of implementation issues and the problem of incorporating atomic actions into a concurrent programming language. We finally examine the use of structured occurrence graphs in connection with techniques for error recovery in decentralised systems.

Consider how one might describe the sequences of atomic actions IF] performable by a s tandard deterministic flowchart scheme F . One can exhibit F as a finite directed graph whose vertices are labeled with letters in a ranked alphabet ~2 (if the vertex v has outdegree k, then the letter labeling v is in the set ~k ). Then we say that the set [F] is the set of all labels of paths in F from the 'begin vertex' to the exit. If one wants to refine this notion further, one can associate a labeled tree with F, the so called 'unfolding' of F , and define [F] as this tree. To describe the tree in great detail, one can show how to associate a tree of depth at most one with each node in the underlying graph of F . This association takes the form of a system of equations. For example, suppose that F is the flowchart scheme

COSY is an abstract programming notation ‘between’ Petri nets and concurrent programs. It allows to analyse the interrelationship of atomic actions, abstracting away from their internal structure. This paper describes control programs, a dialect of COSY, and some of their theory. It exhibits their relationship to Petri nets and shows how a simplified version of CSP can be given a semantics in terms of control programs (and hence also in terms of nets). Amongst other things, this yields a ‘true concurrency’ semantics of CSP.

Some ideas on the construction of user applications as atomic actions are developed. Atomic actions that last a long time pose several problems if conventional ideas on concurrency control and recovery are applied. What is required is some means of delaying commitment without sacrificing performance. A model is proposed in which it is possible for an action to release and process as yet uncommitable objects. The impact of this on recovery is also discussed.