Action dependencies in privacy-preserving multi-agent planning

Collaborative privacy-preserving planning (CPPP) is a multi-agent planning task in which agents need to achieve a common set of goals without revealing certain private information. In many CPPP algorithms, the individual agents reason about a projection of the multi-agent problem onto a single-agent classical planning problem. For example, an agent can plan as if it controls the public actions of other agents, ignoring any private preconditions and effects theses actions may have, and use the cost of this plan as a heuristic estimate of the cost of the full, multi-agent plan. Using such a projection, however, ignores some dependencies between agents’ public actions. In particular, it does not contain dependencies between public actions of other agents caused by their private facts. We propose a projection in which these private dependencies are maintained. The benefit of our dependency-preserving projection is demonstrated by using it to produce high-level plans in a new privacy-preserving planner, and as a heuristic for guiding forward search privacy-preserving algorithms. Both are able to solve more benchmark problems than any other state-of-the-art privacy-preserving planner. This more informed projection does not explicitly expose any private fact, action, or precondition. In addition, we show that even if an adversary agent knows that an agent has some private objects of a given type (e.g., trucks), it cannot infer the number of such private objects that the agent controls. This introduces a novel form of strong privacy, which we call object-cardinality privacy, that is motivated by real-world requirements.     

A Generic and Provably Convergent Shape-from-Shading Method for Orthographic and Pinhole Cameras

We describe a mathematical and algorithmic study of the Lambertian “Shape-From-Shading” problem for orthographic and pinhole cameras. Our approach is based upon the notion of viscosity solutions of Hamilton-Jacobi equations. This approach provides a mathematical framework in which we can show that the problem is well-posed (we prove the existence of a solution and we characterize all the solutions). Our contribution is threefold. First, we model the camera both as orthographic and as perspective (pinhole), whereas most authors assume an orthographic projection (see Horn and Brooks (1989) for a survey of the SFS problem up to 1989 and Zhang et al. (1999), Kozera (1998), Durou et al. (2004) for more recent ones); thus we extend the applicability of shape from shading methods to more realistic acquisition models. In particular it extends the work of Prados et al. (2002a) and Rouy and Tourin (1992). We provide some novel mathematical formulations of this problem yielding new partial differential equations. Results about the existence and uniqueness of their solutions are also obtained. Second, by introducing a “generic” Hamiltonian, we define a general framework allowing to deal with both models (orthographic and perspective), thereby simplifying the formalization of the problem. Thanks to this unification, each algorithm we propose can compute numerical solutions corresponding to all the modeling. Third, our work allows us to come up with two new generic algorithms for computing numerical approximations of the “continuous solution of the “Shape-From-Shading” problem as well as a proof of their convergence toward that solution. Moreover, our two generic algorithms are able to deal with discontinuous images as well as images containing black shadows. First online version published in October, 2005     

A knowledge server for reasoning about temporal constraints between classes and instances of events

Reasoning with temporal constraints is a ubiquitous issue in many computer science tasks, for which many dedicated approaches have been and are being built. In particular, in many areas, including planning, workflow, guidelines, and protocol management, one needs to represent and reason with temporal constraints between classes of events (e.g., between the types of actions needed to achieve a goal) and temporal constraints between instances of events (e.g., between the specific actions being executed). The temporal constraints between the classes of events must be inherited by the instances, and the consistency of both types of constraints must be checked. In this article, we design a general‐purpose domain‐independent knowledge server dealing with these issues. In particular, we propose a formalism to represent temporal constraints, and we point out two orthogonal parameters that affect the definition of reasoning algorithms operating on them. We then show four algorithms to deal with inheritance and to perform temporal consistency checking (depending on the parameters) and we study their properties. Finally, we report the results we obtained by applying our system to the treatment of temporal constraints in clinical guidelines. © 2004 Wiley Periodicals, Inc. Int J Int Syst 19: 919–947, 2004.     

Flux-free Finite Element Method with Lagrange Multipliers for Two-fluid Flows

In this paper we consider the flux-free finite element method based on the Eulerian framework for immiscible incompressible two-fluid flows, which is defined so as to preserve the mass of each fluid. This method is derived from the variational formulation including the flux-free constraint for the Navier–Stokes equations by the Lagrange multiplier technique. Focusing on the stationary problem, we prove the well-posedness of the finite element solution by a discrete inf-sup condition and show basic error estimates. Moreover we also show the stability of the fractional-step projection finite element scheme for the non-stationary problem. Finally, we give some numerical results to validate our method.     

Integrated Temporal Reasoning with Periodic Events

In many areas of Computer Science, including planning, workflows, guidelines, and protocol management, one has to deal with abstract plans, procedures, or schedules involving temporal constraints between classes of actions that have to be repeated at periodic times and may be instantiated in different ways for different executions of the plans (procedures, schedules). In this paper we propose an integrated framework to deal with both qualitative temporal constraints on classes of actions and temporal constraints between instances of actions, in which temporal reasoning is used to amalgamate both types of constraints and to check their consistency. In particular, we consider an expressive formalism to deal with temporal constraints between classes of actions (with special attention to periodic actions) which takes into account different components such as frame times, numeric quantification, periods, and qualitative relations. We define the notions of (contextual) concretization of qualitative temporal constraints between classes and use this notion to formally define the consistency of a knowledge base of temporal constraints between classes and a set of temporal constraints on instances, and to define the algorithm for checking such a consistency. An application for scheduling lessons in a school is shown in an example.     

A penalty PALM method for sparse portfolio selection problems

In this paper, we propose a penalty proximal alternating linearized minimization method for the large-scale sparse portfolio problems in which a sequence of penalty subproblems are solved by utilizing the proximal alternating linearized minimization framework and sparse projection techniques. For exploiting the structure of the problems and reducing the computation complexity, each penalty subproblem is solved by alternately solving two projection problems. The global convergence of the method to a Karush-Kuhn-Tucker point or a local minimizer of the problem can be proved under the characteristic of the problem. The computational results with practical problems demonstrate that our method can find the suboptimal solutions of the problems efficiently and is competitive with some other local solution methods.     

Solving the ignoring problem for partial order reduction

Partial order reduction limits the state explosion problem that arises in model checking by limiting the exploration of redundant interleavings. A state space search algorithm based on this principle may ignore some interleavings by delaying the execution of some actions provided that an equivalent interleaving is explored. However, if one does not choose postponed actions carefully, some of these may be infinitely delayed. This pathological situation is commonly referred to as the ignoring problem. The prevention of this phenomenon is not mandatory if one wants to verify if the system halts but it must be resolved for more elaborate properties like, for example, safety or liveness properties. We present in this work some solutions to this problem. In order to assess the quality of our propositions, we included them in our model checker Helena. We report the result of some experiments which show that our algorithms yield better reductions than state of the art algorithms like those implemented in the Spin tool.     

Finding groups with maximum betweenness centrality

In this paper we consider the problem of identifying the most influential (or central) group of nodes (of some predefined size) in a network. Such a group has the largest value of betweenness centrality or one of its variants, for example, the length-scaled or the bounded-distance betweenness centralities. We demonstrate that this problem can be modelled as a mixed integer program (MIP) that can be solved for reasonably sized network instances using off-the-shelf MIP solvers. We also discuss interesting relations between the group betweenness and the bounded-distance betweenness centrality concepts. In particular, we exploit these relations in an algorithmic scheme to identify approximate solutions for the original problem of identifying the most central group of nodes. Furthermore, we generalize our approach for identification of not only the most central groups of nodes, but also central groups of graph elements that consists of either nodes or edges exclusively, or their combination according to some pre-specified criteria. If necessary, additional cohesiveness properties can also be enforced, for example, the targeted group should form a clique or a κ-club. Finally, we conduct extensive computational experiments with different types of real-life and synthetic network instances to show the effectiveness and flexibility of the proposed framework. Even more importantly, our experiments reveal some interesting insights into the properties of influential groups of graph elements modelled using the maximum betweenness centrality concept or one of its variations.     

A regularization framework for robust dimensionality reduction with applications to image reconstruction and feature extraction

Dimensionality reduction has many applications in pattern recognition, machine learning and computer vision. In this paper, we develop a general regularization framework for dimensionality reduction by allowing the use of different functions in the cost function. This is especially important as we can achieve robustness in the presence of outliers. It is shown that optimizing the regularized cost function is equivalent to solving a nonlinear eigenvalue problem under certain conditions, which can be handled by the self-consistent field (SCF) iteration. Moreover, this regularization framework is applicable in unsupervised or supervised learning by defining the regularization term which provides some types of prior knowledge of projected samples or projected vectors. It is also noted that some linear projection methods can be obtained from this framework by choosing different functions and imposing different constraints. Finally, we show some applications of our framework by various data sets including handwritten characters, face images, UCI data, and gene expression data.     

Exploring Temporal Structure of Trajectory Components for Action Recognition

Action recognition is one of the most important components for video analysis. In addition to objects and atomic actions, temporal relationships are important characteristics for many actions and are not fully exploited in many approaches. We model the temporal structures of midlevel actions (referred to as components) based on dense trajectory components, obtained by clustering individual trajectories. The trajectory components are a higher level and a more stable representation than raw individual trajectories. Based on the temporal ordering of trajectory components, we describe the temporal structure using Allen's temporal relationships in a discriminative manner and combine it with a generative model using bag of components. The main idea behind the model is to extract midlevel features from domain‐independent dense trajectories and classify the actions by exploring the temporal structure among these midlevel features based on a set of relationships. We evaluate the proposed approach on public data sets and compare it with a bag‐of‐words–based approach and state‐of‐the‐art application of the Markov logic network for action recognition. The results demonstrate that the proposed approach produces better recognition accuracy.     

Structured learning of local features for human action classification and localization

Human action recognition is a promising yet non-trivial computer vision field with many potential applications. Current advances in bag-of-feature approaches have brought significant insights into recognizing human actions within complex context. It is, however, a common practice in literature to consider action as merely an orderless set of local salient features. This representation has been shown to be oversimplified, which inherently limits traditional approaches from robust deployment in real-life scenarios. In this work, we propose and show that, by taking into account global configuration of local features, we can greatly improve recognition performance. We first introduce a novel feature selection process called Sparse Hierarchical Bayes Filter to select only the most contributive features of each action type based on neighboring structure constraints. We then present the application of structured learning in human action analysis. That is, by representing human action as a complex set of local features, we can incorporate different spatial and temporal feature constraints into the learning tasks of human action classification and localization. In particular, we tackle the problem of action localization in video using structured learning with two alternatives: one is Dynamic Conditional Random Field from probabilistic perspective; the other is Structural Support Vector Machine from max-margin point of view. We evaluate our modular classification-localization framework on various testbeds, in which our proposed framework is proven to be highly effective and robust compared against bag-of-feature methods.     

The Minimal Structure and Motion Problems with Missing Data for 1D Retina Vision

In this paper we investigate the structure and motion problem for calibrated one-dimensional projections of a two-dimensional environment. The theory of one-dimensional cameras are useful in several areas, e.g. within robotics, autonomous guided vehicles, projection of lines in ordinary vision and vision of vehicles undergoing so called planar motion. In a previous paper the structure and motion problem for all cases with non-missing data was classified and solved. Our aim is here to classify all structure and motion problems, even those with missing data, and to solve them. In the classification we introduce the notion of a prime problem. A prime problem is a minimal problem that does not contain a minimal problem as a sub-problem. We further show that there are infinitely many such prime problems. We give solutions to four prime problems, and using the duality of Carlsson these can be extended to solutions of seven prime problems. Finally we give some experimental results based on synthetic data.     

Learning and parsing video events with goal and intent prediction

In this paper, we present a framework for parsing video events with stochastic Temporal And–Or Graph (T-AOG) and unsupervised learning of the T-AOG from video. This T-AOG represents a stochastic event grammar. The alphabet of the T-AOG consists of a set of grounded spatial relations including the poses of agents and their interactions with objects in the scene. The terminal nodes of the T-AOG are atomic actions which are specified by a number of grounded relations over image frames. An And-node represents a sequence of actions. An Or-node represents a number of alternative ways of such concatenations. The And–Or nodes in the T-AOG can generate a set of valid temporal configurations of atomic actions, which can be equivalently represented as the language of a stochastic context-free grammar (SCFG). For each And-node we model the temporal relations of its children nodes to distinguish events with similar structures but different temporal patterns and interpolate missing portions of events. This makes the T-AOG grammar context-sensitive. We propose an unsupervised learning algorithm to learn the atomic actions, the temporal relations and the And–Or nodes under the information projection principle in a coherent probabilistic framework. We also propose an event parsing algorithm based on the T-AOG which can understand events, infer the goal of agents, and predict their plausible intended actions. In comparison with existing methods, our paper makes the following contributions. (i) We represent events by a T-AOG with hierarchical compositions of events and the temporal relations between the sub-events. (ii) We learn the grammar, including atomic actions and temporal relations, automatically from the video data without manual supervision. (iii) Our algorithm infers the goal of agents and predicts their intents by a top-down process, handles events insertion and multi-agent events, keeps all possible interpretations of the video to preserve the ambiguities, and achieves the globally optimal parsing solution in a Bayesian framework. (iv) The algorithm uses event context to improve the detection of atomic actions, segment and recognize objects in the scene. Extensive experiments, including indoor and out door scenes, single and multiple agents events, are conducted to validate the effectiveness of the proposed approach.     

Diagnosing time-varying misbehavior: an approach based on model decomposition

The analysis of time-varying systems is attracting a lot of attention in the model-based diagnosis community. In this paper we propose an approach to the diagnosis of such systems, relying on a component-oriented model; we provide separately a behavioral model, that is, knowledge about the consequences of differentbehavioral modes of the components, and a model of the possible temporal evolution of such modes (mode transition graphs). In the basic approach, we assume that the consequences of behavioral modes are instantaneous with respect to the transition between two modes; this allows us to decompose the solution of a temporal diagnostic problem into two subtasks: determining solutions of atemporal problems in different time points and assembling the solution of the temporal problem from those of the atemporal ones. Most of the definitions and machinery developed for static diagnosis can be re-used in such a framework. We then consider the consequences of some extensions. Even allowing for very simple temporal relations in the behavioral model leads to a more complex interference between reasoning on the behavioral models and the consistency check with respect to possible temporal evolutions. We also briefly analyze the case of adding quantitative temporal knowledge or probabilistic knowledge to the mode transition graphs.This work was partially supported by CNR under grants 91.00916.PF69 and 91.02351.CT12.     

Self-recalibration of a structured light system via plane-based homography

Self-recalibration of the relative pose in a vision system plays a very important role in many applications and much research has been conducted on this issue over the years. However, most existing methods require information of some points in general three-dimensional positions for the calibration, which is hard to be met in many practical applications. In this paper, we present a new method for the self-recalibration of a structured light system by a single image in the presence of a planar surface in the scene. Assuming that the intrinsic parameters of the camera and the projector are known from initial calibration, we show that their relative position and orientation can be determined automatically from four projection correspondences between an image and a projection plane. In this method, analytical solutions are obtained from second order equations with a single variable and the optimization process is very fast. Another advantage is the enhanced robustness in implementation via the use of over constrained systems. Computer simulations and real data experiments are carried out to validate our method.     

NatureTime: Temporal Granularity in Simulation of Ecosystems

Granularity of time is an important issue for the understanding of how actions performed at coarse levels of time interact with others, working at finer levels. However, it has not received much attention from most AI work on temporal logic. In simpler domains of application we may not need to consider it a problem but it becomes important in more complex domains, such as ecological modelling. In this domain, aggregation of processes working at different time granularities (and sometimes cyclically) is very difficult to achieve reliably. We have proposed a new time granularity theory based onmodular temporal classes, and have developed a temporal reasoning system to specify cyclical processes of simulation models in ecology at many levels of time.     

Temporal XML: modeling, indexing, and query processing

In this paper we address the problem of modeling and implementing temporal data in XML. We propose a data model for tracking historical information in an XML document and for recovering the state of the document as of any given time. We study the temporal constraints imposed by the data model, and present algorithms for validating a temporal XML document against these constraints, along with methods for fixing inconsistent documents. In addition, we discuss different ways of mapping the abstract representation into a temporal XML document, and introduce TXPath, a temporal XML query language that extends XPath 2.0. In the second part of the paper, we present our approach for summarizing and indexing temporal XML documents. In particular we show that by indexing continuous paths, i.e., paths that are valid continuously during a certain interval in a temporal XML graph, we can dramatically increase query performance. To achieve this, we introduce a new class of summaries, denoted TSummary, that adds the time dimension to the well-known path summarization schemes. Within this framework, we present two new summaries: LCP and Interval summaries. The indexing scheme, denoted TempIndex, integrates these summaries with additional data structures. We give a query processing strategy based on TempIndex and a type of ancestor-descendant encoding, denoted temporal interval encoding. We present a persistent implementation of TempIndex, and a comparison against a system based on a non-temporal path index, and one based on DOM. Finally, we sketch a language for updates, and show that the cost of updating the index is compatible with real-world requirements.