Let G be a complete edge-weighted graph on n vertices. To each subset of vertices of G assign the cost of the minimum spanning tree of the subset as its weight. Suppose that n is a multiple of some fixed positive integer k . The k -matching problem is the problem of finding a partition of the vertices of G into k -sets (sets of k elements), that minimizes the sum of the weights of the k -sets. The case of k = 3 has been shown to be NP-hard [Johnsson et al., 1998]. In the Euclidean version, the vertices of G are points in the plane and the weight of an edge is the Euclidean distance between its endpoints. We call this problem the Euclidean k -matching problem. We show that, for every fixed k ≥ 3 , the Euclidean k -matching problem is NP-hard. This resolves an open problem in the literature and provides the first theoretical justification for the use of known heuristic methods in the case of k = 3 . We also show that the problem remains NP-hard if the trees are required to be paths.

A tethered marsupial robotics system comprises three components: an Unmanned Ground Vehicle (UGV), an Unmanned Aerial Vehicle (UAV), and a tether connecting both robots. Marsupial systems are highly beneficial in industry as they extend the UAV's battery life during flight. This paper introduces a novel strategy for a specific path planning problem in marsupial systems, where each of the three components must avoid collisions with ground and aerial obstacles modeled as 3D cuboids. Given an initial configuration in which the UAV is positioned atop the UGV, the goal is to reach an aerial target with the UAV. We assume that the UGV first moves to a position from which the UAV can take off and fly through a vertical plane to reach an aerial target. We propose an approach that discretizes the space to approximate an optimal solution, minimizing the sum of the lengths of the ground and air paths. First, we assume a taut tether and use a novel algorithm that leverages the convexity of the tether and the geometry of obstacles to efficiently determine the locus of feasible take-off points for the UAV. We then apply this result to scenarios that involve loose tethers. The simulation test results show that our approach can solve complex situations in seconds, outperforming a baseline planning algorithm based on RRT* (Rapidly exploring Random Trees).

Automatic inspection of parabolic-trough solar plants is key to preventing failures that can harm the environment and the production of green energy. In this work, we propose a novel methodology to inspect ball joints in parabolic trough collectors, which is a relevant problem that is not adequately covered in the literature. Images collected by an Unmanned Aerial Vehicle are segmented using deep learning to extract ball joint components. In order to generate rich training datasets, we develop a novel data augmentation technique by rotating joints and adding synthetic image background, and demonstrate its impact on the object detection accuracy. Then two types of faults are analyzed: fluid leaks, by means of image color filtering; and geometric shape anomalies, by measuring joint angles of the robotic arms. We propose metrics to quantify these faults and evaluate the damage of the inspected components. Our experimental results with images from operating commercial plants show that we can automatically detect leaks and anomalous angular geometry with a low failure rate compared to human labeling.

This paper proposes a planning algorithm for autonomous media production with multiple Unmanned Aerial Vehicles (UAVs) in outdoor events. Given filming tasks specified by a media Director, we formulate an optimization problem to maximize the filming time considering battery constraints. As we conjecture that the problem is NP-hard, we consider a discretization version, and propose a graph-based algorithm that can find an optimal solution of the discrete problem for a single UAV in polynomial time. Then, a greedy strategy is applied to solve the problem sequentially for multiple UAVs. We demonstrate that our algorithm is efficient for small teams (3-5 UAVs) and that its performance is close to the optimum. We showcase our system in field experiments carrying out actual media production in an outdoor scenario with multiple UAVs.

In music, repetition is a fundamental concept to establish structure and create temporal relationships. Previous approaches to detecting repetition in music recordings have mainly focused on discovering repeated patterns of variable length and instrumentation at arbitrary locations. In this paper, we present a novel method for the discovery of repeated sung phrases in folk music recordings and, in particular, in oral music traditions, where written scores are usually unavailable. At a first stage, a segmentation algorithm partitions automatically generated note-level transcriptions of the singing melody into sections that correspond to the structural unit of a phrase. A clustering algorithm is then used to form clusters of phrases, where each cluster contains instances of the same melodic content. The clustering algorithm operates on the basis of a distance measure between melodic sequences and, to this end, various melodic distance measures are investigated. A detailed evaluation procedure is used to assess the performance of the algorithm on three different European music traditions and the influence of transcription and segmentation errors is investigated. The proposed system is shown to outperform the state-of-the-art in audio-based approaches to repeated phrase discovery for this task.

This paper addresses a synchronization problem that arises when a team of robots needs to communicate while repeatedly performing assigned tasks in a cooperative scenario. Each robot has a limited communication range and moves along a previously defined closed trajectory. When two robots are close enough, a communication link may be established, allowing the robots to exchange information. The goal is to schedule the motions such that the entire system can be synchronized for maximum information exchange; that is, every pair of neighbors always visit the feasible communication link at the same time. An algorithm for scheduling the team of robots in this scenario is proposed and a robust framework that assures the synchronization of a large team of robots is presented. Simulations, experiments, and computational results demonstrate the applicability of the algorithm. The approach allows the design of fault-tolerant systems that can be used for multiple tasks, such as surveillance, area exploration, and searching for targets in hazardous environments, among others.

This paper addresses a synchronization problem that arises when a team of aerial robots (ARs) need to communicate while performing assigned tasks in a cooperative scenario. Each robot has a limited communication range and flies within a previously assigned closed path. When two robots are close enough, a communication link may be established allowing the robots to share information. The goal is to schedule the flights such that the entire system can be synchronized for maximum information exchange, that is, every pair of neighbors are on the feasible communication link at the same time. We propose an algorithm for scheduling a team of robots in this scenario and propose a robust framework where the synchronization of a large team of robots is assured. The approach allows us to design a fault-tolerant system that can be used for multiple tasks such as surveillance, area exploration, searching for targets in a hazardous environment, and assembly and structure construction, to name a few.

Consider a set of receptors belonging to two competitive telecommunication firms, the blue firm and the red firm. The receptors are represented as points in the plane, b are blue and belong to the blue firm and r are red and belong to the red firm. The blue firm has an emitting device represented as a point that moves along a path sending information to blue receptors as follows: At any time, the device sends information to all blue receptors covered by the largest disk centered at it and contains no red receptor. In this scenario, we study two optimization problems. The first problem is to compute a path, P, such that the number of blue receptors served by a moving device is maximized. In particular, we give efficient algorithms when P is a straight line, an anchored half-line and an axis-parallel double ray. As a second task, we study the problem of removing the minimum number of red receptors in such a way that there exists a straight line path P so that if the device moves along P all blue receptors are served. We prove geometrical properties of an optimal straight line and propose efficient algorithms depending on the degrees of freedom of the line.

In this paper we consider some problems that belong to the interplay between the field of Facility Location and the area of Computational Geometry. Specifically, given a set S of points in the plane, we discuss several variations of the problem of finding monotone 1-corner polygonal chains that minimize the maximum vertical distance to S.