Online Knowledge Repositories (OKRs) like Wikipedia offer communities a way to share and preserve information about themselves and their ways of living. However, for communities with low-resourced languages—including most African communities—the quality and volume of content available are often inadequate. One reason for this lack of adequate content could be that many OKRs embody Western ways of knowledge preservation and sharing, requiring many low-resourced language communities to adapt to new interactions. To understand the challenges faced by low-resourced language contributors on the popular OKR Wikipedia, we conducted (1) a thematic analysis of Wikipedia forum discussions and (2) a contextual inquiry study with 14 novice contributors. We focused on three Ethiopian languages: Afan Oromo, Amharic, and Tigrinya. Our analysis revealed several recurring themes; for example, contributors struggle to find resources to corroborate their articles in low-resourced languages, and language technology support, like translation systems and spellcheck, result in several errors that waste contributors’ time. We hope our study will support designers in making online knowledge repositories accessible to low-resourced language speakers.

Traditional automated metrics for evaluating conditional natural language generation rely on pairwise comparisons between a single generated text and the best-matching gold-standard reference. This method is effective when ground truth data diversity can be attributed to noise, however, it falls short when diversity in references holds valuable contextual information, as in visual description or summarization, as it does not evaluate the ability of a model to generate text matching the diversity of the ground truth samples. In this paper, we challenge the adequacy of existing metrics in such semantically diverse contexts and introduce a novel approach for evaluating conditional language generation models, leveraging a family of meta-metrics that build on existing pairwise distance functions. These meta-metrics assess not just single-samples, but distributions of reference and model-generated captions using small sample sets. We demonstrate our approach through a case study of visual description in the English language which reveals not only how current models prioritize single-description quality over diversity, but further sheds light on the impact of sampling methods and temperature settings on description quality and diversity.

Current Large Language Models (LLMs) are not only limited to some maximum context length, but also are not able to robustly consume long inputs. To address these limitations, we propose ReadAgent, an LLM agent system that increases effective context length up to 20x in our experiments. Inspired by how humans interactively read long documents, we implement ReadAgent as a simple prompting system that uses the advanced language capabilities of LLMs to (1) decide what content to store together in a memory episode, (2) compress those memory episodes into short episodic memories called *gist memories*, and (3) take actions to look up passages in the original text if ReadAgent needs to remind itself of relevant details to complete a task. We evaluate ReadAgent against baselines using retrieval methods, using the original long contexts, and using the gist memories. These evaluations are performed on three long-document reading comprehension tasks: QuALITY, NarrativeQA, and QMSum. ReadAgent outperforms the baselines on all three tasks while extending the effective context window by 3.5-20x.

If you ask a human to describe an image, they might do so in a thousand different ways.Image captioning models, on the other hand, are traditionally trained to generate a single "best" (most like a reference) caption.Unfortunately, doing so encourages captions that are informationally impoverished.Such captions often focus on only a subset of possible details, while ignoring other potentially useful information in the scene.In this work, we introduce a simple, yet novel, method: "Image Captioning by Committee Consensus" (IC 3 ), designed to generate a single caption that captures details from multiple viewpoints by sampling from the learned semantic space of a base captioning model, and carefully leveraging a large language model to synthesize these samples into a single comprehensive caption.Our evaluations show that humans rate captions produced by IC 3 more helpful than those produced by SOTA models more than two-thirds of the time, and IC 3 improves the performance of SOTA automated recall systems by up to 84%, outperforming single human-generated reference captions and indicating significant improvements over SOTA approaches for visual description.

The evaluation of machine-generated image captions poses an interesting yet persistent challenge.Effective evaluation measures must consider numerous dimensions of similarity, including semantic relevance, visual structure, object interactions, caption diversity, and specificity.Existing highly-engineered measures attempt to capture specific aspects, but fall short in providing a holistic score that aligns closely with human judgments.Here, we propose CLAIR 1 , a novel method that leverages the zero-shot language modeling capabilities of large language models (LLMs) to evaluate candidate captions.In our evaluations, CLAIR demonstrates a stronger correlation with human judgments of caption quality compared to existing measures.Notably, on Flickr8K-Expert, CLAIR achieves relative correlation improvements over SPICE of 39.6% and over image-augmented methods such as RefCLIP-S of 18.3%.Moreover, CLAIR provides noisily interpretable results by allowing the language model to identify the underlying reasoning behind its assigned score.

A number of recent self-supervised learning methods have shown impressive performance on image classification and other tasks. A somewhat bewildering variety of techniques have been used, not always with a clear understanding of the reasons for their benefits, especially when used in combination. Here we treat the embeddings of images as point particles and consider model optimization as a dynamic process on this system of particles. Our dynamic model combines an attractive force for similar images, a locally dispersive force to avoid local collapse, and a global dispersive force to achieve a globally-homogeneous distribution of particles. The dynamic perspective highlights the advantage of using a delayed-parameter image embedding (a la BYOL) together with multiple views of the same image. It also uses a purely-dynamic local dispersive force (Brownian motion) that shows improved performance over other methods and does not require knowledge of other particle coordinates. The method is called MSBReg which stands for (i) a Multiview centroid loss, which applies an attractive force to pull different image view embeddings toward their centroid, (ii) a Singular value loss, which pushes the particle system toward spatially homogeneous density, (iii) a Brownian diffusive loss. We evaluate downstream classification performance of MSBReg on ImageNet as well as transfer learning tasks including fine-grained classification, multi-class object classification, object detection, and instance segmentation. In addition, we also show that applying our regularization term to other methods further improves their performance and stabilize the training by preventing a mode collapse.

News podcasts are a popular medium to stay informed and dive deep into news topics. Today, most podcasts are handcrafted by professionals. In this work, we advance the state-of-the-art in automatically generated podcasts, making use of recent advances in natural language processing and text-to-speech technology. We present NewsPod, an automatically generated, interactive news podcast. The podcast is divided into segments, each centered on a news event, with each segment structured as a Question and Answer conversation, whose goal is to engage the listener. A key aspect of the design is the use of distinct voices for each role (questioner, responder), to better simulate a conversation. Another novel aspect of NewsPod allows listeners to interact with the podcast by asking their own questions and receiving automatically generated answers. We validate the soundness of this system design through two usability studies, focused on evaluating the narrative style and interactions with the podcast, respectively. We find that NewsPod is preferred over a baseline by participants, with 80% claiming they would use the system in the future.

Short videos have become the most popular form of social media in recent years. In this work, we focus on the threat scenario where video, audio, and their text description are semantically mismatched to mislead the audience. We develop self-supervised methods to detect semantic mismatch across multiple modalities, namely video, audio and text. We use state-of-the-art language, video and audio models to extract dense features from each modality, and explore transformer architecture together with contrastive learning methods on a dataset of one million Twitter posts from 2021 to 2022. Our best-performing method benefits from the robustness of Noise-Contrastive loss and the context provided by fusing modalities together using a cross-transformer. It outperforms state-of-the-art by over 9% in accuracy. We further characterize the performance of our system on topic-specific datasets containing COVID-19 and Russia-Ukraine related tweets, and shows that it outperforms state-of-the-art by over 17% in accuracy.

Unsupervised protein language models trained across millions of diverse sequences learn structure and function of proteins. Protein language models studied to date have been trained to perform inference from individual sequences. The longstanding approach in computational biology has been to make inferences from a family of evolutionarily related sequences by fitting a model to each family independently. In this work we combine the two paradigms. We introduce a protein language model which takes as input a set of sequences in the form of a multiple sequence alignment. The model interleaves row and column attention across the input sequences and is trained with a variant of the masked language modeling objective across many protein families. The performance of the model surpasses current state-of-the-art unsupervised structure learning methods by a wide margin, with far greater parameter efficiency than prior state-of-the-art protein language models.

Learning effective visual representations that generalize well without human supervision is a fundamental problem in order to apply Machine Learning to a wide variety of tasks. Recently, two families of self-supervised methods, contrastive learning and latent bootstrapping, exemplified by SimCLR and BYOL respectively, have made significant progress. In this work, we hypothesize that adding explicit information compression to these algorithms yields better and more robust representations. We verify this by developing SimCLR and BYOL formulations compatible with the Conditional Entropy Bottleneck (CEB) objective, allowing us to both measure and control the amount of compression in the learned representation, and observe their impact on downstream tasks. Furthermore, we explore the relationship between Lipschitz continuity and compression, showing a tractable lower bound on the Lipschitz constant of the encoders we learn. As Lipschitz continuity is closely related to robustness, this provides a new explanation for why compressed models are more robust. Our experiments confirm that adding compression to SimCLR and BYOL significantly improves linear evaluation accuracies and model robustness across a wide range of domain shifts. In particular, the compressed version of BYOL achieves 76.0% Top-1 linear evaluation accuracy on ImageNet with ResNet-50, and 78.8% with ResNet-50 2x.

This work presents a new approach to unsupervised abstractive summarization based on maximizing a combination of coverage and fluency for a given length constraint.It introduces a novel method that encourages the inclusion of key terms from the original document into the summary: key terms are masked out of the original document and must be filled in by a coverage model using the current generated summary.A novel unsupervised training procedure leverages this coverage model along with a fluency model to generate and score summaries.When tested on popular news summarization datasets, the method outperforms previous unsupervised methods by more than 2 R-1 points, and approaches results of competitive supervised methods.Our model attains higher levels of abstraction with copied passages roughly two times shorter than prior work, and learns to compress and merge sentences without supervision.

Humans learn to drive through both practice and theory, e.g. by studying the rules, while most self-driving systems are limited to the former. Being able to incorporate human knowledge of typical causal driving behaviour should benefit autonomous systems. We propose a new approach that learns vehicle control with the help of human advice. Specifically, our system learns to summarize its visual observations in natural language, predict an appropriate action response (e.g. "I see a pedestrian crossing, so I stop"), and predict the controls, accordingly. Moreover, to enhance interpretability of our system, we introduce a fine-grained attention mechanism which relies on semantic segmentation and object-centric RoI pooling. We show that our approach of training the autonomous system with human advice, grounded in a rich semantic representation, matches or outperforms prior work in terms of control prediction and explanation generation. Our approach also results in more interpretable visual explanations by visualizing object-centric attention maps. Code is available at https://github.com/JinkyuKimUCB/advisable-driving.

Sequential pulling policies to flatten and smooth fabrics have applications from surgery to manufacturing to home tasks such as bed making and folding clothes. Due to the complexity of fabric states and dynamics, we apply deep imitation learning to learn policies that, given color (RGB), depth (D), or combined color-depth (RGBD) images of a rectangular fabric sample, estimate pick points and pull vectors to spread the fabric to maximize coverage. To generate data, we develop a fabric simulator and an algorithmic supervisor that has access to complete state information. We train policies in simulation using domain randomization and dataset aggregation (DAgger) on three tiers of difficulty in the initial randomized configuration. We present results comparing five baseline policies to learned policies and report systematic comparisons of RGB vs D vs RGBD images as inputs. In simulation, learned policies achieve comparable or superior performance to analytic baselines. In 180 physical experiments with the da Vinci Research Kit (dVRK) surgical robot, RGBD policies trained in simulation attain coverage of 83% to 95% depending on difficulty tier, suggesting that effective fabric smoothing policies can be learned from an algorithmic supervisor and that depth sensing is a valuable addition to color alone. Supplementary material is available at https://sites.google.com/view/fabric-smoothing.

Iteratively refining and critiquing sketches are crucial steps to developing effective designs. We introduce Scones, a mixed-initiative, machine-learning-driven system that enables users to iteratively author sketches from text instructions. Scones is a novel deep-learning-based system that iteratively generates scenes of sketched objects composed with semantic specifications from natural language. Scones exceeds state-of-the-art performance on a text-based scene modification task, and introduces a mask-conditioned sketching model that can generate sketches with poses specified by high-level scene information. In an exploratory user evaluation of Scones, participants reported enjoying an iterative drawing task with Scones, and suggested additional features for further applications. We believe Scones is an early step towards automated, intelligent systems that support human-in-the-loop applications for communicating ideas through sketching in art and design.

The Predictive Information is the mutual information between the past and the future, I(Xpast; Xfuture). We hypothesize that capturing the predictive information is useful in RL, since the ability to model what will happen next is necessary for success on many tasks. To test our hypothesis, we train Soft Actor-Critic (SAC) agents from pixels with an auxiliary task that learns a compressed representation of the predictive information of the RL environment dynamics using a contrastive version of the Conditional Entropy Bottleneck (CEB) objective. We refer to these as Predictive Information SAC (PI-SAC) agents. We show that PI-SAC agents can substantially improve sample efficiency over challenging baselines on tasks from the DM Control suite of continuous control environments. We evaluate PI-SAC agents by comparing against uncompressed PI-SAC agents, other compressed and uncompressed agents, and SAC agents directly trained from pixels. Our implementation is given on GitHub.

Inspired by human vision, we propose a new periphery-fovea multi-resolution driving model that predicts vehicle speed from dash camera videos. The peripheral vision module of the model processes the full video frames in low resolution with large receptive fields. Its foveal vision module selects sub-regions and uses high-resolution input from those regions to improve its driving performance. We train the fovea selection module with supervision from driver gaze. We show that adding high-resolution input from predicted human driver gaze locations significantly improves the driving accuracy of the model. Our periphery-fovea multi-resolution model outperforms a uni-resolution periphery-only model that has the same amount of floating-point operations. More importantly, we demonstrate that our driving model achieves a significantly higher performance gain in pedestrian-involved critical situations than in other non-critical situations. Our code is publicly available at https://github.com/pascalxia/periphery_fovea_driving.

Sketches and real-world user interface examples are frequently used in multiple stages of the user interface design process. Unfortunately, finding relevant user interface examples, especially in large-scale datasets, is a highly challenging task because user interfaces have aesthetic and functional properties that are only indirectly reflected by their corresponding pixel data and meta-data. This paper introduces Swire, a sketch-based neural-network-driven technique for retrieving user interfaces. We collect the first large-scale user interface sketch dataset from the development of Swire that researchers can use to develop new sketch-based data-driven design interfaces and applications. Swire achieves high performance for querying user interfaces: for a known validation task it retrieves the most relevant example as within the top-10 results for over 60% of queries. With this technique, for the first time designers can accurately retrieve relevant user interface examples with free-form sketches natural to their design workflows. We demonstrate several novel applications driven by Swire that could greatly augment the user interface design process.

Recent success suggests that deep neural control networks are likely to be a key component of self-driving vehicles. These networks are trained on large datasets to imitate human actions, but they lack semantic understanding of image contents. This makes them brittle and potentially unsafe in situations that do not match training data. Here, we propose to address this issue by augmenting training data with natural language advice from a human. Advice includes guidance about what to do and where to attend. We present the first step toward advice giving, where we train an end-to-end vehicle controller that accepts advice. The controller adapts the way it attends to the scene (visual attention) and the control (steering and speed). Attention mechanisms tie controller behavior to salient objects in the advice. We evaluate our model on a novel advisable driving dataset with manually annotated human-to-vehicle advice called Honda Research Institute-Advice Dataset (HAD). We show that taking advice improves the performance of the end-to-end network, while the network cues on a variety of visual features that are provided by advice. The dataset is available at https://usa.honda-ri.com/HAD.

Visual anticipation of ego and object motion over a short time horizons is a key feature of human-level performance in complex environments. We propose a driving policy learning framework that predicts feature representations of future visual inputs; our predictive model infers not only future events but also semantics, which provide a visual explanation of policy decisions. Our Semantic Predictive Control (SPC) framework predicts future semantic segmentation and events by aggregating multi-scale feature maps. A guidance model assists action selection and enables efficient sampling-based optimization. Experiments on multiple simulation environments show that networks which implement SPC can outperform existing model-based reinforcement learning algorithms in terms of data efficiency and total rewards while providing clear explanations for the policy's behavior.

Deep reinforcement learning has recently made significant progress in solving computer games and robotic control tasks. A known problem, though, is that policies overfit to the training environment and may not avoid rare, catastrophic events such as automotive accidents. A classical technique for improving the robustness of reinforcement learning algorithms is to train on a set of randomized environments, but this approach only guards against common situations. Recently, robust adversarial reinforcement learning (RARL) was developed, which allows efficient applications of random and systematic perturbations by a trained adversary. A limitation of RARL is that only the expected control objective is optimized; there is no explicit modeling or optimization of risk. Thus the agents do not consider the probability of catastrophic events (i.e., those inducing abnormally large negative reward), except through their effect on the expected objective. In this paper we introduce risk-averse robust adversarial reinforcement learning (RARARL), using a risk-averse protagonist and a risk-seeking adversary. We test our approach on a self-driving vehicle controller. We use an ensemble of policy networks to model risk as the variance of value functions. We show through experiments that a risk-averse agent is better equipped to handle a risk-seeking adversary, and experiences substantially fewer crashes compared to agents trained without an adversary. Supplementary materials are available at https://sites.google.com/view/rararl.

Protein modeling is an increasingly popular area of machine learning research. Semi-supervised learning has emerged as an important paradigm in protein modeling due to the high cost of acquiring supervised protein labels, but the current literature is fragmented when it comes to datasets and standardized evaluation techniques. To facilitate progress in this field, we introduce the Tasks Assessing Protein Embeddings (TAPE), a set of five biologically relevant semi-supervised learning tasks spread across different domains of protein biology. We curate tasks into specific training, validation, and test splits to ensure that each task tests biologically relevant generalization that transfers to real-life scenarios. We benchmark a range of approaches to semi-supervised protein representation learning, which span recent work as well as canonical sequence learning techniques. We find that self-supervised pretraining is helpful for almost all models on all tasks, more than doubling performance in some cases. Despite this increase, in several cases features learned by self-supervised pretraining still lag behind features extracted by state-of-the-art non-neural techniques. This gap in performance suggests a huge opportunity for innovative architecture design and improved modeling paradigms that better capture the signal in biological sequences. TAPE will help the machine learning community focus effort on scientifically relevant problems. Toward this end, all data and code used to run these experiments is available at https://github.com/songlab-cal/tape

Sketching is an effective communication medium that augments and enhances what can be communicated in text. We introduce Sketchforme, the first neural-network-based system that can generate complex sketches based on text descriptions specified by users. Sketchforme's key contribution is to factor complex sketch rendering into layout and rendering subtasks using neural networks. The sketches composed by Sketchforme are expressive and realistic: we show in our user study that these sketches convey descriptions better than human-generated sketches in several cases, and 36.5% of those sketches were identified as human-generated. We develop some interactive applications using these generated sketches, and show that Sketchforme can significantly improve language learning applications and support intelligent language-based sketching assistants.

Automating precision subtasks such as debridement (removing dead or diseased tissue fragments) with Robotic Surgical Assistants (RSAs) such as the da Vinci Research Kit (dVRK) is challenging due to inherent nOnlinearities in cable-driven systems. We propose and evaluate a novel two-phase coarse-to-fine calibration method. In Phase I (coarse), we place a red calibration marker on the end effector and let it randomly move through a set of open-loop trajectories to obtain a large sample set of camera pixels and internal robot end-effector configurations. This coarse data is then used to train a Deep Neural Network (DNN) to learn the coarse transformation bias. In Phase II (fine), the bias from Phase I is applied to move the end -effector toward a small set of specific target points on a printed sheet. For each target, a human operator manually adjusts the end -effector position by direct contact (not through teleoperation) and the residual compensation bias is recorded. This fine data is then used to train a Random Forest (RF) to learn the fine transformation bias. Subsequent experiments suggest that without calibration, position errors average 4.55mm. Phase I can reduce average error to 2.14mm and the combination of Phase I and Phase II can reduces average error to 1.08mm. We apply these results to debridement of raisins and pumpkin seeds as fragment phantoms. Using an endoscopic stereo camera with standard edge detection, experiments with 120 trials achieved average success rates of 94.5 %, exceeding prior results with much larger fragments (89.4%) and achieving a speedup of 2.1x, decreasing time per fragment from 15.8 seconds to 7.3 seconds. Source code, data, and videos are available at https://sites.google.com/view/calib-icra/.

We present a novel Metropolis-Hastings method for large datasets that uses small expected-size mini-batches of data. Previous work on reducing the cost of Metropolis-Hastings tests yields only constant factor reductions versus using the full dataset for each sample. Here we present a method that can be tuned to provide arbitrarily small batch sizes, by adjusting either proposal step size or temperature. Our test uses the noise-tolerant Barker acceptance test with a novel additive correction variable. The resulting test has similar cost to a normal SGD update. Our experiments demonstrate several order-of-magnitude speedups over previous work.

Modern datasets and models are notoriously difficult to explore and analyze due to their inherent high dimensionality and massive numbers of samples. Existing visualization methods which employ dimensionality reduction to two or three dimensions are often inefficient and/or ineffective for these datasets. This paper introduces T-SNE-CUDA, a GPU-accelerated implementation of t-distributed Symmetric Neighbour Embedding (t-SNE) for visualizing datasets and models. T-SNE-CUDA significantly outperforms current implementations with 50-700x speedups on the CIFAR-10 and MNIST datasets. These speedups enable, for the first time, visualization of the neural network activations on the entire ImageNet dataset - a feat that was previously computationally intractable. We also demonstrate visualization performance in the NLP domain by visualizing the GloVe embedding vectors. From these visualizations, we can draw interesting conclusions about using the L2 metric in these embedding spaces. T-SNE-CUDA is publicly available at https://github.com/CannyLab/tsne-cuda.

We introduce Inquire, a tool designed to enable qualitative exploration of utterances in social media and large-scale texts. As opposed to keyword search, Inquire allows the effective use of sentences as queries to quickly explore millions of documents to retrieve semantically-similar sentences. We apply Inquire to LiveJournal.com (LJ) database, which contains millions of personal diaries, and we use semantic embeddings trained in LJ or Google News (GN) datasets. We present the system design through iterative evaluations with qualitative researchers. We show how queries become a part of the inductive process, enabling researchers to try multiple ideas while gaining intuition and discovering less-obvious insights. We discuss the choice of LJ as a rich source of public posts, the preference for GN embeddings which link formal language (e.g. "reminiscence triggers") with colloquial expressions (e.g. "music brings back memories"), the interplay between tool and user, and potential qualitative and social research opportunities.

The rational camera model recently introduced in [18] provides a general methodology for studying abstract nonlinear imaging systems and their multi-view geometry. This paper builds on this framework to study physical realizations of rational cameras. More precisely, we give an explicit account of the mapping between between physical visual rays and image points (missing in the original description), which allows us to give simple analytical expressions for direct and inverse projections. We also consider primitive camera models, that are orbits under the action of various projective transformations, and lead to a general notion of intrinsic parameters. The methodology is general, but it is illustrated concretely by an in-depth study of two-slit cameras, that we model using pairs of linear projections. This simple analytical form allows us to describe models for the corresponding primitive cameras, to introduce intrinsic parameters with a clear geometric meaning, and to define an epipolar tensor characterizing two-view correspondences. In turn, this leads to new algorithms for structure from motion and self-calibration.

Deep neural perception and control networks are likely to be a key component of self-driving vehicles. These models need to be explainable - they should provide easy-tointerpret rationales for their behavior - so that passengers, insurance companies, law enforcement, developers etc., can understand what triggered a particular behavior. Here we explore the use of visual explanations. These explanations take the form of real-time highlighted regions of an image that causally influence the network’s output (steering control). Our approach is two-stage. In the first stage, we use a visual attention model to train a convolution network endto- end from images to steering angle. The attention model highlights image regions that potentially influence the network’s output. Some of these are true influences, but some are spurious. We then apply a causal filtering step to determine which input regions actually influence the output. This produces more succinct visual explanations and more accurately exposes the network’s behavior. We demonstrate the effectiveness of our model on three datasets totaling 16 hours of driving. We first show that training with attention does not degrade the performance of the end-to-end network. Then we show that the network causally cues on a variety of features that are used by humans while driving.

Machine learning is growing in importance in industry, sciences, and many other fields. In many and perhaps most of these applications, users need to trade off competing goals. Machine learning, however, has evolved around the optimization of a single, usually narrowly-defined criterion. In most cases, an expert makes (or should be making) trade-offs between these criteria which requires high-level (human) intelligence. With interactive customization and optimization the expert can incorporate secondary criteria into the model-generation process in an interactive way. In this paper we develop the techniques to perform customized and interactive model optimization, and demonstrate the approach on several examples. The keys to our approach are (i) a machine learning architecture which is modular and supports primary and secondary loss functions, while users can directly manipulate its parameters during training (ii) high-performance training so that non-trivial models can be trained in real-time (using roofline design and GPU hardware), and (iii) highly-interactive visualization tools that support dynamic creation of visualizations and controls to match various optimization criteria.

We fuse science and design thinking to create a novel, IoT interactive urban lights system focused on increasing positive affect among pedestrians. Our contributions are three-fold. First, the design, construction, and evaluation of an efficient interactive lighting system focused on well-being, as opposed to systems focused on utility or landscaping. Second, we used scientific methods to discover basic design parameters for affective outcomes. Third, we optimized user experiences for low energy profiles, positive affect, and interactivity. Tested interactions show positive and some unexpected negative responses. Optimal interactive designs cut energy consumption by 75% while maintaining positive affect. Furthermore, card sorting design exercises revealed an inverse relationship between perceived pleasant feelings and interactivity. We conclude by discussing the implications of our research for the design of coherent, attractive, and efficient urban lighting.

Little is known about the affective expressivity of multisensory stimuli in wearable devices. While the theory of emotion has referenced single stimulus and multisensory experiments, it does not go further to explain the potential effects of sensorial stimuli when utilized in combination. In this paper, we present an analysis of the combinations of two sensory modalities - haptic (more specifically, vibrotactile) stimuli and auditory stimuli. We present the design of a wrist-worn wearable prototype and empirical data from a controlled experiment (N=40) and analyze emotional responses from a dimensional (arousal + valence) perspective. Differences are exposed between “matching” the emotions expressed through each modality, versus "mixing" auditory and haptic stimuli each expressing different emotions. We compare the effects of each condition to determine, for example, if the matching of two negative stimuli emotions will render a higher negative effect than the mixing of two mismatching emotions. The main research question that we study is: When haptic and auditory stimuli are combined, is there an interaction effect between the emotional type and the modality of the stimuli? We present quantitative and qualitative data to support our hypotheses, and complement it with a usability study to investigate the potential uses of the different modes. We conclude by discussing the implications for the design of affective interactions for wearable devices.

Many systems have been developed for machine learning at scale. Performance has steadily improved, but there has been relatively little work on explicitly defining or approaching the limits of performance. In this paper we describe the application of roofline design, an approach borrowed from computer architecture, to large-scale machine learning. In roofline design, one exposes ALU, memory, and network limits, and the constraints they imply for algorithms. Using roofline design, we have developed a system called BIDMach which has demonstrated the highest performance to date for many ML problems. On one GPU-accelerated node, it generally outperforms other single-machine toolkits and cluster toolkits running on 100s of nodes. This performance level is enabled by a relatively small number of rooflined matrix primitives. Such performance implies a dramatic reduction in the energy used to perform these calculations. Beyond matrix kernels, roofline design can be applied to the end-to-end design of machine learning algorithms which minimize memory usage to optimize speed. This approach offers a further 2x to 3x gain in performance. Roofline design can also be applied to network primitives. We describe recent work on a sparse allreduce primitive called Kylix. We have shown that Kylix approaches the practical network throughput limit for allreduce, a basic primitive for distributed machine learning. Using Kylix, we describe an efficient transformation from model-parallel to data-parallel calculations. This transformation uses a secondary storage roofline, with similar parameters to the network. Finally, we describe several deployments of these techniques on real-world problems in two large internet companies. Once again, single node rooflined design demonstrated substantial gains over alternatives on either single nodes or clusters.

Heart rate monitoring is widely used in clinical care, fitness training, and stress management. However, tracking individuals' heart rates faces two major challenges, namely equipment availability and user motivation. In this paper, we present a novel technique, LivePulse Games (LPG), to measure users' heart rates in real time by having them play games on unmodified mobile phones. With LPG, the heart rate is calculated by detecting changes in transparency of users' fingertips via the built-in camera of a mobile device. More importantly, LPG integrate users' camera lens covering actions as an essential control mechanism in game play, and detect heart rates implicitly from intermittent lens covering actions. We explore the design space and trade-offs of LPG through three rounds of iterative design. In a 12-subject user study, we found that LPG are fun to play and can measure heart rates accurately. We also report the insights for balancing measurement speed, accuracy, and entertainment value in LPG.

Gibbs sampling is a workhorse for Bayesian inference but has several limitations when used for parameter estimation, and is often much slower than non-sampling inference methods. SAME (State Augmentation for Marginal Estimation) [15, 8] is an approach to MAP parameter estimation which gives improved parameter estimates over direct Gibbs sampling. SAME can be viewed as cooling the posterior parameter distribution and allows annealed search for the MAP parameters, often yielding very high quality estimates. But it does so at the expense of additional samples per iteration and generally slower performance. On the other hand, SAME dramatically increases the parallelism in the sampling schedule, and is an excellent match for modern (SIMD) hardware. In this paper we explore the application of SAME to graphical model inference on modern hardware. We show that combining SAME with factored sample representation (or approximation) gives throughput competitive with the fastest symbolic methods, but with potentially better quality. We describe experiments on Latent Dirichlet Allocation, achieving speeds similar to the fastest reported methods (online Variational Bayes) and lower cross-validated loss than other LDA implementations. The method is simple to implement and should be applicable to many other models.

Stress causes and exacerbates many physiological and mental health problems. Routine and unobtrusive monitoring of stress would enable a variety of treatments, from break-taking to calming exercises. It may also be a valuable tool for assessing effects (frustration, difficulty) of using interfaces or applications. Custom sensing hardware is a poor option, because of the need to buy/wear/use it continuously, even before stress-related problems are evident. Here we explore stress measurement from common computer mouse operations. We use a simple model of arm-hand dynamics that captures muscle stiffness during mouse movement. We show that the within-subject mouse-derived stress measure is quite strong, even compared to concurrent physiological sensor measurements. While our study used fixed mouse tasks, the stress signal was still strong even when averaged across widely varying task geometries. We argue that mouse sensing "in the wild" may be feasible, by analyzing frequently-performed operations of particular geometries.

Early literacy is critical to child development, and determines a child's later educational and life opportunities. Moreover, preschool children are incessantly inquisitive, and will readily engage in question answering and asking activities if given the opportunity. We argue here that question asking/answering technologies can play a major role in early literacy. We describe the design and evaluation of a conversational agent called Spot, with the goal of engaging children in a 20-questions game. Towards this goal, we conducted a feasibility study to determine if children's questions are "on-topic" and suitable for ASR/dialogue systems. We evaluated Spot's performance at conducting a game of 20-questions against that of a human partner.

Search advertising shows trends of vertical extension. Vertical ads, including product ads and local search ads, are proliferating at an ever increasing pace. They typically offer better ROI to advertisers as a result of better user engagement. However, campaigns and bids in vertical ads are not set at the keyword level. As a result, the matching between user query and ads suffers low recall rate and the match quality is heavily impacted by tail queries. In this paper, we propose an ad retrieval framework for retail vertical ads, based on query rewrite using personal history data to improve ad recall rate. To insure ad quality, we also present a relevance model for matching rewritten queries with user search intent, with a particular focus on tail queries. In addition, we designed and implemented a GPU-based system to accelerate the training of the relevance model to meet production performance constraints. Finally, we carry out extensive experiments on large-scale logs collected from Bing, and show significant gains in ad retrieval rate without compromising ad quality.

Allreduce is a basic building block for parallel computing. Our target here is "Big Data" processing on commodity clusters (mostly sparse power-law data). Allreduce can be used to synchronize models, to maintain distributed datasets, and to perform operations on distributed data such as sparse matrix multiply. We first review a key constraint on cluster communication, the minimum efficient packet size, which hampers the use of direct all-to-all protocols on large networks. Our allreduce network is a nested, heterogeneous-degree butterfly. We show that communication volume in lower layers is typically much less than the top layer, and total communication across all layers a small constant larger than the top layer, which is close to optimal. A chart of network communication volume across layers has a characteristic "Kylix" shape, which gives the method its name. For optimum performance, the butterfly degrees also decrease down the layers. Furthermore, to efficiently route sparse updates to the nodes that need them, the network must be nested. While the approach is amenable to various kinds of sparse data, almost all "Big Data" sets show power-law statistics, and from the properties of these, we derive methods for optimal network design. Finally, we present experiments showing with Kylix on Amazon EC2 and demonstrating significant improvements over existing systems such as PowerGraph and Hadoop.

Coding style is important to teach to beginning programmers, so that bad habits don't become permanent. This is often done manually at the University level because automated Python static analyzers cannot accurately grade based on a given rubric. However, even manual analysis of coding style encounters problems, as we have seen quite a bit of inconsistency among our graders. We introduce ACCE--Automated Coding Composition Evaluator--a module that automates grading for the composition of programs. ACCE, given certain constraints, assesses the composition of a program through static analysis, conversion from code to AST, and clustering (unsupervised learning), helping automate the subjective process of grading based on style and identifying common mistakes. Further, we create visual representations of the clusters to allow readers and students understand where a submission falls, and the overall trends. We have applied this tool to CS61A--a CS1 level course at UC, Berkeley experiencing rapid growth in student enrollment--in an attempt to help expedite the involved process as well as reduce human grader inconsistencies.

Constituency parsing with rich grammars remains a computational challenge.Graphics Processing Units (GPUs) have previously been used to accelerate CKY chart evaluation, but gains over CPU parsers were modest.In this paper, we describe a collection of new techniques that enable chart evaluation at close to the GPU's practical maximum speed (a Teraflop), or around a half-trillion rule evaluations per second.Net parser performance on a 4-GPU system is over 1 thousand length-30 sentences/second (1 trillion rules/sec), and 400 general sentences/second for the Berkeley Parser Grammar.The techniques we introduce include grammar compilation, recursive symbol blocking, and cache-sharing.

This paper describes the BID Data Suite, a collection of hardware, software and design patterns that enable fast, large-scale data mining at very low cost. By co-designing all of these elements we achieve single-machine performance levels that equal or exceed reported cluster implementations for common benchmark problems. A key design criterion is rapid exploration of models, hence the system is interactive and primarily single-user. The elements of the suite are: (i) the data engine, a hardware design pattern that balances storage, CPU and GPU acceleration for typical data mining workloads, (ii) BIDMat, an interactive matrix library that integrates CPU and GPU acceleration and novel computational kernels (iii), BIDMach, a machine learning system that includes very efficient model optimizers, (iv) Butterfly mixing, a communication strategy that hides the latency of frequent model updates needed by fast optimizers and (v) Design patterns to improve performance of iterative update algorithms. We present several benchmark problems to show how the above elements combine to yield multiple orders-of-magnitude improvements for each problem.

Incremental model-update strategies are widely used in machine learning and data mining.By "incremental update" we refer to models that are updated many times using small subsets of the training data.Two wellknown examples are stochastic gradient and MCMC.Both provide fast sequential performance and have generated many of the best-performing methods for particular problems (logistic regression, SVM, LDA etc.).But these methods are difficult to adapt to parallel or cluster settings because of the overhead of distributing model updates through the network.Updates can be locally batched to reduce communication overhead, but convergence typically suffers as the batch size increases.In this paper we introduce and analyze butterfly mixing, an approach which interleaves communication with computation.We evaluate butterfly mixing on stochastic gradient algorithms for logistic regression and SVM, on two datasets.Results show that butterfly mix steps are fast and failure-tolerant, and overall we achieved a 3.3x speedup over full mix (AllReduce) on an Amazon EC2 cluster.

Understanding and facilitating real-life social interaction is a high-impact goal for Ubicomp research. Microphone arrays offer the unique capability to provide continuous, calm capture of verbal interaction in large physical spaces, such as homes and (especially open-plan) offices. Most microphone array work has focused on arrays of custom sensors in small spaces, and a few recent works have tested small arrays of commodity sensors in single rooms. This paper describes the first working scalable and cost-effective array that offers high-precision localization of conversational speech, and hence enables ongoing studies of verbal interactions in large semi-structured spaces. This work represents significant improvements over prior work in three dimensions -- cost, scale and accuracy. It also achieves high throughput for real-time updates of tens of active sources using off-the-shelf components. We describe the system design, key localization algorithms, and a systematic performance evaluation. We then show how source location data can be usefully aggregated to reveal interesting patterns in group conversations, such as dominance and engagement.

This paper investigates the usefulness of segmental phoneme-dynamics for classification of speaking styles. We modeled transition details based on the phoneme sequences emitted by a speech recognizer, using data obtained from a recording of 39 depressed patients with 7 different speaking styles- nor-mal, pressured, slurred, stuttered, flat, slow and fast speech. We designed and compared two set of phoneme models: a lan-guage model treating each phoneme as a word unit (one for each style) and a context-dependent phoneme duration model based on Gaussians for each speaking style considered. The experi-ments showed that language modeling at the phoneme level per-formed better than the duration model. We also found that better performance can be obtained by user normalization. To see the complementary effect of the phoneme-based models, the classi-fiers were combined at a decision level with a Hidden Markov Model (HMM) classifier built from spectral features. The im-provement was 5.7 % absolute (10.4 % relative), reaching 60.3% accuracy in 7-class and 71.0 % in 4-class classification. Index Terms: speaking styles, language model, phoneme, du-ration

We describe an innovative and scalable recommendation system successfully deployed at eBay. To build recommenders for long-tail marketplaces requires projection of volatile items into a persistent space of latent products. We first present a generative clustering model for collections of unstructured, heterogeneous, and ephemeral item data, under the assumption that items are generated from latent products. An item is represented as a vector of independently and distinctly distributed variables, while a latent product is characterized as a vector of probability distributions, respectively. The probability distributions are chosen as natural stochastic models for different types of data. The learning objective is to maximize the total intra-cluster coherence measured by the sum of log likelihoods of items under such a generative process. In the space of latent products, robust recommendations can then be derived using naive Bayes for ranking, from historical transactional data. Item-based recommendations are achieved by inferring latent products from unseen items. In particular, we develop a probabilistic scoring function of recommended items, which takes into account item-product membership, product purchase probability, and the important auction-end-time factor. With the holistic probabilistic measure of a prospective item purchase, one can further maximize the expected revenue and the more subjective user satisfaction as well. We evaluated the latent product clustering and recommendation ranking models using real-world e-commerce data from eBay, in both forms of offline simulation and online A/B testing. In the recent production launch, our system yielded 3-5 folds improvement over the existing production system in click-through, purchase-through and gross merchandising value; thus now driving 100% related recommendation traffic with billions of items at eBay. We believe that this work provides a practical yet principled framework for recommendation in the domains with affluent user self-input data.

Cellphones have the potential to improve education for the millions of underprivileged users in the developing world. However, mobile learning in developing countries remains under-studied. In this paper, we argue that cellphones are a perfect vehicle for making educational opportunities accessible to rural children in places and times that are more convenient than formal schooling. We carried out participant observations to identify the opportunities in their everyday lives for mobile learning. We next conducted a 26-week study to investigate the extent to which rural children will voluntarily make use of cellphones to access educational content. Our results show a reasonable level of academic learning and motivation. We also report on the social context around these results. Our goal is to examine the feasibility of mobile learning in out-of-school settings in rural, underdeveloped areas, and to help more researchers learn how to undertake similarly difficult studies around mobile computing in the developing world.

Researchers have long been interested in the potential of ICTs to enable positive change in developing regions communities. In these environments, ICT interventions often fail because political, social and cultural forces work against the changes ICTs entail. We argue that familiar uses of ICTs for information services in these contexts are less potent than their use for persuasion and motivation in order to facilitate change. We focus on India's rural maternal health system where health workers are employed in villages to persuade pregnant women to utilize health services. Health workers face challenges due to resistance to change in the village, and because of their limited education, training and status. These factors appear to reduce the motivation of health workers and impair their performance. For two months, we deployed short videos on mobile phones designed to persuade village women and motivate health workers. We also asked health workers to record their own videos. While our results are preliminary, they show evidence that the creation and use of videos did help (1) engage village women in dialogue, (2) show positive effects toward health worker motivation and learning, and (3) motivate key community influencers to participate in promoting the health workers.

In many developing countries such as India and China, low educational levels often hinder economic empowerment. In this paper, we argue that mobile learning games can play an important role in the Chinese literacy acquisition process. We report on the unique challenges in the learning Chinese language, especially its logographic writing system. Based on an analysis of 25 traditional Chinese games currently played by children in China, we present the design and implementation of two culturally inspired mobile group learning games, Multimedia Word and Drumming Strokes. These two mobile games are designed to match Chinese children's understanding of everyday games. An informal evaluation reveals that these two games have the potential to enhance the intuitiveness and engagement of traditional games, and children may improve their knowledge of Chinese characters through group learning activities such as controversy, judgments and self-correction during the game play.

Dictionary-based disambiguation (DBD) is a very popular solution for text entry on mobile phone keypads but suffers from two problems: 1. the resolution of encoding collision (two or more words sharing the same numeric key sequence) and 2. entering out-of-vocabulary (OOV) words. In this paper, we present SHRIMP, a system and method that addresses these two problems by integrating DBD with camera based motion sensing that enables the user to express preference through a tilting or movement gesture. SHRIMP (Small Handheld Rapid Input with Motion and Prediction) runs on camera phones equipped with a standard 12-key keypad. SHRIMP maintains the speed advantage of DBD driven predictive text input while enabling the user to overcome DBD collision and OOV problems seamlessly without even a mode switch. An initial empirical study demonstrates that SHRIMP can be learned very quickly, performed immediately faster than MultiTap and handled OOV words more efficiently than DBD.

Rural health workers in India do not always have the training, credibility or motivation to effectively convince clients to adopt healthy practices. To help build their efficacy, we provided them with messages on mobile phones to present to clients. We present a study which compared three presentations of persuasive health messages by health workers using a phone-based lecture-style message, a phone-based dialogic message that elicits user responses, or no additional aids. We found that dialogic messages significantly improve the quality of counseling sessions and increase discussion between health workers and clients; however, we did not statistically measure an effect of either phone-based message on health behavioral outcomes. We analyze these results in light of the challenges we faced and compromises we made through the research process due to the interplay of social, cultural and environmental realities, and discuss how these factors affect ICTD projects at large.

Lack of proper English pronunciations is a major problem for immigrant population in developed countries like U.S. This poses various problems, including a barrier to entry into mainstream society. This paper presents a research study that explores the use of speech technologies merged with activity-based and arcade-based games to do pronunciation feedback for Hispanic children within the U.S. A 3-month long study with immigrant population in California was used to investigate and analyze the effectiveness of computer aided pronunciation feedback through games. In addition to quantitative findings that point to statistically significant gains in pronunciation quality, the paper also explores qualitative findings, interaction patterns and challenges faced by the researchers in dealing with this community. It also describes the issues involved in dealing with pronunciation as a competency.

Behavioral targeting (BT) leverages historical user behavior to select the ads most relevant to users to display. The state-of-the-art of BT derives a linear Poisson regression model from fine-grained user behavioral data and predicts click-through rate (CTR) from user history. We designed and implemented a highly scalable and efficient solution to BT using Hadoop MapReduce framework. With our parallel algorithm and the resulting system, we can build above 450 BT-category models from the entire Yahoo’s user base within one day, the scale that one can not even imagine with prior systems. Moreover, our approach has yielded 20% CTR lift over the existing production system by leveraging the well-grounded probabilistic model fitted from a much larger training dataset. Specifically, our major contributions include: (1) A MapReduce statistical learning algorithm and implementation that achieve optimal data parallelism, task parallelism, and load balance in spite of the typically skewed distribution of domain data. (2) An in-place feature vector generation algorithm with strict linear-time complexity O ( n ) regardless of the granularity of sliding target window. (3) An in-memory caching scheme that significantly reduces the number of disk IOs to make large-scale learning practical. (4) Highly efficient data structures and sparse representations of models and data to enable fast model updates. We believe that our work makes significant contributions to solving large-scale machine learning problems of industrial relevance in general. Finally, we report comprehensive experimental results, using industrial proprietary codebase and datasets.

Low educational levels hinder economic empowerment in developing countries. We make the case that educational games can impact children in the developing world. We report on exploratory studies with three communities in North and South India to show some problems with digital games that fail to match rural children's understanding of games, to highlight that there is much for us to learn about designing games that are culturally meaningful to them. We describe 28 traditional village games that they play, based on our contextual interviews. We analyze the mechanics in these games and compare these mechanics against existing videogames to show what makes traditional games unique. Our analysis has helped us to interpret the playability issues that we observed in our exploratory studies, and informed the design of a new videogame that rural children found to be more intuitive and engaging.

Video conferencing attempts to convey subtle cues of face-to-face interaction (F2F), but it is generally believed to be less effective than F2F. We argue that careful design based on an understanding of non-verbal communication can mitigate these differences. In this paper, we study the effects of video image framing in one-on-one meetings on empathy formation. We alter the video image by framing the display such that, in one condition, only the head is visible while, in the other condition, the entire upper body is visible. We include a F2F control case. We used two measures of dyad empathy and found a significant difference between head-only framing and both upper-body framing and F2F, but no significant difference between upper-body framing and F2F.

Literacy is one of the great challenges in the developing world. But universal education is an unattainable dream for those children who lack access to quality educational resources such as well-prepared teachers and schools. Worse, many of them do not attend school regularly due to their need to work for the family in the agricultural fields or households. This work commitment puts formal education far out of their reach. On the other hand, educational games on cellphones hold the promise of making learning more accessible and enjoyable. In our projects 4th year, we reached a stage where we could implement a semester-long pilot on cellphone-based learning. The pilot study took the form of an after-school program in a village in India. This paper reports on this summative learning assessment. While we found learning benefits across the board, it seemed that more of the gains accrued to those children who were better equipped to take advantage of this opportunity. We conclude with future directions for designing educational games that target less well-prepared children in developing regions.

We explore natural and calm interfaces for configuring ubiquitous computing environments. A natural interface should enable the user to name a desired configuration and have the system enact that configuration. Users should be able to use familiar names for configurations without learning, which implies the mapping from names to configurations is many-to-one. Instead of users learning the environment's command language, the system simultaneously learns common configurations and infers the keywords that are most salient to them. We call this the SNAC problem (Simultaneous Naming and Configuration). As a case study, we design a speech interface for workspace lighting control on a large array of individually-controllable lights. We present an approach to the SNAC problem and demonstrate its applicability through an evaluation of our system, Illuminac.

Behavioral targeting (BT) leverages historical user behavior to select the ads most relevant to users to display. The state-of-the-art of BT derives a linear Poisson regression model from fine-grained user behavioral data and predicts click-through rate (CTR) from user history. We designed and implemented a highly scalable and efficient solution to BT using Hadoop MapReduce framework. With our parallel algorithm and the resulting system, we can build above 450 BT-category models from the entire Yahoo's user base within one day, the scale that one can not even imagine with prior systems. Moreover, our approach has yielded 20% CTR lift over the existing production system by leveraging the well-grounded probabilistic model fitted from a much larger training dataset.

We adapt a probabilistic latent variable model, namely GaP (Gamma-Poisson), to ad targeting in the contexts of sponsored search (SS) and behaviorally targeted (BT) display advertising. We also approach the important problem of ad positional bias by formulating a one-latent-dimension GaP factorization. Learning from click-through data is intrinsically large scale, even more so for ads. We scale up the algorithm to terabytes of real-world SS and BT data that contains hundreds of millions of users and hundreds of thousands of features, by leveraging the scalability characteristics of the algorithm and the inherent structure of the problem including data sparsity and locality. Specifically, we demonstrate two somewhat orthogonal philosophies of scaling algorithms to large-scale problems, through the SS and BT implementations, respectively. Finally, we report the experimental results using Yahoos vast datasets, and show that our approach substantially outperform the state-of-the-art methods in prediction accuracy. For BT in particular, the ROC area achieved by GaP is exceeding 0.95, while one prior approach using Poisson regression yielded 0.83. For computational performance, we compare a single-node sparse implementation with a parallel implementation using Hadoop MapReduce, the results are counterintuitive yet quite interesting. We therefore provide insights into the underlying principles of large-scale learning.

Poor literacy remains a barrier to economic empowerment in the developing world. Of particular importance is fluency in a widely spoken "world language" such as English, which is typically a second language for these low-income learners. We make the case that mobile games on cellphones is an appropriate solution in the typical ecologies of developing regions. The challenge is to design e-learning games that are both educational and pleasurable for our target learners, who have limited familiarity with high technology. We propose the receptive-practice-activation cycle that could be used as the conceptual model for the designs. We then report how this format could be refined, based on our experiences in the field with three games that have collectively undergone nine rounds of iterations. In particular, it appears that maintaining a distinction between learning and fun to some extent is necessary for effective designs.

Information Technology has had significant impact on the society and has touched all aspects of our lives. So far, computers and expensive devices have fueled this growth. The challenge now is to take this success of IT to its next level where IT services can be accessed by masses. "Masses" here mean the people who (a) are not yet IT literate and/or (b) do not have the purchase power to use the current IT delivery mechanisms (PC centric model) and/or (c) do not find current IT solutions and services relevant to their life or business. Interestingly, a huge portion of the world's population falls in this category. To enable the IT access to such masses, this workshop focuses on easy-to-use and affordable, yet powerful, user interfaces that can be used by this population.

In this paper we explore private computation built on vector addition and its applications in privacy-preserving data mining. Vector addition is a surprisingly general tool for implementing many algorithms prevalent in distributed data mining. Examples include linear algorithms like voting and summation, as well as non-linear algorithms such as SVD, PCA, k-means, ID3, machine learning algorithms based on Expectation Maximization (EM), etc., and all algorithms in the statistical query model [27]. The non-linear algorithms aggregate data only in certain steps, such as conjugate gradient, which are linear in the data. We introduce a new and highly efficient VSS (Verifiable Secret-Sharing) protocol in a special but widely-applicable model that allows secret-shared arithmetic operations in such aggregation steps to be done over small fields (e.g. 32 or 64 bits). There are two major advantages: (1) in this framework private arithmetic operations have the same cost as normal arithmetic and (2) the scheme admits extremely efficient zero-knowledge (ZK) protocols for verifying properties of user data. As a concrete example, we present a very efficient zero-knowledge method based on random projection for verification that uses a linear number of inexpensive small field operations, and only a logarithmic number of large-field (1024 bits or more) cryptographic operations. Our implementation shows that the approach can achieve orders of magnitude reduction in running time over standard techniques (from hours to seconds) for large scale problems. The ZK tools provide efficient mechanisms for dealing with actively cheating users, a realistic threat in distributed data mining which has been lacking practical solutions.

Poor literacy remains a decisive barrier to the economic empowerment of many people in the developing world. Of particular importance is literacy in a widely spoken "world language" such as English, which is typically a second language for these speakers. For complex reasons, schools are often not effective as vehicles for second language learning. In this paper we explore game-like language learning on cell phones. We argue that phones are an excellent technology platform in the typical ecologies of developing countries. We present the PACE framework that is intended to support the rapid, scalable development of language learning software localized for a particular community of learners. These learners are usually skeptical of formal education and of cultural biases they encounter in learning "remote" languages in particular. Localization of content is crucial to make the language relevant to them and to encourage them to adopt it.

Video conferencing is still considered a poor alternative to face-to-face meetings. In the business setting, where these systems are most prevalent, the misuse of video conferencing systems can have detrimental results, especially in high-stakes communications. Prior work suggests that spatial distortions of nonverbal cues, particularly gaze and deixis, negatively impact many aspects of effective communication in dyadic communications. However, video conferencing systems are often used for group-to-group meetings where spatial distortions are exacerbated. Meanwhile, its effects on the group dynamic are not well understood. In this study, we examine the effects that spatial distortions of nonverbal cues have on inter-group trust formation. We conducted a large (169 participant) study of group conferencing under various conditions. We found that the use of systems that introduce spatial distortions negatively affect trust formation patterns. On the other hand, these effects are essentially eliminated by using a spatially faithful video conferencing system.

Technology arguably has the potential to play a key role in improving the lives of people in developing regions. However, these communities are not well understood and designers must thoroughly investigate possibilities for technological innovations in these contexts. We describe findings from two field studies in India and one in Uganda where we explore technological solutions in the domains of communication, microfinance and education. Two common underlying themes emerge from these studies: (1) local stakeholders can contribute cultural information relevant to design such as needs and practices through interaction with technology artifacts and (2) unique social network structures embedded within communities are crucial to the acceptance and potential adoption of technology. We end with a synthesis of the three experiences that draws some practical lessons for ICT designers to elicit meaningful feedback and participation from local stakeholders in developing regions communities.

Recent HCI research shows strong interest in task management systems (e.g. [19, 27]) that support the multi-tasked nature of information work [13]. These systems either require users to manually create and maintain task representations or they depend on explicit user cues to guide the creation and maintenance process. To access and use the task representations in these systems, users must also specify their current task. This interaction overhead inhibits the adoption of these systems. In this paper, we present a novel approach to task management that automates the creation and maintenance of task representations. Our system supports the user by making commonly used information more "ready-at-hand" through an intuitive visualization of their task representations. Users can correct and organize their task representations by directly manipulating the visualization; however, this interaction is not required. We describe a feasibility study that demonstrates the actual utility (in terms of overhead reduction) and perceived utility of our system.

In this paper we introduce a new practical framework, called P4P (peers for privacy), for privacy-preserving data mining. P4P features a hybrid architecture combining P2P and client-server paradigms and provides practical private protocols for user data validation and general computation. The architecture is guided by the natural incentives of the participants and allows the computation to be based on verifiable secret sharing (VSS) where arithmetic operations are done over small fields (e.g. 32 or 64 bits), so that private arithmetic operations have the same cost as normal arithmetic. Verification of user data, which uses large-field public-key arithmetic (1024 bits or more) and homomorphic computation, only requires a small number (constant or logarithmic in the size of user data) of large integer operations. The solution is extremely efficient: In experiments with our implementation, verification of a million-element vector takes a few seconds of server or client time on commodity PCs (in contrast, using standard techniques takes hours). This verification can be used in many privacy-preserving data mining tasks to detect cheating users who attempt to bias the computation by submitting exaggerated values as their inputs. As an example, we demonstrate how association rule mining can be done in the P4P model with near-optimal efficiency and provable privacy

Low levels of education remain a barrier to economic empowerment in the developing world. In our work on English language learning among underserved communities in India since 2004, we have observed differences between school communities in terms of their access to educational opportunities outside school, access to ICTs including cellphones and digital gaming, enthusiasm for visitors, and the relationships between students. We report on these observations and argue that they call for the greater use of a comparative approach in constructing models of the micro-cultures at various schools, so that user-centered design processes and methods can better account for the unique differences across communities.

Many network applications are based on a group communications model where one party sends messages to a large number of authorized recipients and/or receives messages from multiple senders. In this paper we present a secure group communication scheme based on a new cryptosystem that admits a rigorous proof of security against adaptive chosen ciphertext attack (IND-CCA2). Our scheme is bi-directional, supporting both one-to-many and many-to-one communications. Compared with existing solutions, our scheme achieves the following improvements: (1) It guarantees data confidentiality and authenticity in both directions; (2) It is the most scalable solution so far among all existing schemes achieving (1). The group member storage overhead is constant while both the center storage and rekeying communication complexity are independent of group size. (3) It can be made to achieve higher level of security and hide even the information about the group dynamics. We show that this protection is more effective and more efficient than existing solutions.

In this paper we explore private computation built on vector addition which is a surprisingly general tool for implementing many useful analysis on user-provided data. Examples include both linear and non-linear algorithms such as singular value decomposition (SVD), regression, analysis of variance (ANOVA), and several machine learning algorithms based on Expectation Maximization (EM). The non-linear algorithms aggregate user data only in certain steps, such as conjugate gradient, which are linear in per-user data. We introduce a new and highly efficient VSS (Verifiable Secret-Sharing) protocol in a special but widely-applicable model that allows secret-shared arithmetic operations in such aggregation steps to be done over small fields (e.g. 32 or 64 bits), so that private arithmetic operations have the same cost as normal arithmetic. Verification of user data is required to prevent a malicious user from biasing the computation. We provide a random projection method for verification that uses a linear number of inexpensive small field operations, and only a logarithmic number of large-field (1024 bits or more) cryptographic operations. Our implementation shows that the approach can achieve orders of magnitude reduction in running time over standard techniques (from hours to seconds) for large scale problems (e.g. at the scale where the number of values per user is 106).

We present several interesting applications for the Pattern-Annotated Course Tool (PACT) and pedagogical design patterns in the process of curriculum design. PACT is a visual editor in which content designers can create visual representations of their courses and annotate them with references to educational theory in the form of pedagogical patterns. Each usage scenario illustrates the opportunities for learning that PACT, the annotation process, and the artifacts that users create present to experts, novices, and everyone in between. Finally, we take an in-depth look at one ongoing course annotation being crafted by an experienced curriculum designer and examine his interesting findings from the process. An analysis of these discoveries demonstrates the utility of PACT in the curriculum design process.

This paper draws on a 2-week design workshop conducted at a rural primary school in northern India to provide recommendations on carrying out participatory design with school children in rural, underdeveloped regions. From our experiences in prototyping low-tech and hi-tech English language learning games with rural student participants, we advocate that researchers build a more equal relationship that is qualitatively different from one between teachers and students, enlist local adults and children as facilitators, and explore hi-tech prototyping to inspire the best designs.

This paper presents TinyMotion, a pure software approach for detecting a mobile phone user's hand movement in real time by analyzing image sequences captured by the built-in camera. We present the design and implementation of TinyMotion and several interactive applications based on TinyMotion. Through both an informal evaluation and a formal 17-participant user study, we found that 1. TinyMotion can detect camera movement reliably under most background and illumination conditions. 2. Target acquisition tasks based on TinyMotion follow Fitts' law and Fitts law parameters can be used for TinyMotion based pointing performance measurement. 3. The users can use Vision TiltText, a TinyMotion enabled input method, to enter sentences faster than MultiTap with a few minutes of practicing. 4. Using camera phone as a handwriting capture device and performing large vocabulary, multilingual real time handwriting recognition on the cell phone are feasible. 5. TinyMotion based gaming is enjoyable and immediately available for the current generation camera phones. We also report user experiences and problems with TinyMotion based interaction as resources for future design and development of mobile interfaces.

We describe Livenotes, a shared whiteboard system and educational practice that uses wireless communication and tablet computing to support real-time conversations within small groups of students during lectures, independent of class size. We present an interface design that enables group members to interact with one another by taking lecture notes cooperatively, as well as to augment student note-taking by providing instructor slides in the background to annotate over. Livenotes was designed to facilitate more efficient, stimulating modes of learning that other collaborative approaches do not. We report how the system impacts cooperative learning in an undergraduate class and how students interacted with background slides in the workspace. We conclude with directions for improving the system and learning practice.

MultiView is a new video conferencing system that supports collaboration between remote groups of people. MultiView accomplishes this by being spatially faithful. As a result, MultiView preserves a myriad of nonverbal cues, includ-ing gaze and gesture, in a way that should improve com-munication. Previous systems fail to support many of these cues because a single camera perspective warps spatial char-acteristics in group-to-group meetings. In this paper, we present a formal definition of spatial faithfulness. We then apply a metaphor-based design methodology to help us spec-ify and evaluate MultiView's support of spatial faithfulness. We then present results from a low-level user study to mea-sure MultiView's effectiveness at conveying gaze and ges-ture perception. MultiView is the first practical solution to spatially faithful group-to-group conferencing, one of the most common applications of video conferencing.

Based on our findings from an ongoing pilot with shared computers in rural primary schools in Uttar Pradesh, India since 2001 and two follow-up field studies in the same schools in 2004, we propose some principles for designing educational technology for developing countries as hypotheses. They include constructivist, small-group collaborative learning through digital storytelling and integrating paper- with computer-based practices. We also discuss the need to balance pedagogy, usability and mobility.

As cameraphones become the dominant platform for consumer multimedia capture worldwide, multimedia researchers are faced both with the challenge of how to help users manage the billions of photographs they are collectively producing and the opportunity to leverage cameraphones' ability to automatically capture temporal, spatial, and social contextual metadata to help manage consumer multimedia content. In our Mobile Media Metadata 2 (MMM2) prototype, we apply collaborative filtering techniques to automatically gathered contextual metadata to infer the likely sharing recipients for photos captured on cameraphones. We show that while current cameraphone sharing interfaces are fraught with difficulty, it is possible to use a context-aware approach to make the sharing of cameraphone photos simpler and more satisfying for users. Based on our analysis of the relative contributions of different cameraphone sensors to predicting the likely recipients for photos, we discover for our user population that the temporal context of photo capture proved highly predictive of photo sharing behavior.

In this paper, we focus on the use of context-aware, collaborative filtering, machine-learning techniques that leverage automatically sensed and inferred contextual metadata together with computer vision analysis of image content to make accurate predictions about the human subjects depicted in cameraphone photos. We apply Sparse-Factor Analysis (SFA) to both the contextual metadata gathered in the MMM2 system and the results of PCA (Principal Components Analysis) of the photo content to achieve a 60% face recognition accuracy of people depicted in our cameraphone photos, which is 40% better than media analysis alone. In short, we use context-aware media analysis to solve the face recognition problem for cameraphone photos.

We present a probabilistic model for a document corpus that combines many of the desirable features of previous models. The model is called "GaP" for Gamma-Poisson, the distributions of the first and last random variable. GaP is a factor model, that is it gives an approximate factorization of the document-term matrix into a product of matrices Λ and X. These factors have strictly non-negative terms. GaP is a generative probabilistic model that assigns finite probabilities to documents in a corpus. It can be computed with an efficient and simple EM recurrence. For a suitable choice of parameters, the GaP factorization maximizes independence between the factors. So it can be used as an independent-component algorithm adapted to document data. The form of the GaP model is empirically as well as analytically motivated. It gives very accurate results as a probabilistic model (measured via perplexity) and as a retrieval model. The GaP model projects documents and terms into a low-dimensional space of "themes," and models texts as "passages" of terms on the same theme.

Collaborative filtering (CF) is valuable in e-commerce, and for direct recommendations for music, movies, news etc. But today's systems have several disadvantages, including privacy risks. As we move toward ubiquitous computing, there is a great potential for individuals to share all kinds of information about places and things to do, see and buy, but the privacy risks are severe. In this paper we describe a new method for collaborative filtering which protects the privacy of individual data. The method is based on a probabilistic factor analysis model. Privacy protection is provided by a peer-to-peer protocol which is described elsewhere, but outlined in this paper. The factor analysis approach handles missing data without requiring default values for them. We give several experiments that suggest that this is most accurate method for CF to date. The new algorithm has other advantages in speed and storage over previous algorithms. Finally, we suggest applications of the approach to other kinds of statistical analyses of survey or questionaire data.

Server-based collaborative filtering systems have been very successful in e-commerce and in direct recommendation applications. In future, they have many potential applications in ubiquitous computing settings. But today's schemes have problems such as loss of privacy, favoring retail monopolies, and with hampering diffusion of innovations. We propose an alternative model in which users control all of their log data. We describe an algorithm whereby a community of users can compute a public "aggregate" of their data that does not expose individual users' data. The aggregate allows personalized recommendations to be computed by members of the community, or by outsiders. The numerical algorithm is fast, robust and accurate. Our method reduces the collaborative filtering task to an iterative calculation of the aggregate requiring only addition of vectors of user data. Then we use homomorphic encryption to allow sums of encrypted vectors to be computed and decrypted without exposing individual data. We give verification schemes for all parties in the computation. Our system can be implemented with untrusted servers, or with additional infrastructure, as a fully peer-to-peer (P2P) system.

This paper uses a social psychological perspective to study the effectiveness of different media of communication and how they influence interactions in social groups and organizations. In particular, we are interested in the social richness of the media-how effectively they convey the personalities and intentions of their users. We studied CMC (email and chat) and voice telephony, and compared them with face-to-face interaction. Study 1 was a controlled laboratory study in which people got acquainted with a partner. Study 2 was a field survey in which employees reported on naturally occurring interactions at work that took place with people of varying levels of power (supervisor, peer, subordinate). The surprising result is that the telephone generally came out on top in both studies, suggesting that the telephone may provide the optimum blend of richness and presence for natural and satisfying interactions.

We describe a new control method for vibrations-based planar manipulation. We've developed a device-the Universal Planar Manipulator (UPM)-based on a single, horizontally-vibrating plate. Though minimalist in construction (one moving part), the UPM can manipulate several parts on its surface in parallel, simply using friction. The authors previously showed (1998) that a sequence of rigid plate rotations can be computed which produces pre-specified part displacements. Here we present a new method based on a special motion primitive-the "jet"-which displaces a chosen part in a desired direction while keeping all others still. Parallel manipulation then reduces to a round-robin application of jets. This technique is both faster and more robust than the old rotations-based method. Experiments on parallel trajectory following and part sorting are presented. With jets, the UPM becomes a practical technology for applications such as part singulation, feeding, sorting, food handling, product displays, and interactive devices such as active desks and toys.

This is a continuation of our research on the Universal Planar Manipulator (UPM), a device capable of manipulating multiple generic objects with a single horizontally-vibrating, rigid plate (3 DOFs). Objects are propelled by sliding frictional forces developed against the vibrating plate. A special plate vibration creates an average force field called the "jet" which is local, i.e., it is only non-zero near its center. By applying jets at different objects' locations in succession, objects can be made to displace a small amount individually, enabling full parallel manipulation. In particular, a single object can leave on a plane jet, if the jet's center is made to track and its direction made aligned with that object's motion. We provide visualization of the jet with respect to changes in its center, orientation, and focus parameters. Described also are two experiments showing the UPM as a tangible-user interface (docking a beer can to the user's hand) and as a chess player (executing moves of an endgame).

We are developing an interaction technique for rich nonverbal communication through an avatar. By writing a single letter on a pen tablet device, a user can express their ideas or intentions, non-verbally, using their avatar body. Our system solves the difficult problem of controlling the movements of a highly articulated, 3D avatar model using a common input device within the context of an office environment. We believe that writing is a richly expressive and natural means for controlling expressive avatar gesture.

Force feedback coupled with a real-time physically realistic graphic display provides a human operator with an artificial sense of presence in a virtual environment. Furthermore, it allows a human operator to interact with the virtual environment through "touch". We describe a haptic simulation system that allows a human operator to perform real-time interaction with soft 3D objects that go through large global deformations. We model and simulate such a global deformation using geometrically nonlinear finite element methods (FEM). We also introduce an efficient method that computes the force feedback, in real-time, by simulating the collision between the virtual "proxy" and the deformable object. To perceptually satisfy a human operator, haptics requires a much higher update frequency (at least 1000 Hz) than graphics. We update the graphics using full simulation and interpolate the fully simulated states at a higher frequency to render haptics. The interpolation is made possible by intentionally delaying the display (both graphics and haptics) by one full simulation cycle.

Multivariate resultants generalize the Sylvester resultant of two polynomials and characterize the solvability of a polynomial system. They also reduce the computation of all common roots to a problem in linear algebra. We propose a determinantal formula for the sparse resultant of an arbitrary system of n + 1 polynomials in n variables. This resultant generalizes the classical one and has significantly lower degree for polynomials that are sparse in the sense that their mixed volume is lower than their Bézout number. Our algorithm uses a mixed polyhedral subdivision of the Minkowski sum of the Newton polytopes in order to construct a Newton matrix. Its determinant is a nonzero multiple of the sparse resultant and the latter equals the GCD of at most n + 1 such determinants. This construction implies a restricted version of an effective sparse Nullstellensatz. For an arbitrary specialization of the coefficients, there are two methods that use one extra variable and yield the sparse resultant. This is the first algorithm to handle the general case with complexity polynomial in the resultant degree and simply exponential in n . We conjecture its extension to producing an exact rational expression for the sparse resultant.

Many of the most fundamental examples in probability involve the pose statistics of coins and dice as they are dropped on a flat surface. For these parts, the probability assigned to each stable face is justified based on part symmetry, although most gamblers are familiar with the possibility of loaded dice. In industrial part feeding, parts also arrive in random orientations. We consider the following problem: given part geometry and parameters such as center of mass, estimate the probability of encountering each stable pose of the part. We describe three estimators for solving this problem for polyhedral parts with known center of mass. The first estimator uses a quasistatic motion model that is computed in time O(n log n) for a part with n vertices. The second estimator has the same time complexity but takes into account a measure of dynamic stability based on perturbation. The third estimator uses repeated Monte Carlo experiments with a mechanics simulation package. To evaluate these estimators, we used a robot and computer vision system to record the pose statistics based on 3595 physical drop experiments with four different parts. We compare this data to the results from each estimator. We believe this is the first paper to systematically compare alternative estimators and to correlate their performance with statistically significant experiments on industrial parts.

Article Free Access Share on PRoP: personal roving presence Authors: Eric Paulos Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CAView Profile , John Canny Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CA Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, Berkeley, CAView Profile Authors Info & Claims CHI '98: Proceedings of the SIGCHI Conference on Human Factors in Computing SystemsJanuary 1998 Pages 296–303https://doi.org/10.1145/274644.274686Published:01 January 1998Publication History 94citation765DownloadsMetricsTotal Citations94Total Downloads765Last 12 Months92Last 6 weeks25 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

At the intersection of telerobotics, computer networking and human social interaction we have chosen to explore an area we identify as personal tele-embodiment. At the core of this research is an emphasis on the individual person rather than the intricate complexities of the machine. While the mechanical elements of our system are essential to its over-all functionality, our research is driven solely by the study and understanding of the social and psychological aspects of extended human-human interactions rather than the latest techno-gadgetry. In this paper we emphasize the importance of the human component and describe the development of one such simple, inexpensive, Internet-controlled, untethered telerobot or PRoP (personal roving presence) that provides several fundamental elements of personal tele-embodiment.

Part feeders, which separate and orient parts prior to packing and insertion, are critical components of an assembly line. Existing feeders utilize off-plane vibrations of a rigid structure to convey parts along a track. Repeated part hopping/landing phases are concerns if parts are delicate and/or high positioning accuracy is required. Here we consider a simpler feeder design in which parts are in permanent contact with a horizontally-vibrating flat plate. Each vibration is a "pump-like" motion along a single degree of freedom: the plate spends more time moving forward than backward. Parts are propelled forward since dynamic friction is fixed and independent of the relative velocity at the interface. In designing plate vibration profiles we consider issues of waveform simplicity, bandwidth, and feed rate performance. Both bang-bang and sinusoidal control waveforms are analyzed. Expressions are derived for equilibrium feed rates for both waveforms; dynamic simulation is used to verify the analysis. A prototype of the proposed feeder has been implemented with cheap mechanical parts. A simple experiment with the device is presented.

We consider the problem of parallel part manipulation, i.e., the simultaneous position and orientation control of one or more parts in a bounded region of the plane. We propose a novel, minimalist device, based on a single horizontally-vibrating flat plate. We show that a closed rigid motion of the plate, involving its 3 DOF, can be computed which produces desired average forces at a finite number of points, e.g., parts locations. This implies that one or more parts can follow independent trajectories simultaneously, as they interact with a single vibrating plate. This is in sharp contrast with more complex designs such as massively-parallel actuator arrays and/or prehensile manipulation. Dynamic simulation is used to test the current method in two parallel part manipulation examples. A prototype of the device has been built with inexpensive parts; physical implementation of the proposed method is currently underway.

The design of industrial parts feeders is a long, trial-and-error process that can take months-even for the design of feeders that orient only one type of part. This paper describes the use of dynamic simulation to expedite the design and prototyping of parts feeders. We give probabilistic descriptions of vibratory parts feeding behavior and we present a comparison between simulated design experiments and physical experiments done using a real industrial vibratory bowl feeder. Our findings show strong similarities between the results of the two types of experiments. We believe that dynamic simulation is a promising approach for expediting the parts feeder analysis and design process.

We use dynamic simulation to optimize the design of an existing micro-electromechanical (MEM) device, called the manipulation chip (M-Chip). This device contains an excess of 10000 moving actuators, called resonators, which oscillate torsionally at a few kHz. Parts dropped on the chip's surface are conveyed towards a unique direction. Given the enormous number of moving parts, it is impractical to attempt to measure the device's (or part's) dynamic state during a manipulation task. Yet, knowing this information is crucial for redesign and optimization. We make use of a powerful dynamic simulation tool, called "Impulse", to generate synthetic measurements over a range of experiments. From these results, we suggest redesign options which debug existing problems and improve the feed rate. The array is found to behave similar to a viscous spring-loaded conveyor belt; most of its energy is spent on driving the part vertically, calling for a more efficient design.

We analyze the dynamics of part motion for a novel type of planar parts feeder consisting of a longitudinally vibrating flat plate and a part placed on its surface. For each vibration cycle, the plate's velocity is held positive (forward motion) for a longer time than it is held negative (backward motion). This type of asymmetric vibration combined with the nonlinear nature of Coulomb friction causes the part to accelerate along a straight line to a terminal velocity called the "feed rate". The average force exerted by the plate on the part is shown to be proportional to the latter's deviation from the feed rate. In other words, the part behaves as if it were immersed in a forward moving viscous fluid. Expressions for the feed rate and viscosity constants are derived with respect to various physical and control parameters. Rigid-body dynamic simulation results are shown to be in good agreement with the analysis.

Article Interfacing reality (panel): exploring emerging trends between humans and machines Share on Authors: Eric Paulos University of California, Berkeley University of California, BerkeleyView Profile , John Canny University of California, Berkeley University of California, BerkeleyView Profile , Eduardo Kac School of the Art Institute of Chicago School of the Art Institute of ChicagoView Profile , Ken Goldberg University of California, Berkeley University of California, BerkeleyView Profile , Mark Pauline Survival Research Laboratories Survival Research LaboratoriesView Profile , Stelarc Performance Artist Performance ArtistView Profile Authors Info & Claims SIGGRAPH '97: Proceedings of the 24th annual conference on Computer graphics and interactive techniquesAugust 1997 Pages 448–451https://doi.org/10.1145/258734.258904Online:03 August 1997Publication History 0citation384DownloadsMetricsTotal Citations0Total Downloads384Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

No abstract available.

Considers the problem of designing traditional (e.g. vibratory bowl) feeders for singulating and orienting industrial parts. The ultimate goal is to prototype new designs using analytically- and geometrically-based methods. The authors have developed a tool for designing industrial parts feeders based on dynamic simulation. The authors' tool allows them to automatically perform multiple feeder design experiments, and to evaluate their outcomes. These results can then be used to compute the probabilities of a Markov model for the feeder. To demonstrate the technique, the authors present preliminary results for the design of two simple feeders. The findings suggest that using dynamic simulation is a promising approach for designing parts feeders.

In automated assembly lines, part feeders often impose a bottleneck that restricts throughput. To facilitate the design of parts and assembly lines, the authors estimate feedrates based on CAD models of parts. A previous paper (Golberg and Craig, 1995) described how to predict throughput for a vision-based robotic part feeder given the distribution of part poses when parts are randomly dropped on a conveyor belt. Estimating this distribution is also useful for the design of traditional feeders such as vibratory bowls. In this paper the authors describe three algorithms for estimating pose distributions. The authors review the quasi-static estimate reported in Wiegley et al. (1992) and introduce a refinement that takes into account some measure of dynamic stability. The perturbed quasi-static estimate can be computed very rapidly and is more accurate than the quasi-static. Still more accurate are estimates based on Monte Carlo simulation using Impulse, although the latter comes at the penalty of increased computation time. The authors compare estimates from all three algorithms with physical experiments.

Robots provide us with a means to move around in, visualize, and interact with a remote physical world. We have exploited these physical properties coupled with the growing diversity of users on the World Wide Web (WWW) to create a WWW based telerobotic remote environment browser. This browser, called Mechanical Gaze, allows multiple remote WWW users to control a robot arm with an attached camera to explore a real remote environment. The environment varies but is typically composed of collections of physical museum exhibits which WWW users can view at various positions, orientations, and levels of resolution.

The term fixturing refers to the task of immobilizing a workpiece for the purpose of performing operations such as assembly and machining. As such, fixturing is of fundamental importance to industrial manufacturing. Fixtures can either be fabricated from scratch, or assembled from a toolkit of modular components, the latter approach is termed modular fixturing. In this paper, we present a complete algorithm to automatically design fixtures for the fixture vice toolkit. The algorithm enumerates fixture configurations, consisting of peg positions, workpiece pose, and jaw separation, for a given generalized polyhedral workpiece. A generalized polyhedral prismatic workpiece is defined to have a generalized polygonal silhouette, with a boundary composed of linear edges and circular area.

Model based object recognition and object localization are fundamental problems in industrial automation. The authors present techniques which use a scanner composed of binary light beam sensors to quickly recognize objects (as fast as 5 microseconds) and to accurately localize objects (0.025 millimeters), and they describe localization and recognition experiments and present results. Binary sensors only sense whether the part is present or absent at a particular location, and their high performance is due to their simple specification. Fast recognition is achieved by using indexing to solve the correspondence problem, the problem of interpreting the sensed data as model features; indexing involves using the sensed data to directly look up the correspondence information using a precomputed indexing table. Since each experiment only produces a single indexing vector, indexing tables need to be complete; in this paper the authors detail a complete indexing construction method for flat polygonal and polyhedral objects.

We introduce a promising new approach to rigid body dynamic simulation called impulse-based simulation. The method is well suited to modeling physical systems with large numbers of collisions, or with contact modes that change frequently. All types of contact (colliding, rolling, sliding, and resting) are modeled through a series of collision impulses between the objects in contact, hence the method is simpler and faster than constraint-based simulation. We have implemented an impulse-based simulator that can currently achieve interactive simulation times, and real time simulation seems within reach. In addition, the simulator has produced physically accurate results in several qualitative and quantitative experiments. After giving an overview of impulse-based dynamic simulation, we discuss collision detection and collision response in this context, and present results from several experiments.

We wish to increase the power of an arbitrary algorithm designed for nondegenerate input by allowing it to execute on all inputs. We concentrate on infinitesimal symbolic perturbations that do not affect the output for inputs in general position. Otherwise, if the problem mapping is continuous, the input and output space topology are at least as coarse as the real euclidean one, and the output space is connected, then our perturbations make the algorithm produce an output arbitrarily close or identical to the correct one. For a special class of algorithms, which includes several important algorithms in computational geometry, we describe a deterministic method that requires no symbolic computation. Ignoring polylogarithmic factors, this method increases the worst-case bit complexity only by a multiplicative factor which is linear in the dimension of the geometric space. For general algorithms, a randomized scheme with an arbitrarily high probability of success is proposed; the bit complexity is then bounded by a small-degree polynomial in the original worst-case complexity. In addition to being simpler than previous ones, these are the first efficient perturbation methods.

Indexing is a model-based recognition technique, in which unknown objects are identified using lookup tables. Indexing coordinates are extracted from sensed features, and the indexing coordinates specify a table entry containing the object's identity. Usually, only a small fraction of the possible indexing coordinates correspond to modeled objects, and hash tables are often used to save space. In this paper, we present a new indexing data structure called a tree grid which has two advantages over hash tables. (i) The tree grid preserves spatial ordering, so that nearby indexing entries can be retrieved efficiently (ii) The tree grid compacts the storage size of the table by a factor of as much as two orders of magnitude. k coordinates index an ordering of the interpretations, and 1 coordinate determines the consistent interpretations for objects with k degrees of freedom. We also show that for almost all model sets, 2k+1 indexing coordinates care sufficient to discriminate between two generic models, implying that 2k+1 indexing coordinates specify a unique in interpretation. We have implemented an indexing algorithm for recognizing 3D objects from pairs of image rays using the tree grid technique, and the results are reported.>

At the intersection of robotics, computational geometry, and manufacturing engineering, we have identified collection of research problems with near-term industrial applications. The common thread is robot systems with reduced intricacy in sensing and control (RISC), such as light beam sensors and parallel-jaw grippers. We conjecture that such systems, coupled with appropriate algorithms, are capable of recognizing and orienting a broad class of industrial parts. When compared with general-purpose robots, the resulting systems could be: (1) lower in cost, (2) more reliable, and (3) easier to reconfigure. The proposed hardware bears a close resemblance to existing "hard" automation; what is new is the application of computational methods for robust design and control of these systems, and more extensive use of simple sensors. By focusing on a small vocabulary of simple hardware, planning become computationally tractable and we can in some cases make guarantees about the existence of solutions. We borrowed the RISC acronym from computer architecture to acknowledge a common theme: identifying a minimal set of hardware primitives and matching these primitives with highly efficient software. In this paper, we review recent algorithms for locating, feeding, inserting and fixturing industrial parts. We discuss related work and propose a set of open problems for future research.>

We present an efficient contact determination algorithm for objects undergoing rigid motion. The environment consists of polytopes and models described by algebraic sets. We extend an expected constant time collision detection algorithm between convex polytopes to concave polytopes and curved models. The algorithm makes use of hierarchical representations for concave polytopes and local, global methods for solving polynomial equations to determine possible contact points. We also propose techniques to reduce O(n/sup 2/) pairwise intersection tests for a large environment of n objects. These algorithms work well in practice and give real time performance for most environments.>

We consider the problem of finding optimum force closure grasps of two and three-dimensional objects. Our focus is on grasps which are useful in practice, namely grasps with a small number of fingers, with friction at the contacts. Assuming frictional contact and rounded finger tips-very mild assumptions in practice-we give new upper (and lower) bounds on the number of fingers necessary to achieve force closure grasps of 2-D and 3-D objects. We develop an optimality criterion based on the notion of decoupled wrenches, and use this criterion to derive optimum two and three finger grasps of 2-D objects, and optimum three finger grasps for 2-D objects. We present a simple O(n) algorithm for computing these optimum grasps for convex polygons, a O(n log n) algorithm for nonconvex polygons, and an O(n/sup 3/) algorithm for polyhedra. In studying these optimum grasps, we derive several interesting theoretical results concerning grasp geometry.>

Peg-in-hole insertion is not only a longstanding problem in robotics but the most common automated mechanical assembly task. In this paper the authors present a high precision, self-calibrating peg-in-hole insertion strategy using several very simple, inexpensive, and accurate optical sensors. The self-calibrating feature allows the authors to achieve successful dead-reckoning insertions with tolerances of 25 microns without any accurate initial position information for the robot, pegs, or holes. The program the authors implemented works for any cylindrical peg, and the sensing steps do not depend on the peg diameter, which the program does not know. The key to the strategy is the use of a fixed sensor to localize both a mobile sensor and the peg, while the mobile sensor localizes the hole. The authors' strategy is extremely fast, localizing pegs as they are en route to their insertion location without pausing. The result is that insertion times are dominated by the transport time between pick and place operations.>

We propose a truly incremental exact navigation algorithm for general articulated robots: the robot may start with no apriori information about its environment, and is guaranteed to find the goal if it is reachable, or halt otherwise. The algorithm, termed the incremental roadmap algorithm, constructs a roadmap based on distance data collected online and encoded as repulsive potential field. The incremental behavior is achieved with two novel abstract sensors: a critical point detector and a minimum passage detector. We show by examples which environmental features must be measured by the detectors for a planar-body robot.>

Fixturing is a fundamental problem in mechanical assembly. Usually, two and a half dimensional objects can be fixtured in many different ways using a fixture vice, especially if pegs of different radii are available. The authors present an algorithm which enumerates all force closure fixture vice configurations and corresponding object poses. Automatic fixture design algorithms are essential for planning because optimal fixturing selections for multiple operations requires examining all of the valid configurations. The algorithm runs in O(A) time, where A is the number of configurations which simultaneously contact the object.>

In this paper, we present an algorithm and implementation for efficient inverse kinematics for a general six-revolute (6R) manipulator. When stated mathematically, the problem reduces to solving a system of multivariate equations. We make use of the algebraic properties of the system and the symbolic formulation used for reducing the problem to solving a univariate polynomial. However, the polynomial is expressed as a matrix determinant and its roots are computed by reducing to an eigenvalue problem. The other roots of the multivariate system are obtained by computing eigenvectors and substitution. The algorithm involves symbolic preprocessing, matrix computations and a variety of other numerical techniques. The average running time of the algorithm, for most cases, is 11 milliseconds on an IBM RS/6000 workstation. This approach is applicable to inverse kinematics of all serial manipulators.>

We propose an efficient method for computing the resultant, of a sparse polynomial system of n + 1 equations in n unknowns.Our approach carries over from [(UE93] and constructs a matrix whose determinant is a nonzero multiple of the resultant, and from which the latter is easily extracted.For certain classes of syskms, it attains optimality by expressing the resultant, as a sillgle determinant.An illll>lenlelltatioll of the algorithm is described and empirical results presented and conlpared with those from [CE93] and [SZ].In addition, the important subproblem of computiug Mixed [Tolumes is examined and an efficient algorithm is inlplemeuted.Dixon ~esultant, of a perturbed system leads to an algorit,hln that terminates successfully in about 30 minutes, while all major Clrobner bases methods seem to run out of memory after running for a few days, even }vhen wor]iing on a homomorphic image of the problem over a finite field [MC92aj.In general, Grobner bases algorit)hlns can also exploit, sparseness; yet, when a sparse resultant, is known, the solution is much faster, as seen iu these applications.There exist some classes of problems, such as the kinematics of mechanisms and the generalized kinematics problem with ods aw expected 183 constraints, for which sparse methto be very efficient.So, ideally, we would like to have a sparse resultant for every problem, which calls for a general algorithm to construct, sparse resultants.The first efficient, algorithm was proposed in [CE93], while here we take a different, tack at

Recently there has been a lot of activity in algorithms that work over real closed fields, and that perform such calculations as quantifier elimination or computing connected components of semi-algebraic sets. A cornerstone of this work is a symbolic sign determination algorithm due to Ben-Or, Kozen and Reif [2]. In this paper we describe a new sign determination method based on the earlier algorithm, but with two advantages: (i) It is faster in the univariate case, and (ii) In the general case, it allows purely symbolic quantifier elimination in pseudo-polynomial time. By purely symbolic, we mean that it is possible to eliminate a quantified variable from a system of polynomials no matter what the coefficient values are. The previous methods required the coefficients to be themselves polynomials in other variables. Our new method allows transcendental functions or derivatives to appear in the coefficients. Another corollary of the new sign-determination algorithm is a very simple, practical algorithm for deciding existentially-quantified formulae of the theory of the reals. We present an algorithm that has a bit complexity of n(k+1)dO(k) (c log n) (1+∈) randomized, or nn+1)dO(k2) c(1+∈) deterministic, for any ∈>0, where n is the number of polynomial constraints in the defining formula, k is the number of variables, d is a bound on the degree, c bounds the bit length of the coefficient. The algorithm makes no general position assumptions, and its constants are much smaller than other recent quantifier elimination methods.

In this paper we study the problem of determining whether two points lie in the same connected component of a semi-algebraic set S. Although we are mostly concerned with sets S ⊆ Rk, our algorithm can also decide if points in an arbitrary set S ⊆ Rk can be joined by joined by a semi-algebraic path, for any real closed field R. Our algorithm computes a one-dimensional semi-algebraic subset R(S) of S (actually of an embedding of S in a space Rk for a certain real extension field R of the given field R. R(S) is called the roadmap of S. The basis of this work is the roadmap algorithm described in [3,4] which worked only for compact, regularly stratified sets. We measure the complexity of the formula describing the set S by the number of polynomials n, their maximum degree d, the maximum length of their coefficients in bits c, and the number of variables k. With respect to the above measures, the bit complexity of our new algorithm is (nk log n)dO(k2))(c log n(1+∈) randomized, or (nk log n)dO(k4)c1+∈) deterministic, for any ∈ >0. Note that the combinatorial complexity (complexity in terms of n) in both cases is within a polylog factor of the worst-case lower bound for the number of connected components Ω(nk).

Kinodynamicplanmng attempts to solve a robot motion problem subject to simultaneous kinematic and dynamics constraints.In the general problem, ggven a robot system, we must find a minimal-time trajectory that goes from a start position and veloclty to a goal position and velocity while avoiding obstacles by a safety margur and respecting constraints cm velocity and acceleration.We consider the simplified case of a point mass under Newtoman mechanics.together with velocity and acceleration bounds.The point must be flown from a start to a goal, amidst polyhedral obstacles in 2D or 3D.Although exact sohztions to this problem are not known, we provide the first provably good approximation algorlthm, and show that it runs in polynomial time.

NC algorithms are given for determining the number and degrees of the factors, irreducible over the complex numbers ${\bf C}$, of a multivariate polynomial with rational coefficients and for approximating each irreducible factor. NC is the class of functions computable by logspace-uniform boolean circuits of polynomial size and polylogarithmic depth. The measures of size of the input polynomial are its degree, coefficient length, number of variables (d, c, and n, respectively). If n is fixed, we give a deterministic NC algorithm. If the number of variables is not fixed, we give a random (Monte-Carlo) NC algorithm in these input measures to find the number and degree of each irreducible factor. After reducing to the two-variable, square-free case, we apply the classical algebraic geometry fact that the absolute irreducible factors of $(P(z_1 ,z_2 ) = 0)$ correspond to the connected components of the real surface (or complex curve) $P(z_1 ,z_2 ) = 0$ minus its singular points. In finding the number of connected components of the surface $P = 0$, the surface is projected to the the $z_2 $-plane. The singular points of $P(z_1 ,z_2 )$ lie over the projection’s critical values. The inverse image of a grid isolating the critical values in the $z_2 $-plane lifts to a one-dimensional real curve skeleton on the surface $(P = 0)$ whose number of connected components is precisely the number of connected components of $P = 0$ minus its singular points. The connectivity of this curve skeleton is constructed symbolically using Sturm sequences associated with the various polynomials defining these maps. Given the number of irreducible factors and their degrees, the actual factors can be reconstructed using the recent result of Neff [Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pp. 152–162] on finding zeros of one-variable polynomials in NC.

Algorithms in computational geometry often use the real-RAM model of computation. This model as-sumes that exact real numbers can be stored in mem-

We wish to increase the power of an arbitrary geometric algorithm designed for non-degenerate input, by allowing it to execute over arbitrary inputs. This paper describes a deterministic direct perturbation of the input which applies to algorithms whose branching decisions depend on determinants in the input parameters. We concentrate on four predicates that cover most important algorithms in computational geometry. The method alters the input parameters by infinitesimal amounts to guarantee that the perturbed input lies in general position. It is an attractive candidate for practical use, and is considerably simpler as well as more efficient than existing approaches. Specifically, it is the first method with a complexity overhead that is polynomial in the input size and, in most cases, a small constant. Under our real computation model, the asymptotic complexity remains unaffected; the bit complexity is at worst increased by a factor proportional to d^2+alpha, where d is the dimension of the geometric space of the input objects and alpha an arbitrarily small positive constant. A variation of the perturbation, applied to two predicates, achieves optimal bit size for the perturbation quantities and is even more efficient. Lastly, we illustrate the applicability of our approach

The authors address the problem of planning optimal grasps. Two general optimality criteria that consider the total finger force and the maximum finger force are introduced and discussed. Their formalization using various metrics on a space of generalized forces is detailed. The geometric interpretation of the two criteria leads to an efficient planning algorithm. An example of its use in a robotic environment equipped with two-jaw and three-jaw is described.>

The authors present a real-time algorithm for the inverse kinematics of general 6R robot manipulators. The algorithm involves symbolic preprocessing, matrix computation and a variety of numerical techniques. The numerical accuracy of these operations is well understood and for most cases it is possible to compute accurate solutions using 64-b IEEE floating point arithmetic available on most workstations. The average running time of the algorithm, for most cases, is 11 ms on an IBM RS/6000 workstation.>

The authors describe a practical path planner for nonholonomic robots in environments with obstacles. The planner is based on building a one-dimensional, maximal clearance skeleton through the configuration space of the robot. Rather than using the Euclidean metric to determine clearance, a special metric which captures information about the nonholonomy of the robot is used. The robot navigates from start to goal states by loosely following the skeleton. The resulting paths taken by the robot are of low complexity. Much of the computation can be done offline for a given robot, making for an efficient planner. The focus is on path planning for mobile robots, particularly the planar two-axle car, but the underlying ideas may be applied to planners for other nonholonomic robots.>

The problem of eliminating variables from a set of polynomial equations arises in many symbolic and numeric applications.The three main

Algorithms modeled as algebraic branching programs, with inputs from an infinite ordered field, are studied. Direct perturbations on the input, so that an algorithm designed under the assumption of nondegeneracy can be applied to all inputs, are described. A deterministic method for algorithms with determinant tests and a randomized one for arbitrary test expressions are defined. They both incur extra complexity factors that are constant in several cases. Moreover, polynomial and exponential time algorithms always remain in the same complexity class while being enhanced with the power to execute on arbitrary inputs. Both methods are distinguished by their conceptual elegance and are significantly faster than previous ones.>

A simple and efficient algorithm for finding the closest points between two convex polynomials is described. Data from numerous experiments tested on a broad set of convex polyhedra on R/sup 3/ show that the running time is roughly constant for finding closest points when nearest points are approximately known and is linear in total number of vertices if no special initialization is done. This algorithm can be used for collision detection, computation of the distance between two polyhedra in three-dimensional space, and other robotics problems. It forms the heart of the motion planning algorithm previously presented by the authors (Proc. IEEE ICRA, p.1554-9, 1990).>

It was shown in ~er75]that the number of roots in (C") n of a polynomial system depends only on the Newton polytopes of the system, for almost all specializations of the coefficients.

Computational methods for manipulating sets of polynomial equations are becoming of greater im-portance due to the use of polynomial equations in various applications. In some cases we need to elim-inate variables from a given system of polynomial equations to obtain a ‘(symbolical y smaller ” system, while in others we desire to compute the numerical solutions of non-linear polynomial equations. Re-cently, the techniques of Gr6bner bases and polyno-mial continuation have received much attention as algorithmic methods for these symbolic and numeric applications. When it comes to practice, these meth-ods are slow and not effective for a variety of rea-sons. In this paper we present efficient techniques for applying multipolynomial resultant algorithms and show their effectiveness for manipulating system of polynomial equations. In particular, we present ef-ficient algorithms for computing the resultant of a system of polynomial equations (whose coefficients may be symbolic variables). These algorithms can be used for interpolating polynomials from their val-ues and expanding symbolic determinants. Moreover, we use multipolynomial resultants for computing the real or complex solutions of non-linear polynomial equations. We also discuss the implementation of these algorithms in the context of certain applic~ tions. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.

An efficient algorithm and a data structure for computing and representing the aspect graph of polyhedral objects under orthographic projection are presented. The aspect graph is an approach to representing 3-D objects by a set of 2-D views, for the purpose of object recognition. In this approach the viewpoint space is partitioned into regions such that in each region the qualitative structure of the line drawing does not change. The viewing data of an object is the partition of the viewpoint space together with a representative view in each region. The algorithm computes the viewing data for line drawings of polyhedral objects under orthographic projection.>

Article Free Access Share on An exact algorithm for kinodynamic planning in the plane Authors: John Canny Computer Science Division, University of California, Berkeley Computer Science Division, University of California, BerkeleyView Profile , Ashutosh Rege Computer Science Division, University of California, Berkeley Computer Science Division, University of California, BerkeleyView Profile , John Reif Computer Science Department, Duke University, Durham, N.C. Computer Science Department, Duke University, Durham, N.C.View Profile Authors Info & Claims SCG '90: Proceedings of the sixth annual symposium on Computational geometryMay 1990Pages 271–280https://doi.org/10.1145/98524.98584Published:01 May 1990Publication History 22citation29DownloadsMetricsTotal Citations22Total Downloads29Last 12 Months16Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

An algorithm is described for planning the motions of several mobile robots which share the same workspace. Each robot is capable of independent translational motion in two dimensions, and the workspace contains polygonal obstacles. The algorithm computes a path for each robot which avoids all obstacles in the workspace as well as the other robots. It is guaranteed to find a solution if one exists. The algorithm takes a cell decomposition approach, where the decomposition used is based on the idea of a product operation defined on the cells in a decomposition of a two-dimensional free space. This algorithm is being implemented for the case of two robots as part of ongoing research into useful algorithms for task-level programming of the RobotWorld system.>

A robot planning algorithm that constructs a global skeleton of free-space by incremental local methods is described. The curves of the skeleton are the loci of maxima of an artificial potential field that is directly proportional to the distance of the robot from obstacles. The method has the advantage of fast convergence of local methods in uncluttered environments, but it also has a deterministic and efficient method of escaping local extremal points of the potential function. The authors present a general algorithm, for configuration spaces of any dimension, and describe instantiations of the algorithm for robots with two and three degrees of freedom.>

An algorithm is presented for generating near-time-optimal trajectories for an open-kinematic-chain manipulator moving in a cluttered workspace. This is the first algorithm to guarantee bounds on the closeness of an approximation to a time-optimal trajectory. The running time and space required are polynomial in the desired accuracy of the approximation. The user may also specify tolerances by which the trajectories must clear obstacles in the workspace to allow modeling of control errors.>

A notion of robustness for a mobile robot trajectory is introduced. It captures the sense that there are nearby trajectories which are also collision-free and satisfy the kinematic constraints. An algorithm is presented which is guaranteed to plan robust paths with a running time of O(n/sup 4/ log n+n/sup 2// delta /sup 2/), where n is the number of obstacle vertices and delta is a measure of the robustness of the path. Also discussed are the modifications required for the algorithm to allow for uncertainty in position.>

The motion of two rigid bodies under rolling constraint is considered. In particular, the following two problems are addressed: (1) given the geometry of the rigid bodies, determine the existence of an admissible path between two contact configurations; and (2) assuming that an admissible path exists, find such a path. First, the configuration space of contact is defined, and the differential equations governing the rolling constraint are derived. Then, a generalized version of Frobenius's theorem, known as Chow's theorem, for determining the existence of motion is applied. Finally, an algorithm is proposed that generates a desired path with one of the objects being flat. Potential applications of this study include adjusting grasp configurations of a multifingered robot hand without slipping, contour following without dissipation or wear by the end-effector of a manipulator, and wheeled mobile robotics.>

It is shown that fine motion plans in the LMT framework developed by T. Lozano-Perez, M. Mason and R. Taylor (1984) are computable, and an algorithm for computing them by reducing fine motion planing to an algebraic decision problem is presented. Fine-motion planning involves planning a successful motion of a robot at the fine scale of assembly operations, where control and sensor uncertainty are significant. It is shown that, as long as the envelope of trajectories generated by the control system can be described algebraically, there is an effective procedure for deciding if a successful n-step plan exists. The proposed method makes use of recognizable sets as subgoals for multistep planning. These sets are finitely parameterizable, and it is shown that they are the only sets that need be considered as subgoals. Unfortunately, if the full generality of the LMT framework is used, finding a fine-motion plan can take time double exponential in the number of plant steps.>

The authors consider the problem of planning paths for a robot which has a minimum turning radius. This is a first step towards accurately modeling a robot with the kinematics of a car. The technique used is to define a set of canonical trajectories which satisfy the nonholonomic constraints imposed. A configuration space can be constructed for these trajectories in which there is a simple characterization of the boundaries of the obstacles generated by the workspace obstacles. The authors describe a graph search algorithm which divides the configuration space into sample trajectories. The characterization of the boundaries makes it possible to calculate an approximate path in time O(n/sup 3// delta log n+Alog (n/ delta )), where n is the number of obstacle vertices in the environment, A is the number of free trajectories, and delta describes the robustness of the generated path and the closeness of the approximation. The authors also describe a plane sweep for computing the configuration space obstacle for a trajectory segment. They use this to generate robust paths using a quadtree based algorithm in time O(n/sup 4/log n+(n/ delta /sup 2/)).>

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.>

We give NC algorithms for determining the number and degrees of the absolute factors (factors irreducible over the complex numbers C) of a multi-variate polynomial with rational coefficients. NC is the class of functions computable by logspace-uniform Boolean circuits of polynomial size and polylogarithmic depth. The measures of size of the input polynomial are its degree d, coefficient length c, number of variables n, and for sparse polynomials, the number of non-zero coefficients s. For the general case, we give a random (Monte-Carlo) NC algorithm in these input measures. If n is fixed, or if the polynomial is dense, we give a deterministic NC algorithm. The algorithm also works in random NC for polynomials represented by straight-line programs, provided the polynomial can be evaluated at integer points in NC. Finally, we discuss a method for obtaining an approximation to the coefficients of each factor whose running time is polynomial in the size of the original (dense) polynomial. These methods rely on the fact that the connected components of a complex hypersurface P(z1…,zn) = 0 minus its singular points correspond to the absolute factors of P.

Article Free Access Share on Solving systems of nonlinear polynomial equations faster Authors: J. F. Canny Univ. of California, Berkeley Univ. of California, BerkeleyView Profile , E. Kaltofen Rensselaer Polytechnic Institute, Troy, NY Rensselaer Polytechnic Institute, Troy, NYView Profile , L. Yagati Rensselaer Polytechnic Institute, Troy, NY Rensselaer Polytechnic Institute, Troy, NYView Profile Authors Info & Claims ISSAC '89: Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computationJuly 1989Pages 121–128https://doi.org/10.1145/74540.74556Published:17 July 1989Publication History 68citation1,515DownloadsMetricsTotal Citations68Total Downloads1,515Last 12 Months142Last 6 weeks17 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The following problem, is considered: given a robot system find a minimal-time trajectory from a start position and velocity to a goal position and velocity, while avoiding obstacles and respecting dynamic constraints on velocity and acceleration. The simplified case of a point mass under Newtonian mechanics together with velocity and acceleration bounds is considered. The point must be flown from a start to a goal, amid 2-D or 3-D polyhedral obstacles. While exact solutions to this problem are not known, the first provably good approximation algorithm is given and shown to run in polynomial time.

The aspect graph is one of the approaches to representing of 3-D shape for the purposes of object recognition. In this approach, the viewing space of an object is partitioned into regions, such that in each region the topology of the line drawing of the object does not change. The viewing data of an object is the partition of the viewing space together with a representative view in each region. We present an efficient algorithm for computing the viewing data for line drawings of polyhedral objects under orthographic projection. For an object of size O(n) whose partition of size O(m), the algorithm runs O(n^4 log n + m log m) time. Using a novel data structure, we construct the set of all views in optimal O(m) time and space

We give a PSPACE algorithm for determining the signs of multivariate polynomials at the common zeros of a system of polynomial equations. One of the consequences of this result is that the “Generalized Movers' Problem” in robotics drops from EXPTIME into PSPACE, and is therefore PSPACE-complete by a previous hardness result [Rei]. We also show that the existential theory of the real numbers can be decided in PSPACE. Other geometric problems that also drop into PSPACE include the 3-d Euclidean Shortest Path Problem, and the “2-d Asteroid Avoidance Problem” described in [RS]. Our method combines the theorem of the primitive element from classical algebra with a symbolic polynomial evaluation lemma from [BKR]. A decision problem involving several algebraic numbers is reduced to a problem involving a single algebraic number or primitive element, which rationally generates all the given algebraic numbers.

We are interested in Voronoi diagrams as a tool in robot path planning, where the search for a path in an τ dimensional space may be simplified to a search on an τ - 1 dimensional Voronoi diagram. We define a Voronoi diagram V based on a measure of distance which is not a true metric. This formulation has lower algebraic complexity than the usual definition, which is a considerable advantage in motion planning problems with many degrees of freedom. In its simplest form, the measure of distance between a point and a polytope is the maximum of the distances of the point from the half-spaces which pass through faces of the polytope. More generally, the measure is defined in configuration spaces which represent rotation. The Voronoi diagram defined using this distance measure is no longer a strong deformation retract of free space, but it has the following useful property: any path through free space which starts and ends on the diagram can be continuously deformed so that it lies entirely on the diagram. Thus it is still complete for motion planning, but it has lower algebraic complexity than a diagram based on the Euclidean metric.

We present an algorithm which solves the findpath or generalized movers' problem in single exponential sequential time. This is the first algorithm for the problem whose sequential time bound is less than double exponential. In fact, the combinatorial exponent of the algorithm is equal to the number of degrees of freedom, making it worst-case optimal, and equaling or improving the time bounds of many special purpose algorithms. The algorithm accepts a formula for a semi-algebraic set S describing the set of free configurations and produces a one-dimensional skeleton or "roadmap" of the set, which is connected within each connected component of S. Additional points may be linked to the roadmap in linear time. Our method draws from results of singularity theory, and in particular makes use of the notion of stratified sets as an efficient alternative to cell decomposition. We introduce an algebraic tool called the multivariate resultant which gives a necessary and sufficient condition for a system of homogeneous polynomials to have a solution, and show that it can be computed in polynomial parallel time. Among the consequences of this result are new methods for quantifier elimination and an improved gap theorem for the absolute value of roots of a system of polynomials.

We present new techniques for establishing lower bounds in robot motion planning problems. Our scheme is based on path encoding and uses homotopy equivalence classes of paths to encode state. We first apply the method to the shortest path problem in 3 dimensions. The problem is to find the shortest path under an Lp metric (e.g. a euclidean metric) between two points amid polyhedral obstacles. Although this problem has been extensively studied, there were no previously known lower bounds. We show that there may be exponentially many shortest path classes in single-source multiple-destination problems, and that the single-source single-destination problem is NP-hard. We use a similar proof technique to show that two dimensional dynamic motion planning with bounded velocity is NP-hard. Finally we extend the technique to compliant motion planning with uncertainty in control. Specifically, we consider a point in 3 dimensions which is commanded to move in a straight line, but whose actual motion may differ from the commanded motion, possibly involving sliding against obstacles. Given that the point initially lies in some start region, the problem of finding a sequence of commanded velocities which is guaranteed to move the point to the goal is shown to be non-deterministic exponential time hard, making it the first provably intractable problem in robotics.

We consider the collision-detection problem for a three-dimensional solid object moving among polyhedral obstacles. The configuration space for this problem is six-dimensional, and the traditional representation of the space uses three translational parameters and three angles (typically Euler angles). The constraints between the object and obstacles then involve trigonometric functions. We show that a quaternion representation of rotation yields constraints which are purely algebraic in a seven-dimensional space. By simple manipulation, the constraints may be projected down into a six-dimensional space with no increase in complexity. The algebraic form of the constraints greatly simplifies computation of collision points, and allows us to derive an efficient exact intersection test for an object which is translating and rotating among obstacles.

This paper describes a computational approach to edge detection. The success of the approach depends on the definition of a comprehensive set of goals for the computation of edge points. These goals must be precise enough to delimit the desired behavior of the detector while making minimal assumptions about the form of the solution. We define detection and localization criteria for a class of edges, and present mathematical forms for these criteria as functionals on the operator impulse response. A third criterion is then added to ensure that the detector has only one response to a single edge. We use the criteria in numerical optimization to derive detectors for several common image features, including step edges. On specializing the analysis to step edges, we find that there is a natural uncertainty principle between detection and localization performance, which are the two main goals. With this principle we derive a single operator shape which is optimal at any scale. The optimal detector has a simple approximate implementation in which edges are marked at maxima in gradient magnitude of a Gaussian-smoothed image. We extend this simple detector using operators of several widths to cope with different signal-to-noise ratios in the image. We present a general method, called feature synthesis, for the fine-to-coarse integration of information from operators at different scales. Finally we show that step edge detector performance improves considerably as the operator point spread function is extended along the edge.

We describe work in progress toward a polynomial-time algorithm for the classical movers' problem With 6 degrees of freedom. Rotations are represented as a certain 3-dimensional subset of the space of quaternions. This representation gives rise to algebraic constraints on the allowable configurations of the moving object. We define a generalized Voronoi diagram in the configuration space and show that a subset of the diagram, consisting of zero and one dimensional manifolds, can be constructed in polynomial time, and paths found along it. While this subset of the diagram is not always sufficient for path planning, the triangulation of 1- dimensional manifolds can be used as the basis of a complete path planning algorithm by adding other 1-manifolds.