BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Masafumi Yamashita

Masafumi Yamashita appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Distributed, Parallel, and Cluster ComputingRoboticsDiscrete MathematicsComputation and LanguageComputational ComplexityComputational GeometryData Structures and Algorithmsmath.COMultiagent Systems

Catalog footprint

What is connected

10works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2020arXiv

A Characterization of Semi-Synchrony for Asynchronous Robots with Limited Visibility, and its Application to Luminous Synchronizer Design

A mobile robot system consists of anonymous mobile robots, each of which autonomously performs sensing, computation, and movement according to a common algorithm, so that the robots collectively achieve a given task. There are two main models of time and activation of the robots. In the semi-synchronous model (SSYNC), the robots share a common notion of time; at each time unit, a subset of the robots is activated, and each performs all three actions (sensing, computation, and movement) in that time unit. In the asynchronous model (ASYNC), there is no common notion of time, the robots are activated at arbitrary times, and the duration of each action is arbitrary but finite. In this paper, we investigate the problem of synchronizing ASNYC robots with limited sensing range, i.e., limited visibility. We first present a sufficient condition for an ASYNC execution of a common algorithm ${\cal A}$ to have a corresponding SSYNC execution of ${\cal A}$; our condition imposes timing constraints on the activation schedule of the robots and visibility constraints during movement. Then, we prove that this condition is necessary (with probability $1$) under a randomized ASYNC adversary. Finally, we present a synchronization algorithm for luminous ASYNC robots with limited visibility, each equipped with a light that can take a constant number of colors. Our algorithm enables luminous ASYNC robots to simulate any algorithm ${\cal A}$, designed for the (non-luminous) SSYNC robots and satisfying visibility constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Pattern Formation Problem for Synchronous Mobile Robots in the Three Dimensional Euclidean Space

We consider a swarm of autonomous mobile robots each of which is an anonymous point in the three-dimensional Euclidean space (3D-space) and synchronously executes a common distributed algorithm. We investigate the pattern formation problem that requires the robots to form a given target pattern from an initial configuration and characterize the problem by showing a necessary and sufficient condition for the robots to form a given target pattern. The pattern formation problem in the two dimensional Euclidean space (2D-space) has been investigated by Suzuki and Yamashita (SICOMP 1999, TCS 2010), and Fujinaga et al. (SICOMP 2015). The symmetricity $ρ(P)$ of a configuration (i.e., the positions of robots) $P$ is intuitively the order of the cyclic group that acts on $P$. It has been shown that fully-synchronous (FSYNC) robots can form a target pattern $F$ from an initial configuration $P$ if and only if $ρ(P)$ divides $ρ(F)$. We extend the notion of symmetricity to 3D-space by using the rotation groups each of which is defined by a set of rotation axes and their arrangement. We define the symmetricity $\varrho(P)$ of configuration $P$ in 3D-space as the set of rotation groups that acts on $P$ and whose rotation axes do not contain any robot. We show the following necessary and sufficient condition for the pattern formation problem which is a natural extension of the existing results of the pattern formation problem in 2D-space: FSYNC robots in 3D-space can form a target pattern $F$ from an initial configuration $P$ if and only if $\varrho(P) \subseteq \varrho(F)$. For solvable instances, we present a pattern formation algorithm for oblivious FSYNC robots. The insight of this paper is that symmetry of mobile robots in 3D-space is sometimes lower than the symmetry of their positions and the robots can show their symmetry by their movement.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Plane Formation by Synchronous Mobile Robots in the Three Dimensional Euclidean Space

Creating a swarm of mobile computing entities frequently called robots, agents or sensor nodes, with self-organization ability is a contemporary challenge in distributed computing. Motivated by this, we investigate the plane formation problem that requires a swarm of robots moving in the three dimensional Euclidean space to land on a common plane. The robots are fully synchronous and endowed with visual perception. But they do not have identifiers, nor access to the global coordinate system, nor any means of explicit communication with each other. Though there are plenty of results on the agreement problem for robots in the two dimensional plane, for example, the point formation problem, the pattern formation problem, and so on, this is the first result for robots in the three dimensional space. This paper presents a necessary and sufficient condition for fully-synchronous robots to solve the plane formation problem that does not depend on obliviousness i.e., the availability of local memory at robots. An implication of the result is somewhat counter-intuitive: The robots cannot form a plane from most of the semi-regular polyhedra, while they can form a plane from every regular polyhedron (except a regular icosahedron), whose symmetry is usually considered to be higher than any semi-regular polyhedrdon.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Parity Hamiltonian Cycle Problem

Motivated by a relaxed notion of the celebrated Hamiltonian cycle, this paper investigates its variant, parity Hamiltonian cycle (PHC): A PHC of a graph is a closed walk which visits every vertex an odd number of times, where we remark that the walk may use an edge more than once. First, we give a complete characterization of the graphs which have PHCs, and give a linear time algorithm to find a PHC, in which every edge appears at most four times, in fact. In contrast, we show that finding a PHC is NP-hard if a closed walk is allowed to use each edge at most z times for each z=1,2,3 (PHCz for short), even when a given graph is two-edge connected. We then further investigate the PHC3 problem, and show that the problem is in P when an input graph is four-edge connected. Finally, we are concerned with three (or two)-edge connected graphs, and show that the PHC3 is in P for any C_>=5-free or P6-free graphs. Note that the Hamiltonian cycle problem is known to be NP-hard for those graph classes.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Universal Systems of Oblivious Mobile Robots

An oblivious mobile robot is a stateless computational entity located in a spatial universe, capable of moving in that universe. When activated, the robot observes the universe and the location of the other robots, chooses a destination, and moves there. The computation of the destination is made by executing an algorithm, the same for all robots, whose sole input is the current observation. No memory of all these actions is retained after the move. When the universe is a graph, distributed computations by oblivious mobile robots have been intensively studied focusing on the conditions for feasibility of basic problems (e.g., gathering, exploration) in specific classes of graphs under different schedulers. In this paper, we embark on a different, more general, type of investigation. With their movements from vertices to neighboring vertices, the robots make the system transition from one configuration to another. Viewing this transition as the computation of an abstract function, we ask which functions are computed by which systems. Our main interest is on identifying sets of systems that are "universal", in the sense that they can collectively compute all finite functions. We are able to identify several such classes of fully synchronous systems. In particular, among other results, we prove the universality of the set of all graphs with at least one robot, of any set of graphs with at least two robots whose quotient graphs contain arbitrarily long paths, and of any set of graphs with at least three robots and arbitrarily large finite girths. We then focus on the minimum size that a network must have for the robots to be able to compute all functions on a given finite set. We are able to approximate the minimum size of such a network up to a factor that tends to 2 as $n$ goes to infinity.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Deterministic Random Walks for Rapidly Mixing Chains

The rotor-router model is a deterministic process analogous to a simple random walk on a graph. This paper is concerned with a generalized model, functional-router model, which imitates a Markov chain possibly containing irrational transition probabilities. We investigate the discrepancy of the number of tokens at a single vertex between the functional-router model and its corresponding Markov chain, and give an upper bound in terms of the mixing time of the Markov chain.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Total Variation Discrepancy of Deterministic Random Walks for Ergodic Markov Chains

Motivated by a derandomization of Markov chain Monte Carlo (MCMC), this paper investigates deterministic random walks, which is a deterministic process analogous to a random walk. While there are several progresses on the analysis of the vertex-wise discrepancy (i.e., $L_\infty$ discrepancy), little is known about the {\em total variation discrepancy} (i.e., $L_1$ discrepancy), which plays a significant role in the analysis of an FPRAS based on MCMC. This paper investigates upper bounds of the $L_1$ discrepancy between the expected number of tokens in a Markov chain and the number of tokens in its corresponding deterministic random walk. First, we give a simple but nontrivial upper bound ${\rm O}(mt^*)$ of the $L_1$ discrepancy for any ergodic Markov chains, where $m$ is the number of edges of the transition diagram and $t^*$ is the mixing time of the Markov chain. Then, we give a better upper bound ${\rm O}(m\sqrt{t^*\log t^*})$ for non-oblivious deterministic random walks, if the corresponding Markov chain is ergodic and lazy. We also present some lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Rendezvous of Two Robots with Constant Memory

We study the impact that persistent memory has on the classical rendezvous problem of two mobile computational entities, called robots, in the plane. It is well known that, without additional assumptions, rendezvous is impossible if the entities are oblivious (i.e., have no persistent memory) even if the system is semi-synchronous (SSynch). It has been recently shown that rendezvous is possible even if the system is asynchronous (ASynch) if each robot is endowed with O(1) bits of persistent memory, can transmit O(1) bits in each cycle, and can remember (i.e., can persistently store) the last received transmission. This setting is overly powerful. In this paper we weaken that setting in two different ways: (1) by maintaining the O(1) bits of persistent memory but removing the communication capabilities; and (2) by maintaining the O(1) transmission capability and the ability to remember the last received transmission, but removing the ability of an agent to remember its previous activities. We call the former setting finite-state (FState) and the latter finite-communication (FComm). Note that, even though its use is very different, in both settings, the amount of persistent memory of a robot is constant. We investigate the rendezvous problem in these two weaker settings. We model both settings as a system of robots endowed with visible lights: in FState, a robot can only see its own light, while in FComm a robot can only see the other robot's light. We prove, among other things, that finite-state robots can rendezvous in SSynch, and that finite-communication robots are able to rendezvous even in ASynch. All proofs are constructive: in each setting, we present a protocol that allows the two robots to rendezvous in finite time.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Expressivity of Time-Varying Graphs and the Power of Waiting in Dynamic Networks

In infrastructure-less highly dynamic networks, computing and performing even basic tasks (such as routing and broadcasting) is a very challenging activity due to the fact that connectivity does not necessarily hold, and the network may actually be disconnected at every time instant. Clearly the task of designing protocols for these networks is less difficult if the environment allows waiting (i.e., it provides the nodes with store-carry-forward-like mechanisms such as local buffering) than if waiting is not feasible. No quantitative corroborations of this fact exist (e.g., no answer to the question: how much easier?). In this paper, we consider these qualitative questions about dynamic networks, modeled as time-varying (or evolving) graphs, where edges exist only at some times. We examine the difficulty of the environment in terms of the expressivity of the corresponding time-varying graph; that is in terms of the language generated by the feasible journeys in the graph. We prove that the set of languages $L_{nowait}$ when no waiting is allowed contains all computable languages. On the other end, using algebraic properties of quasi-orders, we prove that $L_{wait}$ is just the family of regular languages. In other words, we prove that, when waiting is no longer forbidden, the power of the accepting automaton (difficulty of the environment) drops drastically from being as powerful as a Turing machine, to becoming that of a Finite-State machine. This (perhaps surprisingly large) gap is a measure of the computational power of waiting. We also study bounded waiting; that is when waiting is allowed at a node only for at most $d$ time units. We prove the negative result that $L_{wait[d]} = L_{nowait}$; that is, the expressivity decreases only if the waiting is finite but unpredictable (i.e., under the control of the protocol designer and not of the environment).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Gathering Problem for Two Oblivious Robots with Unreliable Compasses

Anonymous mobile robots are often classified into synchronous, semi-synchronous and asynchronous robots when discussing the pattern formation problem. For semi-synchronous robots, all patterns formable with memory are also formable without memory, with the single exception of forming a point (i.e., the gathering) by two robots. However, the gathering problem for two semi-synchronous robots without memory is trivially solvable when their local coordinate systems are consistent, and the impossibility proof essentially uses the inconsistencies in their coordinate systems. Motivated by this, this paper investigates the magnitude of consistency between the local coordinate systems necessary and sufficient to solve the gathering problem for two oblivious robots under semi-synchronous and asynchronous models. To discuss the magnitude of consistency, we assume that each robot is equipped with an unreliable compass, the bearings of which may deviate from an absolute reference direction, and that the local coordinate system of each robot is determined by its compass. We consider two families of unreliable compasses, namely,static compasses with constant bearings, and dynamic compasses the bearings of which can change arbitrarily. For each of the combinations of robot and compass models, we establish the condition on deviation ϕthat allows an algorithm to solve the gathering problem, where the deviation is measured by the largest angle formed between the x-axis of a compass and the reference direction of the global coordinate system: ϕ< π/2 for semi-synchronous and asynchronous robots with static compasses, ϕ< π/4 for semi-synchronous robots with dynamic compasses, and ϕ< π/6 for asynchronous robots with dynamic compasses. Except for asynchronous robots with dynamic compasses, these sufficient conditions are also necessary.

0 citations0 reviewsNo code linkedOpen access