• Gokarna Sharma

  Optimally Solving Dispersion on Anonymous Graphs

  Consider the recently actively studied problem of dispersion where a group of \(k <= n\) robots (aka agents) with unique identifiers located arbitrarily initially on the nodes of an n-node anonymous undirected port-labeled arbitrary graph must autonomously relocate themselves such that there is at most one robot at a node. The goal has been to minimize (or provide trade-off between) two fundamental performance metrics: (i) time to reach a solution and (ii) memory bits required at each robot. It is known that any deterministic solution needs Omega(k) time and Omega(log(max(k,Delta)) bits per robot, where Delta is the maximum degree of the graph. A recent breakthrough presents a solution with \(O(k log^2k)\) time and \(O(log(max(k,Delta)\) bits per robot, which is memory-optimal, improving significantly on the best previously known \(O(min(m, k Delta))\)-time solution with the same optimal memory requirement. In this talk, I first discuss our efforts on obtaining an \(O(k)\)-time solution with \(O(Delta + log k)\) bits at each robot, achieving time-optimality for the first time, and then present some related open problems.

• Yuichi Sudo

  Graph exploration by a clumsy agent

  Bojko, Gotfryd, Kowalski, and Pajak [MCFS 2022] recently focused on the graph exploration problem by a weak mobile agent, which we call a clumsy agent. Here we use the word "clumsy" in the sense that after the agent moves from a node \(u\) to a node \(v\), it does not recognize the edge \(\{u,v\}\) at \(v\). A clumsy agent cannot easily backtrack from \(v\) to \(u\) after moving \(u\) to \(v\), while a standard or normal agent can easily make a backtrack whenever it wants. Thus, in general, it is not easier to design a time- and/or space-efficient algorithm with clumsy agents than with normal agents. Bojko et al. gave a time-optimal graph exploration algorithm for trees by which a single clumsy agent visits all nodes and terminates thereafter. Some of my students and I gave a time-optimal graph exploration algorithm for general graphs in the last year. In this talk, I will briefly explain this result and give some open problems.

• Quentin Bramas

  Open problems in grid exploration by luminous robots with limited visibility

  In this presentation, I will quickly present the grid exploration problem by luminous robots and make a tour of the results we obtained in the various settings (visibility range, number of robots, number of colors, chirality, etc). I will then present the open problems we left in the different settings, show some unpublished works, and highlight the future challenges.

• Taisuke Izumi

  On Computational Power of Mobile Agents in Node Storage Model

  One of the major research directions in the mobile-agent theory is to characterize the computational power of a given model. Particularly, the amount of memory equipped with each agent is one of the central measures of quantifying the computational power, in relation to the space complexity of the graph exploration problem. In this talk, we focus on the model in which nodes are also equipped with a (small) amount of memory (called storage), and investigate how the computational capability varies according to the model parameters such as agent memory size, storage size, and number of agents. Our talk first presents the recent progress on this research direction, and then proposes a few problems still left open.

• Anissa Lamani

  Stand up indulgent gathering in the discrete universe

  We consider a variant of the crash-fault gathering problem called stand-up indulgent gathering (SUIG). In this problem, a group of mobile robots must eventually gather at a single location, which is not known in advance. If no robots crash, they must all meet at the same location. However, if one or more robots crash at a single location, all non-crashed robots must eventually gather at that location. The SUIG problem was first introduced for robots operating in a two-dimensional continuous Euclidean space, with most solutions relying on the ability of robots to move a prescribed (real) distance at each time instant. We investigate the SUIG problem for robots operating in a discrete universe (i.e., a graph) where they can only move one unit of distance (i.e., to an adjacent node) at each time instant. Specifically, we focus on line-shaped networks and characterize the solvability of the SUIG problem for oblivious robots without multiplicity detection.

• Kazuki Hasegawa

  Uniform deployment of mobile robots with restricted views in path graphs

  We consider the uniform deployment of mobile robots on path graphs. The view each robot can observe is restricted in the sense that each robot can observe the part of the path graph to the nearest robot or the end node in each direction. We first show that no algorithm can achieve uniform deployment in line graphs. Then we show that uniform deployment becomes possible to achieve if a sense of direction is available in line graphs.

• John Augustine

  Byzantine Resilient Gathering of Anonymous Mobile Agents

  It is well known that deterministic gathering is impossible on graphs when the mobile agents are anonymous. Thankfully, randomization provides us a way out and makes the problem solvable. In this talk, we will discuss how randomization can help us in gathering anonymous mobile agents efficiently. Moreover, we will show how we can design protocols that are resilient against an adversary that can maliciously control a large subset of the mobile agents.

• Toshimitsu Masuzawa

  Crash-tolerant graph exploration by two energy-sharing mobile agents

  We consider the problem of graph exploration by energy-sharing mobile agents that are subject to crash faults. More precisely, we consider a team of two agents where at most one of them may fail unpredictably, and exploration of lines, trees, and rings. We consider both the asynchronous and the synchronous settings, and we provide necessary and sufficient conditions for the energy.

• Konstantinos Georgiou

  Search-Type Problems on the Unit Disk

  Consider a number of mobile agents that are initially collocated at the center of a unit disk. Somewhere on the disk, there is a hidden object that the agents can see only upon direct contact. For a movement trajectory of the mobile agents, consider the first time that each agent reaches the hidden object, as well as any cost function of mapping these times to the reals. A long series of well-studied search-type problems can be obtained by considering various mobile agent specifications (including the underlying communication model), as well as different objectives on the cost function with respect to the placement of the hidden object. In this talk we will review known results that fall in this line of research, emphasizing some challenging open questions.

• Binh-Minh Bui-Xuan

  Continuous journeys in (spatio) temporal graphs

  We review some recent results on path finding and present open cases when navigating continuously through a graph having two properties: it is embedded in a Euclidean space; its edges change with time. Such spatio temporal graphs arise in applications such as with SLAM algorithms (simultaneous localization and mapping) for mobile robots, or in connecting waypoints in flight planning.
  For static graphs, when the input graph is embedded into a Euclidean space, A*-like algorithms can be used for very fast practical runtime. Unfortunately for the other hand, when generalising the input to graphs whose edges change with time, the complexity class is more complex. Some definitions of journeys (temporal paths) will lead polynomial path finding problems, while other to NP-difficult problems. For graphs mixing both properties, a lot of questions are still unanswered such as how to generalise A*-like algorithms to the temporal cases.

• Stefan Dobrev

  Finer modeling of dynamic networks using transition graph

  Typically, there are underlying reasons why the network topogy/the dynamic graph is changing with time. That means that models such as t-connected TVGs are somewhat over-pessimistic in giving the adversary (choosing the graph in the next time step) too much freedom. We would like to investigate ways to restrict this freedom while capturing the essence of how and why the graph changes in time.
  The basic idea is to consider a meta-graph \(H\), where the vertices correspond to topologies the graph can take at any particular time, and edges correspond to possible transitions (in one time step) between them.
  We have briefly investigated some particular \(H\) (e.g. trees and directed cycles, both with self-loops at each vertex), but more and nicer results would be better.

• Caterina Faletti

  Computational Power of Opaque Robots: New Results and Open Problems

  The computational power of mobile robot models has been widely investigated. Researchers have presented manifold models by imposing strong limitations, in order to probe how these restrictions affect their computability. The compared models share a common set of core features: robots are autonomous, homogeneous, anonymous, identical, punctiform, (completely or partially) disoriented, and move on the plane. The variable features mainly considered in the literature include (i) the presence of a constant-size memory, (ii) the possibility to send constant-size messages, and (iii) the synchronization mode. Varying features (i-ii), we obtain the well-known models: OBLOT (silent and oblivious robots), FSTA (silent and finite-state robots), FCOM (oblivious and finite-communication robots), and LUMI (finite-state and finite-communication robots). Multifold works show the hierarchical relations (dominance, equivalence, or orthogonality) between these models. However, just transparent robots have been considered.
  In our current research, we are investigating the computational power of opaque robots, and how the obstructed visibility alters their taxonomy. The lack of complete visibility introduces some critical issues so that some results known in the literature cannot be applied in the case of opaqueness. Moreover, the presence of collinearities might require new approaches to analyze the robot configurations and rigorously deal with these models. In this talk, we present some contributions on the computational taxonomy of opaque robots. Eventually, we cite some open questions and research directions in this setting.

• Fabian Frei

  Robots Missing Someone

  Gathering in a single point is a fundamental task for autonomous robots executing simple look-compute-move cycles. The recently introduced defected-view model limits the number of robots detected in each look phase. This talk presents a natural variant of the model and determines, for all variants and each number of robots, whether gathering is feasible if each robot misses at most one other.

• Koichi Wada

  On the power of mobile robots with light?-schedulers, memories, and communications.

  In this talk, we compare the computational power of light-equipped autonomous mobile robots from the perspectives of synchronization (schedulers), memory, and communication. We consider four models of robots with lights: LUMI, FCOM, FSTA, and OBLOT. We also consider four types of schedulers: FSYNCH, RSYNCH, SSYNCH, and ASYNCH. We will outline the capabilities of each of the 16 possible combinations based on existing results and introduce several interesting open problems.

• Andrea Richa

  Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks

  We develop a framework for self-induced phase changes in programmable matter in which a collection of agents with limited computational and communication capabilities can collectively perform appropriate global tasks in response to local stimuli that dynamically appear and disappear. Agents reside on graph vertices, where each stimulus is only recognized locally, and agents communicate via token passing along edges to alert other agents to transition to an aware state when stimuli are present and an unaware state when the stimuli disappear. We present an Adaptive Stimuli Algorithm that is robust to competing waves of messages as multiple stimuli change, possibly adversarially. Moreover, in addition to handling arbitrary stimulus dynamics, the algorithm can handle agents reconfiguring the connections (edges) of the graph over time in a controlled way. As an application, we show how this Adaptive Stimuli Algorithm on reconfigurable graphs can be used to solve the foraging problem, where food sources may be discovered, removed, or shifted at arbitrary times. We would like the agents to consistently self-organize, using only local interactions, such that if the food remains in a position long enough, the agents transition to a gather phase in which many collectively form a single large component with small perimeter around the food. Alternatively, if no food source has existed recently, the agents should undergo a self-induced phase change and switch to a search phase in which they distribute themselves randomly throughout the lattice region to search for food. Unlike previous approaches to foraging, this process is indefinitely repeatable, withstanding competing waves of messages that may interfere with each other. Like a physical phase change, microscopic changes such as the deletion or addition of a single food source trigger these macroscopic, system-wide transitions as agents share information about the environment and respond locally to get the desired collective response. This is joint work with Shunhao Oh and Dana Randall.

• Joshua Daymude

  New Frontiers for Amoebots: Fault Tolerance, Circuit Communication, and 3D Stability

  The amoebot model of programmable matter (SPAA 2014) and its recent canonicalization (DISC 2021; Distributed Computing 2023) has seen much research activity in the last decade from distributed computing theorists, swarm roboticists, and computational geometers. But beyond continued refinements on leader election and shape formation?the most intensely studied problems under this model and programmable matter in general?obstacles remain to realizing true programmable matter systems based on ideas from the amoebot literature. In this short talk, I outline three directions to better close the gap with reality and enable comparisons with real experiments (e.g., on 3D catoms). First, I discuss the shallow history of *fault tolerance* in the amoebot model and opportunities for robustness; second, I review the recent circuit communication extension (DNA 2022) and its surprising capabilities; finally, I revisit the modular robotics problem of achieving gravity stability during 3D reconfiguration in an amoebot context.

• Alfredo Navarra

  Silent programmable matter: State of the art

  By Programmable Matter (PM) is usually meant a system of weak and self-organizing computational entities, called particles. PM can be programmed by providing distributed algorithms for the particles that collectively achieve some global tasks. We consider the SILBOT model where particles are modeled as finite state automata, living and operating in the cells of a hexagonal grid. Particles are all identical, executing the same deterministic algorithm which is based only on the local observation of the surroundings. Particles are asynchronous, without any direct means of communication, disoriented and oblivious, i.e., without any knowledge of past events. Within such a basic model, we take a look at the latest findings, while providing challenging open questions.

• Shinnosuke Seki

  How complex shapes structures can RNA fold into?

  Computing in nature is driven by structures as gene expression is suppressed by a hairpin-like terminator stem. Structures self-assemble efficiently by letting an RNA sequence fold greedily upon itself while being synthesized (transcribed) nucleotide by nucleotide (A, C, G, U), that is, co-transcriptionally. Geary, Rothemund, and Andersen have programmed a rectangular tile structure onto an RNA sequence in the sense that the sequence folds co-transcriptionally into the tile in vitro. As structures of various shapes and sizes are thus programmable nowadays, computation is the next. Using a formal model called oritatami, co-transcriptional folding has proven to be capable of simulating 2D Turing machines intrinsically, yielding even an uncomputable structure. Whatever self-assemblable in nature and matters in practice is however finite. Finite structures self-assemble in linear time in length of a transcript in oritatami, and it seems likely to be the case even in nature. In programming a (finite) structure, the resulting oritatami system must be checked whether it actually folds into the structure, and co-transcriptionality allows this check to be done in linear time in transcript length. How easy is this check more precisely? Can we parallelize it or is it P-hard? In order to prove the P-hardness, the 2D TM simulation mentioned above is of little use as its resulting structure reveals too much of what it has computed, and these pieces of information enable verification to be done in logarithmic space, or equivalently, by a swarm of simple robots with limited vision.