Search

This paper presents a framework to recognize temporal compositions of atomic actions in videos. Specifically, we propose to express temporal compositions of actions as semantic regular expressions and derive an inference framework using probabilistic automata to recognize complex actions as satisfying these expressions on the input video features. Our approach is different from existing works that either predict long-range complex activities as unordered sets of atomic actions, or retrieve videos using natural language sentences. Instead, the proposed approach allows recognizing complex fine-grained activities using only pretrained action classifiers, without requiring any additional data, annotations or neural network training. To evaluate the potential of our approach, we provide experiments on synthetic datasets and challenging real action recognition datasets, such as MultiTHUMOS and Charades. We conclude that the proposed approach can extend state-of-the-art primitive action classifiers to vastly more complex activities without large performance degradation., Accepted in Workshop on Compositionality in Computer Vision at CVPR, 2020

Although First Person Vision systems can sense the environment from the user’s perspective, they are generally unable to predict his intentions and goals. Since human activities can be decomposed in terms of atomic actions and interactions with objects, intelligent wearable systems would benefit from the ability to anticipate user-object interactions. Even if this task is not trivial, the First Person Vision paradigm can provide important cues to address this challenge. We propose to exploit the dynamics of the scene to recognize next-active-objects before an object interaction begins. We train a classifier to discriminate trajectories leading to an object activation from all others and forecast next-active-objects by analyzing fixed-length trajectory segments within a temporal sliding window. The proposed method compares favorably with respect to several baselines on the Activity of Daily Living (ADL) egocentric dataset comprising 10 h of videos acquired by 20 subjects while performing unconstrained interactions with several objects.

The importance of embodiment for effective robot performance has been postulated for a long time. Despite this, only relatively recently concrete quantitative models were put forward to characterize the advantages provided by a well-chosen embodiment. We here use one of these models, based on the concept of relevant information, to identify in a minimalistic scenario how and when embodiment affects the decision density. Concretely, we study how embodiment affects information costs when, instead of atomic actions, scripts are introduced, that is, predefined action sequences. Their inclusion can be treated as a straightforward extension of the basic action space. We will demonstrate the effect on informational decision cost of utilizing scripts vs. basic actions using a simple navigation task. Importantly, we will also employ a world with “mislabeled” actions, which we will call a “twisted” world. This is a model which had been used in an earlier study of the influence of embodiment on decision costs. It will turn out that twisted scenarios, as opposed to well-labeled (“embodied”) ones, are significantly more costly in terms of relevant information. This cost is further worsened when the agent is forced to lower the decision density by employing scripts (once a script is triggered, no decisions are taken until the script has run to its end). This adds to our understanding why well-embodied (interpreted in our model as well-labeled) agents should be preferable, in a quantifiable, objective sense.

This paper addresses the challenging problem of complex human activity understanding from long videos. Towards this goal, we propose a hierarchical description of an activity video, referring to the "which" of activities, "what" of atomic actions, and "when" of atomic actions happening in the video. In our work, each complex activity is characterized as a composition of simple motion units (called atomic actions), and different atomic actions are explained by different video segments. We develop a latent discriminative structural model to detect the complex activity and atomic actions, while learning the temporal structure of atomic actions simultaneously. A segment-annotation mapping matrix is introduced for relating video segments to their associational atomic actions, allowing different video segments to explain different atomic actions. The segment-annotation mapping matrix is treated as latent information in the model, since its ground-truth is not available during both training and testing. Moreover, we present a semi-supervised learning method to automatically predict the atomic action labels of unlabeled training videos when the labeled training data is limited, which could greatly alleviate the laborious and time-consuming annotations of atomic actions for training data. Experiments on three activity datasets demonstrate that our method is able to achieve promising activity recognition results and obtain rich and hierarchical descriptions of activity videos.

We present layered concurrent programs, a compact and expressive notation for specifying refinement proofs of concurrent programs. A layered concurrent program specifies a sequence of connected concurrent programs, from most concrete to most abstract, such that common parts of different programs are written exactly once. These programs are expressed in the ordinary syntax of imperative concurrent programs using gated atomic actions, sequencing, choice, and (recursive) procedure calls. Each concurrent program is automatically extracted from the layered program. We reduce refinement to the safety of a sequence of concurrent checker programs, one each to justify the connection between every two consecutive concurrent programs. These checker programs are also automatically extracted from the layered program. Layered concurrent programs have been implemented in the Civl verifier which has been successfully used for the verification of several complex concurrent programs.

We present a proof calculus and method for the static verification of assertions and procedure specifications in shared-memory concurrent programs. The key idea in our approach is to use atomicity as a proof tool and to simplify the verification of assertions by rewriting programs to consist of larger atomic actions. We propose a novel, iterative proof style in which alternating use of abstraction and reduction is exploited to compute larger atomic code blocks in a sound manner. This makes possible the verification of assertions in the transformed program by simple sequential reasoning within atomic blocks, or significantly simplified application of existing concurrent program verification techniques such as the Owicki-Gries or rely-guarantee methods. Our method facilitates a clean separation of concerns where at each phase of the proof, the user worries only about only either the sequential properties or the concurrency control mechanisms in the program. We implemented our method in a tool called QED. We demonstrate the simplicity and effectiveness of our approach on a number of benchmarks including ones with intricate concurrency protocols.

Inspired by the properties of the refinement development of the Mondex Electronic Purse, we view an atomic action as a family of transitions with a common before-state, and different after-states corresponding to different possible outcomes when the action is attempted. We view a protocol for an atomic action as a computation tree, each branch of which achieves in several steps, one of the outcomes of the atomic action. We show that in this picture, the protocol can be viewed as a relational refinement of the atomic action in a number of ways. Firstly, it yields a 'big diagram' simulation a la ASM. Secondly, it yields a 'small diagram' simulation, in which the atomic action is synchronised with an individual step along each path through the protocol, and all the other steps of the path simulate skip. We show that provided each path through the protocol contains one step synchronised with the atomic action, the choice of synchronisation point can be made freely. We describe the relationship between such synchronisations and forward and backward simulations. We relate this theory to serialisations of system runs containing multiple transactions, and show how existing Mondex refinements embody the ideas developed. Keywords

The implementation of double-loop-learning-based educational scenarios in instructional design in workflow-like e-learning systems appears to be showing a gap; whereas the former assumes that processes can be reflected upon and can be modified or amended by the learners, the latter only predefines a limited set of rigid instructional processes. However, an important advantage of instructional designs implemented in workflow-like e-learning systems using modeling standards is the ease with which they can be exchanged with other (educational) institutions. The workflow environment described here aims to make learner reflection and change to instructional processes feasible while maintaining portability. We present a description of the implementation of the educational scenario of the virtual company in our workflow environment that makes use of dynamic workflow processes. Learners are provided with process building blocks, called “atomic actions,” which they can use to create and revise processes on the fly, thus supporting double-loop learning.

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 calculi that are useful for establishing partial-correctness 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.

Attack trees are widely considered in the fields of security for the analysis of risks (or threats) against electronics, computer control, or physical systems. A major barrier is that attack trees can become largely complex and thus hard to specify. This paper presents ATSyRA, a tooling environment to automatically synthesize attack trees of a system under study. ATSyRA provides advanced editors to specify high-level descriptions of a system, high-level actions to structure the tree, and ways to interactively refine the synthesis. We illustrate how users can specify a military building, abstract and organize attacks, and eventually obtain a readable attack tree.

The intention of this paper is to make a contribution to (compositional) development methods for concurrent programs. The topics touched on include interference, atomicity, observability and granularity. The paper sets out some requirements for an approach to developing systems by ''splitting atoms safely''.

In household environments, robots are expected to conduct many tasks. It is difficult, however, to write programs for all tasks beforehand ddue to task diversity and changing environmental conditions. One basic task of developing autonomous multifunctional robots is to define a set of basic robot actions that are executed unambiguously and checked for completion. A task planner then uses these actions to accomplish complex tasks that home-service robots are expected to do. This paper first proposes a set of tasks for first-generation home-service robots, then systematically decomposes them into sequences of smaller but meaningful actions called molecular actions. Molecular actions are then broken down into yet more primitive actions called atomic actions. Because vision, sound, range sensors, and force sensors are the main means of monitoring task progress and ompletion, atomic actions are classified based on the complexities and frequencies of the sensing algorithms used. The resulting taxonomy of atomic actions serves as a set of basic building blocks for a knowledge-based task planner. Its advantages are verified and demonstrated through experiments.

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.

We demonstrate ways to incorporate nondeterminism in a system designed to formalize the reasoning of agents concerning their abilities and the results of the actions that they may perform. We distinguish between two kinds of nondeterministic choice operators: one that expresses an internal choice, in which the agent decides what action to take, and one that expresses an external choice, which cannot be influenced by the agent. The presence of abilities in our system is the reason why the usual approaches towards nondeterminism cannot be used here. The semantics that we define for nondeterministic actions is based on the idea that composite actions are unravelled in the strings of atomic actions and tests that constitute them. The main notions used in defining this semantics are finite computation sequences and finite computation runs of actions. The results that we obtain meet our intuitions regarding events and abilities in the presence of nondeterminism.

Although the number of proposals discussing various atomic action schemes is increasing, these schemes are very rarely used in designing practical applications. To a large extent, this is accounted for by the gap existing between the languages used in research and the standard or widely spread languages (e.g. C, C++, Ada 83, Ada 95, Java) employed by practitioners. Moreover, very often researchers extend languages with new features or invent new languages to express their ideas better. Even though these approaches seem to be quite natural, they widen the gap between practice and research. To bridge this gap, we should consider fault tolerance schemes in terms of a standard language, taking the language itself for granted. The question which we believe should be addressed is how to use/implement a particular scheme in these languages rather than how to modify the language. Only in this way the schemes could be used directly and the application domains of atomic action schemes extended. The main intention of this paper is to summarise research that has been done in the last years in designing various atomic action and conversation schemes in Ada 83 and Ada 95. This should give a fuller picture of the existing schemes for researchers and help practitioners to choose the appropriate schemes. We would also like to raise and discuss some questions concerned with moving fault tolerance schemes into standard languages and environments. Finally, we intend to discuss the likely directions of future research in this area.

Traces and their extension called combined traces (comtraces) are two formal models used in the analysis and verification of concurrent systems. Both models are based on concepts originating in the theory of formal languages, and they are able to capture the notions of causality and simultaneity of atomic actions which take place during the process of a system's operation. The aim of this paper is a transfer to the domain of comtraces and developing of some fundamental notions, which proved to be successful in the theory of traces. In particular, we introduce and then apply the notion of indivisible steps, the lexicographical canonical form of comtraces, as well as the representation of a comtrace utilising its linear projections to binary action subalphabets. We also provide two algorithms related to the new notions. Using them, one can solve, in an efficient way, the problem of step sequence equivalence in the context of comtraces. One may view our results as a first step towards the development of infinite combined traces, as well as recognisable languages of combined traces., Comment: Short variant of this paper, with no proofs, appeared in Proceedings of CONCUR 2012 conference

The problem is to let n processes concurrently and repeatedly search for free addresses in a range of m addresses. The search must be wait-free: a searching process finds an address in a bounded number of steps. Three solutions are presented. The first one has large atomic actions. The second one is only correct if m greater than or equal to (r + 1). n where r is the maximum number of used addresses. The third solution is always partially correct. It is wait-free if m > r + 2 . n. This solution has a worst-case waiting time quadratic in n and an amortized waiting time linear in n, even linear in the number of active processes.

Cloud computing is based on a large number of ideas and the experience accumulated since the first electronic computer was used to solve computationally challenging problems. In Chapter 2 we review parallel and distributed systems concepts that are important to understanding the basic challenges in the design and use of computer clouds. Readers with a strong systems background can skip this chapter, but it is important for application developers to read it.

A combining network can combine concurrently issued operations on the same variable and fan out responses to the processes that issued the operations. Combining networks have been proposed with the goals of reducing message traffic, hotspots within the network, and contention for shared variables. This paper extends the class of operations that can be combined to include operations from flat atomic actions. We describe a class of networks called isotach networks and show that isotach networks can correctly combine operations from different flat atomic actions. Also we show that isotach combining networks can combine pipelined operations without sacrificing sequential consistency.

An examination of the structure of fault-tolerant systems incorporating backward error recovery indicates a partitioning into two broad classes. Two canonical models, each representing a particular class of systems, have been constructed. The first model incorporates objects and actions as the entities for program construction whereas the second model employs communicating processes and conversations. Applications in areas such as office information and banking systems are typically described and built in terms of the first model whereas applications in the area of process control are usually described and built in terms of the second model. The paper claims that the two models are duals of each other and presents arguments and examples to substantiate this claim. It will be shown that the techniques that have been developed within the context of one model turn out to have interesting and hitherto unexplored duals in the other model.

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.

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.

A compositional Petri net-based semantics is given to a simple language allowing pointer manipulation and parallelism. The model is then applied to give a notion of validity to the judgements made by concurrent separation logic that emphasizes the process-environment duality inherent in such rely-guarantee reasoning. Soundness of the rules of concurrent separation logic with respect to this definition of validity is shown. The independence information retained by the Petri net model is then exploited to characterize the independence of parallel processes enforced by the logic. This is shown to permit a refinement operation capable of changing the granularity of atomic actions.

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.

There seems to be a gap between instructional design, as implemented in workflow-like e-learning sys-tems, and double loop learning, because the former predefines educational processes and the latter as-sumes these processes can be reflected upon and can be modified by the learners. Instructional designs implemented in workflow-like e-learning systems that use modelling standards enable portability of the designs. While maintaining this advantage of portability, the COOPER environment aims to make room for learning reflection and influence as well. We will present a pedagogical scenario called “Virtual Com-pany”, which uses double loop learning extensively, to demonstrate the feasibility of our proposed solu-tion. We provide learners with “atomic actions”, that can be used to create and revise processes “on the fly”, thus enabling double-loop learning.

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.

We present here an implementation relation which allows compositional development of a network of communicating processes, in the event that corresponding specification and implementation components have different interfaces. This relation is compositional, in the sense that a target composed of several connected systems may be implemented by connecting their respective implementations. In addition, an implementation, when plugged into an appropriate environment, is to all intents and purposes a conventional implementation of the target. We illustrate our approach by outlining the development of a fault-tolerant system based on coordinated atomic actions (CA actions).

We present a formal system to reason about and specify the behavior of multiple intelligent artificial agents. Essentially, each agent can perform certain actions, and it may possess a variety of information in order to reason about its and other agent's actions. Thus, our KARO-framework tries to deal formally with the notion of Knowledge, possessed by the agents, and their possible execution of actions. In particular, each agent may reason about its —or, alternatively, other's— Abilities to perform certain actions, the possible Results of such an execution and the availability of the Opportunities to take a particular action. Formally, we combine dynamic and epistemic logic into one modal system, and add the notion of ability to it. We demonstrate that there are several options to define the ability to perform a sequentially composed action, and we outline several properties under two alternative choices. Also, the agents' views on the correctness and feasibility of their plans are highlighted. Finally, the complications in the completeness proof for both systems indicate that the presence of abilities in the logic makes the use of infinite proof rules useful, if not inevitable.

This paper is devoted to developed description of informative model of the user, who may be under the threat of socioengineering attack, and some other models, which is connected to the first one: users group model, model of control area, informative objects (documents) model. Specified informative model are included into the base for analyzing of the protection of users of informative system from socioengineering attack. Informative model of the user allows to consider name and surname of the user, his post in the organization, belongings of user to user group, and vulnerability of the user on socioengineering attacks. informative model of user group allows to consider name of user group, it’s description, allows for different atomic actions which user can perform with informative objects, type of access to information objects and information objects, which this group of users can use. Informative model of control area allows to consider name of control area and it’s description. Information model of information objects includes damage estimation of losses of confidentially, losses of integrity and losses of sufficiency. The example of socioengineering attack is brought. Development of this attack is described through suggested informative models.

Prefix iteration is a variation on the original binary version of theKleene star operation P*Q, obtained by restricting the first argument to be an atomic action, and yields simple iterative behaviours that can be equationally characterized by means of finite collections of axioms. In this paper, we present axiomatic characterizations for a significant fragment of the notions of equivalence and preorder in van Glabbeek's linear-time/branching-time spectrum over Milner's basic CCS extended with prefix iteration. More precisely, we consider ready simulation, simulation, readiness, trace and language semantics, and provide complete (in)equational axiomatizations for each of these notions over BCCS with prefix iteration. All of the axiom systems we present are finite, if so is the set of atomic actions under consideration.

We investigate split and ST bisimulation semantics, in particular the deadlock behaviour of processes in these semantics. We define and axiomatise a variant of ACP, where atomic actions and durational actions coexist, and define split and ST bisimulation semantics on this theory. We exhibit a closed term that has a deadlock in split semantics, but not in ST bisimulation semantics, and vice versa: a closed term that has a deadlock in ST bisimulation semantics but not in split semantics. As an application, we investigate different versions of durational communication.

We describe the speech-enabling approach to building auditory interfaces that treat speech as a first-class modality. The process of designing effective auditory interfaces is decomposed into identifying the atomic actions that make up the user interaction and the conversational gestures that enable these actions. The auditory interface is then synthesized by mapping these conversational gestures to appropriate primitives in the auditory environment.We illustrate this process with a concrete example by developing an auditory interface to the visually intensive task of playing tetris. Playing Tetris is a fun activity that has many of the same demands as day-to-day activities on the electronic desktop. Speech-enabling Tetris thus not only provides a fun way to exercise ones geometric reasoning abilities - it provides useful lessons in speech-enabling commonplace computing tasks.