Archives for 2007

Today I read a paper titled “Ontological Representations of Software Patterns”

The abstract is:
This paper is based on and advocates the trend in software engineering of extending the use of software patterns as means of structuring solutions to software development problems (be they motivated by best practice or by company interests and policies).

The paper argues that, on the one hand, this development requires tools for automatic organisation, retrieval and explanation of software patterns.

On the other hand, that the existence of such tools itself will facilitate the further development and employment of patterns in the software development process.

The paper analyses existing pattern representations and concludes that they are inadequate for the kind of automation intended here.

Adopting a standpoint similar to that taken in the semantic web, the paper proposes that feasible solutions can be built on the basis of ontological representations.

Today I read a paper titled “Reinforcement Learning for Adaptive Routing”

The abstract is:
Reinforcement learning means learning a policy–a mapping of observations into actions–based on feedback from the environment.

The learning can be viewed as browsing a set of policies while evaluating them by trial through interaction with the environment.

We present an application of gradient ascent algorithm for reinforcement learning to a complex domain of packet routing in network communication and compare the performance of this algorithm to other routing methods on a benchmark problem.

Today I read a paper titled “Image compression and entanglement”

The abstract is:
The pixel values of an image can be casted into a real ket of a Hilbert space using an appropriate block structured addressing.

The resulting state can then be rewritten in terms of its matrix product state representation in such a way that quantum entanglement corresponds to classical correlations between different coarse-grained textures.

A truncation of the MPS representation is tantamount to a compression of the original image.

The resulting algorithm can be improved adding a discrete Fourier transform preprocessing and a further entropic lossless compression.

Today I read a paper titled “On Reasoning with Ambiguities”

The abstract is:
The paper adresses the problem of reasoning with ambiguities.

Semantic representations are presented that leave scope relations between quantifiers and/or other operators unspecified.

Truth conditions are provided for these representations and different consequence relations are judged on the basis of intuitive correctness.

Finally inference patterns are presented that operate directly on these underspecified structures, i.e.

do not rely on any translation into the set of their disambiguations..

Today I read a paper titled “Locked and Unlocked Polygonal Chains in 3D”

The abstract is:
In this paper, we study movements of simple polygonal chains in 3D.

We say that an open, simple polygonal chain can be straightened if it can be continuously reconfigured to a straight sequence of segments in such a manner that both the length of each link and the simplicity of the chain are maintained throughout the movement.

The analogous concept for closed chains is convexification: reconfiguration to a planar convex polygon.

Chains that cannot be straightened or convexified are called locked.

While there are open chains in 3D that are locked, we show that if an open chain has a simple orthogonal projection onto some plane, it can be straightened.

For closed chains, we show that there are unknotted but locked closed chains, and we provide an algorithm for convexifying a planar simple polygon in 3D with a polynomial number of moves.

Today I read a paper titled “On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing”

The abstract is:
The Sum of Squares algorithm for bin packing was defined in [2] and studied in great detail in [1], where it was proved that its worst case performance ratio is at most 3.

In this note, we improve the asymptotic worst case bound to 2.7777…

Today I read a paper titled “Prop-Based Haptic Interaction with Co-location and Immersion: an Automotive Application”

The abstract is:
Most research on 3D user interfaces aims at providing only a single sensory modality.

One challenge is to integrate several sensory modalities into a seamless system while preserving each modality’s immersion and performance factors.

This paper concerns manipulation tasks and proposes a visuo-haptic system integrating immersive visualization, tactile force and tactile feedback with co-location.

An industrial application is presented.

Today I read a paper titled “2D Path Solutions from a Single Layer Excitable CNN Model”

The abstract is:
An easily implementable path solution algorithm for 2D spatial problems, based on excitable/programmable characteristics of a specific cellular nonlinear network (CNN) model is presented and numerically investigated.

The network is a single layer bioinspired model which was also implemented in CMOS technology.

It exhibits excitable characteristics with regionally bistable cells.

The related response realizes propagations of trigger autowaves, where the excitable mode can be globally preset and reset.

It is shown that, obstacle distributions in 2D space can also be directly mapped onto the coupled cell array in the network.

Combining these two features, the network model can serve as the main block in a 2D path computing processor.

The related algorithm and configurations are numerically experimented with circuit level parameters and performance estimations are also presented.

The simplicity of the model also allows alternative technology and device level implementation, which may become critical in autonomous processor design of related micro or nanoscale robotic applications.

Today I read a paper titled “Passive Control Architecture for Virtual Humans”

The abstract is:
In the present paper, we introduce a new control architecture aimed at driving virtual humans in interaction with virtual environments, by motion capture.

It brings decoupling of functionalities, and also of stability thanks to passivity.

We show projections can break passivity, and thus must be used carefully.

Our control scheme enables task space and internal control, contact, and joint limits management.

Thanks to passivity, it can be easily extended.

Besides, we introduce a new tool as for manikin’s control, which makes it able to build passive projections, so as to guide the virtual manikin when sharp movements are needed.

Today I read a paper titled “Matrix Games, Linear Programming, and Linear Approximation”

The abstract is:
The following four classes of computational problems are equivalent: solving matrix games, solving linear programs, best $l^{\infty}$ linear approximation, best $l^1$ linear approximation.

Today I read a paper titled “A bounded-degree network formation game”

The abstract is:
Motivated by applications in peer-to-peer and overlay networks we define and study the \emph{Bounded Degree Network Formation} (BDNF) game.

In an $(n,k)$-BDNF game, we are given $n$ nodes, a bound $k$ on the out-degree of each node, and a weight $w_{vu}$ for each ordered pair $(v,u)$ representing the traffic rate from node $v$ to node $u$.

Each node $v$ uses up to $k$ directed links to connect to other nodes with an objective to minimize its average distance, using weights $w_{vu}$, to all other destinations.

We study the existence of pure Nash equilibria for $(n,k)$-BDNF games.

We show that if the weights are arbitrary, then a pure Nash wiring may not exist.

Furthermore, it is NP-hard to determine whether a pure Nash wiring exists for a given $(n,k)$-BDNF instance.

A major focus of this paper is on uniform $(n,k)$-BDNF games, in which all weights are 1.

We describe how to construct a pure Nash equilibrium wiring given any $n$ and $k$, and establish that in all pure Nash wirings the cost of individual nodes cannot differ by more than a factor of nearly 2, whereas the diameter cannot exceed $O(\sqrt{n \log_k n})$.

We also analyze best-response walks on the configuration space defined by the uniform game, and show that starting from any initial configuration, strong connectivity is reached within $\Theta(n^2)$ rounds.

Convergence to a pure Nash equilibrium, however, is not guaranteed.

We present simulation results that suggest that loop-free best-response walks always exist, but may not be polynomially bounded.

We also study a special family of \emph{regular} wirings, the class of Abelian Cayley graphs, in which all nodes imitate the same wiring pattern, and show that if $n$ is sufficiently large no such regular wiring can be a pure Nash equilibrium.

Today I read a paper titled “The Symmetric Traveling Salesman Problem”

The abstract is:
Let M be an nXn symetric matrix, n, even, T, an upper bound for T_OPT, an optimal tour, sigma_T, the smaller-valued perfect matching obtained from alternate edges of T expressed as a product of 2-cycles.

Applying the modified Floyd-Warshall algorithm to (sigma_T)^-1M^-, we construct acceptable and 2-circuit cycles some sets of which may yield circuits that can be patched into tours.

We obtain necessary and sufficient conditions for a set, S, of cycles to yield circuits that may be patched into a tour.Assume that the following (Condition A)is valid: If (sigma_T)s = T*, |T*|

Given Condition(A), using F-W, we can always obtain S(FWOPT).

Using Condition A but not F-W, S_OPT is always obtainable from a subset of the cycles obtained.