Author name cluster

Alfredo Navarra

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers

2 author rows

TCS Journal 2025 Journal Article

Optimal gathering of robots in anonymous butterfly networks via leader election

Serafino Cicerone
Alessia Di Fonso
Gabriele Di Stefano
Alfredo Navarra

Robots with very weak capabilities placed on the vertices of a graph are required to move toward a common vertex from where they do not move anymore. The task is known as the Gathering problem and it has been extensively studied in the last decade with respect to both general graphs and specific topologies. Most of the challenges faced are due to possible isometries observable from the placement of the robots with respect to the underlying topology. Rings, Grids, and Complete graphs are just a few examples of very regular topologies where the placement of the robots and suitable movements are crucial for succeeding in Gathering. Here we are interested in understanding what can be done in Butterfly graphs where really many isometries are present and most importantly unavoidable by any movement. We propose a Gathering algorithm for the so-called leader configurations, i. e. , those where the initial placement of the robots admits the detection (and election) of one robot as the leader. We introduce a non-trivial technique to elect the leader which is of its own interest. We also prove that the proposed Gathering algorithm is asymptotically optimal in terms of synchronous rounds required.

TCS Journal 2024 Journal Article

Molecular pattern formation on grids in the Moblot model

Serafino Cicerone
Alessia Di Fonso
Gabriele Di Stefano
Alfredo Navarra

In the theoretical studies on distributed algorithms for swarm robotics, the complexity and capabilities of the robots are usually reduced to their minimum. Recently, the Moblot model has been introduced in order to deal with robots considered silent, anonymous, and oblivious but capable to aggregate into more complex structures, called molecules. We study the case where robots move along a graph based on a square lattice and we formally define the Molecular Pattern Formation (MPF) problem, where a specific configuration of robots assembled into molecules must be reached. As a preliminary general result, we provide a necessary condition for its solvability. Then, we actually show that dealing with molecules can resolve in some cases the symmetry breaking issue on grids where otherwise robots cannot. Finally, we introduce an interesting case study, representative of the MPF problem, in which the molecules can be formed by the set of the seven tetrominoes (aka Tetris blocks). We provide a complete characterization of this specific problem, providing a distributed algorithm able to form a molecular pattern whenever the necessary condition for the solvability of MPF is verified.

TCS Journal 2023 Journal Article

Arbitrary pattern formation on infinite regular tessellation graphs

Serafino Cicerone
Alessia Di Fonso
Gabriele Di Stefano
Alfredo Navarra

Given a set R of robots, each one located at a different vertex of an infinite regular tessellation graph, we aim to explore the Arbitrary Pattern Formation (APF) problem. Given a multiset F of grid vertices such that | R | = | F |, APF asks for a distributed algorithm that moves robots so as to reach a configuration similar to F. Similarity means that robots must be disposed as F regardless of translations, rotations, reflections. So far, as possible graph discretizing the Euclidean plane only the standard square grid has been considered in the context of the classical OBLOT model. However, it is natural to consider also the other regular tessellation graphs, that are triangular and hexagonal grids. In particular, the former can be considered as the most general in terms of possible symmetries and trajectories. We provide a resolution algorithm for APF when the initial configuration is asymmetric and the considered topology is any regular tessellation graph. The algorithm and its correctness are based on a rigorous methodology.

TCS Journal 2021 Journal Article

Gathering robots in graphs: The central role of synchronicity

Serafino Cicerone
Gabriele Di Stefano
Alfredo Navarra

The Gathering task for k robots disposed on the n vertices of a graph G requires robots to move toward a common vertex from where they do not move anymore. When dealing with very weak robots in terms of capabilities, considering synchronous or asynchronous settings may heavily affect the feasibility of the problem. In fact, even though dealing with asynchronous robots in general requires more sophisticated strategies with respect to the synchronous counterpart, sometimes it comes out that asynchronous robots simply cannot solve the problem whereas synchronous robots can. We study general properties of graphs that can be exploited in order to accomplish the gathering task in the synchronous setting, obtaining an interesting and innovative sufficient condition for the feasibility of the gathering task in graphs, regardless the topology. Furthermore, we consider dense and symmetric graphs like complete and complete bipartite graphs where in general the topology does not allow to distinguish vertices where to finalize the gathering. In such topologies, we fully characterize the solvability of the gathering task in the synchronous setting by suitably combining some strategies arising from the general approach with specific techniques dictated by the considered topologies. From the lower bound point of view in terms of number of synchronous time units required to accomplish the gathering task, in general nothing better than Ω ( D G ), with D G being the diameter of the input graph G, can be provided. For both complete and complete bipartite graphs, we prove a lower bound of Ω ( log ϕ ⁡ k ), with ϕ being the well-known golden ratio. Combined with the provided algorithms, this reveals to be asymptotically tight for complete graphs while for complete bipartite graphs an additive factor of δ ( k ) is achieved, with δ ( k ) being the function that returns the number of divisors of the integer k.

AAMAS Conference 2021 Conference Paper

MOBLOT: Molecular Oblivious Robots

Serafino Cicerone
Alessia Di Fonso
Gabriele Di Stefano
Alfredo Navarra

In swarm robotics, research mainly follows a theoretical approach that considers robot systems in the abstract, where the complexity and capabilities of the underlying model are often reduced to their minimum. One general and well-investigated model is OBLOT, where the robots are silent, anonymous, and oblivious. In this work, we introduce MOBLOT, a model that extends OBLOT to address a larger spectrum of cases. MOBLOT stands for molecular oblivious robots: like atoms combine themselves to form molecules, in MOBLOT simple robots can move to form more complex computational units, having an extent and different capabilities with respect to robots; like molecules combine themselves to form the matter, in MOBLOT the complex structures can exploit their own capabilities to arrange themselves to form any shape defining an acceptable final structure. In MOBLOT, we formally define the Matter Formation (MF) problem and, as a preliminary general result, we provide a necessary condition for its solvability which relies on symmetricity. Informally, the symmetricity of a configuration measures the amount of symmetries of the robots’ disposal. We actually show how dealing with molecules can resolve in some cases the symmetry breaking issue where OBLOT cannot. Finally, we provide a case study for MOBLOT, that is, a representative MF problem along with a resolution distributed algorithm.

TCS Journal 2020 Journal Article

On the curve complexity of 3-colored point-set embeddings

Emilio Di Giacomo
Leszek Gąsieniec
Giuseppe Liotta
Alfredo Navarra

We establish new results on the curve complexity of k-colored point-set embeddings when k = 3. We show that there exist 3-colored caterpillars with only three independent edges whose 3-colored point-set embeddings may require Ω ( n 1 3 ) bends on Ω ( n 2 3 ) edges. This settles an open problem by Badent et al. [5] about the curve complexity of point set embeddings of k-colored trees and it extends a lower bound by Pach and Wenger [35] to the case that the graph only has O ( 1 ) independent edges. Concerning upper bounds, we prove that any 3-colored path admits a 3-colored point-set embedding with curve complexity at most 4. In addition, we introduce a variant of the k-colored simultaneous embeddability problem and study its relationship with the k-colored point-set embeddability problem.

ICRA Conference 2020 Conference Paper

Optimal Routing Schedules for Robots Operating in Aisle-Structures

Francesco Betti Sorbelli
Stefano Carpin
Federico Corò
Alfredo Navarra
Cristina M. Pinotti

In this paper, we consider the Constant-cost Orienteering Problem (COP) where a robot, constrained by a limited travel budget, aims at selecting a path with the largest reward in an aisle-graph. The aisle-graph consists of a set of loosely connected rows where the robot can change lane only at either end, but not in the middle. Even when considering this special type of graphs, the orienteering problem is known to be intractable. We optimally solve in polynomial time two special cases, COP-FR where the robot can only traverse full rows, and COP-SC where the robot can access the rows only from one side. To solve the general COP, we then apply our special case algorithms as well as a new heuristic that suitably combines them. Despite its light computational complexity and being confined into a very limited class of paths, the optimal solutions for COP-FR turn out to be competitive in terms of achieved rewards even for COP. This is shown by means of extended simulations performed on both real and synthetic scenarios. Furthermore, our new heuristic for the general case outperforms state-of-art algorithms, especially for input with highly unbalanced rewards.

I&C Journal 2018 Journal Article

Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane

Mattia D'Emidio
Gabriele Di Stefano
Daniele Frigioni
Alfredo Navarra

In this paper we study the computational power of mobile robots without global coordination. A comprehensive evaluation of the computational power of robots moving within the Euclidean plane has been proposed by Das et al. in 2016. In their work, the authors study the relations between classic synchronization models, namely fully-synchronous, semi-synchronous, and asynchronous, and variations of them where robots are endowed with a visible light, i. e. they are luminous. Here we are interested in similar settings but for robots moving on graphs. In particular, we first prove computational relationships among classic models on graphs. To this respect, we investigate the gathering problem and disprove conjectures previously posed in the literature. Second, we compare classic models against luminous models. Third, we highlight the differences among different luminous models. Finally, we compare our results with those holding in the Euclidean plane.

I&C Journal 2017 Journal Article

Gathering of oblivious robots on infinite grids with minimum traveled distance

Gabriele Di Stefano
Alfredo Navarra

A largely studied version of the gathering problem asks to move a set of robots initially placed at different vertices of an anonymous graph toward a common vertex, and to let them remain at such a vertex. Asynchronous robots move based on the so-called Look–Compute–Move model. Each time a robot wakes-up, it perceives the current configuration in terms of occupied vertices (Look), it decides whether to move toward one of its neighbors (Compute), and then it performs the computed move (Move), eventually. So far, the main goal has been to detect the minimal assumptions that allow to accomplish the task, without taking care of any cost measure. In this paper, we are interested in optimal algorithms in terms of total number of moves. We consider infinite grids, and we fully characterize when optimal gathering is achievable by providing a distributed algorithm.

TCS Journal 2017 Journal Article

Online knapsack of unknown capacity

Alfredo Navarra
Cristina M. Pinotti

We propose a new variant of the standard online knapsack problem where the only information missing to the provided instances is the capacity B of the knapsack. We refer to this problem as the online Knapsack of Unknown Capacity (KUC) problem. Any algorithm solving the KUC problem must provide a strategy for filling online the knapsack until its capacity is revealed. When the knapsack capacity is revealed, no other item can be inserted and also the last inserted item is discarded if it does not completely fit in the knapsack. Apart for the interest in a new version of the fundamental knapsack problem, the motivations that lead to define this new variant come from energy consumption constraints in smartphones communications. We provide lower and upper bounds to the problem for various cases. In general, we design an optimal algorithm admitting a 1 2 -competitive ratio. When all items admit uniform ratio of profit over size, our algorithm provides a 49 86 =. 569 … competitive ratio that leaves some gap with the provided bound of 1 φ =. 618 …, the inverse of the golden number. We then conduct experimental analysis for the competitive ratio guaranteed algorithms compared to the optimum and to various heuristics.

TCS Journal 2016 Journal Article

Gathering of robots on anonymous grids and trees without multiplicity detection

Gianlorenzo D'Angelo
Gabriele Di Stefano
Ralf Klasing
Alfredo Navarra

The paper studies the gathering problem on grid and tree networks. A team of robots placed at different nodes of the input graph, has to meet at some node and remain there. Robots operate in Look–Compute–Move cycles; in one cycle, a robot perceives the current configuration in terms of occupied nodes (Look), decides whether to move toward one of its neighbors (Compute), and in the positive case makes the computed move instantaneously (Move). Cycles are performed asynchronously for each robot. The problem has been deeply studied for the case of ring networks. However, the known techniques used on rings cannot be directly extended to grids and trees. Moreover, on rings, another assumption concerning the so-called multiplicity detection capability was required in order to accomplish the gathering task. That is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. In this paper, we provide a full characterization about gatherable configurations for grids and trees. In particular, we show that on these topologies, the multiplicity detection is not required. Very interestingly, sometimes the problem appears trivial, as it is for the case of grids with both odd sides, while sometimes the involved techniques require new insights with respect to the well-studied ring case. Moreover, our results reveal the importance of structures like grids and trees that allow to overcome the multiplicity detection with respect to the ring case.

TCS Journal 2015 Journal Article

Explore and repair graphs with black holes using mobile entities

Mattia D'Emidio
Daniele Frigioni
Alfredo Navarra

In this paper, we study the problem of mobile entities that synchronously have to explore and repair a graph with faulty nodes, usually called black-holes, that destroy any entering entity. We consider the scenario where the destruction of an entity by means of a black-hole also affects all the entities within a fixed range r (in terms of number of edges), while the black-hole disappears. Clearly, if there are b black-holes in the graph, then k ≥ b entities are necessary to remove all of them from that graph. We ask for the minimum number of synchronous steps needed to make safe all the graph. The results of this paper are both theoretical and experimental, and can be summarized as follows. From the theoretical point of view, first we show that the problem is NP-hard even for b = k = 1. Then, we provide a general lower bound holding when r ≥ 0 and a higher one for the case of r > 0. We then consider the case of r ≤ 1. We propose an optimal solution holding when k is unbounded, that is, an infinite number of robots is available. Then, we provide three different exploration strategies, named snake, scout, and parallel-scout, respectively, for the case of bounded k, that is, the number of robots is fixed a priori. The three strategies are then analyzed according to the time complexity with respect to the lower bound. From the experimental point of view, we implemented the three strategies and tested them on different scenarios with the aim of assessing their practical performance. The experiments confirm the theoretical analysis and show that parallel-scout is always by far the best exploration strategy in practice.

TCS Journal 2015 Journal Article

The minimum k-storage problem on directed graphs

Gianlorenzo D'Angelo
Daniele Diodati
Alfredo Navarra
Cristina M. Pinotti

In standard sensor network applications, sensors generate raw data that have to be sent to a sink node. In order to save energy, special intermediate storage nodes can be exploited in order to compress data before forwarding them to the sink. We consider the problem of locating k storage nodes in order to minimize the energy consumed for converging data to the sink. This is known as the minimum k-storage problem. We show that in directed graphs (and in particular in Directed Acyclic Graphs) the problem does not admit an algorithm with a constant approximation ratio, unless P = NP. If the topology is restricted to trees where the arcs are directed towards the sink (typical scenario in sensor networks), the problem is solvable in polynomial time. We give a dynamic programming algorithm that requires O ( min ⁡ { k n 2, k 2 P } ) time, where n and P are the number of nodes and the path length of the tree [7], respectively. We improve over a previous algorithm which requires O ( k n 2 ( max ⁡ { k, d } ) d − 1 ) time, where d is the maximum out-degree of the tree [8].

TCS Journal 2013 Journal Article

Maximum matching in multi-interface networks

Adrian Kosowski
Alfredo Navarra
Dominik Pajak
Cristina M. Pinotti

In heterogeneous networks, devices can communicate by means of multiple wireless interfaces. By choosing which interfaces to switch on at each device, several connections might be established. That is, the devices at the endpoints of each connection share at least one active interface. In this paper, we consider the standard matching problem in the context of multi-interface wireless networks. The aim is to maximize the number of parallel connections without incurring interferences. Given a network G = ( V, E ), nodes V represent the devices, and edges E represent the connections that can be established. If node x participates in the communication with one of its neighbors by means of interface i, then another neighboring node of x can establish a connection (but not with x ) only if it makes use of interface j ≠ i. The size of a solution for an instance of the outcoming matching problem, which we call Maximum Matching in Multi-Interface networks (MMMI for short), is always in between the sizes of the solutions for the same instance with respect to the standard matching and its induced version problems. However, we prove that MMMI is NP-hard even for proper interval graphs and for bipartite graphs of maximum degree Δ ≥ 3. We also show polynomially solvable cases of MMMI with respect to different assumptions.

TCS Journal 2011 Journal Article

Synchronous black hole search in directed graphs

Adrian Kosowski
Alfredo Navarra
Cristina M. Pinotti

The paper considers a team of robots which has to explore a graph G, where some nodes can be harmful. Robots are initially located at the so-called home base node. The dangerous nodes are the so-called black hole nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore G in such a way that minimum number of robots is wasted. The exploration ends if there is at least one surviving robot which knows all the edges leading to the black holes. As many variations of the problem have been considered so far, the solution and its measure heavily depend on the initial knowledge and the capabilities of the robots. In this paper, we assume that G is a directed graph, the robots are associated with unique identifiers, they know the number of nodes n of G (or at least an upper bound on n ), and they know the number of edges Δ leading to the black holes. Each node is associated with a whiteboard where robots can read and write information in a mutual exclusive way. A recently posed question [J. Czyzowicz, S. Dobrev, R. Kralovic, S. Miklik, D. Pardubska, Black hole search in directed graphs, in: Proc. of 16th International Colloquium on Structural Information and Communication Complexity, SIROCCO, LNCS, vol. 5869, 2009, pp. 182–194. ] is whether some number of robots, expressed as a function of parameter Δ only, is sufficient to detect black holes in directed graphs of arbitrarily large order n. We give a positive answer to this question for the synchronous case, i. e. , when the robots share a common clock, showing that O ( Δ ⋅ 2 Δ ) robots are sufficient to solve the problem. This bound is nearly tight, since it is known that at least 2 Δ robots are required for some instances. Quite surprisingly, we also show that unlike in the case of undirected graphs, for the directed version of the problem, synchronization can sometimes make a difference: for Δ = 2, in the synchronous case 4 robots are always sufficient, whereas in the asynchronous case at least 5 robots are sometimes required.

TCS Journal 2010 Journal Article

Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring

Ralf Klasing
Adrian Kosowski
Alfredo Navarra

One of the recently considered models of robot-based computing makes use of identical, memoryless mobile units placed in nodes of an anonymous graph. The robots operate in Look–Compute–Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of the nodes adjacent to its current position (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. In such a restricted scenario, we study the influence of symmetries of the robot configuration on the feasibility of certain computational tasks. More precisely, we deal with the problem of gathering all robots at one node of the graph, and propose a solution based on a symmetry-preserving strategy. When the considered graph is an undirected ring and the number of robots is sufficiently large (more than 18), such an approach is proved to solve the problem for all starting situations, as long as gathering is feasible. In this way we also close the open problem of characterizing symmetric situations on the ring which admit a gathering [R. Klasing, E. Markou, A. Pelc: Gathering asynchronous oblivious mobile robots in a ring, Theoret. Comput. Sci. 390 (1) (2008) 27–39]. The proposed symmetry-preserving approach, which is complementary to symmetry-breaking techniques found in related work, appears to be new and may have further applications in robot-based computing.

MFCS Conference 2009 Conference Paper

Graph Decomposition for Improving Memoryless Periodic Exploration

Adrian Kosowski
Alfredo Navarra

Abstract We consider a general framework in which a memoryless robot periodically explores all the nodes of a connected anonymous graph by following local information available at each vertex. For each vertex v, the endpoints of all edges adjacent to v are assigned unique labels from the range 1 to deg( v ) (the degree of v ). The generic exploration strategy is implemented using a right-hand-rule transition function: after entering vertex v via the edge labeled i, the robot proceeds with its exploration, leaving via the edge having label [ i mod deg(v)]+1 at v. A lot of attention has been given to the problem of labeling the graph so as to achieve a periodic exploration having the minimum possible length π. It has recently been proved [Czyzowicz et al. , Proc. SIROCCO’09 [1]] that \(\pi \leq 4\frac13 n\) holds for all graphs of n vertices. Herein, we provide a new labeling scheme which leads to shorter exploration cycles, improving the general bound to π ≤ 4 n − 2. This main result is shown to be tight with respect to the class of labelings admitting certain connectivity properties. The labeling scheme is based on a new graph decomposition which may be of independent interest.

TCS Journal 2005 Journal Article

On routing of wavebands for all-to-all communications in all-optical paths and cycles

Michele Flammini
Alfredo Navarra
Andrzej Proskurowski

We discuss a model of the all-optical communication technology and an implementation of a simple task, all-to-all, in simple topologies like paths and cycles. The model assumes a single interval (variant of band-pass) filter extracting signal wavelengths for processing and forwarding in intermediate communication nodes. In an attempt to use a minimum number of wavelengths, we give lower and upper bounds on the cardinality of the spectrum used in four cases arising from different assumptions on the topology and the filters. In particular, we propose efficient schedules of directed paths between all pairs of nodes in graphs of maximum node degree two, under the assumption of either a “linear” or “wrapped-around” wavelength spectrum.