-
TWIMP: Two-Wheel Inverted Musculoskeletal Pendulum as a Learning Control Platform in the Real World with Environmental Physical Contact
Authors:
Kento Kawaharazuka,
Tasuku Makabe,
Shogo Makino,
Kei Tsuzuki,
Yuya Nagamatsu,
Yuki Asano,
Takuma Shirai,
Fumihito Sugai,
Kei Okada,
Koji Kawasaki,
Masayuki Inaba
Abstract:
By the recent spread of machine learning in the robotics field, a humanoid that can act, perceive, and learn in the real world through contact with the environment needs to be developed. In this study, as one of the choices, we propose a novel humanoid TWIMP, which combines a human mimetic musculoskeletal upper limb with a two-wheel inverted pendulum. By combining the benefit of a musculoskeletal…
▽ More
By the recent spread of machine learning in the robotics field, a humanoid that can act, perceive, and learn in the real world through contact with the environment needs to be developed. In this study, as one of the choices, we propose a novel humanoid TWIMP, which combines a human mimetic musculoskeletal upper limb with a two-wheel inverted pendulum. By combining the benefit of a musculoskeletal humanoid, which can achieve soft contact with the external environment, and the benefit of a two-wheel inverted pendulum with a small footprint and high mobility, we can easily investigate learning control systems in environments with contact and sudden impact. We reveal our whole concept and system details of TWIMP, and execute several preliminary experiments to show its potential ability.
△ Less
Submitted 22 April, 2024;
originally announced April 2024.
-
Toward Practical Benchmarks of Ising Machines: A Case Study on the Quadratic Knapsack Problem
Authors:
Kentaro Ohno,
Tatsuhiko Shirai,
Nozomu Togawa
Abstract:
Combinatorial optimization has wide applications from industry to natural science. Ising machines bring an emerging computing paradigm for efficiently solving a combinatorial optimization problem by searching a ground state of a given Ising model. Current cutting-edge Ising machines achieve fast sampling of near-optimal solutions of the max-cut problem. However, for problems with additional constr…
▽ More
Combinatorial optimization has wide applications from industry to natural science. Ising machines bring an emerging computing paradigm for efficiently solving a combinatorial optimization problem by searching a ground state of a given Ising model. Current cutting-edge Ising machines achieve fast sampling of near-optimal solutions of the max-cut problem. However, for problems with additional constraint conditions, their advantages have been hardly shown due to difficulties in handling the constraints. In this work, we focus on benchmarks of Ising machines on the quadratic knapsack problem (QKP). To bring out their practical performance, we propose fast two-stage post-processing for Ising machines, which makes handling the constraint easier. Simulation based on simulated annealing shows that the proposed method substantially improves the solving performance of Ising machines and the improvement is robust to a choice of encoding of the constraint condition. Through evaluation using an Ising machine called Amplify Annealing Engine, the proposed method is shown to dramatically improve its solving performance on the QKP. These results are a crucial step toward showing advantages of Ising machines on practical problems involving various constraint conditions.
△ Less
Submitted 14 July, 2024; v1 submitted 28 March, 2024;
originally announced March 2024.
-
On the complexity of list $\mathcal H$-packing for sparse graph classes
Authors:
Tatsuya Gima,
Tesshu Hanaka,
Yasuaki Kobayashi,
Yota Otachi,
Tomohito Shirai,
Akira Suzuki,
Yuma Tamura,
Xiao Zhou
Abstract:
The problem of packing as many subgraphs isomorphic to $H \in \mathcal H$ as possible in a graph for a class $\mathcal H$ of graphs is well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for $H$ that contains at least three vertices and at least three edges, respectively. In this paper, we consider ``list variants'' of these problems: Given a…
▽ More
The problem of packing as many subgraphs isomorphic to $H \in \mathcal H$ as possible in a graph for a class $\mathcal H$ of graphs is well studied in the literature. Both vertex-disjoint and edge-disjoint versions are known to be NP-complete for $H$ that contains at least three vertices and at least three edges, respectively. In this paper, we consider ``list variants'' of these problems: Given a graph $G$, an integer $k$, and a collection $\mathcal L_{\mathcal H}$ of subgraphs of $G$ isomorphic to some $H \in \mathcal H$, the goal is to compute $k$ subgraphs in $\mathcal L_{\mathcal H}$ that are pairwise vertex- or edge-disjoint. We show several positive and negative results, focusing on classes of sparse graphs, such as bounded-degree graphs, planar graphs, and bounded-treewidth graphs.
△ Less
Submitted 13 December, 2023;
originally announced December 2023.
-
Disordered complex networks: energy optimal lattices and persistent homology
Authors:
Subhro Ghosh,
Naoto Miyoshi,
Tomoyuki Shirai
Abstract:
Disordered complex networks are of fundamental interest as stochastic models for information transmission over wireless networks. Well-known networks based on the Poisson point process model have limitations vis-a-vis network efficiency, whereas strongly correlated alternatives, such as those based on random matrix spectra (RMT), have tractability and robustness issues. In this work, we demonstrat…
▽ More
Disordered complex networks are of fundamental interest as stochastic models for information transmission over wireless networks. Well-known networks based on the Poisson point process model have limitations vis-a-vis network efficiency, whereas strongly correlated alternatives, such as those based on random matrix spectra (RMT), have tractability and robustness issues. In this work, we demonstrate that network models based on random perturbations of Euclidean lattices interpolate between Poisson and rigidly structured networks, and allow us to achieve the best of both worlds : significantly improve upon the Poisson model in terms of network efficacy measured by the Signal to Interference plus Noise Ratio (abbrv. SINR) and the related concept of coverage probabilities, at the same time retaining a considerable measure of mathematical and computational simplicity and robustness to erasure and noise.
We investigate the optimal choice of the base lattice in this model, connecting it to the celebrated problem optimality of Euclidean lattices with respect to the Epstein Zeta function, which is in turn related to notions of lattice energy. This leads us to the choice of the triangular lattice in 2D and face centered cubic lattice in 3D. We demonstrate that the coverage probability decreases with increasing strength of perturbation, eventually converging to that of the Poisson network. In the regime of low disorder, we approximately characterize the statistical law of the coverage function.
In 2D, we determine the disorder strength at which the PTL and the RMT networks are the closest measured by comparing their network topologies via a comparison of their Persistence Diagrams . We demonstrate that the PTL network at this disorder strength can be taken to be an effective substitute for the RMT network model, while at the same time offering the advantages of greater tractability.
△ Less
Submitted 11 March, 2022; v1 submitted 12 September, 2020;
originally announced September 2020.
-
Tail asymptotics of signal-to-interference ratio distribution in spatial cellular network models
Authors:
Naoto Miyoshi,
Tomoyuki Shirai
Abstract:
We consider a spatial stochastic model of wireless cellular networks, where the base stations (BSs) are deployed according to a simple and stationary point process on $\mathbb{R}^d$, $d\ge2$. In this model, we investigate tail asymptotics of the distribution of signal-to-interference ratio (SIR), which is a key quantity in wireless communications. In the case where the path-loss function represent…
▽ More
We consider a spatial stochastic model of wireless cellular networks, where the base stations (BSs) are deployed according to a simple and stationary point process on $\mathbb{R}^d$, $d\ge2$. In this model, we investigate tail asymptotics of the distribution of signal-to-interference ratio (SIR), which is a key quantity in wireless communications. In the case where the path-loss function representing signal attenuation is unbounded at the origin, we derive the exact tail asymptotics of the SIR distribution under an appropriate sufficient condition. While we show that widely-used models based on a Poisson point process and on a determinantal point process meet the sufficient condition, we also give a counterexample violating it. In the case of bounded path-loss functions, we derive a logarithmically asymptotic upper bound on the SIR tail distribution for the Poisson-based and $α$-Ginibre-based models. A logarithmically asymptotic lower bound with the same order as the upper bound is also obtained for the Poisson-based model.
△ Less
Submitted 15 March, 2017;
originally announced March 2017.
-
Spatial modeling and analysis of cellular networks using the Ginibre point process: A tutorial
Authors:
Naoto Miyoshi,
Tomoyuki Shirai
Abstract:
Spatial stochastic models have been much used for performance analysis of wireless communication networks. This is due to the fact that the performance of wireless networks depends on the spatial configuration of wireless nodes and the irregularity of node locations in a real wireless network can be captured by a spatial point process. Most works on such spatial stochastic models of wireless netwo…
▽ More
Spatial stochastic models have been much used for performance analysis of wireless communication networks. This is due to the fact that the performance of wireless networks depends on the spatial configuration of wireless nodes and the irregularity of node locations in a real wireless network can be captured by a spatial point process. Most works on such spatial stochastic models of wireless networks have adopted homogeneous Poisson point processes as the models of wireless node locations. While this adoption makes the models analytically tractable, it assumes that the wireless nodes are located independently of each other and their spatial correlation is ignored. Recently, the authors have proposed to adopt the Ginibre point process---one of the determinantal point processes---as the deployment models of base stations (BSs) in cellular networks. The determinantal point processes constitute a class of repulsive point processes and have been attracting attention due to their mathematically interesting properties and efficient simulation methods. In this tutorial, we provide a brief guide to the Ginibre point process and its variant, $α$-Ginibre point process, as the models of BS deployments in cellular networks and show some existing results on the performance analysis of cellular network models with $α$-Ginibre deployed BSs. The authors hope the readers to use such point processes as a tool for analyzing various problems arising in future cellular networks.
△ Less
Submitted 9 June, 2016;
originally announced June 2016.
-
A sufficient condition for tail asymptotics of SIR distribution in downlink cellular networks
Authors:
Naoto Miyoshi,
Tomoyuki Shirai
Abstract:
We consider the spatial stochastic model of single-tier downlink cellular networks, where the wireless base stations are deployed according to a general stationary point process on the Euclidean plane with general i.i.d. propagation effects. Recently, Ganti & Haenggi (2016) consider the same general cellular network model and, as one of many significant results, derive the tail asymptotics of the…
▽ More
We consider the spatial stochastic model of single-tier downlink cellular networks, where the wireless base stations are deployed according to a general stationary point process on the Euclidean plane with general i.i.d. propagation effects. Recently, Ganti & Haenggi (2016) consider the same general cellular network model and, as one of many significant results, derive the tail asymptotics of the signal-to-interference ratio (SIR) distribution. However, they do not mention any conditions under which the result holds. In this paper, we compensate their result for the lack of the condition and expose a sufficient condition for the asymptotic result to be valid. We further illustrate some examples satisfying such a sufficient condition and indicate the corresponding asymptotic results for the example models. We give also a simple counterexample violating the sufficient condition.
△ Less
Submitted 15 March, 2016; v1 submitted 2 February, 2016;
originally announced February 2016.
-
Downlink Coverage Probability in a Cellular Network with Ginibre Deployed Base Stations and Nakagami-m Fading Channels
Authors:
Naoto Miyoshi,
Tomoyuki Shirai
Abstract:
Recently, spatial stochastic models based on determinantal point processes (DPP) are studied as promising models for analysis of cellular wireless networks. Indeed, the DPPs can express the repulsive nature of the macro base station (BS) configuration observed in a real cellular network and have many desirable mathematical properties to analyze the network performance. However, almost all the prio…
▽ More
Recently, spatial stochastic models based on determinantal point processes (DPP) are studied as promising models for analysis of cellular wireless networks. Indeed, the DPPs can express the repulsive nature of the macro base station (BS) configuration observed in a real cellular network and have many desirable mathematical properties to analyze the network performance. However, almost all the prior works on the DPP based models assume the Rayleigh fading while the spatial models based on Poisson point processes have been developed to allow arbitrary distributions of fading/shadowing propagation effects. In order for the DPP based model to be more promising, it is essential to extend it to allow non-Rayleigh propagation effects. In the present paper, we propose the downlink cellular network model where the BSs are deployed according to the Ginibre point process, which is one of the main examples of the DPPs, over Nakagami-m fading. For the proposed model, we derive a numerically computable form of the coverage probability and reveal some properties of it numerically and theoretically.
△ Less
Submitted 18 March, 2015;
originally announced March 2015.