We consider multi-robot service scenarios, where tasks appear at any time and in any location of the working area. A solution to such a service task problem requires finding a suitable task assignment and a collision-free trajectory for each robot of a multi-robot team. In cluttered environments, such as indoor spaces with hallways, those two problems are tightly coupled. We propose a decentralized algorithm for simultaneously solving both problems, called Hierarchical Task Assignment and Path Finding (HTAPF). HTAPF extends a previous bio-inspired Multi-Robot Task Allocation (MRTA) framework [1]. In this work, task allocation is performed on an arbitrarily deep hierarchy of work areas and is tightly coupled with a fully distributed version of the priority-based planning paradigm [12], using only broadcast communication. Specifically, priorities are assigned implicitly by the order in which data is received from nearby robots. No token passing procedure or specific schedule is in place ensuring robust execution also in the presence of limited probabilistic communication and robot failures.
more »
« less
Efficient Algorithms for Optimal Perimeter Guarding
We investigate the problem of optimally assigning a
large number of robots (or other types of autonomous agents) to
guard the perimeters of closed 2D regions, where the perimeter of
each region to be guarded may contain multiple disjoint polygonal
chains. Each robot is responsible for guarding a subset of a
perimeter and any point on a perimeter must be guarded by
some robot. In allocating the robots, the main objective is to
minimize the maximum 1D distance to be covered by any robot
along the boundary of the regions. For this optimization problem
which we call optimal perimeter guarding (OPG), thorough
structural analysis is performed, which is then exploited to develop
fast exact algorithms that run in guaranteed low polynomial
time. In addition to formal analysis and proofs, experimental
evaluations and simulations are performed that further validate
the correctness and effectiveness of our algorithmic results.
more »
« less
- NSF-PAR ID:
- 10111592
- Date Published:
- Journal Name:
- Robotics: science and systems
- ISSN:
- 2330-7668
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract In this paper, we present a decentralized approach based on a simple set of rules to schedule multi-robot cooperative additive manufacturing (AM). The results obtained using the decentralized approach are compared with those obtained from an optimization-based method, representing the class of centralized approaches for manufacturing scheduling. Two simulated case studies are conducted to evaluate the performance of both approaches in total makespan. In the first case, four rectangular bars of different dimensions from small to large are printed. Each bar is first divided into small subtasks (called chunks), and four robots are then assigned to cooperatively print the resulting chunks. The second case study focuses on testing geometric complexity, where four robots are used to print a mask stencil (an inverse stencil, not face covering). The result shows that the centralized approach provides a better solution (shorter makespan) compared to the decentralized approach for small-scale problems (i.e., a few robots and chunks). However, the gap between the solutions shrinks while the scale increases, and the decentralized approach outperforms the centralized approach for large-scale problems. Additionally, the runtime for the centralized approach increased by 39-fold for the extra-large problem (600 chunks and four robots) compared to the small-scale problem (20 chunks and four robots). In contrast, the runtime for the decentralized approach was not affected by the scale of the problem. Finally, a Monte-Carlo analysis was performed to evaluate the robustness of the centralized approach against uncertainties in AM. The result shows that the variations in the printing time of different robots can lead to a significant discrepancy between the generated plan and the actual implementation, thereby causing collisions between robots that should have not happened if there were no uncertainties. On the other hand, the decentralized approach is more robust because a collision-free schedule is generated in real-time.more » « less
-
Goaoc, Xavier ; Kerber, Michael (Ed.)We consider the following surveillance problem: Given a set P of n sites in a metric space and a set R of k robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency L of a schedule is the maximum latency of any site, where the latency of a site s is the supremum of the lengths of the time intervals between consecutive visits to s. When k = 1 the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. For k ≥ 2 (which is the version we are interested in) the problem becomes even more challenging; for example, it is not even clear if the decision version of the problem is decidable, in particular in the Euclidean case. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into 𝓁 groups, for some 𝓁 ≤ k, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a 1+ε factor loss in the approximation factor and an O((k/ε) ^k) factor loss in the runtime, for any ε > 0. Our second main result shows that an optimal cyclic solution is a 2(1-1/k)-approximation of the overall optimal solution. Note that for k = 2 this implies that an optimal cyclic solution is optimal overall. We conjecture that this is true for k ≥ 3 as well. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a (2(1-1/k)+ε)-approximation of the optimal unrestricted (not necessarily cyclic) solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting. Similar results can be obtained by combining our results with other known TSP algorithms in non-Euclidean metrics.more » « less
-
We introduce and study a new search-type problem with ( 𝑛+1 )-robots on a disk. The searchers (robots) all start from the center of the disk, have unit speed, and can communicate wirelessly. The goal is for a distinguished robot (the queen) to reach and evacuate from an exit that is hidden on the perimeter of the disk in as little time as possible. The remaining n robots (servants) are there to facilitate the queen’s objective and are not required to reach the hidden exit. We provide upper and lower bounds for the time required to evacuate the queen. Namely, we propose an algorithm specifying the trajectories of the robots which guarantees evacuation of the queen in time always better than 2+4(\sqrt{2}-1)\pi/n for 𝑛≥4 servants. We also demonstrate that for 𝑛≥4 servants the queen cannot be evacuated in time less than 2 + \pi/n + 2/n^2.more » « less
-
This paper addresses the complete area coverage problem of a known environment by multiple-robots. Complete area coverage is the problem of moving an end-effector over all available space while avoiding existing obstacles. In such tasks, using multiple robots can increase the efficiency of the area coverage in terms of minimizing the operational time and increase the robustness in the face of robot attrition. Unfortunately, the problem of finding an optimal solution for such an area coverage problem with multiple robots is known to be NP-complete. In this paper we present two approximation heuristics for solving the multi-robot coverage problem. The first solution presented is a direct extension of an efficient single robot area coverage algorithm, based on an exact cellular decomposition. The second algorithm is a greedy approach that divides the area into equal regions and applies an efficient single-robot coverage algorithm to each region. We present experimental results for two algorithms. Results indicate that our approaches provide good coverage distribution between robots and minimize the workload per robot, meanwhile ensuring complete coverage of the area.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.15607/RSS.2019.XV.002
