Learning dexterous in-hand manipulation Andrychowicz, OpenAI: Marcin; Baker, Bowen; Chociej, Maciek ...
The International journal of robotics research,
01/2020, Letnik:
39, Številka:
1
Journal Article
Recenzirano
Odprti dostop
We use reinforcement learning (RL) to learn dexterous in-hand manipulation policies that can perform vision-based object reorientation on a physical Shadow Dexterous Hand. The training is performed ...in a simulated environment in which we randomize many of the physical properties of the system such as friction coefficients and an object’s appearance. Our policies transfer to the physical robot despite being trained entirely in simulation. Our method does not rely on any human demonstrations, but many behaviors found in human manipulation emerge naturally, including finger gaiting, multi-finger coordination, and the controlled use of gravity. Our results were obtained using the same distributed RL system that was used to train OpenAI Five. We also include a video of our results: https://youtu.be/jwSbzNHGflM.
We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph
G
to graph
H
cannot be done in time |
V
(
H
)|
o
(|
V
(
G
)|)
. We also show an ...exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of |
V
(
H
)|
o
(|
V
(
H
)|)
-time algorithm deciding if graph
G
is a subgraph of
H
. For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems.
Moreover, as a consequence of our reductions, conditional lower bounds follow for other related problems such as Locally Injective Homomorphism, Graph Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic Assignment Problem.
We give an algorithm which in O(nlog2n) time counts all distinct squares in a labeled tree. There are two main obstacles to overcome. The first one is that the number of distinct squares in a tree is ...Ω(n4/3) (see Crochemore et al., 2012 7), which differs substantially from the case of classical strings for which there are only linearly many distinct squares. We overcome this obstacle by using a compact representation of all squares (based on maximal cyclic shifts) which requires only O(nlogn) space. The second obstacle is lack of adequate algorithmic tools for labeled trees, consequently we design several novel tools, this is the most complex part of the paper. In particular we extend to trees Imre Simon's compact representations of the failure table in pattern matching machines.
Extracting dense subgraphs from large graphs is a key primitive in a variety of graph mining applications, ranging from mining social networks and the Web graph to bioinformatics 41. In this paper we ...focus on a family of poly-time solvable formulations, known as the k-clique densest subgraph problem (k-Clique-DSP) 57. When k=2, the problem becomes the well-known densest subgraph problem (DSP) 22, 31, 33, 39. Our main contribution is a sampling scheme that gives densest subgraph sparsifier, yielding a randomized algorithm that produces high-quality approximations while providing significant speedups and improved space complexity. We also extend this family of formulations to bipartite graphs by introducing the (p,q)-biclique densest subgraph problem ((p,q)-Biclique-DSP), and devise an exact algorithm that can treat both clique and biclique densities in a unified way.
As an example of performance, our sparsifying algorithm extracts the 5-clique densest subgraph --which is a large-near clique on 62 vertices-- from a large collaboration network. Our algorithm achieves 100% accuracy over five runs, while achieving an average speedup factor of over 10,000. Specifically, we reduce the running time from ∼2 107 seconds to an average running time of 0.15 seconds. We also use our methods to study how the k-clique densest subgraphs change as a function of time in time-evolving networks for various small values of k. We observe significant deviations between the experimental findings on real-world networks and stochastic Kronecker graphs, a random graph model that mimics real-world networks in certain aspects.
We believe that our work is a significant advance in routines with rigorous theoretical guarantees for scalable extraction of large near-cliques from networks.
We study the Manhattan Sequence Consensus problem (MSC problem) in which we are given k integer sequences, each of length ℓ, and we are to find an integer sequence x of length ℓ (called a consensus ...sequence) such that the maximum Manhattan distance of x from each of the input sequences is minimized. A related problem, with Hamming distance instead of Manhattan distance, is called Hamming String Consensus (HSC), also known under the names of string center problem or closest string problem. For binary sequences Manhattan distance coincides with Hamming distance, hence in this case HSC is a special case of MSC. We design a practically efficient O(ℓ)-time algorithm solving MSC for k≤5 sequences. It improves upon the quadratic algorithm by Amir et al. (2012) 1 for HSC for k=5 binary strings. Similarly as in the algorithm of Amir et al., we use a column-based framework. We replace the implied general integer linear programming by its easy special cases due to combinatorial properties of MSC for k≤5. Practicality of our algorithms has been verified experimentally. We also show that for a general parameter k any instance can be reduced in linear time to a kernel of size k!, so the problem is fixed-parameter tractable. Nevertheless, for k≥4 this is still too large for any naive solution to be feasible in practice.
This is a full version of an article published at SPIRE 2014 15.
We derive a simple efficient algorithm for Abelian periods knowing all Abelian squares in a string. An efficient algorithm for the latter problem was given by Cummings and Smyth in 1997. By the way ...we show an alternative algorithm for Abelian squares. We also obtain a linear time algorithm finding all “long” Abelian periods. The aim of the paper is a (new) reduction of the problem of all Abelian periods to that of (already solved) all Abelian squares which provides new insight into both connected problems.
► We show a reduction of the Abelian periods problem to Abelian squares in a string. ► We derive a simple O(n2) time algorithm for Abelian periods. ► We obtain a linear time algorithm finding all long Abelian periods.
A \emph{power} is a word of the form $\underbrace{uu...u}_{k \;
\text{times}}$, where $u$ is a word and $k$ is a positive integer; the power is
also called a {\em $k$-power} and $k$ is its {\em ...exponent}. We prove that for
any $k \ge 2$, the maximum number of different non-empty $k$-power factors in a
word of length $n$ is between $\frac{n}{k-1}-\Theta(\sqrt{n})$ and
$\frac{n-1}{k-1}$. We also show that the maximum number of different non-empty
power factors of exponent at least 2 in a length-$n$ word is at most $n-1$.
Both upper bounds generalize the recent upper bound of $n-1$ on the maximum
number of different square factors in a length-$n$ word by Brlek and Li (2022).
We show that schemes for sparsifying matrices based on iteratively resampling rows yield guarantees matching classic 'offline' sparsifiers (see e.g. Spielman and Srivastava STOC 2008). In particular, ...this gives a formal analysis of a scheme very similar to the one proposed by Kelner and Levin TCS 2013.
PDF
