-
Multi-UAVs end-to-end Distributed Trajectory Generation over Point Cloud Data
Authors:
Antonio Marino,
Claudio Pacchierotti,
Paolo Robuffo Giordano
Abstract:
This paper introduces an end-to-end trajectory planning algorithm tailored for multi-UAV systems that generates collision-free trajectories in environments populated with both static and dynamic obstacles, leveraging point cloud data. Our approach consists of a 2-fork neural network fed with sensing and localization data, able to communicate intermediate learned features among the agents. One netw…
▽ More
This paper introduces an end-to-end trajectory planning algorithm tailored for multi-UAV systems that generates collision-free trajectories in environments populated with both static and dynamic obstacles, leveraging point cloud data. Our approach consists of a 2-fork neural network fed with sensing and localization data, able to communicate intermediate learned features among the agents. One network branch crafts an initial collision-free trajectory estimate, while the other devises a neural collision constraint for subsequent optimization, ensuring trajectory continuity and adherence to physicalactuation limits. Extensive simulations in challenging cluttered environments, involving up to 25 robots and 25% obstacle density, show a collision avoidance success rate in the range of 100 -- 85%. Finally, we introduce a saliency map computation method acting on the point cloud data, offering qualitative insights into our methodology.
△ Less
Submitted 28 June, 2024;
originally announced June 2024.
-
Liquid-Graph Time-Constant Network for Multi-Agent Systems Control
Authors:
Antonio Marino,
Claudio Pacchierotti,
Paolo Robuffo Giordano
Abstract:
In this paper, we propose the Liquid-Graph Time-constant (LGTC) network, a continuous graph neural network(GNN) model for control of multi-agent systems based on therecent Liquid Time Constant (LTC) network. We analyse itsstability leveraging contraction analysis and propose a closed-form model that preserves the model contraction rate and doesnot require solving an ODE at each iteration. Compared…
▽ More
In this paper, we propose the Liquid-Graph Time-constant (LGTC) network, a continuous graph neural network(GNN) model for control of multi-agent systems based on therecent Liquid Time Constant (LTC) network. We analyse itsstability leveraging contraction analysis and propose a closed-form model that preserves the model contraction rate and doesnot require solving an ODE at each iteration. Compared todiscrete models like Graph Gated Neural Networks (GGNNs),the higher expressivity of the proposed model guaranteesremarkable performance while reducing the large amountof communicated variables normally required by GNNs. Weevaluate our model on a distributed multi-agent control casestudy (flocking) taking into account variable communicationrange and scalability under non-instantaneous communication
△ Less
Submitted 22 April, 2024;
originally announced April 2024.
-
Visual Action Planning with Multiple Heterogeneous Agents
Authors:
Martina Lippi,
Michael C. Welle,
Marco Moletta,
Alessandro Marino,
Andrea Gasparri,
Danica Kragic
Abstract:
Visual planning methods are promising to handle complex settings where extracting the system state is challenging. However, none of the existing works tackles the case of multiple heterogeneous agents which are characterized by different capabilities and/or embodiment. In this work, we propose a method to realize visual action planning in multi-agent settings by exploiting a roadmap built in a low…
▽ More
Visual planning methods are promising to handle complex settings where extracting the system state is challenging. However, none of the existing works tackles the case of multiple heterogeneous agents which are characterized by different capabilities and/or embodiment. In this work, we propose a method to realize visual action planning in multi-agent settings by exploiting a roadmap built in a low-dimensional structured latent space and used for planning. To enable multi-agent settings, we infer possible parallel actions from a dataset composed of tuples associated with individual actions. Next, we evaluate feasibility and cost of them based on the capabilities of the multi-agent system and endow the roadmap with this information, building a capability latent space roadmap (C-LSR). Additionally, a capability suggestion strategy is designed to inform the human operator about possible missing capabilities when no paths are found. The approach is validated in a simulated burger cooking task and a real-world box packing task.
△ Less
Submitted 25 March, 2024;
originally announced March 2024.
-
On Computing Optimal Temporal Branchings and Spanning Subgraphs
Authors:
Daniela Bubboloni,
Costanza Catalano,
Andrea Marino,
Ana Silva
Abstract:
In this work we extend the concept of out/in-branchings spanning the vertices of a digraph (also called directed spanning trees) to temporal graphs, which are digraphs where arcs are available only at prescribed times. While the literature has focused on minimum weight/earliest arrival time Temporal Out-Branchings (TOB), we solve the problem for other optimization criteria. In particular, we defin…
▽ More
In this work we extend the concept of out/in-branchings spanning the vertices of a digraph (also called directed spanning trees) to temporal graphs, which are digraphs where arcs are available only at prescribed times. While the literature has focused on minimum weight/earliest arrival time Temporal Out-Branchings (TOB), we solve the problem for other optimization criteria. In particular, we define five different types of TOBs based on the optimization of the travel duration (FT-TOB), of the departure time (LD-TOB), of the number of transfers (MT-TOB), of the total waiting time (MW-TOB), and of the travelling time (ST-TOB). For D$\in \{$LD,MT,ST$\}$, we provide necessary and sufficient conditions for the existence of a spanning D-TOB; when it does not exist, we characterize the maximum vertex set that a D-TOB can span. Moreover, we provide a log linear algorithm for computing such branchings. For D$\in \{$FT,MW$\}$, we prove that deciding the existence of a spanning D-TOB is NP-complete; we also show that the same results hold for optimal temporal in-branchings. Finally, we investigate the related problem of computing a spanning temporal subgraph with the minimum number of arcs and optimizing a chosen criterion D. This problem turns out to be NP-hard for any D. The hardness results are quite surprising, as computing optimal paths between nodes can always be done in polynomial time.
△ Less
Submitted 18 December, 2023;
originally announced December 2023.
-
Input State Stability of Gated Graph Neural Networks
Authors:
Antonio Marino,
Claudio Pacchierotti,
Paolo Robuffo Giordano
Abstract:
In this paper, we aim to find the conditions for input-state stability (ISS) and incremental input-state stability ($δ$ISS) of Gated Graph Neural Networks (GGNNs). We show that this recurrent version of Graph Neural Networks (GNNs) can be expressed as a dynamical distributed system and, as a consequence, can be analysed using model-based techniques to assess its stability and robustness properties…
▽ More
In this paper, we aim to find the conditions for input-state stability (ISS) and incremental input-state stability ($δ$ISS) of Gated Graph Neural Networks (GGNNs). We show that this recurrent version of Graph Neural Networks (GNNs) can be expressed as a dynamical distributed system and, as a consequence, can be analysed using model-based techniques to assess its stability and robustness properties. Then, the stability criteria found can be exploited as constraints during the training process to enforce the internal stability of the neural network. Two distributed control examples, flocking and multi-robot motion control, show that using these conditions increases the performance and robustness of the gated GNNs.
△ Less
Submitted 6 February, 2024; v1 submitted 30 May, 2023;
originally announced May 2023.
-
A Task Allocation Framework for Human Multi-Robot Collaborative Settings
Authors:
Martina Lippi,
Paolo Di Lillo,
Alessandro Marino
Abstract:
The requirements of modern production systems together with more advanced robotic technologies have fostered the integration of teams comprising humans and autonomous robots. However, along with the potential benefits also comes the question of how to effectively handle these teams considering the different characteristics of the involved agents. For this reason, this paper presents a framework fo…
▽ More
The requirements of modern production systems together with more advanced robotic technologies have fostered the integration of teams comprising humans and autonomous robots. However, along with the potential benefits also comes the question of how to effectively handle these teams considering the different characteristics of the involved agents. For this reason, this paper presents a framework for task allocation in a human multi-robot collaborative scenario. The proposed solution combines an optimal offline allocation with an online reallocation strategy which accounts for inaccuracies of the offline plan and/or unforeseen events, human subjective preferences and cost of switching from one task to another so as to increase human satisfaction and team efficiency. Experiments are presented for the case of two manipulators cooperating with a human operator for performing a box filling task.
△ Less
Submitted 25 October, 2022;
originally announced October 2022.
-
Gestural and Touchscreen Interaction for Human-Robot Collaboration: a Comparative Study
Authors:
Antonino Bongiovanni,
Alessio De Luca,
Luna Gava,
Lucrezia Grassi,
Marta Lagomarsino,
Marco Lapolla,
Antonio Marino,
Patrick Roncagliolo,
Simone Macciò,
Alessandro Carfì,
Fulvio Mastrogiovanni
Abstract:
Close human-robot interaction (HRI), especially in industrial scenarios, has been vastly investigated for the advantages of combining human and robot skills. For an effective HRI, the validity of currently available human-machine communication media or tools should be questioned, and new communication modalities should be explored. This article proposes a modular architecture allowing human operat…
▽ More
Close human-robot interaction (HRI), especially in industrial scenarios, has been vastly investigated for the advantages of combining human and robot skills. For an effective HRI, the validity of currently available human-machine communication media or tools should be questioned, and new communication modalities should be explored. This article proposes a modular architecture allowing human operators to interact with robots through different modalities. In particular, we implemented the architecture to handle gestural and touchscreen input, respectively, using a smartwatch and a tablet. Finally, we performed a comparative user experience study between these two modalities.
△ Less
Submitted 8 July, 2022;
originally announced July 2022.
-
Menger's Theorem for Temporal Paths (Not Walks)
Authors:
Allen Ibiapina,
Raul Lopes,
Andrea Marino,
Ana Silva
Abstract:
A (directed) temporal graph is a (directed) graph whose edges are available only at specific times during its lifetime $τ$. Temporal walks are sequences of adjacent edges whose appearing times are either strictly increasing or non-decreasing (here called non-strict), depending on the scenario. Paths are temporal walks where no vertex repetition is allowed. A temporal vertex is a pair $(u,i)$ where…
▽ More
A (directed) temporal graph is a (directed) graph whose edges are available only at specific times during its lifetime $τ$. Temporal walks are sequences of adjacent edges whose appearing times are either strictly increasing or non-decreasing (here called non-strict), depending on the scenario. Paths are temporal walks where no vertex repetition is allowed. A temporal vertex is a pair $(u,i)$ where $u$ is a vertex and $i\in[τ]$ a timestep. In this paper we focus on the questions: (i) are there at least $k$ paths from a single source $s$ to a single target $t$, no two of which internally intersect on a temporal vertex? (ii) are there at most $h$ temporal vertices whose removal disconnects $s$ from $t$? Let $k^*$ be the maximum value $k$ for which the answer to (i) is YES, and let $h^*$ be the minimum value $h$ for which the answer to (ii) is YES. In static graphs, $k^*$ and $h^*$ are equal by Menger's Theorem and this is a crucial property to solve efficiently both (i) and (ii). In temporal graphs such equality has been investigated only focusing on disjoint walks rather than disjoint paths. In this context, we prove that $k^*$ is equal to $h^*$ if and only if $k^*$ is 1. We show that this implies a dichotomy for (i), which turns out to be polynomial-time solvable when $k \le 2$, and NP-complete for $k \ge 3$. Finally, we give hardness results and an XP algorithm for (ii).
△ Less
Submitted 6 November, 2023; v1 submitted 30 June, 2022;
originally announced June 2022.
-
Augment-Connect-Explore: a Paradigm for Visual Action Planning with Data Scarcity
Authors:
Martina Lippi,
Michael C. Welle,
Petra Poklukar,
Alessandro Marino,
Danica Kragic
Abstract:
Visual action planning particularly excels in applications where the state of the system cannot be computed explicitly, such as manipulation of deformable objects, as it enables planning directly from raw images. Even though the field has been significantly accelerated by deep learning techniques, a crucial requirement for their success is the availability of a large amount of data. In this work,…
▽ More
Visual action planning particularly excels in applications where the state of the system cannot be computed explicitly, such as manipulation of deformable objects, as it enables planning directly from raw images. Even though the field has been significantly accelerated by deep learning techniques, a crucial requirement for their success is the availability of a large amount of data. In this work, we propose the Augment-Connect-Explore (ACE) paradigm to enable visual action planning in cases of data scarcity.
We build upon the Latent Space Roadmap (LSR) framework which performs planning with a graph built in a low dimensional latent space. In particular, ACE is used to i) Augment the available training dataset by autonomously creating new pairs of datapoints, ii) create new unobserved Connections among representations of states in the latent graph, and iii) Explore new regions of the latent space in a targeted manner. We validate the proposed approach on both simulated box stacking and real-world folding task showing the applicability for rigid and deformable object manipulation tasks, respectively.
△ Less
Submitted 1 August, 2022; v1 submitted 24 March, 2022;
originally announced March 2022.
-
Safety in human-multi robot collaborative scenarios: a trajectory scaling approach
Authors:
Martina Lippi,
Alessandro Marino
Abstract:
In this paper, a strategy to handle the human safety in a multi-robot scenario is devised. In the presented framework, it is foreseen that robots are in charge of performing any cooperative manipulation task which is parameterized by a proper task function. The devised architecture answers to the increasing demand of strict cooperation between humans and robots, since it equips a general multi-rob…
▽ More
In this paper, a strategy to handle the human safety in a multi-robot scenario is devised. In the presented framework, it is foreseen that robots are in charge of performing any cooperative manipulation task which is parameterized by a proper task function. The devised architecture answers to the increasing demand of strict cooperation between humans and robots, since it equips a general multi-robot cell with the feature of making robots and human working together. The human safety is properly handled by defining a safety index which depends both on the relative position and velocity of the human operator and robots. Then, the multi-robot task trajectory is properly scaled in order to ensure that the human safety never falls below a given threshold which can be set in worst conditions according to a minimum allowed distance. Simulations results are presented in order to prove the effectiveness of the approach.
△ Less
Submitted 16 July, 2021;
originally announced July 2021.
-
A Data-Driven Approach for Contact Detection, Classification and Reaction in Physical Human-Robot Collaboration
Authors:
Martina Lippi,
Giuseppe Gillini,
Alessandro Marino,
Filippo Arrichiello
Abstract:
This paper considers a scenario where a robot and a human operator share the same workspace, and the robot is able to both carry out autonomous tasks and physically interact with the human in order to achieve common goals. In this context, both intentional and accidental contacts between human and robot might occur due to the complexity of tasks and environment, to the uncertainty of human behavio…
▽ More
This paper considers a scenario where a robot and a human operator share the same workspace, and the robot is able to both carry out autonomous tasks and physically interact with the human in order to achieve common goals. In this context, both intentional and accidental contacts between human and robot might occur due to the complexity of tasks and environment, to the uncertainty of human behavior, and to the typical lack of awareness of each other actions. Here, a two stage strategy based on Recurrent Neural Networks (RNNs) is designed to detect intentional and accidental contacts: the occurrence of a contact with the human is detected at the first stage, while the classification between intentional and accidental is performed at the second stage. An admittance control strategy or an evasive action is then performed by the robot, respectively. The approach also works in the case the robot simultaneously interacts with the human and the environment, where the interaction wrench of the latter is modeled via Gaussian Mixture Models (GMMs). Control Barrier Functions (CBFs) are included, at the control level, to guarantee the satisfaction of robot and task constraints while performing the proper interaction strategy. The approach has been validated on a real setup composed of a Kinova Jaco2 robot.
△ Less
Submitted 12 June, 2021;
originally announced June 2021.
-
A Mixed-Integer Linear Programming Formulation for Human Multi-Robot Task Allocation
Authors:
Martina Lippi,
Alessandro Marino
Abstract:
In this work, we address a task allocation problem for human multi-robot settings. Given a set of tasks to perform, we formulate a general Mixed-Integer Linear Programming (MILP) problem aiming at minimizing the overall execution time while optimizing the quality of the executed tasks as well as human and robotic workload. Different skills of the agents, both human and robotic, are taken into acco…
▽ More
In this work, we address a task allocation problem for human multi-robot settings. Given a set of tasks to perform, we formulate a general Mixed-Integer Linear Programming (MILP) problem aiming at minimizing the overall execution time while optimizing the quality of the executed tasks as well as human and robotic workload. Different skills of the agents, both human and robotic, are taken into account and human operators are enabled to either directly execute tasks or play supervisory roles; moreover, multiple manipulators can tightly collaborate if required to carry out a task. Finally, as realistic in human contexts, human parameters are assumed to vary over time, e.g., due to increasing human level of fatigue. Therefore, online monitoring is required and re-allocation is performed if needed. Simulations in a realistic scenario with two manipulators and a human operator performing an assembly task validate the effectiveness of the approach.
△ Less
Submitted 12 June, 2021;
originally announced June 2021.
-
Königsberg Sightseeing: Eulerian Walks in Temporal Graphs
Authors:
Andrea Marino,
Ana Silva
Abstract:
An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graph $G$ at least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. What if Euler had to take a bus? In a temporal graph $(G,λ)$, with $λ: E(G)\to 2^{[τ]}$, an edge $e\in E(G)$ is available only at the times specified…
▽ More
An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graph $G$ at least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. What if Euler had to take a bus? In a temporal graph $(G,λ)$, with $λ: E(G)\to 2^{[τ]}$, an edge $e\in E(G)$ is available only at the times specified by $λ(e)\subseteq [τ]$, in the same way the connections of the public transportation network of a city or of sightseeing tours are available only at scheduled times. In this scenario, even though several translations of Eulerian trails and walks are possible in temporal terms, only a very particular variation has been exploited in the literature, specifically for infinite dynamic networks (Orlin, 1984). In this paper, we deal with temporal walks, local trails, and trails, respectively referring to edge traversal with no constraints, constrained to not repeating the same edge in a single timestamp, and constrained to never repeating the same edge throughout the entire traversal. We show that, if the edges are always available, then deciding whether $(G,λ)$ has a temporal walk or trail is polynomial, while deciding whether it has a local trail is NP-complete even if it has lifetime~2. In contrast, in the general case, solving any of these problems is NP-complete, even under very strict hypothesis.
△ Less
Submitted 12 March, 2021;
originally announced March 2021.
-
Enabling Visual Action Planning for Object Manipulation through Latent Space Roadmap
Authors:
Martina Lippi,
Petra Poklukar,
Michael C. Welle,
Anastasia Varava,
Hang Yin,
Alessandro Marino,
Danica Kragic
Abstract:
We present a framework for visual action planning of complex manipulation tasks with high-dimensional state spaces, focusing on manipulation of deformable objects. We propose a Latent Space Roadmap (LSR) for task planning which is a graph-based structure globally capturing the system dynamics in a low-dimensional latent space. Our framework consists of three parts: (1) a Mapping Module (MM) that m…
▽ More
We present a framework for visual action planning of complex manipulation tasks with high-dimensional state spaces, focusing on manipulation of deformable objects. We propose a Latent Space Roadmap (LSR) for task planning which is a graph-based structure globally capturing the system dynamics in a low-dimensional latent space. Our framework consists of three parts: (1) a Mapping Module (MM) that maps observations given in the form of images into a structured latent space extracting the respective states as well as generates observations from the latent states, (2) the LSR which builds and connects clusters containing similar states in order to find the latent plans between start and goal states extracted by MM, and (3) the Action Proposal Module that complements the latent plan found by the LSR with the corresponding actions. We present a thorough investigation of our framework on simulated box stacking and rope/box manipulation tasks, and a folding task executed on a real robot.
△ Less
Submitted 30 June, 2022; v1 submitted 3 March, 2021;
originally announced March 2021.
-
Efficient Estimation of Graph Trussness
Authors:
Alessio Conte,
Roberto Grossi,
Andrea Marino,
Luca Versari
Abstract:
A $k$-truss is an edge-induced subgraph $H$ such that each of its edges belongs to at least $k-2$ triangles of $H$. This notion has been introduced around ten years ago in social network analysis and security, as a form of cohesive subgraph that is rich of triangles and less stringent than the clique. The \emph{trussness} of a graph is the maximum $k$ such that a $k$-truss exists.
The problem of…
▽ More
A $k$-truss is an edge-induced subgraph $H$ such that each of its edges belongs to at least $k-2$ triangles of $H$. This notion has been introduced around ten years ago in social network analysis and security, as a form of cohesive subgraph that is rich of triangles and less stringent than the clique. The \emph{trussness} of a graph is the maximum $k$ such that a $k$-truss exists.
The problem of computing $k$-trusses has been largely investigated from the practical and engineering point of view. On the other hand, the theoretical side of the problem has received much less attention, despite presenting interesting challenges. The existing methods share a common design, based on iteratively removing the edge with smallest support, where the support of an edge is the number of triangles containing it.
The aim of this paper is studying algorithmic aspects of graph trussness. While it is possible to show that the time complexity of computing exactly the graph trussness and that of counting/listing all triangles is inherently the same, we provide efficient algorithms for estimating its value, under suitable conditions, with significantly lower complexity than the exact approach. In particular, we provide a $(1 \pm ε)$-approximation algorithm that is asymptotically faster than the exact approach, on graphs which contain $ω(m \, polylog(n))$ triangles, and has the same running time on graphs that do not. For the latter case, we also show that it is impossible to obtain an approximation algorithm with faster running time than the one of the exact approach when the number of triangles is $O(m)$, unless well known conjectures on triangle-freeness and Boolean matrix multiplication are false.
△ Less
Submitted 2 October, 2020;
originally announced October 2020.
-
Weakly-supervised land classification for coastal zone based on deep convolutional neural networks by incorporating dual-polarimetric characteristics into training dataset
Authors:
Sheng Sun,
Armando Marino,
Wenze Shui,
Zhongwen Hu
Abstract:
In this work we explore the performance of DCNNs on semantic segmentation using spaceborne polarimetric synthetic aperture radar (PolSAR) datasets. The semantic segmentation task using PolSAR data can be categorized as weakly supervised learning when the characteristics of SAR data and data annotating procedures are factored in. Datasets are initially analyzed for selecting feasible pre-training i…
▽ More
In this work we explore the performance of DCNNs on semantic segmentation using spaceborne polarimetric synthetic aperture radar (PolSAR) datasets. The semantic segmentation task using PolSAR data can be categorized as weakly supervised learning when the characteristics of SAR data and data annotating procedures are factored in. Datasets are initially analyzed for selecting feasible pre-training images. Then the differences between spaceborne and airborne datasets are examined in terms of spatial resolution and viewing geometry. In this study we used two dual-polarimetric images acquired by TerraSAR-X DLR. A novel method to produce training dataset with more supervised information is developed. Specifically, a series of typical classified images as well as intensity images serve as training datasets. A field survey is conducted for an area of about 20 square kilometers to obtain a ground truth dataset used for accuracy evaluation. Several transfer learning strategies are made for aforementioned training datasets which will be combined in a practicable order. Three DCNN models, including SegNet, U-Net, and LinkNet, are implemented next.
△ Less
Submitted 23 January, 2024; v1 submitted 30 March, 2020;
originally announced March 2020.
-
Latent Space Roadmap for Visual Action Planning of Deformable and Rigid Object Manipulation
Authors:
Martina Lippi,
Petra Poklukar,
Michael C. Welle,
Anastasiia Varava,
Hang Yin,
Alessandro Marino,
Danica Kragic
Abstract:
We present a framework for visual action planning of complex manipulation tasks with high-dimensional state spaces such as manipulation of deformable objects. Planning is performed in a low-dimensional latent state space that embeds images. We define and implement a Latent Space Roadmap (LSR) which is a graph-based structure that globally captures the latent system dynamics. Our framework consists…
▽ More
We present a framework for visual action planning of complex manipulation tasks with high-dimensional state spaces such as manipulation of deformable objects. Planning is performed in a low-dimensional latent state space that embeds images. We define and implement a Latent Space Roadmap (LSR) which is a graph-based structure that globally captures the latent system dynamics. Our framework consists of two main components: a Visual Foresight Module (VFM) that generates a visual plan as a sequence of images, and an Action Proposal Network (APN) that predicts the actions between them. We show the effectiveness of the method on a simulated box stacking task as well as a T-shirt folding task performed with a real robot.
△ Less
Submitted 19 March, 2020;
originally announced March 2020.
-
Edge-Disjoint Branchings in Temporal Graphs
Authors:
Victor Campos,
Raul Lopes,
Andrea Marino,
Ana Silva
Abstract:
A temporal digraph ${\cal G}$ is a triple $(G, γ, λ)$ where $G$ is a digraph, $γ$ is a function on $V(G)$ that tells us the timestamps when a vertex is active, and $λ$ is a function on $E(G)$ that tells for each $uv \in E(G)$ when $u$ and $v$ are linked. Given a static digraph $G$, and a subset $R\subseteq V(G)$, a spanning branching with root $R$ is a subdigraph of $G$ that has exactly one path f…
▽ More
A temporal digraph ${\cal G}$ is a triple $(G, γ, λ)$ where $G$ is a digraph, $γ$ is a function on $V(G)$ that tells us the timestamps when a vertex is active, and $λ$ is a function on $E(G)$ that tells for each $uv \in E(G)$ when $u$ and $v$ are linked. Given a static digraph $G$, and a subset $R\subseteq V(G)$, a spanning branching with root $R$ is a subdigraph of $G$ that has exactly one path from $R$ to each $v\in V(G)$. In this paper, we consider the temporal version of Edmonds' classical result about the problem of finding $k$ edge-disjoint spanning branchings respectively rooted at given $R_1,\cdots,R_k$. We introduce and investigate different definitions of spanning branchings, and of edge-disjointness in the context of temporal graphs. A branching ${\cal B}$ is vertex-spanning if the root is able to reach each vertex $v$ of $G$ at some time where $v$ is active, while it is temporal-spanning if $v$ can be reached from the root at every time where $v$ is active. On the other hand, two branchings ${\cal B}_1$ and ${\cal B}_2$ are edge-disjoint if they do not use the same edge of $G$, and are temporal-edge-disjoint if they can use the same edge of $G$ but at different times. This lead us to four definitions of disjoint spanning branchings and we prove that, unlike the static case, only one of these can be computed in polynomial time, namely the temporal-edge-disjoint temporal-spanning branchings problem, while the other versions are $\mathsf{NP}$-complete, even under very strict assumptions.
△ Less
Submitted 28 February, 2020;
originally announced February 2020.
-
Proximity Search For Maximal Subgraph Enumeration
Authors:
Alessio Conte,
Andrea Marino,
Roberto Grossi,
Takeaki Uno,
Luca Versari
Abstract:
This paper proposes a new general technique for maximal subgraph enumeration which we call proximity search, whose aim is to design efficient enumeration algorithms for problems that could not be solved by existing frameworks. To support this claim and illustrate the technique we include output-polynomial algorithms for several problems for which output-polynomial algorithms were not known, includ…
▽ More
This paper proposes a new general technique for maximal subgraph enumeration which we call proximity search, whose aim is to design efficient enumeration algorithms for problems that could not be solved by existing frameworks. To support this claim and illustrate the technique we include output-polynomial algorithms for several problems for which output-polynomial algorithms were not known, including the enumeration of Maximal Bipartite Subgraphs, Maximal k-Degenerate Subgraphs (for bounded k), Maximal Induced Chordal Subgraphs, and Maximal Induced Trees. Using known techniques, such as reverse search, the space of all maximal solutions induces an implicit directed graph called "solution graph" or "supergraph", and solutions are enumerated by traversing it; however, nodes in this graph can have exponential out-degree, thus requiring exponential time to be spent on each solution. The novelty of proximity search is a formalization that allows us to define a better solution graph, and a technique, which we call canonical reconstruction, by which we can exploit the properties of given problems to build such graphs. This results in solution graphs whose nodes have significantly smaller (i.e., polynomial) out-degree with respect to existing approaches, but that remain strongly connected, so that all solutions can be enumerated in polynomial delay by a traversal. A drawback of this approach is the space required to keep track of visited solutions, which can be exponential: we further propose a technique to induce a parent-child relationship among solutions and achieve polynomial space when suitable conditions are met.
△ Less
Submitted 18 August, 2021; v1 submitted 31 December, 2019;
originally announced December 2019.
-
Automated detection and segmentation of non-mass enhancing breast tumors with dynamic contrast-enhanced magnetic resonance imaging
Authors:
Ignacio Alvarez Illan,
Javier Ramirez,
Juan M. Gorriz,
Maria Adele Marino,
Daly Avendaño,
Thomas Helbich,
Pascal Baltzer,
Katja Pinker,
Anke Meyer-Baese
Abstract:
Non-mass enhancing lesions (NME) constitute a diagnostic challenge in dynamic contrast enhanced magnetic resonance imaging (DCE-MRI) of the breast. Computer Aided Diagnosis (CAD) systems provide physicians with advanced tools for analysis, assessment and evaluation that have a significant impact on the diagnostic performance. Here, we propose a new approach to address the challenge of NME detectio…
▽ More
Non-mass enhancing lesions (NME) constitute a diagnostic challenge in dynamic contrast enhanced magnetic resonance imaging (DCE-MRI) of the breast. Computer Aided Diagnosis (CAD) systems provide physicians with advanced tools for analysis, assessment and evaluation that have a significant impact on the diagnostic performance. Here, we propose a new approach to address the challenge of NME detection and segmentation, taking advantage of independent component analysis (ICA) to extract data-driven dynamic lesion characterizations. A set of independent sources was obtained from DCE-MRI dataset of breast patients, and the dynamic behavior of the different tissues was described by multiple dynamic curves, together with a set of eigenimages describing the scores for each voxel. A new test image is projected onto the independent source space using the unmixing matrix, and each voxel is classified by a support vector machine (SVM) that has already been trained with manually delineated data. A solution to the high false positive rate problem is proposed by controlling the SVM hyperplane location, outperforming previously published approaches.
△ Less
Submitted 26 September, 2018; v1 submitted 12 March, 2018;
originally announced March 2018.
-
Listing Maximal Subgraphs in Strongly Accessible Set Systems
Authors:
Alessio Conte,
Roberto Grossi,
Andrea Marino,
Luca Versari
Abstract:
Algorithms for listing the subgraphs satisfying a given property (e.g.,being a clique, a cut, a cycle, etc.) fall within the general framework of set systems. A set system (U, F) uses a ground set U (e.g., the network nodes) and an indicator F, subset of 2^U, of which subsets of U have the required property. For the problem of listing all sets in F maximal under inclusion, the ambitious goal is to…
▽ More
Algorithms for listing the subgraphs satisfying a given property (e.g.,being a clique, a cut, a cycle, etc.) fall within the general framework of set systems. A set system (U, F) uses a ground set U (e.g., the network nodes) and an indicator F, subset of 2^U, of which subsets of U have the required property. For the problem of listing all sets in F maximal under inclusion, the ambitious goal is to cover a large class of set systems, preserving at the same time the efficiency of the enumeration. Among the existing algorithms, the best-known ones list the maximal subsets in time proportional to their number but may require exponential space. In this paper we improve the state of the art in two directions by introducing an algorithmic framework that, under standard suitable conditions, simultaneously (i) extends the class of problems that can be solved efficiently to strongly accessible set systems, and (ii) reduces the additional space usage from exponential in |U| to stateless, thus accounting for just O(q) space, where q <= |U| is the largest size of a maximal set in F
△ Less
Submitted 9 March, 2018;
originally announced March 2018.
-
Computing top-k Closeness Centrality Faster in Unweighted Graphs
Authors:
Elisabetta Bergamini,
Michele Borassi,
Pierluigi Crescenzi,
Andrea Marino,
Henning Meyerhenke
Abstract:
Given a connected graph $G=(V,E)$, the closeness centrality of a vertex $v$ is defined as $\frac{n-1}{\sum_{w \in V} d(v,w)}$. This measure is widely used in the analysis of real-world complex networks, and the problem of selecting the $k$ most central vertices has been deeply analysed in the last decade. However, this problem is computationally not easy, especially for large networks: in the firs…
▽ More
Given a connected graph $G=(V,E)$, the closeness centrality of a vertex $v$ is defined as $\frac{n-1}{\sum_{w \in V} d(v,w)}$. This measure is widely used in the analysis of real-world complex networks, and the problem of selecting the $k$ most central vertices has been deeply analysed in the last decade. However, this problem is computationally not easy, especially for large networks: in the first part of the paper, we prove that it is not solvable in time $Ø(|E|^{2-ε})$ on directed graphs, for any constant $ε>0$, under reasonable complexity assumptions. Furthermore, we propose a new algorithm for selecting the $k$ most central nodes in a graph: we experimentally show that this algorithm improves significantly both the textbook algorithm, which is based on computing the distance between all pairs of vertices, and the state of the art. For example, we are able to compute the top $k$ nodes in few dozens of seconds in real-world networks with millions of nodes and edges. Finally, as a case study, we compute the $10$ most central actors in the IMDB collaboration network, where two actors are linked if they played together in a movie, and in the Wikipedia citation network, which contains a directed edge from a page $p$ to a page $q$ if $p$ contains a link to $q$.
△ Less
Submitted 27 April, 2017; v1 submitted 4 April, 2017;
originally announced April 2017.
-
BUbiNG: Massive Crawling for the Masses
Authors:
Paolo Boldi,
Andrea Marino,
Massimo Santini,
Sebastiano Vigna
Abstract:
Although web crawlers have been around for twenty years by now, there is virtually no freely available, opensource crawling software that guarantees high throughput, overcomes the limits of single-machine systems and at the same time scales linearly with the amount of resources available. This paper aims at filling this gap, through the description of BUbiNG, our next-generation web crawler built…
▽ More
Although web crawlers have been around for twenty years by now, there is virtually no freely available, opensource crawling software that guarantees high throughput, overcomes the limits of single-machine systems and at the same time scales linearly with the amount of resources available. This paper aims at filling this gap, through the description of BUbiNG, our next-generation web crawler built upon the authors' experience with UbiCrawler [Boldi et al. 2004] and on the last ten years of research on the topic. BUbiNG is an opensource Java fully distributed crawler; a single BUbiNG agent, using sizeable hardware, can crawl several thousands pages per second respecting strict politeness constraints, both host- and IP-based. Unlike existing open-source distributed crawlers that rely on batch techniques (like MapReduce), BUbiNG job distribution is based on modern high-speed protocols so to achieve very high throughput.
△ Less
Submitted 26 January, 2016;
originally announced January 2016.
-
Fast and Simple Computation of Top-k Closeness Centralities
Authors:
Michele Borassi,
Pierluigi Crescenzi,
Andrea Marino
Abstract:
Closeness is an important centrality measure widely used in the analysis of real-world complex networks. In particular, the problem of selecting the k most central nodes with respect to this measure has been deeply analyzed in the last decade. However, even for not very large networks, this problem is computationally intractable in practice: indeed, Abboud et al have recently shown that its comple…
▽ More
Closeness is an important centrality measure widely used in the analysis of real-world complex networks. In particular, the problem of selecting the k most central nodes with respect to this measure has been deeply analyzed in the last decade. However, even for not very large networks, this problem is computationally intractable in practice: indeed, Abboud et al have recently shown that its complexity is strictly related to the complexity of the All-Pairs Shortest Path (in short, APSP) problem, for which no subcubic "combinatorial" algorithm is known. In this paper, we propose a new algorithm for selecting the k most closeness central nodes in a graph. In practice, this algorithm significantly improves over the APSP approach, even though its worst-case time complexity is the same. For example, the algorithm is able to compute the top k nodes in few dozens of seconds even when applied to real-world networks with millions of nodes and edges. We will also experimentally prove that our algorithm drastically outperforms the most recently designed algorithm, proposed by Olsen et al. Finally, we apply the new algorithm to the computation of the most central actors in the IMDB collaboration network, where two actors are linked if they played together in a movie.
△ Less
Submitted 6 July, 2015;
originally announced July 2015.
-
Enumerating Cyclic Orientations of a Graph
Authors:
Alessio Conte,
Roberto Grossi,
Andrea Marino,
Romeo Rizzi
Abstract:
Acyclic and cyclic orientations of an undirected graph have been widely studied for their importance: an orientation is acyclic if it assigns a direction to each edge so as to obtain a directed acyclic graph (DAG) with the same vertex set; it is cyclic otherwise. As far as we know, only the enumeration of acyclic orientations has been addressed in the literature. In this paper, we pose the problem…
▽ More
Acyclic and cyclic orientations of an undirected graph have been widely studied for their importance: an orientation is acyclic if it assigns a direction to each edge so as to obtain a directed acyclic graph (DAG) with the same vertex set; it is cyclic otherwise. As far as we know, only the enumeration of acyclic orientations has been addressed in the literature. In this paper, we pose the problem of efficiently enumerating all the \emph{cyclic} orientations of an undirected connected graph with $n$ vertices and $m$ edges, observing that it cannot be solved using algorithmic techniques previously employed for enumerating acyclic orientations.We show that the problem is of independent interest from both combinatorial and algorithmic points of view, and that each cyclic orientation can be listed with $\tilde{O}(m)$ delay time. Space usage is $O(m)$ with an additional setup cost of $O(n^2)$ time before the enumeration begins, or $O(mn)$ with a setup cost of $\tilde{O}(m)$ time.
△ Less
Submitted 19 June, 2015;
originally announced June 2015.
-
Entity-Linking via Graph-Distance Minimization
Authors:
Roi Blanco,
Paolo Boldi,
Andrea Marino
Abstract:
Entity-linking is a natural-language-processing task that consists in identifying the entities mentioned in a piece of text, linking each to an appropriate item in some knowledge base; when the knowledge base is Wikipedia, the problem comes to be known as wikification (in this case, items are wikipedia articles). One instance of entity-linking can be formalized as an optimization problem on the un…
▽ More
Entity-linking is a natural-language-processing task that consists in identifying the entities mentioned in a piece of text, linking each to an appropriate item in some knowledge base; when the knowledge base is Wikipedia, the problem comes to be known as wikification (in this case, items are wikipedia articles). One instance of entity-linking can be formalized as an optimization problem on the underlying concept graph, where the quantity to be optimized is the average distance between chosen items. Inspired by this application, we define a new graph problem which is a natural variant of the Maximum Capacity Representative Set. We prove that our problem is NP-hard for general graphs; nonetheless, under some restrictive assumptions, it turns out to be solvable in linear time. For the general case, we propose two heuristics: one tries to enforce the above assumptions and another one is based on the notion of hitting distance; we show experimentally how these approaches perform with respect to some baselines on a real-world dataset.
△ Less
Submitted 29 July, 2014;
originally announced July 2014.
-
Synchronous Context-Free Grammars and Optimal Linear Parsing Strategies
Authors:
Pierluigi Crescenzi,
Daniel Gildea,
Andrea Marino,
Gianluca Rossi,
Giorgio Satta
Abstract:
Synchronous Context-Free Grammars (SCFGs), also known as syntax-directed translation schemata, are unlike context-free grammars in that they do not have a binary normal form. In general, parsing with SCFGs takes space and time polynomial in the length of the input strings, but with the degree of the polynomial depending on the permutations of the SCFG rules. We consider linear parsing strategies,…
▽ More
Synchronous Context-Free Grammars (SCFGs), also known as syntax-directed translation schemata, are unlike context-free grammars in that they do not have a binary normal form. In general, parsing with SCFGs takes space and time polynomial in the length of the input strings, but with the degree of the polynomial depending on the permutations of the SCFG rules. We consider linear parsing strategies, which add one nonterminal at a time. We show that for a given input permutation, the problems of finding the linear parsing strategy with the minimum space and time complexity are both NP-hard.
△ Less
Submitted 25 November, 2013;
originally announced November 2013.
-
Optimal Listing of Cycles and st-Paths in Undirected Graphs
Authors:
Rui Ferreira,
Roberto Grossi,
Andrea Marino,
Nadia Pisanti,
Romeo Rizzi,
Gustavo Sacomoto
Abstract:
We present the first optimal algorithm for the classical problem of listing all the cycles in an undirected graph. We exploit their properties so that the total cost is the time taken to read the input graph plus the time to list the output, namely, the edges in each of the cycles. The algorithm uses a reduction to the problem of listing all the paths from a vertex s to a vertex t which we also so…
▽ More
We present the first optimal algorithm for the classical problem of listing all the cycles in an undirected graph. We exploit their properties so that the total cost is the time taken to read the input graph plus the time to list the output, namely, the edges in each of the cycles. The algorithm uses a reduction to the problem of listing all the paths from a vertex s to a vertex t which we also solve optimally.
△ Less
Submitted 5 July, 2012; v1 submitted 12 May, 2012;
originally announced May 2012.
