Archives for 2013

Today I read a paper titled “Motion Planning via Manifold Samples”

The abstract is:
We present a general and modular algorithmic framework for path planning of robots.

Our framework combines geometric methods for exact and complete analysis of low-dimensional configuration spaces, together with practical, considerably simpler sampling-based approaches that are appropriate for higher dimensions.

In order to facilitate the transfer of advanced geometric algorithms into practical use, we suggest taking samples that are entire low-dimensional manifolds of the configuration space that capture the connectivity of the configuration space much better than isolated point samples.

Geometric algorithms for analysis of low-dimensional manifolds then provide powerful primitive operations.

The modular design of the framework enables independent optimization of each modular component.

Indeed, we have developed, implemented and optimized a primitive operation for complete and exact combinatorial analysis of a certain set of manifolds, using arrangements of curves of rational functions and concepts of generic programming.

This in turn enabled us to implement our framework for the concrete case of a polygonal robot translating and rotating amidst polygonal obstacles.

We demonstrate that the integration of several carefully engineered components leads to significant speedup over the popular PRM sampling-based algorithm, which represents the more simplistic approach that is prevalent in practice.

We foresee possible extensions of our framework to solving high-dimensional problems beyond motion planning.

Today I read a paper titled “Generalized Stable Matching in Bipartite Networks”

The abstract is:
In this paper we study the generalized version of weighted matching in bipartite networks.

Consider a weighted matching in a bipartite network in which the nodes derive value from the split of the matching edge assigned to them if they are matched.

The value a node derives from the split depends both on the split as well as the partner the node is matched to.

We assume that the value of a split to the node is continuous and strictly increasing in the part of the split assigned to the node.

A stable weighted matching is a matching and splits on the edges in the matching such that no two adjacent nodes in the network can split the edge between them so that both of them can derive a higher value than in the matching.

We extend the weighted matching problem to this general case and study the existence of a stable weighted matching.

We also present an algorithm that converges to a stable weighted matching.

The algorithm generalizes the Hungarian algorithm for bipartite matching.

Faster algorithms can be made when there is more structure on the value functions.

Today I read a paper titled “Crowdsourcing for Usability Testing”

The abstract is:
While usability evaluation is critical to designing usable websites, traditional usability testing can be both expensive and time consuming.

The advent of crowdsourcing platforms such as Amazon Mechanical Turk and CrowdFlower offer an intriguing new avenue for performing remote usability testing with potentially many users, quick turn-around, and significant cost savings.

To investigate the potential of such crowdsourced usability testing, we conducted two similar (though not completely parallel) usability studies which evaluated a graduate school’s website: one via a traditional usability lab setting, and the other using crowdsourcing.

While we find crowdsourcing exhibits some notable limitations in comparison to the traditional lab environment, its applicability and value for usability testing is clearly evidenced.

We discuss both methodological differences for crowdsourced usability testing, as well as empirical contrasts to results from more traditional, face-to-face usability testing.

Today I read a paper titled “A Vehicle for Research: Using Street Sweepers to Explore the Landscape of Environmental Community Action”

The abstract is:
Researchers are developing mobile sensing platforms to facilitate public awareness of environmental conditions.

However, turning such awareness into practical community action and political change requires more than just collecting and presenting data.

To inform research on mobile environmental sensing, we conducted design fieldwork with government, private, and public interest stakeholders.

In parallel, we built an environmental air quality sensing system and deployed it on street sweeping vehicles in a major U.S.

city; this served as a “research vehicle” by grounding our interviews and affording us status as environmental action researchers.

In this paper, we present a qualitative analysis of the landscape of environmental action, focusing on insights that will help researchers frame meaningful technological interventions.

Today I read a paper titled “Upper Tag Ontology (UTO) For Integrating Social Tagging Data”

The abstract is:
Data integration and mediation have become central concerns of information technology over the past few decades.

With the advent of the Web and the rapid increases in the amount of data and the number of Web documents and users, researchers have focused on enhancing the interoperability of data through the development of metadata schemes.

Other researchers have looked to the wealth of metadata generated by bookmarking sites on the Social Web.

While several existing ontologies capitalize on the semantics of metadata created by tagging activities, the Upper Tag Ontology (UTO) emphasizes the structure of tagging activities to facilitate modeling of tagging data and the integration of data from different bookmarking sites as well as the alignment of tagging ontologies.

UTO is described and its utility in harvesting, modeling, integrating, searching and analyzing data is demonstrated with metadata harvested from three major social tagging systems (Delicious, Flickr and YouTube).

Today I read a paper titled “Social Network Based Search for Experts”

The abstract is:
Our system illustrates how information retrieved from social networks can be used for suggesting experts for specific tasks.

The system is designed to facilitate the task of finding the appropriate person(s) for a job, as a conference committee member, an advisor, etc.

This short description will demonstrate how the system works in the context of the HCIR2012 published tasks.

Today I read a paper titled “Uncovering space-independent communities in spatial networks”

The abstract is:
Many complex systems are organized in the form of a network embedded in space.

Important examples include the physical Internet infrastucture, road networks, flight connections, brain functional networks and social networks.

The effect of space on network topology has recently come under the spotlight because of the emergence of pervasive technologies based on geo-localization, which constantly fill databases with people’s movements and thus reveal their trajectories and spatial behaviour.

Extracting patterns and regularities from the resulting massive amount of human mobility data requires the development of appropriate tools for uncovering information in spatially-embedded networks.

In contrast with most works that tend to apply standard network metrics to any type of network, we argue in this paper for a careful treatment of the constraints imposed by space on network topology.

In particular, we focus on the problem of community detection and propose a modularity function adapted to spatial networks.

We show that it is possible to factor out the effect of space in order to reveal more clearly hidden structural similarities between the nodes.

Methods are tested on a large mobile phone network and computer-generated benchmarks where the effect of space has been incorporated.

Today I read a paper titled “On Sharing Viral Video over an Ad Hoc Wireless Network”

The abstract is:
We consider the problem of broadcasting a viral video (a large file) over an ad hoc wireless network (e.g., students in a campus).

Many smartphones are GPS enabled, and equipped with peer-to-peer (ad hoc) transmission mode, allowing them to wirelessly exchange files over short distances rather than use the carrier’s WAN.

The demand for the file however is transmitted through the social network (e.g., a YouTube link posted on Facebook).

To address this coupled-network problem (demand on the social network; bandwidth on the wireless network) where the two networks have different topologies, we propose a file dissemination algorithm.

In our scheme, users query their social network to find geographically nearby friends that have the desired file, and utilize the underlying ad hoc network to route the data via multi-hop transmissions.

We show that for many popular models for social networks, the file dissemination time scales sublinearly with n; the number of users, compared to the linear scaling required if each user who wants the file must download it from the carrier’s WAN.

Today I read a paper titled “Automated Training and Maintenance through Kinect”

The abstract is:
In this paper, we have worked on reducing burden on mechanic involving complex automobile maintenance activities that are performed in centralised workshops.

We have presented a system prototype that combines Augmented Reality with Kinect.

With the use of Kinect, very high quality sensors are available at considerably low costs, thus reducing overall expenditure for system design.

The system can be operated either in Speech mode or in Gesture mode.

The system can be controlled by various audio commands if user opts for Speech mode.

The same controlling can also be done by using a set of Gestures in Gesture mode.

Gesture recognition is the task performed by Kinect system.

This system, bundled with RGB and Depth camera, processes the skeletal data by keeping track of 20 different body joints.

Recognizing Gestures is done by verifying user movements and checking them against predefined condition.

Augmented Reality module captures real-time image data streams from high resolution camera.

This module then generates 3D model that is superimposed on real time data.

Today I read a paper titled “BiopSym: a simulator for enhanced learning of ultrasound-guided prostate biopsy”

The abstract is:
This paper describes a simulator of ultrasound-guided prostate biopsies for cancer diagnosis.

When performing biopsy series, the clinician has to move the ultrasound probe and to mentally integrate the real-time bi-dimensional images into a three-dimensional (3D) representation of the anatomical environment.

Such a 3D representation is necessary to sample regularly the prostate in order to maximize the probability of detecting a cancer if any.

To make the training of young physicians easier and faster we developed a simulator that combines images computed from three-dimensional ultrasound recorded data to haptic feedback.

The paper presents the first version of this simulator.

Today I read a paper titled “A small-world of weak ties provides optimal global integration of self-similar modules in functional brain networks”

The abstract is:
The human brain is organized in functional modules.

Such an organization presents a basic conundrum: modules ought to be sufficiently independent to guarantee functional specialization and sufficiently connected to bind multiple processors for efficient information transfer.

It is commonly accepted that small-world architecture of short lengths and large local clustering may solve this problem.

However, there is intrinsic tension between shortcuts generating small-worlds and the persistence of modularity; a global property unrelated to local clustering.

Here, we present a possible solution to this puzzle.

We first show that a modified percolation theory can define a set of hierarchically organized modules made of strong links in functional brain networks.

These modules are “large-world” self-similar structures and, therefore, are far from being small-world.

However, incorporating weaker ties to the network converts it into a small-world preserving an underlying backbone of well-defined modules.

Remarkably, weak ties are precisely organized as predicted by theory maximizing information transfer with minimal wiring cost.

This trade-off architecture is reminiscent of the “strength of weak ties” crucial concept of social networks.

Such a design suggests a natural solution to the paradox of efficient information flow in the highly modular structure of the brain.

Today I read a paper titled “A Distributed Software Architecture for Collaborative Teleoperation based on a VR Platform and Web Application Interoperability”

The abstract is:
Augmented Reality and Virtual Reality can provide to a Human Operator (HO) a real help to complete complex tasks, such as robot teleoperation and cooperative teleassistance.

Using appropriate augmentations, the HO can interact faster, safer and easier with the remote real world.

In this paper, we present an extension of an existing distributed software and network architecture for collaborative teleoperation based on networked human-scaled mixed reality and mobile platform.

The first teleoperation system was composed by a VR application and a Web application.

However the 2 systems cannot be used together and it is impossible to control a distant robot simultaneously.

Our goal is to update the teleoperation system to permit a heterogeneous collaborative teleoperation between the 2 platforms.

An important feature of this interface is based on different Mobile platforms to control one or many robots.

Today I read a paper titled “Digital herders and phase transition in a voting model”

The abstract is:
In this paper, we discuss a voting model with two candidates, C_1 and C_2.

We set two types of voters–herders and independents.

The voting of independent voters is based on their fundamental values; on the other hand, the voting of herders is based on the number of votes.

Herders always select the majority of the previous $r$ votes, which is visible to them.

We call them digital herders.

We can accurately calculate the distribution of votes for special cases.

When r>=3, we find that a phase transition occurs at the upper limit of t, where t is the discrete time (or number of votes).

As the fraction of herders increases, the model features a phase transition beyond which a state where most voters make the correct choice coexists with one where most of them are wrong.

On the other hand, when r<3, there is no phase transition.

In this case, the herders’ performance is the same as that of the independent voters.

Finally, we recognize the behavior of human beings by conducting simple experiments.

Today I read a paper titled “Fast Color Quantization Using Weighted Sort-Means Clustering”

The abstract is:
Color quantization is an important operation with numerous applications in graphics and image processing.

Most quantization methods are essentially based on data clustering algorithms.

However, despite its popularity as a general purpose clustering algorithm, k-means has not received much respect in the color quantization literature because of its high computational requirements and sensitivity to initialization.

In this paper, a fast color quantization method based on k-means is presented.

The method involves several modifications to the conventional (batch) k-means algorithm including data reduction, sample weighting, and the use of triangle inequality to speed up the nearest neighbor search.

Experiments on a diverse set of images demonstrate that, with the proposed modifications, k-means becomes very competitive with state-of-the-art color quantization methods in terms of both effectiveness and efficiency.

Today I read a paper titled “GPU-based Image Analysis on Mobile Devices”

The abstract is:
With the rapid advances in mobile technology many mobile devices are capable of capturing high quality images and video with their embedded camera.

This paper investigates techniques for real-time processing of the resulting images, particularly on-device utilizing a graphical processing unit.

Issues and limitations of image processing on mobile devices are discussed, and the performance of graphical processing units on a range of devices measured through a programmable shader implementation of Canny edge detection.

Today I read a paper titled “Telerobotic Pointing Gestures Shape Human Spatial Cognition”

The abstract is:
This paper aimed to explore whether human beings can understand gestures produced by telepresence robots.

If it were the case, they can derive meaning conveyed in telerobotic gestures when processing spatial information.

We conducted two experiments over Skype in the present study.

Participants were presented with a robotic interface that had arms, which were teleoperated by an experimenter.

The robot could point to virtual locations that represented certain entities.

In Experiment 1, the experimenter described spatial locations of fictitious objects sequentially in two conditions: speech condition (SO, verbal descriptions clearly indicated the spatial layout) and speech and gesture condition (SR, verbal descriptions were ambiguous but accompanied by robotic pointing gestures).

Participants were then asked to recall the objects’ spatial locations.

We found that the number of spatial locations recalled in the SR condition was on par with that in the SO condition, suggesting that telerobotic pointing gestures compensated ambiguous speech during the process of spatial information.

In Experiment 2, the experimenter described spatial locations non-sequentially in the SR and SO conditions.

Surprisingly, the number of spatial locations recalled in the SR condition was even higher than that in the SO condition, suggesting that telerobotic pointing gestures were more powerful than speech in conveying spatial information when information was presented in an unpredictable order.

The findings provide evidence that human beings are able to comprehend telerobotic gestures, and importantly, integrate these gestures with co-occurring speech.

This work promotes engaging remote collaboration among humans through a robot intermediary.