We present CurveQuad, a miniature curved origami quadruped that is able to self-fold and unfold, crawl, and steer, all using a single actuator. CurveQuad is designed for planar manufacturing, with parts that attach and stack sequentially on a flat body. The design uses 4 curved creases pulled by 2 pairs of tendons from opposite ends of a link on a 270°servo. It is 8 cm in the longest direction and weighs 10.9 g. Rotating the horn pulls the tendons inwards to induce folding. Continuing to rotate the horn shears the robot, enabling the robot to shuffle forward while turning in either direction. We experimentally validate the robot's ability to fold, steer, and unfold by changing the magnitude of horn rotation. We also demonstrate basic feedback control by steering towards a light source from a variety of starting positions and orientations, and swarm aggregation by having 4 robots simultaneously steer towards the light. The results demonstrate the potential of using curved crease origami in self-assembling and deployable robots with complex motions such as locomotion.

The field of analytic combinatorics, which studies the asymptotic behaviour of sequences through analytic properties of their generating functions, has led to the development of deep and powerful tools with applications across mathematics and the natural sciences. In addition to the now classical univariate theory, recent work in the study of analytic combinatorics in several variables (ACSV) has shown how to derive asymptotics for the coefficients of certain D-finite functions represented by diagonals of multivariate rational functions. We give a pedagogical introduction to the methods of ACSV from a computer algebra viewpoint, developing rigorous algorithms and giving the first complexity results in this area under conditions which are broadly satisfied. Furthermore, we give several new applications of ACSV to the enumeration of lattice walks restricted to certain regions. In addition to proving several open conjectures on the asymptotics of such walks, a detailed study of lattice walk models with weighted steps is undertaken.

The method of types is one of the most popular techniques in information theory and combinatorics. However, thus far the method has been mostly applied to 1-D Markov processes, and it has not been thoroughly studied for general Markov fields. Markov fields over a finite alphabet of size m ≥ 2 can be viewed as models for multidimensional systems with local interactions. The locality of these interactions is represented by a shape S while its marking by symbols of the underlying alphabet is called a tile. Two assignments in a Markov field have the same type if they have the same empirical distribution, i.e., if they have the same number of tiles of a given type. Our goal is to study the growth of the number of possible Markov field types in either a d-dimensional box of lengths n1, .. . ,ndor its cyclic counterpart, a d-dimensional torus. We relate this question to the enumeration of nonnegative integer solutions of a large system of Diophantine linear equations called the conservation laws. We view a Markov type as a vector in a D =m|S| dimensional space and count the number of such vectors satisfying the conservation laws, which turns out to be the number of integer points in a certain polytope. For the torus, this polytope is of dimension μ = D - 1 - rk(C), where rk(C) is the number of linearly independent conservation laws C. This provides an upper bound on the number of types. Then, we construct a matching lower bound leading to the conclusion that the number of types in the torus Markov field is θ(Nμ), where N = n1. . . nd. These results are derived by geometric tools, including ideas of discrete and convex multidimensional geometry.

The method of types is one of the most popular technique in information theory and combinatorics. However, it was never thoroughly studied for Markov fields. Markov fields can be viewed as models for systems involving a large number of variables with local dependencies and interactions. These local dependencies can be captured by a shape of interactions (locations that contribute the next probability transition). Shapes marked by symbols from a finite alphabet are called tiles. Two assignments in a Markov filed have the same type if they have the same empirical distribution or they can be tiled by the same number of tile types. Our goal is to study the growth of the number of Markov field types or the number of tile types. This intricate and important problem was left open for too long.

We define a new adaptive embedding approach for data dimension reduction applications. Our technique entails a local learning of the manifold of the initial data, with the objective of defining local distance metrics that take into account the different correlations between the data points. We choose to illustrate the properties of our work on the isomap algorithm. We show through multiple simulations that the new adaptive version of isomap is more robust to noise than the original non-adaptive one.

Our contribution in this paper is a scalable, easily implemented, self-organizing, energy conserving intrusion-detection sensor system applying concepts from cellular automata theory. The system self-assembles periodic wake-sensor barriers (waves) that sweep the sensor field; it is highly effective even in the case of frequent communication failures, sensor failures, large obstacles, and when intruders know sensor locations.

Cyclic Cellular Automata (CCAs) have been found to provide a natural, beguilingly simple, and elegant infrastructure for the design of sensor systems with sleep-wake scheduling to maximize system lifetime. The Greenberg-Hastings model (GHMZ) [3, 2] defined on the integer lattice Z2 is particularly appropriate and is described as follows. Each grid square of the integer lattice is a cell with a set of k ≫ 1 states and a neighborhood N; the neighborhoods of interest here are the von Neumann neighborhood and the Moore neighborhood. The von Neumann neighborhood Nx of cell x consists of just those cells to thenorth, east, south, and west of x, whereas the Moore neighborhood expands to that 3 £ 3 array of cells with x at its center, i.e., all cells that touch x at a side or vertex. All cells change state synchronously step by step according to aclock cycle and transition function common to all. The local rule for state changes is little more than a counter: The state »t+1(x) of cell x at time t + 1 is a simple mod k increment: »t+1(x) = »t(x) + 1 if »t(x) ≫ 0. But if »t(x) = 0;the state is incremented to 1 if and only if it has at least one neighbor in Nx which is currently in state 1.