Abstract Given a finite set of weighted points in $${\mathbb {R}}^d$$ R d (where there can be negative weights), the maximum box problem asks for an axis-aligned rectangle (i.e., box) such that the sum of the weights of the points that it contains is maximized. We consider that each point of the input has a probability of being present in the final random point set, and these events are mutually independent; then, the total weight of a maximum box is a random variable. We aim to compute both the probability that this variable is at least a given parameter, and its expectation. We show that even in $$d=1$$ d = 1 these computations are #P-hard, and give pseudo-polynomial time algorithms in the case where the weights are integers in a bounded interval. For $$d=2$$ d = 2 , we consider that each point is colored red or blue, where red points have weight $$+1$$ + 1 and blue points weight $$-\infty $$ - ∞ . The random variable is the maximum number of red points that can be covered with a box not containing any blue point. We prove that the above two computations are also #P-hard, and give a polynomial-time algorithm for computing the probability that there is a box containing exactly two red points, no blue point, and a given point of the plane.

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.

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.