Physical agility is a necessary skill in competitive table tennis, but by no means sufficient. Champions excel in this fast-paced and highly dynamic environment by anticipating their opponent’s intent – buying themselves the necessary time to react. In this work, we take one step towards designing such an anticipatory agent. Previous works have developed systems capable of real-time table tennis gameplay, though they often do not leverage anticipation. Among the works that forecast opponent actions, their approaches are limited by dataset size and variety. Our paper contributes (1) a scalable system for reconstructing monocular video of table tennis matches in 3D and (2) an uncertainty-aware controller that anticipates opponent actions. We demonstrate in simulation that our policy improves the ball return rate against high-speed hits from 49.9% to 59.0% as compared to a baseline non-anticipatory policy. Project website: https://sastry-group.github.io/LATTE-MV/

Reinforcement learning combined with sim-to-real transfer offers a general framework for developing locomotion controllers for legged robots. To facilitate successful deployment in the real world, smoothing techniques, such as low-pass filters and smoothness rewards, are often employed to develop policies with smooth behaviors. However, because these techniques are non-differentiable and usually require tedious tuning of a large set of hyperparameters, they tend to require extensive manual tuning for each robotic platform. To address this challenge and establish a general technique for enforcing smooth behaviors, we propose a simple and effective method that imposes a Lipschitz constraint on a learned policy, which we refer to as Lipschitz-Constrained Policies (LCP). We show that the Lipschitz constraint can be implemented in the form of a gradient penalty, which provides a differentiable objective that can be easily incorporated with automatic differentiation frameworks. We demonstrate that LCP effectively replaces the need for smoothing rewards or low-pass filters and can be easily integrated into training frameworks for many distinct humanoid robots. We extensively evaluate LCP in both simulation and real-world humanoid robots, producing smooth and robust locomotion controllers. All simulation and deployment code, along with complete checkpoints, is available on our project page: https://lipschitz-constrained-policy.github.io.

A common assumption for real-world, learnable data is its possession of some low-dimensional structure, and one way to formalize this structure is through the manifold hypothesis: that learnable data lies near some low-dimensional manifold. Deep learning architectures often have a compressive autoencoder component, where data is mapped to a lower-dimensional latent space, but often many architecture design choices are done by hand, since such models do not inherently exploit mathematical structure of the data. To utilize this geometric data structure, we propose an iterative process in the style of a geometric flow for explicitly constructing a pair of neural networks layer-wise that linearize and reconstruct an embedded submanifold, from finite samples of this manifold. Our such-generated neural networks, called Flattening Networks (FlatNet), are theoretically interpretable, computationally feasible at scale, and generalize well to test data, a balance not typically found in manifold-based learning methods. We present empirical results and comparisons to other models on synthetic high-dimensional manifold data and 2D image data. Our code is publicly available.

Min-max optimization is emerging as a key framework for analyzing problems of robustness to strategically and adversarially generated data. We propose the random reshuffling-based gradient-free Optimistic Gradient Descent-Ascent algorithm for solving convex-concave min-max problems with finite sum structure. We prove that the algorithm enjoys the same convergence rate as that of zeroth-order algorithms for convex minimization problems. We deploy the algorithm to solve the distributionally robust strategic classification problem, where gradient information is not readily available, by reformulating the latter into a finite dimensional convex concave min-max problem. Through illustrative simulations, we observe that our proposed approach learns models that are simultaneously robust against adversarial distribution shifts and strategic decisions from the data sources, and outperforms existing methods from the strategic classification literature.

We study the problem of online learning in competitive settings in the context of two-sided matching markets. In particular, one side of the market, the agents, must learn about their preferences over the other side, the firms, through repeated interaction while competing with other agents for successful matches. We propose a class of decentralized, communication- and coordination-free algorithms that agents can use to reach to their stable match in structured matching markets. In contrast to prior works, the proposed algorithms make decisions based solely on an agent's own history of play and requires no foreknowledge of the firms' preferences. Our algorithms are constructed by splitting up the statistical problem of learning one's preferences, from noisy observations, from the problem of competing for firms. We show that under realistic structural assumptions on the underlying preferences of the agents and firms, the proposed algorithms incur a regret which grows at most logarithmically in the time horizon. However, we note that in the worst case, it may grow exponentially in the size of the market.

Motion optimization for legible robot intent has largely ignored the robot’s dynamics, citing burdensome complexity that prevents online deployment. Even where the original task (to be communicated) could be solved on the dynamical system, the legibility problem (to communicate that task’s intent) could not. This work simplifies the legibility objective to have equivalent computational complexity as the original objective to be communicated. This enables any optimal control algorithm that can solve the original task to also solve the legible version of that task.Along the way, we expand the definition of "intent" to include any parameter of the optimal control problem, thereby opening the door to extend communications beyond merely desired end-points to running preferences or even, in the future, hard capabilities or safety constraints. We demonstrate how this method can replicate the properties introduced in previous communicative motion state-of-the-art (like legibility, exaggeration, and anticipation) as well as apply to non-holonomic dynamical systems.

As predictive models are deployed into the real world, they must increasingly contend with strategic behavior. A growing body of work on strategic classification treats this problem as a Stackelberg game: the decision-maker "leads" in the game by deploying a model, and the strategic agents "follow" by playing their best response to the deployed model. Importantly, in this framing, the burden of learning is placed solely on the decision-maker, while the agents’ best responses are implicitly treated as instantaneous. In this work, we argue that the order of play in strategic classification is fundamentally determined by the relative frequencies at which the decision-maker and the agents adapt to each other’s actions. In particular, by generalizing the standard model to allow both players to learn over time, we show that a decision-maker that makes updates faster than the agents can reverse the order of play, meaning that the agents lead and the decision-maker follows. We observe in standard learning settings that such a role reversal can be desirable for both the decision-maker and the strategic agents. Finally, we show that a decision-maker with the freedom to choose their update frequency can induce learning dynamics that converge to Stackelberg equilibria with either order of play.

Robots need models of human behavior for both inferring human goals and preferences, and predicting what people will do. A common model is the Boltzmann noisily-rational decision model, which assumes people approximately optimize a reward function and choose trajectories in proportion to their exponentiated reward. While this model has been successful in a variety of robotics domains, its roots lie in econometrics, and in modeling decisions among different discrete options, each with its own utility or reward. In contrast, human trajectories lie in a continuous space, with continuous-valued features that influence the reward function. We propose that it is time to rethink the Boltzmann model, and design it from the ground up to operate over such trajectory spaces. We introduce a model that explicitly accounts for distances between trajectories, rather than only their rewards. Rather than each trajectory affecting the decision independently, similar trajectories now affect the decision together. We start by showing that our model better explains human behavior in a user study. We then analyze the implications this has for robot inference, first in toy environments where we have ground truth and find more accurate inference, and finally for a 7DOF robot arm learning from user demonstrations.

We present a novel approach to control design for nonlinear systems which leverages model-free policy optimization techniques to learn a linearizing controller for a physical plant with unknown dynamics. Feedback linearization is a technique from nonlinear control which renders the input-output dynamics of a nonlinear plant linear under application of an appropriate feedback controller. Once a linearizing controller has been constructed, desired output trajectories for the nonlinear plant can be tracked using a variety of linear control techniques. However, the calculation of a linearizing controller requires a precise dynamics model for the system. As a result, model-based approaches for learning exact linearizing controllers generally require a simple, highly structured model of the system with easily identifiable parameters. In contrast, the model-free approach presented in this paper is able to approximate the linearizing controller for the plant using general function approximation architectures. Specifically, we formulate a continuous-time optimization problem over the parameters of a learned linearizing controller whose optima are the set of parameters which best linearize the plant. We derive conditions under which the learning problem is (strongly) convex and provide guarantees which ensure the true linearizing controller for the plant is recovered. We then discuss how model-free policy optimization algorithms can be used to solve a discrete-time approximation to the problem using data collected from the real-world plant. The utility of the framework is demonstrated in simulation and on a real-world robotic platform.

The actions of an autonomous vehicle on the road affect and are affected by those of other drivers, whether overtaking, negotiating a merge, or avoiding an accident. This mutual dependence, best captured by dynamic game theory, creates a strong coupling between the vehicle's planning and its predictions of other drivers' behavior, and constitutes an open problem with direct implications on the safety and viability of autonomous driving technology. Unfortunately, dynamic games are too computationally demanding to meet the real-time constraints of autonomous driving in its continuous state and action space. In this paper, we introduce a novel game-theoretic trajectory planning algorithm for autonomous driving, that enables real-time performance by hierarchically decomposing the underlying dynamic game into a long-horizon “strategic” game with simplified dynamics and full information structure, and a short-horizon “tactical” game with full dynamics and a simplified information structure. The value of the strategic game is used to guide the tactical planning, implicitly extending the planning horizon, pushing the local trajectory optimization closer to global solutions, and, most importantly, quantitatively accounting for the autonomous vehicle and the human driver's ability and incentives to influence each other. In addition, our approach admits non-deterministic models of human decision-making, rather than relying on perfectly rational predictions. Our results showcase richer, safer, and more effective autonomous behavior in comparison to existing techniques.

Despite growing attention in autonomy, there are still many open problems, including how autonomous vehicles will interact and communicate with other agents, such as human drivers and pedestrians. Unlike most approaches that focus on pedestrian detection and planning for collision avoidance, this paper considers modeling the interaction between human drivers and pedestrians and how it might influence map estimation, as a proxy for detection. We take a mapping inspired approach and incorporate people as sensors into mapping frameworks. By taking advantage of other agents' actions, we demonstrate how we can impute portions of the map that would otherwise be occluded. We evaluate our framework in human driving experiments and on real-world data, using occupancy grids and landmark-based mapping approaches. Our approach significantly improves overall environment awareness and outperforms standard mapping techniques.

When a human supervisor collaborates with a team of robots, the human's attention is divided, and cognitive resources are at a premium. We aim to optimize the distribution of these resources and the flow of attention. To this end, we propose the model of an idealized supervisor to describe human behavior. Such a supervisor employs a potentially inaccurate internal model of the the robots' dynamics to judge safety. We represent these safety judgements by constructing a safe set from this internal model using reachability theory. When a robot leaves this safe set, the idealized supervisor will intervene to assist, regardless of whether or not the robot remains objectively safe. False positives, where a human supervisor incorrectly judges a robot to be in danger, needlessly consume supervisor attention. In this work, we propose a method that decreases false positives by learning the supervisor's safe set and using that information to govern robot behavior. We prove that robots behaving according to our approach will reduce the occurrence of false positives for our idealized supervisor model. Furthermore, we empirically validate our approach with a user study that demonstrates a significant (p = 0.0328) reduction in false positives for our method compared to a baseline safety controller.

Training a neural network with the gradient descent algorithm gives rise to a discrete-time nonlinear dynamical system. Consequently, behaviors that are typically observed in these systems emerge during training, such as convergence to an orbit but not to a fixed point or dependence of convergence on the initialization. Step size of the algorithm plays a critical role in these behaviors: it determines the subset of the local optima that the algorithm can converge to, and it specifies the magnitude of the oscillations if the algorithm converges to an orbit. To elucidate the effects of the step size on training of neural networks, we study the gradient descent algorithm as a discrete-time dynamical system, and by analyzing the Lyapunov stability of different solutions, we show the relationship between the step size of the algorithm and the solutions that can be obtained with this algorithm. The results provide an explanation for several phenomena observed in practice, including the deterioration in the training error with increased depth, the hardness of estimating linear mappings with large singular values, and the distinct performance of deep residual networks.

In assistive teleoperation, an autonomous agent uses a prediction about a human user's intent to attempt to align the behavior of a controlled system with the human's goal, even if the human's own inputs are not perfectly aligned to that goal. Haptic Assistance achieves this effect by influencing the human through forces/torques applied to the human's control interface. In this work, we describe our method for creating such haptic assistance via Inverse Reinforcement Learning applied to successful task demonstrations. We then use our assistance method to examine the role that haptic feedback plays in assistive teleoperation. Through our user study, we find that when the assistance incorrectly predicts a user's intent, aiding the user via haptic feedback on their control interface, rather than directly modifying their input signal, is preferable and provides the user with a significantly greater sense of control over the system.

The Internet of Things (IoT) promises many advantages in the control and monitoring of physical systems from both efficacy and efficiency perspectives. However, in the wrong hands, the data might pose a privacy threat. In this article, we consider the tradeoff between the operational value of data collected in the IoT and the privacy of consumers. We present a general framework for quantifying this tradeoff in the IoT, and focus on a smart grid application for a proof of concept. In particular, we analyze the tradeoff between smart grid operations and how often data are collected by considering a realistic direct-load control example using thermostatically controlled loads, and we give simulation results to show how its performance degrades as the sampling frequency decreases. Additionally, we introduce a new privacy metric, which we call inferential privacy. This privacy metric assumes a strong adversary model and provides an upper bound on the adversary’s ability to infer a private parameter, independent of the algorithm he uses. Combining these two results allows us to directly consider the tradeoff between better operational performance and consumer privacy.

We address the problem of diagnosing and repairing specifications for hybrid systems, formalized in signal temporal logic (STL). Our focus is on automatic synthesis of controllers from specifications using model predictive control. We build on recent approaches that reduce the controller synthesis problem to solving one or more mixed integer linear programs (MILPs), where infeasibility of an MILP usually indicates unrealizability of the controller synthesis problem. Given an infeasible STL synthesis problem, we present algorithms that provide feedback on the reasons for unrealizability, and suggestions for making it realizable. Our algorithms are sound and complete relative to the synthesis algorithm, i.e., they provide a diagnosis that makes the synthesis problem infeasible, and always terminate with a non-trivial specification that is feasible using the chosen synthesis method, when such a solution exists. We demonstrate the effectiveness of our approach on controller synthesis for various cyber-physical systems, including an autonomous driving application and an aircraft electric power system.

Much of estimation of human internal state (goal, intentions, activities, preferences, etc.) is passive: an algorithm observes human actions and updates its estimate of human state. In this work, we embrace the fact that robot actions affect what humans do, and leverage it to improve state estimation. We enable robots to do active information gathering, by planning actions that probe the user in order to clarify their internal state. For instance, an autonomous car will plan to nudge into a human driver's lane to test their driving style. Results in simulation and in a user study suggest that active information gathering significantly outperforms passive state estimation.

Finding an informative subset of a large collection of data points or models is at the center of many problems in computer vision, recommender systems, bio/health informatics as well as image and natural language processing. Given pairwise dissimilarities between the elements of a 'source set' and a 'target set,' we consider the problem of finding a subset of the source set, called representatives or exemplars, that can efficiently describe the target set. We formulate the problem as a row-sparsity regularized trace minimization problem. Since the proposed formulation is, in general, NP-hard, we consider a convex relaxation. The solution of our optimization finds representatives and the assignment of each element of the target set to each representative, hence, obtaining a clustering. We analyze the solution of our proposed optimization as a function of the regularization parameter. We show that when the two sets jointly partition into multiple groups, our algorithm finds representatives from all groups and reveals clustering of the sets. In addition, we show that the proposed framework can effectively deal with outliers. Our algorithm works with arbitrary dissimilarities, which can be asymmetric or violate the triangle inequality. To efficiently implement our algorithm, we consider an Alternating Direction Method of Multipliers (ADMM) framework, which results in quadratic complexity in the problem size. We show that the ADMM implementation allows to parallelize the algorithm, hence further reducing the computational time. Finally, by experiments on real-world datasets, we show that our proposed algorithm improves the state of the art on the two problems of scene categorization using representative images and time-series modeling and segmentation using representative models.

This paper demonstrates the limitation of the flow-based travel time functions. This paper presents a density-based travel time function and further develops a fundamental model of travel time dynamics that is built from a given fundamental traffic relationship and vehicle characteristics. The travel time dynamics produce an asymmetric one-sided coupled system of hyperbolic partial differential equations, where the first equation represents the macroscopic traffic dynamics. The existence of the solution for the mathematical model is then presented. The main contribution of this paper is the mathematical development and analysis of the real-time model of travel time. Moreover, this paper also shows various intelligent transportation system applications where travel time is an important factor and where this new model would be extremely useful and important.

This paper presents and shows why density-based travel-time function is consistent with the fundamental diagram from traffic theory and then reviews the applications of travel time in intelligent transportation systems. This paper presents a density-based travel-time function that does not have the ill-posedness that is present in flow-based travel-time functions. The classic steady-state traffic assignment is cast using this new travel-time function, and corresponding mathematical programming formulations are proposed. It is shown that the modified Beckman formulation based on the density-based travel-time function provides a unique solution for link flows and link densities where the Wardrop condition has nonunique values for arc traffic densities.

In this paper, we consider the problem of energy disaggregation, i.e., decomposing a whole home electricity signal into its component appliances. We propose a new supervised algorithm, which in the learning stage, automatically extracts signature consumption patterns of each device by modeling the device as a mixture of dynamical systems. In order to extract signature consumption patterns of a device corresponding to its different modes of operation, we define appropriate dissimilarities between energy snippets of the device and use them in a subset selection scheme, which we generalize to deal with time-series data. We then form a dictionary that consists of extracted power signatures across all devices. We cast the disaggregation problem as an optimization over a representation in the learned dictionary and incorporate several novel priors such as device-sparsity, knowledge about devices that do or do not work together as well as temporal consistency of the disaggregated solution. Real experiments on a publicly available energy dataset demonstrate that our proposed algorithm achieves promising results for energy disaggregation.

We give an overview of the main challenges in the specification, design, and verification of human cyber-physical systems, with a special focus on semi-autonomous vehicles. We identify unique characteristics of formal modeling, specification, verification and synthesis in this domain. Some initial results and design principles are presented along with directions for future work.

We consider a reach-avoid differential game, in which one of the players aims to steer the system into a target set without violating a set of state constraints, while the other player tries to prevent the first from succeeding; the system dynamics, target set, and state constraints may all be time-varying. The analysis of this problem plays an important role in collision avoidance, motion planning and aircraft control, among other applications. Previous methods for computing the guaranteed winning initial conditions and strategies for each player have either required augmenting the state vector to include time, or have been limited to problems with either no state constraints or entirely static targets, constraints and dynamics. To incorporate time-varying dynamics, targets and constraints without the need for state augmentation, we propose a modified Hamilton-Jacobi-Isaacs equation in the form of a double-obstacle variational inequality, and prove that the zero sublevel set of its viscosity solution characterizes the capture basin for the target under the state constraints. Through this formulation, our method can compute the capture basin and winning strategies for time-varying games at virtually no additional computational cost relative to the time-invariant case. We provide an implementation of this method based on well-known numerical schemes and show its convergence through a simple example; we include a second example in which our method substantially outperforms the state augmentation approach.

We present a framework for parameter and state estimation of personalized human kinematic models from motion capture data. These models can be used to optimize a variety of human-robot collaboration scenarios for the comfort or ergonomics of an individual human collaborator. Our approach offers two main advantages over prior approaches from the literature and commercial software: the kinematic models are estimated for a specific individual without a priori assumptions on limb dimensions or range of motion, and our kinematic formalism explicitly encodes the natural kinematic constraints of the human body. The personalized models are tested in a human-robot collaborative manipulation experiment. We find that human subjects with a restricted range of motion rotate their torso significantly less during bimanual object handoffs if the robot uses a personalized kinematic model to plan the handoff configuration, as compared to previous approaches using generic human kinematic models.

Existing commercial driver assistance systems, including automatic braking systems and lane-keeping systems, may monitor the state of the vehicle or the environment to determine whether the systems should intervene. However, the state of the human driver is not typically included in the decision making process. In this paper, we propose to use hidden mode stochastic hybrid systems to model the interaction between the human driver and the vehicle. We show that by monitoring the human behavior as well as the vehicle state, we can infer the human state and enhance the quality of decision making in a driver assistance system. The resulting control policy is obtained by solving an optimal planning problem of the proposed hidden mode hybrid system. The policy can automatically balance the decision making about when to give warning to the driver and when to actually intervene in the control of the vehicle.

This paper presents a feedback control design for a coordinated ramp metering problem for two consecutive on-ramps. We design a traffic allocation scheme for ramps based on Godunov's numerical method and using a distributive model. Most of the previous work for designing feedback control for ramp metering is based on either the discretized linear methods or nonlinear methods based on the traffic ordinary differential equations (ODEs). We utilize the distributive model to construct a control condition for regulating the traffic density at critical density. Then, we design a Godunov-method-based satisfiable allocation scheme that gives us the actual control for each ramp individually. We show the stability properties of the closed-loop system and validate the effectiveness of the feedback control law by running a simulation using real traffic flow measurements with parameter estimation.

This paper provides a model-based method for analysis and hypothesis testing for paired data where one source of data has to be validated against another source of data that contains subjective and dynamic errors. This study deals with human-observed flow counts collected from traffic videos of freeway cameras. The available videos are mainly used for the purpose of manual observation by transportation personnel in case of emergency. This amounts to a varying inconsistency of the quality of the videos, which presents an additional challenge when analyzing the data. Video processing cannot be performed due to the mentioned issues with regard to the video quality. The processing has to be manually performed by humans who unfortunately have an inherent bias. If the video data have to be used for validating flow detector sensors, then a technique that performs validation with subjective and dynamic erroneous data as a result of the human bias is needed. This paper presents a methodology to deal with this issue. It is based on statistical testing with heteroscedasticity, which is demonstrated through a case study using data from traffic flow detectors and traffic cameras installed on highways in the Southern Nevada Region. A model for the relationship between the video ratings and the distribution of the human errors is developed taking into consideration the human bias. A method for identification of faulty detectors is also demonstrated based on the developed technique.

Automatic recognition of human actions in video has been a highly addressed problem in robotics and computer vision. Majority of the recent work in literature has focused on classifying pre-segmented video clips, and some progress has also been made on joint detection and recognition of actions in complex video sequences. These methods, however, are not designed for wireless camera networks where the sensors have limited internal processing and communication capabilities. In this paper we present an efficient system for the joint detection and recognition of human actions using a network of wireless smart cameras. The foundation of our work is based on Deformable Part Models (DPMs) for detecting objects in static images. We have extended this framework to the single-view and multi-view video setting to jointly detect and recognize actions. We call this the Deformable Keyframe Model (DKM) and tightly integrate it within a centralized video analysis system. In our system, feature extraction is locally performed on-board wireless smart cameras, and the classification is performed at a base station with higher processing power. Our analysis demonstrates that this decoupling of the the recognition pipeline can significantly minimize the power and bandwidth consumed by the wireless cameras. We experimentally validate our DKMs on two data sets. We first demonstrate the competitiveness of our algorithm by comparing its performance against other state-of-the-art methods, on a publicly available dataset. Then, we extensively validate our system on a novel dataset called the Bosch Multiview Complex Action (BMCA) dataset. Our dataset consists of 11 actions continuously performed by 20 different subjects while being captured by cameras located at 4 different vantage points. In our experiments, we demonstrate that the presence of multiple-views improves the performance of action detection and recognition by about 15% over the single-view setting.

This paper presents the detailed analysis of a Godunov-approximation-based dynamics model for an isolated traffic ramp metering problem. The model for the system is based on a Godunov numerical scheme so that the lumped parameter approximation retains the weak solution shock and rarefaction wave properties exhibited by the distributed model. This paper explicitly considers uncertainty in the system parameters and shows how to design controllers that are robust to those uncertainties. Simulations are performed to show the effectiveness of the proposed control law.

Mobile data traffic has been steadily rising in the past years. This has generated a significant interest in the deployment of incentive mechanisms to reduce peak-time congestion. Typically, the design of these mechanisms requires information about user demand and sensitivity to prices. Such information is naturally imperfect. In this paper, we propose a fixed-budget rebate mechanism that gives each user a reward proportional to his percentage contribution to the aggregate reduction in peak-time demand. For comparison, we also study a time-of-day pricing mechanism that gives each user a fixed reward per unit reduction of his peak-time demand. To evaluate the two mechanisms, we introduce a game-theoretic model that captures the public good nature of decongestion. For each mechanism, we demonstrate that the socially optimal level of decongestion is achievable for a specific choice of the mechanism's parameter. We then investigate how imperfect information about user demand affects the mechanisms' effectiveness. From our results, the fixed-budget rebate pricing is more robust when the users' sensitivity to congestion is “sufficiently” convex. This feature of the fixed-budget rebate mechanism is attractive for many situations of interest and is driven by its closed-loop property, i.e., the unit reward decreases as the peak-time demand decreases.

Single-sample face recognition is one of the most challenging problems in face recognition. We propose a novel face recognition algorithm to address this problem based on a sparse representation based classification (SRC) framework. The new algorithm is robust to image misalignment and pixel corruption, and is able to reduce required training images to one sample per class. To compensate the missing illumination information typically provided by multiple training images, a sparse illumination transfer (SIT) technique is introduced. The SIT algorithms seek additional illumination examples of face images from one or more additional subject classes, and form an illumination dictionary. By enforcing a sparse representation of the query image, the method can recover and transfer the pose and illumination information from the alignment stage to the recognition stage. Our extensive experiments have demonstrated that the new algorithms significantly outperform the existing algorithms in the single-sample regime and with less restrictions. In particular, the face alignment accuracy is comparable to that of the well-known Deformable SRC algorithm using multiple training images, and the face recognition accuracy exceeds those of the SRC and Extended SRC algorithms using hand labeled alignment initialization.

The classical shift retrieval problem considers two signals in vector form that are related by a cyclic shift. In this paper, we develop a compressive variant where the measurement of the signals is undersampled. While the standard procedure to shift retrieval is to maximize the real part of their dot product, we show that the shift can be exactly recovered from the corresponding compressed measurements if the sensing matrix satisfies certain conditions. A special case is the partial Fourier matrix. In this setting we show that the true shift can be found by as low as two measurements. We further show that the shift can often be recovered when the measurements are perturbed by noise.

In many image/video/web classification problems, we have access to a large number of unlabeled samples. However, it is typically expensive and time consuming to obtain labels for the samples. Active learning is the problem of progressively selecting and annotating the most informative unlabeled samples, in order to obtain a high classification performance. Most existing active learning algorithms select only one sample at a time prior to retraining the classifier. Hence, they are computationally expensive and cannot take advantage of parallel labeling systems such as Mechanical Turk. On the other hand, algorithms that allow the selection of multiple samples prior to retraining the classifier, may select samples that have significant information overlap or they involve solving a non-convex optimization. More importantly, the majority of active learning algorithms are developed for a certain classifier type such as SVM. In this paper, we develop an efficient active learning framework based on convex programming, which can select multiple samples at a time for annotation. Unlike the state of the art, our algorithm can be used in conjunction with any type of classifiers, including those of the family of the recently proposed Sparse Representation-based Classification (SRC). We use the two principles of classifier uncertainty and sample diversity in order to guide the optimization program towards selecting the most informative unlabeled samples, which have the least information overlap. Our method can incorporate the data distribution in the selection process by using the appropriate dissimilarity between pairs of samples. We show the effectiveness of our framework in person detection, scene categorization and face recognition on real-world datasets.

l1-minimization refers to finding the minimum l1-norm solution to an underdetermined linear system [Formula: see text]. Under certain conditions as described in compressive sensing theory, the minimum l1-norm solution is also the sparsest solution. In this paper, we study the speed and scalability of its algorithms. In particular, we focus on the numerical implementation of a sparsity-based classification framework in robust face recognition, where sparse representation is sought to recover human identities from high-dimensional facial images that may be corrupted by illumination, facial disguise, and pose variation. Although the underlying numerical problem is a linear program, traditional algorithms are known to suffer poor scalability for large-scale applications. We investigate a new solution based on a classical convex optimization framework, known as augmented Lagrangian methods. We conduct extensive experiments to validate and compare its performance against several popular l1-minimization solvers, including interior-point method, Homotopy, FISTA, SESOP-PCD, approximate message passing, and TFOCS. To aid peer evaluation, the code for all the algorithms has been made publicly available.

Smart camera networks have recently emerged as a new class of sensor network infrastructure that is capable of supporting high-power in-network signal processing and enabling a wide range of applications. In this article, we provide an exposition of our efforts to build a low-bandwidth wireless camera network platform, called CITRIC, and its applications in smart camera networks. The platform integrates a camera, a microphone, a frequency-scalable (up to 624 MHz) CPU, 16 MB FLASH, and 64 MB RAM onto a single device. The device then connects with a standard sensor network mote to form a wireless camera mote. With reasonably low power consumption and extensive algorithmic libraries running on a decent operating system that is easy to program, CITRIC is ideal for research and applications in distributed image and video processing. Its capabilities of in-network image processing also reduce communication requirements, which has been high in other existing camera networks with centralized processing. Furthermore, the mote easily integrates with other low-bandwidth sensor networks via the IEEE 802.15.4 protocol. To justify the utility of CITRIC, we present several representative applications. In particular, concrete research results will be demonstrated in two areas, namely, distributed coverage hole identification and distributed object recognition.

We present a novel primal-dual analysis on a class of NP-hard sparsity minimization problems to provide new interpretations for their well known convex relaxations. We show that the Lagrangian bidual (i.e., the Lagrangian dual of the Lagrangian dual) of the sparsity minimization problems can be used to derive interesting convex relaxations: the bidual of the ℓ0-minimization problem is ℓ1-minimization; and the bidual of ℓ0,1-minimization for enforcing group sparsity on structured data is ℓ1,∞-minimization problem. Intuitions from the bidual-based relaxation are used to introduce a new family of relaxations for the group sparsity minimization problem.

While compressive sensing (CS) has been one of the most vibrant and active research fields in the past few years, most development only applies to linear models. This limits its application and excludes many areas where CS ideas could make a difference. This paper presents a novel extension of CS to the phase retrieval problem, where intensity measurements of a linear system are used to recover a complex sparse signal. We propose a novel solution using a lifting technique -- CPRL, which relaxes the NP-hard problem to a nonsmooth semidefinite program. Our analysis shows that CPRL inherits many desirable properties from CS, such as guarantees for exact recovery. We further provide scalable numerical solvers to accelerate its implementation. The source code of our algorithms will be provided to the public.

Bag-of-words (BoW) methods are a popular class of object recognition methods that use image features (e.g., SIFT) to form visual dictionaries and subsequent histogram vectors to represent object images in the recognition process. The accuracy of the BoW classifiers, however, is often limited by the presence of uninformative features extracted from the background or irrelevant image segments. Most existing solutions to prune out uninformative features rely on enforcing pairwise epipolar geometry via an expensive structure-from-motion (SfM) procedure. Such solutions are known to break down easily when the camera transformation is large or when the features are extracted from low-resolution, low-quality images. In this paper, we propose a novel method to select informative object features using a more efficient algorithm called Sparse PCA. First, we show that using a large-scale multiple-view object database, informative features can be reliably identified from a highdimensional visual dictionary by applying Sparse PCA on the histograms of each object category. Our experiment shows that the new algorithm improves recognition accuracy compared to the traditional BoW methods and SfM methods. Second, we present a new solution to Sparse PCA as a semidefinite programming problem using the Augmented Lagrangian Method. The new solver outperforms the state of the art for estimating sparse principal vectors as a basis for a low-dimensional subspace model.

This paper presents recent advances in multiagent sensing and operation in dynamic environments. Technology trends point towards a fusion of wireless sensor networks with robotic swarms of mobile robots. In this paper, we discuss the coordination and collaboration between networked robotic systems, featuring algorithms for cooperative operations such as unmanned aerial vehicles (UAVs) swarming. We have developed cooperative actions of groups of agents such as probabilistic pursuit-evasion game for search and rescue operations, protection of resources, and security applications. We have demonstrated a hierarchical system architecture which provides wide-range sensing capabilities to unmanned vehicles through spatially deployed wireless sensor networks, highlighting the potential collaboration between wireless sensor networks and unmanned vehicles. This paper also includes a short review of our current research efforts in heterogeneous sensor networks, which is being evolved into mobile sensor networks with swarm mobility. In a very essential way, this represents the fusion of mobility of ensembles with the network embedded systems, the robotic sensor web.

This article investigates the vulnerabilities of Supervisory Control and Data Acquisition (SCADA) systems which monitor and control the modern day irrigation canal systems.\nThis type of monitoring and control infrastructure is also common for many other water distribution systems. We present a linearized shallow water partial differential equation (PDE) system that can model water flow in a network of canal pools which are equipped with lateral offtakes for water withdrawal and are connected by automated gates. The knowledge of the system dynamics enables us to develop a deception attack scheme based on switching the PDE parameters and proportional (P) boundary control actions, to withdraw water from the pools through offtakes. We briefly discuss the limits on detectability of such attacks. We use a known formulation based on low frequency approximation of the PDE model and an associated proportional integral (PI) controller, to create a stealthy deception scheme capable of compromising the performance of the closed-loop system. We test the proposed attack scheme in simulation, using a shallow water solver; and show that the attack is indeed realizable in practice by implementing it on a physical canal in Southern France: the Gignac canal. A successful field experiment shows that the attack scheme enables us to steal water stealthily from the canal until the end of the attack.

Analysis of stability and stabilizability of switched linear systems is a well-researched topic. This article pursues a polar coordinate approach which offers a convenient framework to analyze second-order continuous time switched linear systems. We elaborate on the analytic utility of polar coordinates and present necessary and sufficient conditions under which a stabilizing switched control law can be constructed. Implications of polar coordinate analysis for switched linear systems include sensitivity analysis of switching control laws and the design of oscillators.

One of the oldest problems in the study of dynamical systems is the calculation of an optimal control. Though the determination of a numerical solution for the general non-convex optimal control problem for hybrid systems has been pursued relentlessly to date, it has proven difficult, since it demands nominal mode scheduling. In this paper, we calculate a numerical solution to the optimal control problem for a constrained switched nonlinear dynamical system with a running and final cost. The control parameter has a discrete component, the sequence of modes, and two continuous components, the duration of each mode and the continuous input while in each mode. To overcome the complexity posed by the discrete optimization problem, we propose a bi-level hierarchical optimization algorithm: at the higher level, the algorithm updates the mode sequence by using a single-mode variation technique, and at the lower level, the algorithm considers a fixed mode sequence and minimizes the cost functional over the continuous components. Numerical examples detail the potential of our proposed methodology.

We provide a comprehensive review of five representative ℓ1-minimization methods, i.e., gradient projection, homotopy, iterative shrinkage-thresholding, proximal gradient, and augmented Lagrange multiplier. The repository is intended to fill in a gap in the existing literature to systematically benchmark the performance of these algorithms using a consistent experimental setting. The experiment will be focused on the application of face recognition, where a sparse representation framework has recently been developed to recover human identities from facial images that may be affected by illumination change, occlusion, and facial disguise. The paper also provides useful guidelines to practitioners working in similar fields.

An application of compressive sensing (CS) theory in imagebased robust face recognition is considered. Most contemporary face recognition systems suffer from limited abilities to handle image nuisances such as illumination, facial disguise, and pose misalignment. Motivated by CS, the problem has been recently cast in a sparse representation framework: The sparsest linear combination of a query image is sought using all prior training images as an overcomplete dictionary, and the dominant sparse coefficients reveal the identity of the query image. The ability to perform dense error correction directly in the image space also provides an intriguing solution to compensate pixel corruption and improve the recognition accuracy exceeding most existing solutions. Furthermore, a local iterative process can be applied to solve for an image transformation applied to the face region when the query image is misaligned. Finally, we discuss the state of the art in fast ℓ1-minimization to improve the speed of the robust face recognition system. The paper also provides useful guidelines to practitioners working in similar fields, such as acoustic/speech recognition. Index Terms: face recognition, compressive sensing, ℓ1minimization 1.

This paper studies segmentation of multiple rigid-body motions in a 3-D dynamic scene under perspective camera projection. We consider dynamic scenes that contain both 3-D rigid-body structures and 2-D planar structures. Based on the well-known epipolar and homography constraints between two views, we propose a hybrid perspective constraint (HPC) to unify the representation of rigid-body and planar motions. Given a mixture of K hybrid perspective constraints, we propose an algebraic process to partition image correspondences to the individual 3-D motions, called Robust Algebraic Segmentation (RAS). Particularly, we prove that the joint distribution of image correspondences is uniquely determined by a set of (2K)-th degree polynomials, a global signature for the union of K motions of possibly mixed type. The first and second derivatives of these polynomials provide a means to recover the association of the individual image samples to their respective motions. Finally, using robust statistics, we show that the polynomials can be robustly estimated in the presence of moderate image noise and outliers. We conduct extensive simulations and real experiments to validate the performance of the new algorithm. The results demonstrate that RAS achieves notably higher accuracy than most existing robust motion-segmentation methods, including random sample consensus (RANSAC) and its variations. The implementation of the algorithm is also two to three times faster than the existing methods. The implementation of the algorithm and the benchmark scripts are available at http://perception.csl.illinois.edu/ras/ .

In this paper, sensor network scenarios are considered where the underlying signals of interest exhibit a degree of sparsity, which means that in an appropriate basis, they can be expressed in terms of a small number of nonzero coefficients. Following the emerging theory of compressive sensing (CS), an overall architecture is considered where the sensors acquire potentially noisy projections of the data, and the underlying sparsity is exploited to recover useful information about the signals of interest, which will be referred to as distributed sensor perception. First, we discuss the question of which projections of the data should be acquired, and how many of them. Then, we discuss how to take advantage of possible joint sparsity of the signals acquired by multiple sensors, and show how this can further improve the inference of the events from the sensor network. Two practical sensor applications are demonstrated, namely, distributed wearable action recognition using low-power motion sensors and distributed object recognition using high-power camera sensors. Experimental data support the utility of the CS framework in distributed sensor perception.

Sensor networks have been widely used for surveillance, monitoring, and tracking. Camera networks, in particular, provide a large amount of information that has traditionally been processed in a centralized manner employing a priori knowledge of camera location and of the physical layout of the environment. Unfortunately, these conventional requirements are far too demanding for ad-hoc distributed networks. In this article, we present a simplicial representation of a camera network called the camera network complex ( CN-complex), that accurately captures topological information about the visual coverage of the network. This representation provides a coordinate-free calibration of the sensor network and demands no localization of the cameras or objects in the environment. A distributed, robust algorithm, validated via two experimental setups, is presented for the construction of the representation using only binary detection information. We demonstrate the utility of this representation in capturing holes in the coverage, performing tracking of agents, and identifying homotopic paths.

Robotic manipulators on ships and platforms suffer from large inertial forces due to the non-inertial motion of the ship or platform. When operating in high sea state, operation of such manipulators can be made more efficient and robust if these non-inertial effects are taken into account in the motion planning and control systems. Motivated by this application, we present a rigorous and singularity-free formulation of the dynamics of a robotic manipulator mounted on a non-inertial base. We extend the classical dynamics equations for a serial manipulator to include the 6-DoF motion of the non-inertial base. Then, we show two examples of a 1-DoF and a 4-DoF manipulator to illustrate how these non-inertial effects can be taken into account in the motion planning.

We consider the problem of automatically recognizing human faces from frontal views with varying expression and illumination, as well as occlusion and disguise. We cast the recognition problem as one of classifying among multiple linear regression models and argue that new theory from sparse signal representation offers the key to addressing this problem. Based on a sparse representation computed by l{1}-minimization, we propose a general classification algorithm for (image-based) object recognition. This new framework provides new insights into two crucial issues in face recognition: feature extraction and robustness to occlusion. For feature extraction, we show that if sparsity in the recognition problem is properly harnessed, the choice of features is no longer critical. What is critical, however, is whether the number of features is sufficiently large and whether the sparse representation is correctly computed. Unconventional features such as downsampled images and random projections perform just as well as conventional features such as Eigenfaces and Laplacianfaces, as long as the dimension of the feature space surpasses certain threshold, predicted by the theory of sparse representation. This framework can handle errors due to occlusion and corruption uniformly by exploiting the fact that these errors are often sparse with respect to the standard (pixel) basis. The theory of sparse representation helps predict how much occlusion the recognition algorithm can handle and how to choose the training images to maximize robustness to occlusion. We conduct extensive experiments on publicly available databases to verify the efficacy of the proposed algorithm and corroborate the above claims.

The impact of model-based design on the software engineering community is impressive, and recent research in model transformations, and elegant behavioral specifications of systems has the potential to revolutionize the way in which systems are designed. Such techniques aim to raise the level of abstraction at which systems are specified, to remove the burden of producing application-specific programs with general-purpose programming. For complex real-time systems, however, the impact of model-driven approaches is not nearly so widespread. In this paper, we present a perspective of model-based design researchers who joined with software experts in robotics to enter the DARPA Urban Challenge, and to what extent model-based design techniques were used. Further, we speculate on why, according to our experience and the testimonies of many teams, the full promises of model-based design were not widely realized for the competition. Finally, we present some thoughts for the future of model-based design in complex systems such as these, and what advancements in modeling are needed to motivate small-scale projects to use model-based design in these domains.

Human movement models often divide movements into parts. In walking, the stride can be segmented into four different parts, and in golf and other sports, the swing is divided into sections based on the primary direction of motion. These parts are often divided based on key events, also called temporal parameters. When analyzing a movement, it is important to correctly locate these key events, and so automated techniques are needed. There exist many methods for dividing specific actions using data from specific sensors, but for new sensors or sensing positions, new techniques must be developed. We introduce a generic method for temporal parameter extraction called the hidden Markov event model based on hidden Markov models. Our method constrains the state structure to facilitate precise location of key events. This method can be quickly adapted to new movements and new sensors/sensor placements. Furthermore, it generalizes well to subjects not used for training. A multiobjective optimization technique using genetic algorithms is applied to decrease error and increase cross-subject generalizability. Further, collaborative techniques are explored. We validate this method on a walking dataset by using inertial sensors placed on various locations on a human body. Our technique is designed to be computationally complex for training, but computationally simple at runtime to allow deployment on resource-constrained sensor nodes.

Due to standardization and connectivity to other networks, networked control systems, a vital component of many nations' critical infrastructures, face potential disruption. Its possible manifestation can affect Kalman filter, the primary recursive estimation method used in control engineering field. Whereas to improve such estimation, data fusion may take place at a central location to fuse and process multiple sensor measurements delivered over the network. In a uncertain networked control system where the nodes and links are subject to attacks, false or compromised or missing individual readings can produce skewed result. To assure the validity of data fusion, this paper proposes a centralized trust rating system that evaluates the trustworthiness of each sensor reading on top of the fusion mechanism. The ratings are represented by Beta distribution, the conjugate prior of the binomial distribution and its posterior. Then an illustrative example demonstrates its efficiency.

The paper describes a target tracking system running on a heterogeneous sensor network (HSN) and presents results gathered from a realistic deployment. The system fuses audio direction of arrival data from mote class devices and object detection measurements from embedded PCs equipped with cameras. The acoustic sensor nodes perform beamforming and measure the energy as a function of the angle. The camera nodes detect moving objects and estimate their angle. The sensor detections are sent to a centralized sensor fusion node via a combination of two wireless networks. The novelty of our system is the unique combination of target tracking methods customized for the application at hand and their implementation on an actual HSN platform.

Bevel-tip flexible needles have greater mobility than straight rigid needles, and can be used to reach targets behind sensitive or impenetrable areas. Accurately planning and executing the optimal motions for such steerable needles is difficult, however, and requires solving inverse kinematics for a nonholonomic system.This paper presents an approach to 3D motion planning for bevel-tip needles in an environment with obstacles. Instead of discretizing the configuration space as in earlier work, we discretize the control space, such that the trajectory of the needle can be expressed analytically without the need for approximate numerical simulation. This results in a fast optimization routine that finds a locally optimal path in a 3D environment with obstacles, requiring just a few seconds of computation time on a standard PC.We introduce two different discretization strategies that lead to differently structured paths and show that both produce valid trajectories from start to goal. To our knowledge, the presented method is the first to address motion planning for bevel-tip needles in a 3D environment with obstacles.

This paper studies an active steering problem of unmanned ground vehicles (UGVs) when avoiding obstacles during sensor based navigation in unknown environments. The overall problem is treated using the nonlinear model predictive framework, in which the sensor information of a limited sensing range is incorporated online. Results show that the introduction of the modified parallax effectively reflects the threat of obstacles and consequently achieves safe navigation in unknown environments satisfying dynamic constraints.

A fundamental building block in distributed wireless sensor networks is time synchronization. Given resource constrained nature of sensor networks, previous research has focused on developing various energy efficient time synchronization protocols tailored for these networks. However, many of these protocols have not been designed with security in mind. In this paper, we describe FTSP which is one of the major time synchronization protocols for sensor networks. We outline the adverse effects of the time synchronization attacks on some important sensor network applications, and explain the set of possible attacks on FTSP. We then propose a number of countermeasures to mitigate the effect of the security attacks. We implement these attack scenarios on a sensor network testbed and show the extent each attack is successful in desynchronizing the network. Finally, we implement the countermeasures on our sensor network testbed to validate their usefulness in mitigating security attacks. We show that adding a sequence number filter to the original FTSP helps mitigate the effect of attacks on this protocol.

We present a compressed domain scheme that is able to recognize and localize actions at high speeds. The recognition problem is posed as performing an action video query on a test video sequence. Our method is based on computing motion similarity using compressed domain features which can be extracted with low complexity. We introduce a novel motion correlation measure that takes into account differences in motion directions and magnitudes. Our method is appearance-invariant, requires no prior segmentation, alignment or stabilization, and is able to localize actions in both space and time. We evaluated our method on a benchmark action video database consisting of six actions performed by 25 people under three different scenarios. Our proposed method achieved a classification accuracy of 90%, comparing favorably with existing methods in action classification accuracy, and is able to localize a template video of 80 x 64 pixels with 23 frames in a test video of 368 x 184 pixels with 835 frames in just 11 s, easily outperforming other methods in localization speed. We also perform a systematic investigation of the effects of various encoding options on our proposed approach. In particular, we present results on the compression-classification tradeoff, which would provide valuable insight into jointly designing a system that performs video encoding at the camera front-end and action classification at the processing back-end.

Many of the routing protocols that have been designed for wireless ad-hoc networks focus on energy-efficiency and guaranteeing high throughput in a non-adversarial setting. However, given that ad-hoc and sensor networks are deployed and left unattended for long periods of time, it is crucial to design secure routing protocols for these networks. Over the past few years, attacks on the routing protocols have been studied and a number of secure routing protocols have been designed for wireless sensor networks. However, there has not been a comprehensive study of how these protocols compare in terms of achieving security goals and maintaining high throughput. In this paper, we focus on the problem of analyzing the inherent security of routing protocols with respect to two categories: multi-path and single-path routing. Within each category, we focus on deterministic vs. probabilistic mechanisms for setting up the routes. We consider the scenario in which an adversary has subverted a subset of the nodes, and as a result, the paths going through these nodes are compromised. We present our findings through simulation results.

Many signal processing applications of graphical models require efficient methods for computing (approximate) marginal probabilities over subsets of nodes in the graph. The intractability of this marginalization problem for general graphs with cycles motivates the use of approximate message-passing algorithms, including the sum-product algorithm and variants thereof. This paper studies the convergence and stability properties of the family of reweighted sum-product algorithms, a generalization of the standard updates in which messages are adjusted with graph-dependent weights. For homogenous models, we provide a complete characterization of the potential settings and message weightings that guarantee uniqueness of fixed points, and convergence of the updates. For more general inhomogeneous models, we derive a set of sufficient conditions that ensure convergence, and provide estimates of rates. These theoretical results are complemented with experimental simulations on various classes of graphs.

Camera networks are being used in more applications as different types of sensor networks are used to instrument large spaces. Here we show a method for localizing the cameras in a camera network to recover the orientation and position up to scale of each camera, even when cameras are wide-baseline or have different photometric properties. Using moving objects in the scene, we use an intra-camera step and an inter-camera step in order to localize. The intra-camera step compares frames from a single camera to build the tracks of the objects in the image plane of the camera. The inter-camera step uses these object image tracks from each camera as features for correspondence between cameras. We demonstrate this idea on both simulated and real data.

In this paper, we present a vision-based terrain mapping and analysis system, and a model predictive control (MPC)-based flight control system, for autonomous landing of a helicopter-based unmanned aerial vehicle (UAV) in unknown terrain. The vision system is centered around Geyer et al.'s recursive multi-frame planar parallax algorithm (2006), which accurately estimates 3D structure using geo-referenced images from a single camera, as well as a modular and efficient mapping and terrain analysis module. The vision system determines the best trajectory to cover large areas of terrain or to perform closer inspection of potential landing sites, and the flight control system guides the vehicle through the requested flight pattern by tracking the reference trajectory as computed by a real-time MPC-based optimization. This trajectory layer, which uses a constrained system model, provides an abstraction between the vision system and the vehicle. Both vision and flight control results are given from flight tests with an electric UAV.

One of the potential benefits of robotic systems in cardiac surgery is that their use can increase the number of possible off-pump (beating heart) coronary artery bypass grafting procedures. Robotic systems can actively synchronize the motion of surgical tools to the motion of the surface of the heart, with the surgeon specifying only the relative motion of the tool with respect to the heart. Accurate prediction of the motion of the heart surface is obviously of crucial importance for the safety and robustness of such a system. This paper presents a novel approach to predict the motion of the surface of a beating heart. We show how ECG and respiratory information can be used to extract two periodic components from the quasi-periodic motion of the heart surface. Contrary to most existing literature, we consider the full geometric motion, including rotation due to respiration. We then show how to combine the periodic components to accurately predict future motion of the heart surface, and how this information can be used to design an explicit controller that asymptotically stabilizes the relative motion of the surgical tool to a desired relative distance and orientation.

To address privacy concerns with digital video surveillance cameras, we propose a practical, real-time approach that preserves the ability to observe actions while obscuring individual identities. In our proposed respectful cameras system, people who wish to remain anonymous agree to wear colored markers such as a hat or vest. The system automatically tracks these markers using statistical learning and classification to infer the location and size of each face and then inserts elliptical overlays. Our objective is to obscure the face of each individual wearing a marker, while minimizing the overlay area in order to maximize the remaining observable region of the scene. Our approach incorporates a visual color-tracker based on a 9 dimensional color-space by using a probabilistic AdaBoost classifier with axis-aligned hyperplanes as weak-learners. We then use particle filtering to incorporate interframe temporal information. We present experiments illustrating the performance of our system in both indoor and outdoor settings, where occlusions, multiple crossing targets, and lighting changes occur. Results suggest that the respectful camera system can reduce false negative rates to acceptable levels (under 2%).

Given a large collection of videos containing activities, we investigate the problem of organizing it in an unsupervised fashion into a hierarchy based on the similarity of actions embedded in the videos. We use spatio-temporal volumes of filtered motion vectors to compute appearance-invariant action similarity measures efficiently - and use these similarity measures in hierarchical agglomerative clustering to organize videos into a hierarchy such that neighboring nodes contain similar actions. This naturally leads to a simple automatic scheme for selecting videos of representative actions (exemplars) from the database and for efficiently indexing the whole database. We compute a performance metric on the hierarchical structure to evaluate goodness of the estimated hierarchy, and show that this metric has potential for predicting the clustering performance of various joining criteria used in building hierarchies. Our results show that perceptually meaningful hierarchies can be constructed based on action similarities with minimal user supervision, while providing favorable clustering performance and retrieval performance.

This paper considers control and estimation problems where the sensor signals and the actuator signals are transmitted to various subsystems over a network. In contrast to traditional control and estimation problems, here the observation and control packets may be lost or delayed. The unreliability of the underlying communication network is modeled stochastically by assigning probabilities to the successful transmission of packets. This requires a novel theory which generalizes classical control/estimation paradigms. The paper offers the foundations of such a novel theory.

This paper considers the problem of pursuit evasion games (PEGs), where the objective of a group of pursuers is to chase and capture a group of evaders in minimum time with the aid of a sensor network. The main challenge in developing a real-time control system using sensor networks is the inconsistency in sensor measurements due to packet loss, communication delay, and false detections. We address this challenge by developing a real-time hierarchical control system, namedLochNess, which decouples the estimation of evader states from the control of pursuers via multiple layers of data fusion. The multiple layers of data fusion convert noisy, inconsistent, and bursty sensor measurements into a consistent set of fused measurements. Three novel algorithms are developed forLochNess: multisensor fusion, hierarchical multitarget tracking, and multiagent coordination algorithms. The multisensor fusion algorithm converts correlated sensor measurements into position estimates, the hierarchical multitarget tracking algorithm based on Markov chain Monte Carlo data association (MCMCDA) tracks an unknown number of targets, and the multiagent coordination algorithm coordinates pursuers to chase and capture evaders using robust minimum-time control. The control systemLochNessis evaluated in simulation and successfully demonstrated using a large-scale outdoor sensor network deployment.

There is an alarming increase in the number of virus and worm attacks, phishing emails, identity theft both on the internet and physical infrastructures. Indeed, cyberspace has several features of lawlessness which make it difficult for us to mirror societal trust relationships into cyberspace. A cursory examination of the issues involved in an issue like phishing or electronic voting reveals that the problems that we are confronting have both a technology and a policy component. Further, with our increase dependency on computing and communication to instrument physical infrastructures, such as electric power, water, gas, etc. we find that they are vulnerable to information attack as well. To address these grand challenge societal problem, in June 2005, the NSF has established a Science and Technology Center entitled "TRUST: Team for Research in Ubiquitous Secure Technologies" between Berkeley (lead), CMU, Cornell, Stanford and Vanderbilt with outreach partners at San Jose State, Mills and Smith College. In this talk, I will give you a snap shot of the kinds of research, education, technology transfer, privacy and policy work that we have underway. Rather than present a smorgasbord of work at the Center I will give a selected few examples of the work, technology transfer and impact that the Center has already had in the area of network embedded systems:

On August 30, 2005, we successfully demonstrated a large-scale, real-time, surveillance and control application on a wireless sensor network. The task was to track multiple human targets walking through a 5041 square meter sensor field and dispatch simulated pursuers to capture them. We employed a multi-target tracking algorithm that was a combination of a multi-sensor fusion algorithm for fusing binary detections and a Markov chain Monte Carlo data association (MCMCDA) algorithm that can initiate and terminates tracks autonomously and is robust to a high level of false alarms and missing measurements, a common problem in sensor networks. The tracks were used by a multi-agent coordination and control algorithm to capture the evaders. We were able to demonstrate successful pursuit of two crossing targets and successful tracking of three targets moving through a 144 node sensor field. To the authors' best knowledge, this experiment is the largest demonstration to date of a real-time tracking and control system on a wireless sensor network that does not use classification information

A record of this keynote presentation was not made available for publication as part of the conference proceedings.

We present a compressed domain scheme that is able to recognize and localize actions in real-time. The recognition problem is posed as performing a video query on a test video sequence. Our method is based on computing motion similarity using compressed domain features which can be extracted with low complexity. We introduce a novel motion correlation measure that takes into account differences in motion magnitudes. Our method is appearance invariant, requires no prior segmentation, alignment or stabilization, and is able to localize actions in both space and time. We evaluated our method on a large action video database consisting of 6 actions performed by 25 people under 3 different scenarios. Our classification results compare favorably with existing methods at only a fraction of their computational cost

Ad-hoc sensor networks are becoming more common, yet security of these networks is still an issue. Node misbehavior due to malicious attacks can impair the overall functioning of the system. Existing approaches mainly rely on cryptography to ensure data authentication and integrity. These approaches only address part of the problem of security in sensor networks. However, cryptography is not sufficient to prevent the attacks in which some of the nodes are overtaken and compromised by a malicious user. Recently, the use of reputation systems has shown positive results as a self-policing mechanism in ad-hoc networks. This scheme can aid in decreasing vulnerabilities which are not solved by cryptography. We look at how a distributed reputation scheme can benefit the object tracking application in sensor networks. Tracking multiple objects is one of the most important applications of the sensor network. In our setup, nodes detect misbehavior locally from observations, and assign a reputation to each of their neighbors. These reputations are used to weight node readings appropriately when performing object tracking. Over time, data from malicious nodes will not be included in the track formation process. We evaluate the reputation system experimentally and demonstrate how it improves object tracking in the presence of malicious nodes

In this paper, we present the design of the flight control algorithms for flapping wing micromechanical flying insects (MFIs). Inspired by the sensory feedback and neuromotor structure of insects, we propose a similar top-down hierarchical architecture to achieve high performance despite the MFIs' limited on-board computational resources. The flight stabilization problem is formulated as high-frequency periodic control of an underactuated system. In particular, we provide a methodology to approximate the time-varying dynamics caused by the aerodynamic forces with a time-invariant model using averaging theory and a biomimetic parametrization of the wing trajectories. This approximation leads to a simpler dynamical model that can be identified using experimental data from the on-board sensors and the voltage inputs to the wing actuators. The overall control law is a periodic proportional output feedback. Simulations, including sensor and actuator models, demonstrate stable flight in hovering mode.

This paper presents the mathematical modeling of flapping flight inch-size micro aerial vehicles (MAVs), namely micromechanical flying insects (MFIs). The target robotic insects are electromechanical devices propelled by a pair of independent flapping wings to achieve sustained autonomous flight, thereby mimicking real insects. In this paper, we describe the system dynamic models which include several elements that are substantially different from those present in fixed or rotary wing MAVs. These models include the wing-thorax dynamics, the flapping flight aerodynamics at a low Reynolds number regime, the body dynamics, and the biomimetic sensory system consisting of ocelli, halteres, magnetic compass, and optical flow sensors. The mathematical models are developed based on biological principles, analytical models, and experimental data. They are presented in the Virtual Insect Flight Simulator (VIFS) and are integrated together to give a realistic simulation for MFI and insect flight. VIFS is a software tool intended for modeling flapping flight mechanisms and for testing and evaluating the performance of different flight control algorithms.

To compare spatial patterns of gene expression, one must analyze a large number of images as current methods are only able to measure a small number of genes at a time. Bringing images of corresponding tissues into alignment is a critical first step in making a meaningful comparative analysis of these spatial patterns. Significant image noise and variability in the shapes make it hard to pick a canonical shape model. In this paper, we address these problems by combining segmentation and unsupervised shape learning algorithms. We first segment images to acquire structures of interest, then jointly align the shapes of these acquired structures using an unsupervised nonparametric maximum likelihood algorithm along the lines of 'congealing' (E. G. Miller et al., 2000), while simultaneously learning the underlying shape model and associated transformations. The learned transformations are applied to corresponding images to bring them into alignment in one step. We demonstrate the results for images of various classes of Drosophila imaginal discs and discuss the methodology used for a quantitative analysis of spatial gene expression patterns.

We present a novel approach for the estimation of 3D-motion directly from two images using the Radon transform. We assume a similarity function defined on the cross-product of two images which assigns a weight to all feature pairs. This similarity function is integrated over all feature pairs that satisfy the epipolar constraint. This integration is equivalent to filtering the similarity function with a Dirac function embedding the epipolar constraint. The result of this convolution is a function of the five unknown motion parameters with maxima at the positions of compatible rigid motions. The breakthrough is in the realization that the Radon transform is a filtering operator: If we assume that images are defined on spheres and the epipolar constraint is a group action of two rotations on two spheres, then the Radon transform is a convolution/correlation integral. We propose a new algorithm to compute this integral from the spherical harmonics of the similarity and Dirac functions. The resulting resolution in the motion space depends on the bandwidth we keep from the spherical transform. The strength of the algorithm is in avoiding a commitment to correspondences, thus being robust to erroneous feature detection, outliers, and multiple motions. The algorithm has been tested in sequences of real omnidirectional images and it outperforms correspondence-based structure from motion.

Multiple-target tracking is a canonical application of sensor networks as it exhibits different aspects of sensor networks such as event detection, sensor information fusion, multi-hop communication, sensor management and decision making. The task of tracking multiple objects in a sensor network is challenging due to constraints on a sensor node such as short communication and sensing ranges, a limited amount of memory and limited computational power. In addition, since a sensor network surveillance system needs to operate autonomously without human operators, it requires an autonomous tracking algorithm which can track an unknown number of targets. In this paper, we develop a scalable hierarchical multiple-target tracking algorithm that is autonomous and robust against transmission failures, communication delays and sensor localization error.

In this work we consider the problem of pursuit evasion games (PEGs) where a group of pursuers is required to detect, chase and capture a group of evaders with the aid of a sensor network in minimum time. Differently from standards PEGs where the environment and the location of evaders is unknown and a probabilistic map is built based on the pursuer’s onboard sensors, here we consider a scenario where a sensor network, previously deployed in the region of concern, can detect the presence of moving vehicles and can relay this information to the pursuers. Here we propose a general framework for the design of a hierarchical control architecture that exploits the advantages of a sensor network by combining both centralized and decentralized real-time control algorithms. We also propose a coordination scheme for the pursuers to minimize the time-to-capture of all evaders. In particular, we focus on PEGs with sensor networks orbiting in space for artificial space debris detection and removal.

This paper considers the problem of tracking objects with sparsely located binary sensors. Tracking with a sensor network is a challenging task due to the inaccuracy of sensors and difficulties in sensor network localization. Based on the simplest sensor model, in which each sensor reports only a binary value indicating whether an object is present near the sensor or not, we present an optimal distributed tracking algorithm which does not require sensor network localization. The tracking problem is formulated as a hidden state estimation problem over the finite state space of sensors. Then a distributed tracking algorithm is derived from the Viterbi algorithm. We also describe provably good pruning strategies for scalability of the algorithm and show the conditions under which the algorithm is robust against false detections. The algorithm is also extended to handle non-disjoint sensing regions and to track multiple moving objects. Since the computation and storage of track information are done in a completely distributed manner, the method is robust against node failures and transmission failures. In addition, the use of binary sensors makes the proposed algorithm suitable for many sensor network applications.

This paper presents an algebro-geometric solution to the problem of segmenting an unknown number of subspaces of unknown and varying dimensions from sample data points. We represent the subspaces with a set of homogeneous polynomials whose degree is the number of subspaces and whose derivatives at a data point give normal vectors to the subspace passing through the point. When the number of subspaces is known, we show that these polynomials can be estimated linearly from data; hence, subspace segmentation is reduced to classifying one point per subspace. We select these points optimally from the data set by minimizing certain distance function, thus dealing automatically with moderate noise in the data. A basis for the complement of each subspace is then recovered by applying standard PCA to the collection of derivatives (normal vectors). Extensions of GPCA that deal with data in a high-dimensional space and with an unknown number of subspaces are also presented. Our experiments on low-dimensional data show that GPCA outperforms existing algebraic algorithms based on polynomial factorization and provides a good initialization to iterative techniques such as K-subspaces and Expectation Maximization. We also present applications of GPCA to computer vision problems such as face clustering, temporal video segmentation, and 3D motion segmentation from point correspondences in multiple affine views.

In this paper, the problem of automated aircraft conflict prediction is studied for two-aircraft midair encounters. A model is introduced to predict the aircraft positions along some look-ahead time horizon, during which each aircraft is trying to follow a prescribed flight plan despite the presence of additive wind perturbations to its velocity. A spatial correlation structure is assumed for the wind perturbations such that the closer the two aircraft, the stronger the correlation between the perturbations to their velocities. Using this model, a method is introduced to evaluate the criticality of the encounter situation by estimating the probability of conflict, namely, the probability that the two aircraft come closer than a minimum allowed distance at some time instant during the look-ahead time horizon. The proposed method is based on the introduction of a Markov chain approximation of the stochastic processes modeling the aircraft motions. Several generalizations of the proposed approach are also discussed.

In this paper, we study attitude stabilization strategies via output sensor feedback for micro aerial vehicles (MAVs), inch-size robots capable of autonomous flight. In order to compensate for the size and power limitations of MAVs, we introduce the ocelli and halteres, the body orientation and rotation sensing mechanisms used by flying insects. The analysis and simulations of these sensors show the feasibility of using such biologically inspired approaches to build biomimetic gyroscopes and angular position detectors. Finally, attitude stabilization techniques based on these sensors are proposed and successfully tested on an aerodynamic model for a micromechanical flying insect (NIFI). To the authors' knowledge, this is the first attempt in using output feedback from biomimetic devices with ocelli and halteres to achieve attitude stabilization in MAVs.

We propose an algebraic geometric approach to the problem of estimating a mixture of linear subspaces from sample data points, the so-called generalized principal component analysis (GPCA) problem. In the absence of noise, we show that GPCA is equivalent to factoring a homogeneous polynomial whose degree is the number of subspaces and whose factors (roots) represent normal vectors to each subspace. We derive a formula for the number of subspaces n and provide an analytic solution to the factorization problem using linear algebraic techniques. The solution is closed form if and only if n /spl les/ 4. In the presence of noise, we cast GPCA as a constrained nonlinear least squares problem and derive an optimal function from which the subspaces can be directly recovered using standard nonlinear optimization techniques. We apply GPCA to the motion segmentation problem in computer vision, i.e. the problem of estimating a mixture of motion models from 2D imagery.

We present a novel algorithm for optimally segmenting dynamic scenes containing multiple rigidly moving objects. We cast the motion segmentation problem as a constrained nonlinear least squares problem, which minimizes the reprojection error subject to all multibody epipolar constraints. By converting this constrained problem into an unconstrained one, we obtain an objective function that depends on the motion parameters only (fundamental matrices), but is independent on the segmentation of the image features. Therefore, our algorithm does not iterate between feature segmentation and single body motion estimation. Instead, it uses standard nonlinear optimization techniques to simultaneously recover all the fundamental matrices, without prior segmentation. We test our approach on a real sequence.

This paper describes recent developments on the model identification and attitude control system for a micromechanical flying insect (MFI). We include recently developed dynamical models for the thorax actuators and the various sensor models. Wing kinematic parameterization scheme was designed to generate feasible wing motions to decouple the body torques under the constraints of the thorax model. A nominal state-space LTI model in hover was identified through linear estimation and a LQR controller was designed to achieve stable hovering and steering maneuvers. Simulation results show satisfactory performance comparable to that of the real insects.

We present an algorithm for infinitesimal motion estimation and segmentation from multiple central panoramic views. We first show that the central panoramic optical flows corresponding to independent motions lie in orthogonal ten-dimensional subspaces of a higher-dimensional linear space. We then propose a factorization-based technique that estimates the number of independent motions, the segmentation of the image measurements and the motion of each object relative to the camera from a set of image points and their optical flows in multiple frames. Finally, we present the experimental results on motion estimation and segmentation for a real image sequence with two independently moving mobile robots, and evaluate the performance of our algorithm by comparing the vision estimates with GPS measurements gathered by the mobile robots.

We consider the problem of having a team of nonholonomic mobile robots follow a desired leader-follower formation using omnidirectional vision. By specifying the desired formation in the image plane, we translate the control problem into a separate visual servoing task for each follower. We use a rank constraint on the omnidirectional optical flows across multiple frames to estimate the position and velocities of the leaders in the image plane of each follower. We show that the direct feedback-linearization of the leader-follower dynamics suffers from degenerate configurations due to the nonholonomic constraints of the robots and the nonlinearity of the omnidirectional projection model. We therefore design a nonlinear tracking controller that avoids such degenerate configurations, while preserving the formation input-to-state stability. Our control law naturally incorporates collision avoidance by exploiting the geometry of omnidirectional cameras. We present simulations and experiments evaluating our omnidirectional vision-based formation control scheme.

Given a group of autonomous vehicles, an initial configuration, a final configuration, a set of inter- and intra-vehicle constraints, and a time for reconfiguration, the Formation Reconfiguration Planning problem is focused on determining a nominal input trajectory for each vehicle such that the group can start from the initial configuration and reach its final configuration at the specified time while satisfying the set of inter-and intra-vehicle constraints. In this paper, we are interested in solving the Formation Reconfiguration Planning problem for a specific class of systems and a particular form of input signals so that the problem can be reformulated as an optimization problem which can be solved more efficiently, especially for a large group of vehicles.

We consider the problem of having a group of nonholonomic mobile robots equipped with omnidirectional cameras maintain a desired leader-follower formation. Our approach is to translate the formation control problem from the configuration space into a separate visual servoing task for each follower. We derive the questions of motion of the leader in the image plane of the follower and propose two control schemes for the follower. The first one is based on feedback linearization and is either string stable or leader-to-formation stable, depending on the sensing capabilities of the followers. The second one assumes a kinematic model for the evolution of the leader velocities and combines a Luenberger observer with a linear control law that is locally stable. We present simulation results evaluating our vision-based follow-the-leader control strategies.

Autonomous helicopter flight represents a challenging control problem, with complex, noisy, dynamics. In this paper, we describe a successful application of reinforcement learning to autonomous helicopter flight. We first fit a stochastic, nonlinear model of the helicopter dynamics. We then use the model to learn to hover in place, and to fly a number of maneuvers taken from an RC helicopter competition.

Automatic control systems typically incorporate legacy code and components that were originally designed to operate independently. Furthermore, they operate under stringent safety and timing constraints. Current design strategies deal with these requirements and characteristics with ad hoc approaches. In particular, when designing control laws, implementation constraints are often ignored or cursorily estimated. Indeed, costly redesigns are needed after a prototype of the control system is built because of missed timing constraints and subtle transient errors. In this paper, we use the concepts of platform-based design to develop a methodology for the design of automatic control systems that builds in modularity and correct-by-construction procedures. We illustrate our strategy by describing the (successful) application of the methodology to the design of a time-based control system for a helicopter-based uninhabited aerial vehicle.

Provides an overview of the technical articles and features presented in this issue.

Sensor networks are gaining a central role in the research community. This paper addresses some of the issues arising from the use of sensor networks in control applications. Classical control theory proves to be insufficient in modeling distributed control problems where issues of communication delay, jitter, and time synchronization between components are not negligible. After discussing our hardware and software platform and our target application, we review useful models of computation and then suggest a mixed model for design, analysis, and synthesis of control algorithms within sensor networks. We present a hierarchical model composed of continuous time-trigger components at the low level and discrete event-triggered components at the high level.

This paper describes recent development on the design of the flight control system for a micromechanical flying insect (MFI), a 10-25 mm (wingtip-to-wingtip) device capable of sustained autonomous flight. High level attitude control is considered. Based on our previous work, in which the complex time-varying component of aerodynamic forces are treated as external disturbances, a nominal state-space linear time-invariant model in hover is developed through linear estimation. The identified model is validated through the virtual insect flight simulator (VIFS), and is used to design feedback controllers for the MFI. A LQG controller is designed and compared with a PD controller. The identification scheme provides a more systematic way of treating aerodynamic modeling errors, and the controllers designed based on the identified model shows better overall performance in simulation. Another advantage of this approach is that measurement of the instantaneous aerodynamic forces is not necessary, thus simplifies the experimental setup for the real MFI.

Body rotation and orientation sensing mechanisms used by flying insects are introduced and their mathematical models are presented. The analysis and simulations of these models showed the feasibility of using such biologically inspired approaches to build biomimetic gyroscopes and angular position detectors. Further, an approximate rigid body model for the insect body dynamics is developed so that attitude stabilization techniques for a flying robotic insect can be tested to illustrate the utility of these novel sensor architectures. To the authors' knowledge, this is the first attempt in using output feedback from biomimetic devices such as ocelli and halters to achieve attitude stabilization.

This paper presents a flight management system (FMS) implemented as on-board intelligence for rotorcraft-based unmanned aerial vehicles (RUAV's), in order to gradually refine given abstract mission commands into real-time control signals for each vehicle. A strategy planner uses the probabilistic decision making algorithms to determine suboptimal action at each time step. A graphical interface on ground station enables human intervention. We derive nonlinear dynamics model upon which we design a tracking control layer using nonlinear model predictive control and integrate with a trajectory generator for logistical action planning. The proposed structure has been implemented on Berkeley RUAVs and validated in probabilistic pursuit-evasion games to show the possibility of intelligent flying robots.

We present a multiple view algorithm for vision based landing of an unmanned aerial vehicle. Our algorithm is based on our results in multiple view geometry which exploit the rank deficiency of the so called multiple view matrix. We show how the use of multiple views significantly improves motion and structure estimation. We compare our algorithm to our previous linear and non-linear two-view algorithms using an actual flight test. Our results show that the vision-based state estimates are accurate to within 7cm in each axis of translation and 4 degrees in each axis of rotation.

We consider the problem of having a team of unmanned aerial vehicles (UAVs) and unmanned ground vehicles (UGVs) pursue a second team of evaders while concurrently building a map in an unknown environment. We cast the problem in a probabilistic game theoretical framework, and consider two computationally feasible greedy pursuit policies: local-mar and global-max. To implement this scenario on real UAVs and UGVs, we propose a distributed hierarchical hybrid system architecture which emphasizes the autonomy of each agent, yet allows for coordinated team efforts. We describe the implementation of the architecture on a fleet of UAVs and UGVs, detailing components such as high-level pursuit policy computation, map building and interagent communication, and low-level navigation, sensing, and control. We present both simulation and experimental results of real pursuit-evasion games involving our fleet of UAVs and UGVs, and evaluate the pursuit policies relating expected capture times to the speed and intelligence of the evaders and the sensing capabilities of the pursuers.

Describes results on the design and simulation of a flight control system for the micromechanical flying insect (MFI), a 10-25 mm (wingtip-to-wingtip) device eventually capable of sustained autonomous flight. The biologically inspired system architecture results in a hierarchical structure of different control methodologies, which give the possibility to plan complex missions from a sequence of simple flight modes and maneuvers. As a case study, a stabilizing hovering control scheme is presented and simulated with VIFS, a software simulator for insect flight.

Presents the design of the software simulator, VIFS, for insect flight. In particular, it is intended to estimate flight control algorithms and performance for a micromechanical flying insect (MFI), a 10-25 mm (wingtip-to-wingtip) device eventually capable of sustained autonomous flight. The VIFS is an end-to-end tool composed of several modular blocks which model actuator dynamics, wing aerodynamics, body motion, visual and inertial sensors, environment perception, and control algorithms. A 3D virtual environment simulation is also developed as a visualization tool. We present the current state of art of its implementation and preliminary results.

We present the design and implementation of a real-time computer vision system for a rotor-craft unmanned aerial vehicle to land onto a known landing target. This vision system consists of customized software and off-the-shelf hardware which perform image processing, segmentation, feature point extraction, camera pan/tilt control, and motion estimation. We introduce the design of a landing target which significantly simplifies the computer vision tasks such as corner detection and correspondence matching. Customized algorithms are developed to allow for realtime computation at a frame rate of 30Hz. Such algorithms include certain linear and nonlinear optimization schemes for model-based camera pose estimation. We present results from an actual flight test which show the vision-based state estimates are accurate to within 5cm in each axis of translation and 5 degrees in each axis of rotation, making vision a viable sensor to be placed in the control loop of a hierarchical flight management system.

Presents the implementation of a hierarchical architecture for the coordination and control of a heterogeneous team of autonomous agents. We consider the problem of having a team of agents pursue a second team of evaders while building a map of the environment. The control architecture emphasizes the autonomy of each agent yet allows for coordinated efforts among them. We address the technical challenges and implementation issues of multi-agent operation. Finally we present experimental results of a pursuit-evasion game scenario between unmanned ground and aerial vehicles.

We present a method to design controllers for safety specifications in hybrid systems. The hybrid system combines discrete event dynamics with nonlinear continuous dynamics: the discrete event dynamics model linguistic and qualitative information and naturally accommodate mode switching logic, and the continuous dynamics model the physical processes themselves, such as the continuous response of an aircraft to the forces of aileron and throttle. Input variables model both continuous and discrete control and disturbance parameters. We translate safety specifications into restrictions on the system's reachable sets of states. Then, using analysis based on optimal control and game theory for automata and continuous dynamical systems, we derive Hamilton-Jacobi equations whose solutions describe the boundaries of reachable sets. These equations are the heart of our general controller synthesis technique for hybrid systems, in which we calculate feedback control laws for the continuous and discrete variables, which guarantee that the hybrid system remains in the "safe subset" of the reachable set. We discuss issues related to computing solutions to Hamilton-Jacobi equations. Throughout, we demonstrate out techniques on examples of hybrid automata modeling aircraft conflict resolution, autopilot flight mode switching, and vehicle collision avoidance.

Conflict detection and resolution schemes operating at the mid-range and short-range level of the air traffic management process are discussed. Probabilistic models for predicting the aircraft position in the near-term and mid-term future are developed. Based on the mid-term prediction model, the maximum instantaneous probability of conflict is proposed as a criticality measure for two aircraft encounters. Randomized algorithms are introduced to efficiently estimate this measure of criticality and provide quantitative bounds on the level of approximation introduced. For short-term detection, approximate closed-form analytical expressions for the probability of conflict are obtained, using the short-term prediction model. Based on these expressions, an algorithm for decentralized conflict detection and resolution that generalizes potential fields methods for path planning to a probabilistic dynamic environment is proposed. The algorithms are validated using Monte Carlo simulations.

The necessary and sufficient conditions for being able to estimate scene structure, motion and camera calibration from a sequence of images are very rarely satisfied in practice. What exactly can be estimated in sequences of practical importance, when such conditions are not satisfied? In this paper we give a complete answer to this question. For every camera motion that fails to meet the conditions, we give explicit formulas for the ambiguities in the reconstructed scene, motion and calibration. Such a characterization is crucial both for designing robust estimation algorithms (that do not try to recover parameters that cannot be recovered), and for generating novel views of the scene by controlling the vantage point. To this end, we characterize explicitly all the vantage points that give rise to a valid Euclidean reprojection regardless of the ambiguity in the reconstruction. We also characterize vantage points that generate views that are altogether invariant to the ambiguity. All the results are presented using simple notation that involves no tensors nor complex projective geometry, and should be accessible with basic background in linear algebra.

In this paper, various aspects of robotic telesurgery are studied. After a general introduction to laparoscopic surgery and medical applications of robotics, the UC Berkeley/Endorobotics Inc./UC San Francisco Telesurgical Workstation, a master-slave telerobotic system for laparoscopic surgery, is introduced, followed by its kinematic analysis, control, and experimental results. Some conceptual and future issues on telesurgery are discussed, including teleoperation and hybrid control, focusing on the special requirements of telesurgery.

Theoretical and analytical aspects of the visual servoing problem have not received much attention. Furthermore, the problem of estimation from the vision measurements has been considered separately from the design of the control strategies. Instead of addressing the pose estimation and control problems separately, we attempt to characterize the types of control tasks which can be achieved using only quantities directly measurable in the image, bypassing the pose estimation phase. We consider the task of navigation for a nonholonomic ground mobile base tracking an arbitrarily shaped continuous ground curve. This tracking problem is formulated as one of controlling the shape of the curve in the image plane. We study the controllability of the system characterizing the dynamics of the image curve, and show that the shape of the image curve is controllable only up to its "linear" curvature parameters. We present stabilizing control laws for tracking piecewise analytic curves, and propose to track arbitrary curves by approximating them by piecewise "linear" curvature curves. Simulation results are given for these control schemes. Observability of the curve dynamics by using direct measurements from vision sensors as the outputs is studied and an extended Kalman filter is proposed to dynamically estimate the image quantities needed for feedback control from the actual noisy images.

We explore the use of distributed online motion planning algorithms for multiple mobile agents, in air traffic management systems (ATMS). The work is motivated by current trends in ATMS to move towards decentralized air traffic management, in which the aircraft operate in "free flight" mode instead of following prespecified "sky freeways". Conflict resolution strategies are an integral part of the free flight setting. The purpose of this paper is to obtain a set of manoeuvres to cover all possible conflict scenarios involving multiple agents. A distributed motion planning algorithm based on potential and vortex fields is used. While the algorithm is not always guaranteed to generate flyable trajectories, the obtained trajectories can serve as qualitative prototypes for coordination manoeuvres between multiple aircraft. The actual manoeuvres are generated by approximating these prototypes with trajectories made zip of straight lines and are further verified using hybrid verification techniques.

We are developing a sophomore course to serve as a first course in electrical engineering. The course focuses on discrete-time systems. Its goal is to give students an intuitive understanding of concepts such as sinusoids, frequency domain, sampling, aliasing, and quantization. In the laboratory, students build simulations and real-time systems to test these ideas. By using a combination of high-level and DSP assembly languages, the students experiment with a variety of views into the representation, design, and implementation of systems. The students are exposed to a digital style of implementation based on programming both desktop and embedded processors.

This paper examines the kinematic model of an autonomous mobile robot system consisting of a chain of steerable cars and passive trailers, linked together with rigid bars. The state space and kinematic equations of the system are defined, and it is shown how these kinematic equations may be converted into a multiinput chained form. The advantages of the chained form are that many methods are available for the open-loop steering of such systems as well as for point-stabilization; some of these methods are discussed here. Dynamic state feedback is used to convert the system to this multiinput chained form. It is shown how the dynamic state feedback that is used in this paper corresponds to adding, in front of the steerable cars, a chain of virtual axles which diverges from the original chain of trailers. Two different example systems are also presented, along with simulation results for a parallel-parking maneuver.

Provides algorithms for reorienting linked rigid bodies floating in space. The dynamics of these systems conserve both linear and angular momentum. The conservation of angular momentum is a nonintegrable or nonholonomic constraint. The authors derive this constraint by applying Noether's theorem to the Lagrangian of the system. When the total angular momentum is zero, the authors may dualize the constraint to a control system. The problem of reorienting the satellite becomes a steering problem for a drift free control system. The authors give explicit solutions for steering a planar skater and a satellite with two rotors. The planar skater has been simulated and animated on a graphics workstation. The authors also discuss the hardware setup which they built to verify the theoretical results.>

The authors present a technique to analyze the forces and dynamics of a class of mechanical systems, called fingerlike systems, which may be viewed as an extension of simple robots to include networks for force/displacement generation and transmission. Fingerlike mechanical system can be described using a graph-theoretic approach to force and displacement generation and transmission. Branches consist of actuators, cables, springs, and other building blocks. Upon specification of the connectivity graph and branch behaviors, a symbolic mathematics program can generate the affine maps from actuator control variables to mechanical system torques and forces. This process systematizes and simplifies the determination of biological and robotic mechanical dynamics.>

Compares the performance of hierarchical and single-level controllers in a grasping context, and concludes that for rapid, planar grasping motions of heavy objects the performance of a hierarchical control structure is superior to that of the two single-level controllers tested. Although the theory discussed applies to grasping problems of arbitrary complexity, the focus is on planar, two-fingered grasping for the sake of clarity and to simplify implementation and experimental testing of the proposed control algorithms. The control algorithms have been implemented on a multifingered hand.>

Methods for steering car-like robots with trailers are investigated. A connection is demonstrated between Murray and Sastry's (1990, 1991) work of steering with integrally related sinusoids and Sussmann and Liu's (1991) recent work on asymptotic behavior of systems with high-frequency sinusoids as inputs. The merits of coordinate transformations, relative to the convergence properties, are discussed. Simulation results for a car-like robot with two trailers are presented.>

A technique for stabilizing nonholonomic systems to trajectories is presented. It is well known that such systems cannot be stabilized to a point using smooth static-state feedback. The authors suggest the use of control laws for stabilizing a system about a trajectory, instead of a point. Given a nonlinear system and a desired nominal feasible trajectory, an explicit control law which will locally exponentially stabilize the system to the desired trajectory is given. The theory is applied to several examples, including a car-like robot.>

The problem of dynamic control of a multifingered hand manipulating an object is considered, under the condition that some of the fingertips slide on the object surface. This work has many useful applications when considered in conjunction with work already done in the area of regrasping. In performing certain tasks with grasped objects, it is often necessary to change the contact locations of the fingers on the object. One method of achieving this is to break and remake the contacts; another method is to slide the fingertips on the object surface. This work provides a dynamic coordinated control scheme for a hand by which one can perform regrasping and reorientation of an object in the planar case.>

A set of primitive operations that forms the core of a robot system description and control language is presented. The actions of the individual primitives are derived from the mathematical structure of the equations of motion for constrained mechanical systems. The recursive nature of the primitives allows composite robots to be constructed from more elementary daughter robots. A few pertinent results of classical mechanics are reviewed, the functionality of the primitive operation is described, and several different hierarchical strategies for the description and control of a two-fingered hand holding a box are presented.>

A methodology is developed for describing of hierarchical control of robot systems in a manner which is faithful to the underlying mechanics, structured enough to be used as an interpreted language, and sufficiently flexible to encompass a wide variety of systems. A consistent set of primitive operations which form the core of a robot system description and control language is presented. This language, motivated by the hierarchical organization of neuromuscular systems, is capable of describing a large class of robot systems under a variety of single-level and distributed control schemes.>

The authors consider the problem of grasp choice for an object held within a multifingered hand from the viewpoint of avoiding collisions between the manipulator links and the object during trajectory execution. A grasp planner is provided in the form of an algorithm that checks the feasibility of a given object trajectory and provides an envelope of feasible contact positions. During execution of the trajectory, contact positions of the fingertips on the object can be changed by sliding the fingertip along the object surface in a controlled manner. A dynamic control law that achieves this is presented and integrated with the grasp planner to determine a dynamic regrasping algorithm, which is illustrated by simulation.>

The authors formulate the dextrous manipulation problem for a robot hand. First, dextrous manipulation is decomposed into coordinated manipulation, rolling motion, sliding motion, and finger relocation. Then the authors develop motion constraints for each of the manipulation modes and show that for finger motions that satisfy these constraints there exists a well-defined lift to the total space that links two contact configurations. Of special note is the incorporation of nonholonomic as well as holonomic and unilateral as well as bilateral constraints in motion planning.>

Many algorithms have been proposed in the literature for control of multifingered robot hands. The authors compare the performance of several of these algorithms, as well as some extensions of more conventional manipulator control laws, in the case of planar grasping. Based on experiments performed on Styx, the most effective control laws are found to be the simple joint control law and the generalized computed torque law. The computed torque control law is shown to be an attractive alternative for position control of multifingered hands.>

The kinematics of rolling contact for two surfaces of arbitrary shape rolling of each other is derived. Applying these kinematic equations to two planar multifingered hands manipulating some object of arbitrary shape, a scheme is presented for the control of these hands which is a generalization of the computed torque method of control of robot manipulators. In implementing the control, it is required that all applied forces lie within the friction cone of the object so that sliding does not occur. The theory is illustrated with graphic simulations of the control law applied to the system dynamics for two examples.>

The authors provide a dynamic control law that guarantees the tracking of a given end-effector trajectory and also provides for the control of the redundant joint velocity. The desired redundant joint velocity can then be specified to optimize a cost function over the configurations allowed by the extra degrees of freedom that achieve the given end-effector position.>

Two problems in the study of multifingered robot hands are considered, namely grasp planning and the determination of coordinated control laws with point contact models. using the dual notions of grasp stability and manipulability, and a procedure previously developed for task modeling, the structure grasp quality measures are defined. These measures are then integrated to devise a grasp planning algorithm. Based on the assumption of point contact models, a computed-torque-like control algorithm is developed for the coordinated manipulation of a multifingered robot hand. This control algorithm, which takes into account both the dynamics of the object and the dynamics of the hand, is computationally effective and can be generalized to allow rolling motion of the object with respect to the fingertip.>

The problem of optimal grasping of an object by a multifingered robot hand is discussed. Using screw theory and elementary differential geometry, the concept of a grasp is axiomated and its stability characterized. Three quality measures for evaluating a grasp are then proposed. The last quality measure is task-oriented and needs the development of a procedure for modeling tasks as ellipsoids in the wrench space of the object. Numerical computations of these quality measures and the selection of an optimal grasp are addressed in detail. Several examples are given using these quality measures to show that they are consistent with measurements yielded by the authors' experiments on grasping.>

We present a new scheme for the adaptive control of mechanical manipulators along with proof of convergence. This work is an extension of our earlier work [Craig, Hsu and Sastry] [1]. The new scheme does not require the measurement of joint accelerations and needs less computation. We illustrate the theory with some simulations.

We discuss the problem of optimal grasping to an object by a multifingered robot hand. We axiomatize using screw theory and elementary differential geometry the concept of a grasp and characterize its stability. Three quality measures for evaluating a grasp are then proposed. The last quality measure is task oriented and needs the development of a procedure for modeling tasks as ellipsoids in the wrench space of the object. Numerical computations of these quality measures and the selection of an optimal grasp are addressed in detail. Several examples are given using these quality measures to show that they are consistent with human grasping experience.

We present an adaptive version of the computed torque method for the control of manipulators with rigid links. The algorithun estimates parameters on-line which appear in the non-linear dynamic model of the manipulator, such as load and link mass parameters and friction parameters, and uses the latest estimates in the computed torque servo. We present what we believe is the first golbally convergent, rigorous proof of the stability of such a scheme in its non-linear setting, as well as its asymptotic properties and conditions for parameter convergence. We illustrate the theory with some simulation results.