This paper addresses the problem of activity and event discovery in multi dimensional time series data by proposing a novel method for locating multi dimensional motifs in time series. While recent work has been done in finding single dimensional and multi dimensional motifs in time series, we address motifs in general case, where the elements of multi dimensional motifs have temporal, length, and frequency variations. The proposed method is validated by synthetic data, and empirical evaluation has been done on several wearable systems that are used by real subjects.

Recently, online reputation mechanisms have been proposed that reward agents for honest feedback about products and services with fixed quality. Many real-world settings, however, are inherently dynamic. As an example, consider a web service that wishes to publish the expected download speed of a file mirrored on different server sites. In contrast to the models of Miller, Resnick and Zeckhauser and of Jurca and Faltings, the quality of the service (e. g., a server’s available bandwidth) changes over time and future agents are solely interested in the present quality levels. We show that hidden Markov models (HMM) provide natural generalizations of these static models and design a payment scheme that elicits honest reports from the agents after they have experienced the quality of the service.

We have developed a simulation model that accepts instructions in unconstrained natural language, and then guides a robot to the correct destination. The instructions are segmented on the basis of the actions to be taken, and each segment is labeled with the required action. This flat formulation reduces the problem to a sequential labeling task, to which machine learning methods are applied. We propose an innovativemachine learningmethod for explicitly modeling the actions described in instructions and integrating learning and inference about the physical environment. We obtained a corpus of 840 route instructions that experimenters verified as follow-able, given by people in building navigation situations. Using the four-fold cross validation, our experiments showed that the simulated robot reached the correct destination 88% of the time.

First order decision diagrams (FODD) were recently introduced as a compact knowledge representation expressing functions over relational structures. FODDs represent numerical functions that, when constrained to the Boolean range, use only existential quantification. Previous work developed a set of operations over FODDs, showed how they can be used to solve relational Markov decision processes (RMDP) using dynamic programming algorithms, and demonstrated their success in solving stochastic planning problems from the International Planning Competition in the system FODD-Planner. A crucial ingredient of this scheme is a set of operations to remove redundancy in decision diagrams, thus keeping them compact. This paper makes three contributions. First, we introduce Generalized FODDs (GFODD) and combination algorithms for them, generalizing FODDs to arbitrary quantification. Second, we show how GFODDs can be used in principle to solve RMDPs with arbitrary quantification, and develop a particularly promising case where an arbitrary number of existential quantifiers is followed by an arbitrary number of universal quantifiers. Third, we develop a new approach to reduce FODDs and GFODDs using model checking. This yields a reduction that is complete for FODDs and provides a sound reduction procedure for GFODDs.

A method for expressive melody synthesis is presented seeking to capture the prosodic (stress and directional) element of musical interpretation. An expressive performance is represented as a note-level annotation, classifying each note according to a small alphabet of symbols describing the role of the note within a larger context.  An audio performance of the melody is represented in terms of two time-varying functions describing the evolving frequency and intensity.  A method is presented that transforms the expressive annotation into the frequency and intensity functions, thus giving the audio performance. The problem of expressive rendering is then cast as estimation of the most likely sequence of hidden variables corresponding to the prosodic annotation. Examples are presented on a dataset of around 50 folk-like melodies, realized both from hand-marked and estimated annotations.

A common approach to the control problem in partially observable environments is to perform a direct search in policy space, as defined over some set of features of history. In this paper we consider predictive features, whose values are conditional probabilities of future events, given history. Since predictive features provide direct information about the agent's future, they have a number of advantages for control. However, unlike more typical features defined directly over past observations, it is not clear how to maintain the values of predictive features over time. A model could be used, since a model can make any prediction about the future, but in many cases learning a model is infeasible. In this paper we demonstrate that in some cases it is possible to learn to maintain the values of a set of predictive features even when a learning a model is infeasible, and that natural predictive features can be useful for policy-search methods.

The Canadian Traveler Problem (CTP) is a navigation problem where a graph is initially known,  but some edges may be blocked with a known probability.  The task is to minimize travel effort of reaching the goal. We generalize CTP to allow for remote sensing actions, now requiring minimization  of the sum of the travel cost and the remote sensing cost. Finding optimal policies for both versions is intractable. We provide optimal solutions for special case graphs. We then develop a framework that utilizes heuristics to determine when and where to sense the environment in order to minimize total costs. Several such heuristics, based on the expected total cost are introduced.  Empirical evaluations show the benefits of our heuristics and support some of the theoretical results.

We call this a topological structure [Dai and Goldsmith, 2007; Over the past few years, point-based POMDP Bonet and Geffner, 2003; Abbad and Boustique, 2003] and solvers scaled up to produce approximate solutions say that a problem has much topological structure when the to mid-sized domains. However, to solve real world problem state space has many layers. These characteristics problems, solvers must exploit the structure of the are embodied in many real-world applications including assembly domain. In this paper we focus on the topological line optimization; network routing; or railway traffic structure of the problem, where the state space control. Consider the assembly of a car that consists in multiple contains layers of states. We present here the Topological steps: first the car moves to the engine installation; then Order Planner (TOP) that utilizes the topological the engine installation crew checks for malfunctions; thereafter structure of the domain to compute belief finishing the engine installation the car moves respectively space trajectories. TOP rapidly produces trajectories to the hood and the wheel stations. Each transition focused on the solveable regions of the belief from a station to another is preceded by a quality measurement space, thus reducing the number of redundant backups procedure that prevents car malfunctions.

In many real-world situations we are charged with detecting change as soon as possible. Important examples include detecting medical conditions, detecting security breaches, and updating caches of distributed databases. In those situations, sensing can be expensive, but it is also important to detect change in a timely manner. In this paper we present tractable greedy algorithms and prove that they solve this decision problem either optimally or approximate the optimal solution in many cases. Our problem model is a POMDP that includes a cost for sensing, a cost for delayed detection, a reward for successful detection, and no-cost partial observations. Making optimal decisions is difficult in general. We show that our tractable greedy approach finds optimal policies for sensing both a single variable and multiple correlated variables. Further, we provide approximations for the optimal solution to multiple hidden or observed variables per step. Our algorithms outperform previous algorithms in experiments over simulated data and live Wikipedia WWW pages.

The recognition of the goal a user is pursing when interacting with a software application is a crucial task for an interface agent as it serves as a context for making opportune interventions to provide assistance to the user. The prediction of the user goal must be fast and a goal recognizer must be able to make early predictions with few observations of the user actions. In this work we propose an approach to automatically build an intention model from a plan corpus using Variable Order Markov models. We claim that following our approach, an interface agent will be capable of accurately ranking the most probable user goals in a time linear to the number of goals modeled.