Assigning a kekulé structure to a conjugated molecule

The Edmonds Matching Algorithm, which leads easily to finding a perfect matching in a chemical graph, which is equivalent to a Kekulé structure in a conjugated molecule, is recalled. An extension is made to the case where only vertices of a specified set must be covered by edges of the matching which is sought.     

How to Guard a Graph?

We initiate the study of the algorithmic foundations of games in which a set of cops has to guard a region in a graph (or digraph) against a robber. The robber and the cops are placed on vertices of the graph; they take turns in moving to adjacent vertices (or staying). The goal of the robber is to enter the guarded region at a vertex with no cop on it. The problem is to find the minimum number of cops needed to prevent the robber from entering the guarded region. The problem is highly non-trivial even if the robber’s or the cops’ regions are restricted to very simple graphs. The computational complexity of the problem depends heavily on the chosen restriction. In particular, if the robber’s region is only a path, then the problem can be solved in polynomial time. When the robber moves in a tree (or even in a star), then the decision version of the problem is NP-complete. Furthermore, if the robber is moving in a directed acyclic graph, the problem becomes PSPACE-complete.     

Partial Similarity of Objects,or How to Compare a Centaur to a Horse

Similarity is one of the most important abstract concepts in human perception of the world. In computer vision, numerous applications deal with comparing objects observed in a scene with some a priori known patterns. Often, it happens that while two objects are not similar, they have large similar parts, that is, they are partially similar. Here, we present a novel approach to quantify partial similarity using the notion of Pareto optimality. We exemplify our approach on the problems of recognizing non-rigid geometric objects, images, and analyzing text sequences.     

What causes a neuron to spike?

The computation performed by a neuron can be formulated as a combination of dimensional reduction in stimulus space and the nonlinearity inherent in a spiking output. White noise stimulus and reverse correlation (the spike-triggered average and spike-triggered covariance) are often used in experimental neuroscience to "ask" neurons which dimensions in stimulus space they are sensitive to and to characterize the nonlinearity of the response. In this article, we apply reverse correlation to the simplest model neuron with temporal dynamics-the leaky integrate-and-fire model-and find that for even this simple case, standard techniques do not recover the known neural computation. To overcome this, we develop novel reverse-correlation techniques by selectively analyzing only "isolated" spikes and taking explicit account of the extended silences that precede these isolated spikes. We discuss the implications of our methods to the characterization of neural adaptation. Although these methods are developed in the context of the leaky integrate-and-fire model, our findings are relevant for the analysis of spike trains from real neurons.     

How to Steer a Quantum System over a Schrödinger Bridge

A new approach to the steering problem for the Schrödinger equation relying on stochastic mechanics and on the theory of Schrödinger bridges is presented. Given the initial and final states ₀ and ₁, respectively, the desired quantum evolution is constructed with the aid of a reference quantum evolution. The Nelson process corresponding to the latter evolution is used as reference process in a Schrödinger bridge problem with marginal probability densities | ₀|² and | ₁|². This approach is illustrated by working out a simple Gaussian example. PACS: 03.65.-w     

Can a rational agent afford to be affectless? a formal approach

In this article, we expose some of the issues raised by the critics of the neoclassical approach to rational agent modeling and we propose a formal approach for the design of artificial rational agents that includes some of the functions of emotions found in the human system. We suggest that emotions and rationality are closely linked in the human mind (and in the body, for that matter) and, therefore, need to be included in architectures for designing rational artificial agents, whether these agents are to interact with humans, to model humans' behaviors and actions, or both. We describe an Affective Knowledge Representation (AKR) scheme to represent emotion schemata, which we developed to guide the design of a variety of socially intelligent artificial agents. Our approach focuses on the notion of "social expertise" of socially intelligent agents in terms of their external behavior and internal motivational goal-based abilities. AKR, which uses probabilistic frames, is derived from combining multiple emotion theories into a hierarchical model of affective phenomena useful for artificial agent design. AKR includes a taxonomy of affect, mood, emotion, and personality, and a framework for emotional state dynamics using probabilistic Markov Models.     

How to “alternatize” a clustering algorithm

Given a clustering algorithm, how can we adapt it to find multiple, nonredundant, high-quality clusterings? We focus on algorithms based on vector quantization and describe a framework for automatic ‘alternatization’ of such algorithms. Our framework works in both simultaneous and sequential learning formulations and can mine an arbitrary number of alternative clusterings. We demonstrate its applicability to various clustering algorithms—k-means, spectral clustering, constrained clustering, and co-clustering—and effectiveness in mining a variety of datasets.     

Is computational complexity a barrier to manipulation?

When agents are acting together, they may need a simple mechanism to decide on joint actions. One possibility is to have the agents express their preferences in the form of a ballot and use a voting rule to decide the winning action(s). Unfortunately, agents may try to manipulate such an election by mis-reporting their preferences. Fortunately, it has been shown that it is NP-hard to compute how to manipulate a number of different voting rules. However, NP-hardness only bounds the worst-case complexity. In this survey article, we summarize the evidence for and against computational complexity being a barrier to manipulation. We look both at techniques identified to increase complexity (for example, hybridizing together two or more voting rules), as well as other features that may change the computational complexity of computing a manipulation (for example, if votes are restricted to be single peaked then some of the complexity barriers fall away). We discuss recent theoretical results that consider the average case, as well as simple greedy and approximate methods. We also describe how computational ??phase transitions??, which have been fruitful in identifying hard instances of propositional satisfiability and other NP-hard problems, have provided insight into the hardness of manipulating voting rules in practice. Finally, we consider manipulation of other related problems like stable marriage and tournament problems.     

Velocity planning for a mobile robot to track a moving target — a potential field approach

Potential field method has been widely used for mobile robot path planning, but mostly in a static environment where the target and the obstacles are stationary. The path planning result is normally the direction of the robot motion. In this paper, the potential field method is applied for both path and speed planning, or the velocity planning, for a mobile robot in a dynamic environment where the target and the obstacles are moving. The robot’s planned velocity is determined by relative velocities as well as relative positions among robot, obstacles and targets. The implementation factors such as maximum linear and angular speed of the robot are also considered. The proposed approach guarantees that the robot tracks the moving target while avoiding moving obstacles. Simulation studies are provided to verify the effectiveness of the proposed approach.     

WebGALAXY: beyond point and click — a conversational interface to a browser

This paper presents WebGALAXY, a flexible multi-modal user interface system that allows wide access to selected information on the World Wide Web (WWW) by integrating spoken and typed natural language queries and hypertext navigation. WebALAXY extends our GALAXY spoken language system, a distributed client-server system for retrieving information from online sources through speech and natural language. WebGALAXY supports a spoken user interface via a standard telephone line as well as a graphical user interface via a standard Web browser using either Java/JavaScript or a cgi-bin/forms front end. Natural language understanding is performed by the system and information servers retrieve the requested information from various online resources including WWW servers, Gopher servers and CompuServe. Currently, queries about three domains are supported: weather, air travel, and points of interest around Boston.     

Data privacy as a tool to combat discrimination?

This article will show how data privacy is legally recognized and treated in Japan and argue in particular how it can (not) play a role as a tool to combat discrimination in the workplace. The first part will depict a brief history of the development of the ‘right to privacy’ in Japan. This part will also take a look at the national Act on Protection of Personal Information and its complicated enforcement, paying attention to the general legal culture in Japan. The second part will observe other laws which are related to personal data protection and legal protection against discrimination. At the end of this article the author will make a comment on the Japanese data privacy law and its desirable development.     

How hard is it to control a group?

We consider group identification models in which the aggregation of individual opinions concerning who is qualified in a given society determines the set of socially qualified persons. In this setting, we study the extent to which social qualification can be changed when societies expand, shrink, or partition themselves. The answers we provide are with respect to the computational complexity of the corresponding control problems and fully cover the class of consent aggregation rules introduced by Samet and Schmeidler (J Econ Theory, 110(2):213–233, 2003) as well as procedural rules for group identification. We obtain both polynomial-time solvability results and NP-hardness results. In addition, we also study these problems from the parameterized complexity perspective, and obtain some fixed-parameter tractability results.     

Teaching a humanoid robot to draw ‘Shapes’

The core cognitive ability to perceive and synthesize ‘shapes’ underlies all our basic interactions with the world, be it shaping one’s fingers to grasp a ball or shaping one’s body while imitating a dance. In this article, we describe our attempts to understand this multifaceted problem by creating a primitive shape perception/synthesis system for the baby humanoid iCub. We specifically deal with the scenario of iCub gradually learning to draw or scribble shapes of gradually increasing complexity, after observing a demonstration by a teacher, by using a series of self evaluations of its performance. Learning to imitate a demonstrated human movement (specifically, visually observed end-effector trajectories of a teacher) can be considered as a special case of the proposed computational machinery. This architecture is based on a loop of transformations that express the embodiment of the mechanism but, at the same time, are characterized by scale invariance and motor equivalence. The following transformations are integrated in the loop: (a) Characterizing in a compact, abstract way the ‘shape’ of a demonstrated trajectory using a finite set of critical points, derived using catastrophe theory: Abstract Visual Program (AVP); (b) Transforming the AVP into a Concrete Motor Goal (CMG) in iCub’s egocentric space; (c) Learning to synthesize a continuous virtual trajectory similar to the demonstrated shape using the discrete set of critical points defined in CMG; (d) Using the virtual trajectory as an attractor for iCub’s internal body model, implemented by the Passive Motion Paradigm which includes a forward and an inverse motor model; (e) Forming an Abstract Motor Program (AMP) by deriving the ‘shape’ of the self generated movement (forward model output) using the same technique employed for creating the AVP; (f) Comparing the AVP and AMP in order to generate an internal performance score and hence closing the learning loop. The resulting computational framework further combines three crucial streams of learning: (1) motor babbling (self exploration), (2) imitative action learning (social interaction) and (3) mental simulation, to give rise to sensorimotor knowledge that is endowed with seamless compositionality, generalization capability and body-effectors/task independence. The robustness of the computational architecture is demonstrated by means of several experimental trials of gradually increasing complexity using a state of the art humanoid platform.     

How to localize humanoids with a single camera?

In this paper, we propose a real-time vision-based localization approach for humanoid robots using a single camera as the only sensor. In order to obtain an accurate localization of the robot, we first build an accurate 3D map of the environment. In the map computation process, we use stereo visual SLAM techniques based on non-linear least squares optimization methods (bundle adjustment). Once we have computed a 3D reconstruction of the environment, which comprises of a set of camera poses (keyframes) and a list of 3D points, we learn the visibility of the 3D points by exploiting all the geometric relationships between the camera poses and 3D map points involved in the reconstruction. Finally, we use the prior 3D map and the learned visibility prediction for monocular vision-based localization. Our algorithm is very efficient, easy to implement and more robust and accurate than existing approaches. By means of visibility prediction we predict for a query pose only the highly visible 3D points, thus, speeding up tremendously the data association between 3D map points and perceived 2D features in the image. In this way, we can solve very efficiently the Perspective-n-Point (PnP) problem providing robust and fast vision-based localization. We demonstrate the robustness and accuracy of our approach by showing several vision-based localization experiments with the HRP-2 humanoid robot.