Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Localization (6)
- Information retrieval (4)
- Robotics (4)
- Algorithms (3)
- Reinforcement learning (3)
-
- Cache (2)
- Computer Vision (2)
- Digital elevation models (2)
- Evaluation (2)
- Information Retrieval (2)
- Language Models (2)
- Machine Learning (2)
- Mobile robots (2)
- Photogrammetry (2)
- Probabilistic memory safety (2)
- Simulation (2)
- World Wide Web (2)
- Reinforcement Learning (RL) (1)
- decision-theoretic planning. (1)
- explicit congestion notification (ECN) (1)
- explicit loss notification (ELN) (1)
- notation. (1)
- 3D (1)
- Abstraction (1)
- Alias analysis (1)
- Anomaly detection. (1)
- Anonymity (1)
- Anonymous communication (1)
- Application (1)
- Applications (1)
Articles 1 - 30 of 229
Full-Text Articles in Physical Sciences and Mathematics
Quantifying The Impact Of Non-Stationarity In Reinforcement Learning-Based Traffic Signal Control, Lucas N. Alegre, Ana L.C. Bazzan, Bruno C. Da Silva
Quantifying The Impact Of Non-Stationarity In Reinforcement Learning-Based Traffic Signal Control, Lucas N. Alegre, Ana L.C. Bazzan, Bruno C. Da Silva
Computer Science Department Faculty Publication Series
In reinforcement learning (RL), dealing with non-stationarity is a challenging issue. However, some domains such as traffic optimization are inherently non-stationary. Causes for and effects of this are manifold. In particular, when dealing with traffic signal controls, addressing non-stationarity is key since traffic conditions change over time and as a function of traffic control decisions taken in other parts of a network. In this paper we analyze the effects that different sources of non-stationarity have in a network of traffic signals, in which each signal is modeled as a learning agent. More precisely, we study both the effects of changing …
Multi-Sensor Mobile Robot Localization For Diverse Environments, Joydeep Biswas, Manuela M. Veloso
Multi-Sensor Mobile Robot Localization For Diverse Environments, Joydeep Biswas, Manuela M. Veloso
Computer Science Department Faculty Publication Series
Mobile robot localization with different sensors and algorithms is a widely studied problem, and there have been many approaches proposed, with considerable degrees of success. However, every sensor and algorithm has limitations, due to which we believe no single localization algorithm can be “perfect,” or universally applicable to all situations. Laser rangefinders are commonly used for localization, and state-of-theart algorithms are capable of achieving sub-centimeter accuracy in environments with features observable by laser rangefinders. Unfortunately, in large scale environments, there are bound to be areas devoid of features visible by a laser rangefinder, like open atria or corridors with glass …
Episodic Non-Markov Localization: Reasoning About Short-Term And Long-Term Features, Joydeep Biswas, Manuela M. Veloso
Episodic Non-Markov Localization: Reasoning About Short-Term And Long-Term Features, Joydeep Biswas, Manuela M. Veloso
Computer Science Department Faculty Publication Series
Markov localization and its variants are widely used for localization of mobile robots. These methods assume Markov independence of observations, implying that observations made by a robot correspond to a static map. However, in real human environments, observations include occlusions due to unmapped objects like chairs and tables, and dynamic objects like humans. We introduce an episodic non-Markov localization algorithm that maintains estimates of the belief over the trajectory of the robot while explicitly reasoning about observations and their correlations arising from unmapped static objects, moving objects, as well as objects from the static map. Observations are classified as arising …
Localization And Navigation Of The Cobots Over Long-Term Deployments, Joydeep Biswas, Manuela M. Veloso
Localization And Navigation Of The Cobots Over Long-Term Deployments, Joydeep Biswas, Manuela M. Veloso
Computer Science Department Faculty Publication Series
For the last three years, we have developed and researched multiple collaborative robots, CoBots, which have been autonomously traversing our multi-floor buildings. We pursue the goal of long-term autonomy for indoor service mobile robots as the ability for them to be deployed indefinitely while they perform tasks in an evolving environment. The CoBots include several levels of autonomy, and in this paper we focus on their localization and navigation algorithms. We present the Corrective Gradient Refinement (CGR) algorithm, which refines the proposal distribution of the particle filter used for localization with sensor observations using analytically computed state space derivatives on …
Depth Camera Based Indoor Mobile Robot Localization And Navigation, Joydeep Biswas, Manuela M. Veloso
Depth Camera Based Indoor Mobile Robot Localization And Navigation, Joydeep Biswas, Manuela M. Veloso
Computer Science Department Faculty Publication Series
The sheer volume of data generated by depth cameras provides a challenge to process in real time, in particular when used for indoor mobile robot localization and navigation. We introduce the Fast Sampling Plane Filtering (FSPF) algorithm to reduce the volume of the 3D point cloud by sampling points from the depth image, and classifying local grouped sets of points as belonging to planes in 3D (the “plane filtered” points) or points that do not correspond to planes within a specified error margin (the “outlier” points). We then introduce a localization algorithm based on an observation model that down-projects the …
Planar Polygon Extraction And Merging From Depth Images, Joydeep Biswas, Manuela M. Veloso
Planar Polygon Extraction And Merging From Depth Images, Joydeep Biswas, Manuela M. Veloso
Computer Science Department Faculty Publication Series
— There has been considerable interest recently in building 3D maps of environments using inexpensive depth cameras like the Microsoft Kinect sensor. We exploit the fact that typical indoor scenes have an abundance of planar features by modeling environments as sets of plane polygons. To this end, we build upon the Fast Sampling Plane Filtering (FSPF) algorithm that extracts points belonging to local neighborhoods of planes from depth images, even in the presence of clutter. We introduce an algorithm that uses the FSPF-generated plane filtered point clouds to generate convex polygons from individual observed depth images. We then contribute an …
Corrective Gradient Refinement For Mobile Robot Localization, Joydeep Biswas, Manuela M. Veloso, Brian Coltin
Corrective Gradient Refinement For Mobile Robot Localization, Joydeep Biswas, Manuela M. Veloso, Brian Coltin
Computer Science Department Faculty Publication Series
Particle filters for mobile robot localization must balance computational requirements and accuracy of localization. Increasing the number of particles in a particle filter improves accuracy, but also increases the computational requirements. Hence, we investigate a different paradigm to better utilize particles than to increase their numbers. To this end, we introduce the Corrective Gradient Refinement (CGR) algorithm that uses the state space gradients of the observation model to improve accuracy while maintaining low computational requirements. We develop an observation model for mobile robot localization using point cloud sensors (LIDAR and depth cameras) with vector maps. This observation model is then …
Wifi Localization And Navigation For Autonomous Indoor Mobile Robots, Joydeep Biswas, Manuela M. Veloso
Wifi Localization And Navigation For Autonomous Indoor Mobile Robots, Joydeep Biswas, Manuela M. Veloso
Computer Science Department Faculty Publication Series
Building upon previous work that demonstrates the effectiveness of WiFi localization information per se, in this paper we contribute a mobile robot that autonomously navigates in indoor environments using WiFi sensory data. We model the world as a WiFi signature map with geometric constraints and introduce a continuous perceptual model of the environment generated from the discrete graph-based WiFi signal strength sampling. We contribute our WiFi localization algorithm which continuously uses the perceptual model to update the robot location in conjunction with its odometry data. We then briefly introduce a navigation approach that robustly uses the WiFi location estimates. We …
Analyzing Myopic Approaches For Multi-Agent Communication, Raphen Becker
Analyzing Myopic Approaches For Multi-Agent Communication, Raphen Becker
Computer Science Department Faculty Publication Series
Choosing when to communicate is a fundamental problem in multi-agent systems. This problem becomes particularly challenging when communication is constrained and each agent has different partial information about the overall situation. We take a decision-theoretic approach to this problem that balances the benefits of communication against the costs. Although computing the exact value of communication is intractable, it can be estimated using a standardmyopic assumption—that communication is only possible at the present time.We examine specific situations in which this assumption leads to poor performance and demonstrate an alternative approach that relaxes the assumption and improves performance. The results provide an …
Autonomous Geometric Precision Error Estimation In Low-Level Computer Vision Tasks, Andrés Corrada-Emmanuel, Howard Schultz
Autonomous Geometric Precision Error Estimation In Low-Level Computer Vision Tasks, Andrés Corrada-Emmanuel, Howard Schultz
Computer Science Department Faculty Publication Series
Errors in map-making tasks using computer vision are sparse. We demonstrate this by considering the construction of digital elevation models that employ stereo matching algorithms to triangulate real-world points. This sparsity, coupled with a geometric theory of errors recently developed by the authors, allows for autonomous agents to calculate their own precision independently of ground truth. We connect these developments with recent advances in the mathematics of sparse signal reconstruction or compressed sensing. The theory presented here extends the autonomy of 3-D model reconstructions discovered in the 1990s to their errors.
Autonomous Estimates Of Horizontal Decorrelation Lengths For Digital Elevation Models, Andres Corrada-Emmanuel, Howard Schultz
Autonomous Estimates Of Horizontal Decorrelation Lengths For Digital Elevation Models, Andres Corrada-Emmanuel, Howard Schultz
Computer Science Department Faculty Publication Series
The precision errors in a collection of digital elevation models (DEMs) can be estimated in the presence of large but sparse correlations even when no ground truth is known. We demonstrate this by considering the problem of how to estimate the horizontal decorrelation length of DEMs produced by an automatic photogrammetric process that relies on the epipolar constraint equations. The procedure is based on a set of autonomous elevation difference equations recently proposed by us. In this paper we show that these equations can only estimate the precision errors of DEMs. The accuracy errors are unknowable since there is no …
Value Function Approximation In Reinforcement Learning Using The Fourier Basis, George Konidaris, Sarah Osentoski
Value Function Approximation In Reinforcement Learning Using The Fourier Basis, George Konidaris, Sarah Osentoski
Computer Science Department Faculty Publication Series
We describe the Fourier Basis, a linear value function approximation scheme based on the Fourier Series. We empirically evaluate its properties, and demonstrate that it performs well compared to Radial Basis Functions and the Polynomial Basis, the two most popular fixed bases for linear value function approximation, and is competitive with learned Proto-Value Functions even though no extra experience or computation is required.
Here Or There: Preference Judgments For Relevance, Ben Carterette, Paul N. Bennett, David Maxwell Chickering, Susan T. Dumais
Here Or There: Preference Judgments For Relevance, Ben Carterette, Paul N. Bennett, David Maxwell Chickering, Susan T. Dumais
Computer Science Department Faculty Publication Series
Information retrieval systems have traditionally been evaluated over absolute judgments of relevance: each document is judged for relevance on its own, independent of other documents that may be on topic. We hypothesize that preference judgments of the form “document A is more relevant than document B” are easier for assessors to make than absolute judgments, and provide evidence for our hypothesis through a study with assessors. We then investigate methods to evaluate search engines using preference judgments. Furthermore, we show that by using inferences and clever selection of pairs to judge, we need not compare all pairs of documents in …
Watch Global, Cache Local: Youtube Network Traffic At A Campus Network - Measurements And Implications, Michael Zink, Kyoungwon Suh, Yu Gu, Jim Kurose
Watch Global, Cache Local: Youtube Network Traffic At A Campus Network - Measurements And Implications, Michael Zink, Kyoungwon Suh, Yu Gu, Jim Kurose
Computer Science Department Faculty Publication Series
User Generated Content has become very popular since the birth of web services such as YouTube allowing the distribution of such user-produced media content in an easy manner. YouTube-like services are different from existing traditional VoD services because the service provider has only limited control over the creation of new content. We analyze how the content distribution in YouTube is realized and then conduct a measurement study of YouTube traffic in a large university campus network. The analysis of the traffic shows that: (1) No strong correlation is observed between global and local popularity; (2) neither time scale nor user …
Manifold Alignment Using Procrustes Analysis, Chang Wang, Sridhar Mahadevan
Manifold Alignment Using Procrustes Analysis, Chang Wang, Sridhar Mahadevan
Computer Science Department Faculty Publication Series
In this paper we introduce a novel approach to manifold alignment, based on Procrustes analysis. Our approach di®ers from \semi- supervised alignment" in that it results in a mapping that is de¯ned everywhere { when used with a suitable dimensionality reduction method { rather than just on the training data points. We describe and evaluate our approach both theoretically and experimen- tally, providing results showing useful knowl- edge transfer from one domain to another. Novel applications of our method including cross-lingual information retrieval and trans- fer learning in Markov decision processes are presented.
Pacemakers And Implantable Cardiac Defibrillators: Software Radio Attacks And Zero-Power Defenses, Daniel Halperin
Pacemakers And Implantable Cardiac Defibrillators: Software Radio Attacks And Zero-Power Defenses, Daniel Halperin
Computer Science Department Faculty Publication Series
Our study analyzes the security and privacy properties of an implantable cardioverter defibrillator (ICD). Introduced to the U.S. market in 2003, this model of ICD includes pacemaker technology and is designed to communicate wirelessly with a nearby external programmer in the 175 kHz frequency range. After partially reverse-engineering the ICD’s communications protocol with an oscilloscope and a software radio, we implemented several software radio-based attacks that could compromise patient safety and patient privacy. Motivated by our desire to improve patient safety, and mindful of conventional trade-offs between security and power consumption for resourceconstrained devices, we introduce three new zero-power defenses …
Resisting Structural Reidentification Anonymized Social Networks, Michael Hay, Gerome Miklau, David Jensen, Don Towsley, Philipp Weis
Resisting Structural Reidentification Anonymized Social Networks, Michael Hay, Gerome Miklau, David Jensen, Don Towsley, Philipp Weis
Computer Science Department Faculty Publication Series
We identify privacy risks associated with releasing network data sets and provide an algorithm that mitigates those risks. A network consists of entities connected by links representing relations such as friendship, communication, or shared activity. Maintaining privacy when publishing networked data is uniquely challenging because an individual’s network context can be used to identify them even if other identifying information is removed. In this paper, we quantify the privacy risks associated with three classes of attacks on the privacy of individuals in networks, based on the knowledge used by the adversary. We show that the risks of these attacks vary …
Interactive Wifi Connectivity For Moving Vehicles, Aruna Balasubramanian, Ratul Mahajan, Arun Venkataramani, Brian Neil Levine, John Zahorjan
Interactive Wifi Connectivity For Moving Vehicles, Aruna Balasubramanian, Ratul Mahajan, Arun Venkataramani, Brian Neil Levine, John Zahorjan
Computer Science Department Faculty Publication Series
We ask if the ubiquity of WiFi can be leveraged to provide cheap connectivity from moving vehicles for common applications such as Web browsing and VoIP. Driven by this question, we conduct a study of connection quality available to vehicular WiFi clients based on measurements from testbeds in two different cities. We find that current WiFi handoff methods, in which clients communicate with one basestation at a time, lead to frequent disruptions in connectivity. We also find that clients can overcome many disruptions by communicating with multiple basestations simultaneously. These findings lead us to develop ViFi, a protocol that opportunistically …
Exterminator: Automatically Correcting Memory Errors With High Probability, Gene Novark
Exterminator: Automatically Correcting Memory Errors With High Probability, Gene Novark
Computer Science Department Faculty Publication Series
Programs written in C and C++ are susceptible to memory errors, including buffer overflows and dangling pointers. These errors, which can lead to crashes, erroneous execution, and security vulnerabilities, are notoriously costly to repair. Tracking down their location in the source code is difficult, even when the full memory state of the program is available. Once the errors are finally found, fixing them remains challenging: even for critical security-sensitive bugs, the average time between initial reports and the issuance of a patch is nearly one month. We present Exterminator, a system that automatically corrects heap-based memory errors without programmer intervention. …
Piecewise Pseudolikelihood For Efficient Training Of Conditional Random Fields, Charles Sutton, Andrew Mccallum
Piecewise Pseudolikelihood For Efficient Training Of Conditional Random Fields, Charles Sutton, Andrew Mccallum
Computer Science Department Faculty Publication Series
Discriminative training of graphical models can be expensive if the variables have large cardinality, even if the graphical structure is tractable. In such cases, pseudolikelihood is an attractive alternative, because its running time is linear in the variable cardinality, but on some data its accuracy can be poor. Piecewise training (Sutton & McCallum, 2005) can have better accuracy but does not scale as well in the variable cardinality. In this paper, we introduce piecewise pseudolikelihood, which retains the computational efficiency of pseudolikelihood but can have much better accuracy. On several benchmark NLP data sets, piecewise pseudolikelihood has better accuracy than …
Compact Spectral Bases For Value Function Approximation Using Kronecker Factorization, Jeff Johns
Compact Spectral Bases For Value Function Approximation Using Kronecker Factorization, Jeff Johns
Computer Science Department Faculty Publication Series
A new spectral approach to value function approximation has recently been proposed to automatically construct basis functions from samples. Global basis functions called proto-value functions are generated by diagonalizing a diffusion operator, such as a reversible random walk or the Laplacian, on a graph formed from connecting nearby samples. This paper addresses the challenge of scaling this approach to large domains. We propose using Kronecker factorization coupled with the Metropolis-Hastings algorithm to decompose reversible transition matrices. The result is that the basis functions can be computed on much smaller matrices and combined to form the overall bases. We demonstrate that …
Relational Dependency Networks, Jennifer Neville
Relational Dependency Networks, Jennifer Neville
Computer Science Department Faculty Publication Series
Recent work on graphical models for relational data has demonstrated significant improvements in classification and inference when models represent the dependencies among instances. Despite its use in conventional statistical models, the assumption of instance independence is contradicted by most relational datasets. For example, in citation data there are dependencies among the topics of a paper’s references, and in genomic data there are dependencies among the functions of interacting proteins. In this paper, we present relational dependency networks (RDNs), graphical models that are capable of expressing and reasoning with such dependencies in a relational setting. We discuss RDNs in the context …
On Unstructured File Sharing Networks, Honggang Zhang
On Unstructured File Sharing Networks, Honggang Zhang
Computer Science Department Faculty Publication Series
We study the interaction among users of unstructured file sharing applications, who compete for available network resources (link bandwidth or capacity) by opening multiple connections on multiple paths so as to accelerate data transfer. We model this interaction with an unstructured file sharing game. Users are players and their strategies are the numbers of sessions on available paths. We consider a general bandwidth sharing framework proposed by Kelly [1] and Mo and Walrand [2], with TCP as a special case. Furthermore, we incorporate the Tit-for-Tat strategy (adopted by BitTorrent [3] networks) into the unstructured file sharing game to model the …
Web Search From A Bus, Aruna Balasubramanian, Yun Zhou, Bruce Croft, Brian Neil Levine, Arun Venkataramani
Web Search From A Bus, Aruna Balasubramanian, Yun Zhou, Bruce Croft, Brian Neil Levine, Arun Venkataramani
Computer Science Department Faculty Publication Series
Opportunistic connections to the Internet from open wireless access points is now commonly possible in municipal areas. Vehicular networks can opportunistically connect to the internet for several seconds via open access points. In this paper, we adapt the interactive process of web search and retrieval to vehicular networks with intermittent Internet access. Our system, called Thedu has mobile nodes use an Internet proxy to collect search engine results and prefetch result pages. The mobiles nodes download the pre-fetched web pages from the proxy. Our contribution is a novel set of techniques to make aggressive but selective prefetching practical, resulting in …
Cryptanalysis Of Two Lightweight Rfid Authentication Schemes, Benessa Defend, Kevin Fu, Ari Juels
Cryptanalysis Of Two Lightweight Rfid Authentication Schemes, Benessa Defend, Kevin Fu, Ari Juels
Computer Science Department Faculty Publication Series
Vajda and Buttyan proposed several lightweight authentication protocols for authenticating RFID tags to readers, and left open the quantifiable cryptographic strength. Our cryptanalysis answers this open question by implementing and measuring attacks against their XOR and SUBSET protocols. A passive eavesdropper can impersonate a tag in the XOR protocol after observing only 70 challenge-response transactions between the tag and reader. In contrast, the theoretical maximum strength of the XOR protocol could have required 16! * 2 observed transactions to break the key. Our experiments also show that a passive eavesdropper can recover the shared secret used in the XOR protocol …
Simple, Robust, Scalable Semi-Supervised Learning Via Expectation Regularization, Gideon S. Mann
Simple, Robust, Scalable Semi-Supervised Learning Via Expectation Regularization, Gideon S. Mann
Computer Science Department Faculty Publication Series
Although semi-supervised learning has been an active area of research, its use in deployed applications is still relatively rare because the methods are often difficult to implement, fragile in tuning, or lacking in scalability. This paper presents expectation regularization, a semi-supervised learning method for exponential family parametric models that augments the traditional conditional label-likelihood objective function with an additional term that encourages model predictions on unlabeled data to match certain expectations—such as label priors. The method is extremely easy to implement, scales as well as logistic regression, and can handle non-independent features. We present experiments on five different data sets, …
Anonymizing Social Networks, Michael Hay, Gerome Miklau, David Jensen, Philipp Weis, Siddharth Srivastava
Anonymizing Social Networks, Michael Hay, Gerome Miklau, David Jensen, Philipp Weis, Siddharth Srivastava
Computer Science Department Faculty Publication Series
Advances in technology have made it possible to collect data about individuals and the connections between them, such as email correspondence and friendships. Agencies and researchers who have collected such social network data often have a compelling interest in allowing others to analyze the data. However, in many cases the data describes relationships that are private (e.g., email correspondence) and sharing the data in full can result in unacceptable disclosures. In this paper, we present a framework for assessing the privacy risk of sharing anonymized network data. This includes a model of adversary knowledge, for which we consider several variants …
Structure Theorem And Strict Alternation Hierarchy For Fo2 On Words, Philipp Weis
Structure Theorem And Strict Alternation Hierarchy For Fo2 On Words, Philipp Weis
Computer Science Department Faculty Publication Series
It is well-known that every first-order property on words is expressible using at most three variables. The subclass of properties expressible with only two variables is also quite interesting and wellstudied. We prove precise structure theorems that characterize the exact expressive power of first-order logic with two variables on words. Our results apply to FO2[<] and FO 2[<; Suc], the latter of which includes the binary successor relation in addition to the linear ordering on string positions. For both languages, our structuretheorems showexactly whatis expressible using a given quantifier depth, n, and using m blocks of alternating quantifiers, for any m ≤ n. Using these characterizations, we prove, among other results, that there is a strict hierarchy of alternating quantifiers for both languages. The question whether there was such a hierarchy had been completely open. As another consequence of our structural results, we show that satisfiability for FO2[<], which is NEXP-complete in general, becomes NP-complete once we only consider alphabets of a bounded size.
Learning State-Action Basis Functions For Hierarchical Mdps, Sarah Osentoski
Learning State-Action Basis Functions For Hierarchical Mdps, Sarah Osentoski
Computer Science Department Faculty Publication Series
This paper introduces a new approach to actionvalue function approximation by learning basis functions from a spectral decomposition of the state-action manifold. This paper extends previous work on using Laplacian bases for value function approximation by using the actions of the agent as part of the representation when creating basis functions. The approach results in a nonlinear learned representation particularly suited to approximating action-value functions, without incurring the wasteful duplication of state bases in previous work. We discuss two techniques to create state-action graphs: offpolicy and on-policy. We show that these graphs have a greater expressive power and have better …
Evaluating Search Engines By Modeling The Relationship Between Relevance And Clicks, Ben Carterette, Rosie Jones
Evaluating Search Engines By Modeling The Relationship Between Relevance And Clicks, Ben Carterette, Rosie Jones
Computer Science Department Faculty Publication Series
We propose a model that leverages the millions of clicks received by web search engines to predict document relevance. This allows the comparison of ranking functions when clicks are available but complete relevance judgments are not. After an initial training phase using a set of relevance judgments paired with click data, we show that our model can predict the relevance score of documents that have not been judged. These predictions can be used to evaluate the performance of a search engine, using our novel formalization of the confidence of the standard evaluation metric discounted cumulative gain (DCG), so comparisons can …