In recent years, tasks regarding autonomous mobility favoredthe use of legged robots rather than wheeled ones thanks to their higher mobility on rough and uneven terrains. This comes at the cost of more complex motion planners and controllers to ensure robot stability and balance. However, in the case of quadrupedal robots, balancing is simpler than it is for bipeds thanks to their larger support polygons. Until a few years ago, most scientists and engineers addressed the quadrupedal locomotion problem with model-based approaches, which require a great deal of modeling expertise. A new trend is the use of data-driven methods, which seem to be quite promising and have shown great results. These methods do not require any modeling effort, but they suffer from computational limitations dictated by the hardware resources used. However, only the design phase of these algorithms requires large computing resources (controller training); their execution in the operational phase (deployment), takes place in real time on common processors. Moreover, adaptive feet capable of sensing terrain profile information have been designed and have shown great performance. Still, no dynamic locomotion control method has been specifically designed to leverage the advantages and supplementary information provided by this type of adaptive feet. In this work, we investigate the use and evaluate the performance of different end-to-end control policies trained via reinforcement learning algorithms specifically designed and trained to work on quadrupedal robots equipped with passive adaptive feet for their dynamic locomotion control over a diverse set of terrains. We examine how the addition of the haptic perception of the terrain affects the locomotion performance.
We present different techniques for applying Combinatorial Nullstellensatz to polynomials over finite fields. For examples, we generalize theorems from Noga Alon's paper on the subject, and present a few of our own.
We show in this note that the average number of terms in the optimal double-base number system is in Omega(n / log n). The lower bound matches the upper bound shown earlier by Dimitrov, Imbert, and Mishra (Math. of Comp. 2008).
We present simple graph-theoretic characterizations of Cayley graphs for monoids, semigroups and groups. We extend these characterizations to commutative monoids, semilattices, and abelian groups.
Проведен геометрический и топологический анализ металлооксида с минимальным известным содержанием кислорода CsO, образующегося из кислородсодержащего расплава металлического Cs. Для определения кластеров-прекурсоров кристаллических структур использованы специальные алгоритмы разложения структурных графов на кластерные субструктуры (пакет программ ToposPro). Определены участвующие в самосборке кристаллических структур кластеры-прекурсоры: трехоктаэдрические кластеры CsO, октаэдрические кластеры Cs, тетраэдрические кластеры Cs. Реконструированы симметрийный и топологический коды процессов самосборки кристаллических структур из кластеров-прекурсоров в виде: первичная цепь микрослой микрокаркас.
We consider several examples of probabilistic existence proofs using compressibility arguments, including some results that involve Lovász local lemma.
The partial representation extension problem, introduced by Klavík et al. (2011), generalizes the recognition problem. In this short note we show that this problem is NP-complete for unit circular-arc graphs.
This paper gives an algebraic proof of the correctness of Von Schelling formula for the probability of the coupon collector problem waiting time for non-uniform distributions and partial collections. It introduces a theorem on sums of powers of subset probabilities which to our knowledge is new. A set of binomial coefficients is used as a basis for decomposition of these sums of powers.
Assume that $n, \delta ,k$ are integers with $0 \leq k < \delta < n$. Given a graph $G=(V,E)$ with $|V|=n$. The symbol $G-F, F \subseteq V$, denotes the graph with $V(G-F)=V-F$, and $E(G-F)$ obtained by $E$ after deleting the edges with at least one endvertex in $F$. $G$ is called <i>$k$-vertex fault traceable</i>, <i>$k$-vertex fault Hamiltonian</i>, or <i>$k$-vertex fault Hamiltonian-connected</i> if $G-F$ remains traceable, Hamiltonian, and Hamiltonian-connected for all $F$ with $0 \leq |F| \leq k$, respectively. The notations $h_1(n, \delta ,k)$, $h_2(n, \delta ,k)$, and $h_3(n, \delta ,k)$ denote the minimum number of edges required to guarantee an $n$-vertex graph with minimum degree $\delta (G) \geq \delta$ to be $k$-vertex fault traceable, $k$-vertex fault Hamiltonian, and $k$-vertex fault Hamiltonian-connected, respectively. In this paper, we establish a theorem which uses the degree sequence of a given graph to characterize the $k$-vertex fault traceability/hamiltonicity/Hamiltonian-connectivity, respectively. Then we use this theorem to obtain the formulas for $h_i(n, \delta ,k)$ for $1 \leq i \leq 3$, which improves and extends the known results for $k=0$.
In this paper, we construct a weakly universal cellular automaton in the heptagrid, the tessellation $\{7,3\}$ which is not rotation invariant but which is truly planar. This result, under these conditions, cannot be improved for the tessellations $\{p,3\}$.
The Narumi-Katayama index of a graph was introduced in 1984 for representing the carbon skeleton of a saturated hydrocarbons and is defined as the product of degrees of all the vertices of the graph. In this paper, we examine the Narumi-Katayama index of different total transformation graphs.
We introduce a new graph parameter that measures fractional covering of a graph by cuts. Besides being interesting in its own right, it is useful for study of homomorphisms and tension-continuous mappings. We study the relations with chromatic number, bipartite density, and other graph parameters. We find the value of our parameter for a family of graphs based on hypercubes. These graphs play for our parameter the role that cliques play for the chromatic number and Kneser graphs for the fractional chromatic number. The fact that the defined parameter attains on these graphs the correct value suggests that our definition is a natural one. In the proof we use the eigenvalue bound for maximum cut and a recent result of Engström, Färnqvist, Jonsson, and Thapper [An approximability-related parameter on graphs – properties and applications, DMTCS vol. 17:1, 2015, 33–66]. We also provide a polynomial time approximation algorithm based on semidefinite programming and in particular on vector chromatic number (defined by Karger, Motwani and Sudan [Approximate graph coloring by semidefinite programming, J. ACM 45 (1998), no. 2, 246–265]).
In this paper we present an analysis of some generalization of the classic urn and balls model. In our model each urn has a fixed capacity and initially is filled with white balls. Black balls are added to the system of connected urns and gradually displace white balls. We show a general form of formulas for the expected numbers of black balls in a given urn and we analyze some special cases (parallel and serial configurations). We are mainly interested in a counterpart of the Coupon Collector Problem for the model considered. The primary motivation for our research is the formal analysis of the mix networks (introduced by D. Chaum) and its immunity to so-called flooding (blending) attacks.
In this article we deal with the problems of finding the disimplicial arcs of a digraph and recognizing some interesting graph classes defined by their existence. A <i>diclique</i> of a digraph is a pair $V$ → $W$ of sets of vertices such that $v$ → $w$ is an arc for every $v$ ∈ $V$ and $w$ ∈ $W$. An arc $v$ → $w$ is <i>disimplicial</i> when it belongs to a unique maximal diclique. We show that the problem of finding the disimplicial arcs is equivalent, in terms of time and space complexity, to that of locating the transitive vertices. As a result, an efficient algorithm to find the bisimplicial edges of bipartite graphs is obtained. Then, we develop simple algorithms to build disimplicial elimination schemes, which can be used to generate bisimplicial elimination schemes for bipartite graphs. Finally, we study two classes related to perfect disimplicial elimination digraphs, namely weakly diclique irreducible digraphs and diclique irreducible digraphs. The former class is associated to finite posets, while the latter corresponds to dedekind complete finite posets.
Richard Ehrenborg, Sergey Kitaev, Einar Steingrımsson
The graph of overlapping permutations is defined in a way analogous to the De Bruijn graph on strings of symbols. However, instead of requiring the tail of one permutation to equal the head of another for them to be connected by an edge, we require that the head and tail in question have their letters appear in the same order of size. We give a formula for the number of cycles of length $d$ in the subgraph of overlapping $312$-avoiding permutations. Using this we also give a refinement of the enumeration of $312$-avoiding affine permutations.
After extending classical results on simple varieties of trees to trees counted by their number of leaves, we describe a filtration of the set of permutations based on their strong interval trees. For each subclass we provide asymptotic formulas for number of trees (by leaves), average number of nodes of fixed arity, average subtree size sum, and average number of internal nodes. The filtration is motivated by genome comparison of related species.
Chris Berg, Nantel Bergeron, Franco Saliola
et al.
We introduce a new basis of the non-commutative symmetric functions whose elements have Schur functions as their commutative images. Dually, we build a basis of the quasi-symmetric functions which expand positively in the fundamental quasi-symmetric functions and decompose Schur functions according to a signed combinatorial formula.