Assignment Algorithms for Variable Robot Formations
- First Online: 07 May 2020
Cite this chapter
- Srinivas Akella 14
Part of the book series: Springer Proceedings in Advanced Robotics ((SPAR,volume 13))
1545 Accesses
1 Citations
This paper describes algorithms to perform optimal assignment of teams of robots translating in the plane from an initial formation to a variable goal formation. We consider the case when each robot is to be assigned a goal position, the individual robots are interchangeable, and the goal formation can be scaled or translated.We compute the costs for all candidate pairs of initial, goal robot assignments as functions of the parameters of the goal formation, and partition the parameter space into equivalence classes invariant to the cost order using computational geometry techniques. We compute a minimum completion time assignment for an equivalence class by formulating it as a linear bottleneck assignment problem (LBAP). To improve efficiency, we solve the LBAP problem for each equivalence class by incrementally updating the solution as the formation parameters are varied. This work is motivated by applications that include the motion of droplet formations in digital microfluidic lab-on-a-chip devices, and of robot and drone formations in the plane.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Subscribe and save.
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
- Available as PDF
- Read on any device
- Instant download
- Own it forever
- Compact, lightweight edition
- Dispatched in 3 to 5 business days
- Free shipping worldwide - see info
- Durable hardcover edition
Tax calculation will be finalised at checkout
Purchases are for personal use only
Institutional subscriptions
Unable to display preview. Download preview PDF.
Similar content being viewed by others
The Max-Line-Formation Problem
An Effective Algorithmic Framework for Near Optimal Multi-robot Path Planning
Trajectory Planning and Assignment in Multirobot Systems
Adler, A., de Berg, M., Halperin, D., Solovey, K.: Efficient multi-robot motion planning for unlabeled discs in simple polygons. In: 11th International Workshop on the Algorithmic Foundations of Robotics (WAFR) (2014)
Google Scholar
Akella, S., Hutchinson, S.: Coordinating the motions of multiple robots with specified trajectories. In: IEEE International Conference on Robotics and Automation. pp. 624–631. Washington, DC (May 2002)
Alonso-Mora, J., Baker, S., Rus, D.: Multi-robot navigation in formation via sequential convex programming. In: 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 4634–4641 (2015)
van den Berg, J., Guy, S.J., Lin, M., Manocha, D.: Reciprocal n-body collision avoidance. In: Pradalier, C., Siegwart, R., Hirzinger, G. (eds.) Robotics Research: The 14th International Symposium ISRR, pp. 3–19. Springer, Berlin, Heidelberg (2011)
van den Berg, J., Snoeyink, J., Lin, M., Manocha, D.: Centralized path planning for multiple robots: Optimal decoupling into sequential plans. In: Robotics: Science and Systems. pp. 137–144 (2010)
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer-Verlag, Berlin, third edn. (2008)
Burkard, R., Dell’Amico, M., Martello, S.: Assignment Problems. SIAM, revised reprint edn. (2012)
Choset, H., Lynch, K.M., Hutchinson, S., Kantor, G.A., Burgard, W., Kavraki, L.E., Thrun, S.: Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press (2005)
Derenick, J.C., Spletzer, J.R.: Convex optimization strategies for coordinating large-scale robot formations. IEEE Transactions on Robotics 23(6), 1252–1259 (2007)
Halperin, D.: Personal communication (2016)
Halperin, D., Sharir, M.: Arrangements. In: Goodman, J.E., O’Rourke, J., Tóth, C.D. (eds.) Handbook of Discrete and Computational Geometry. CRC Press, Boca Raton, FL, third edn. (2017), to appear
Katsev, M., Yu, J., LaValle, S.M.: Efficient formation path planning on large graphs. In: 2013 IEEE International Conference on Robotics and Automation (ICRA) (2013)
Kloder, S., Hutchinson, S.: Path planning for permutation-invariant multirobot formations. IEEE Transactions on Robotics 22(4), 650–665 (2006)
Latombe, J.C.: Robot Motion Planning. Kluwer Academic Publishers, Norwell, MA (1991)
LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge, U.K. (2006), available at http://planning.cs.uiuc.edu/
LaValle, S.M., Hutchinson, S.A.: Optimal motion planning for multiple robots having independent goals. IEEE Transactions on Robotics and Automation 14(6), 912–925 (Dec 1998)
Liu, L., Shell, D.: Large-scale multi-robot task allocation via dynamic partitioning and distribution. Autonomous Robots 33(3), 291–307 (2012)
Luna, R., Bekris, K.E.: Efficient and complete centralized multi-robot path planning. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-11). San Francisco, CA (25-30 Sept 2011)
Ma, Z., Akella, S.: Coordination of droplets on light-actuated digital microfluidic systems. In: IEEE International Conference on Robotics and Automation. pp. 2510–2516. St. Paul, MN (May 2012)
Nam, C., Shell, D.A.: When to do your own thing: Analysis of cost uncertainties in multi-robot task allocation at run-time. In: 2015 IEEE International Conference on Robotics and Automation (ICRA). Seattle, Washington (May 2015)
Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, New Jersey (1982)
Park, S.Y., Teitell, M.A., Chiou, E.P.Y.: Single-sided continuous optoelectrowetting (SCOEW) for droplet manipulation with light patterns. Lab Chip 10, 1655–1661 (2010), https://doi.org/10.1039/C001324B
Pei, S.N., Valley, J.K., Neale, S.L., Jamshidi, A., Hsu, H., Wu, M.C.: Lightactuated digital microfluidics for large-scale, parallel manipulation of arbitrarily sized droplets. In: 23rd IEEE International Conference on Micro Electro Mechanical Systems. pp. 252–255. Wanchai, Hong Kong (Jan 2010)
Peng, J., Akella, S.: Coordinating multiple robots with kinodynamic constraints along specified paths. International Journal of Robotics Research 24(4), 295–310 (Apr 2005)
Shekar, V., Campbell, M., Akella, S.: Towards automated optoelectrowetting on dielectric devices for multi-axis droplet manipulation. In: IEEE International Conference on Robotics and Automation. pp. 1431–1437. Karlsruhe, Germany (May 2013)
Simeon, T., Leroy, S., Laumond, J.P.: Path coordination for multiple mobile robots: A resolution-complete algorithm. IEEE Transactions on Robotics and Automation 18(1), 42–49 (Feb 2002)
Solovey, K., Halperin, D.: k-color multi-robot motion planning. International Journal of Robotics Research 33(1), 82–97 (2014)
Solovey, K., Halperin, D.: On the hardness of unlabeled multi-robot motion planning. In: Robotics: Science and Systems. Rome, Italy (Jul 2015)
Solovey, K., Yu, J., Zamir, O., Halperin, D.: Motion planning for unlabeled discs with optimality guarantees. In: Robotics: Science and Systems. Rome, Italy (Jul 2015)
Turpin, M., Michael, N., Kumar, V.: CAPT: Concurrent assignment and planning of trajectories for multiple robots. The International Journal of Robotics Research 33(1), 98–112 (2014)
Turpin, M., Mohta, K., Michael, N., Kumar, V.: Goal assignment and trajectory planning for large teams of interchangeable robots. Autonomous Robots 37(4), 401–415 (Dec 2014)
Wagner, G., Choset, H.: Subdimensional expansion for multirobot path planning. Artificial Intelligence 219, 1–24 (Feb 2015)
Wurman, P., D’Andrea, R., Mountz, M.: Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Magazine 29(1), 9–19 (2008)
Yu, J., LaValle, S.M.: Multi-agent path planning and network flow. In: Frazzoli, E., Lozano-Perez, T., Roy, N., Rus, D. (eds.) Algorithmic Foundations of Robotics X, Springer Tracts in Advanced Robotics, vol. 86, pp. 157–173. Springer Berlin Heidelberg (2013)
Yu, J., LaValle, S.M.: Planning optimal paths for multiple robots on graphs. In: 2013 IEEE International Conference on Robotics and Automation (ICRA) (2013)
Download references
Author information
Authors and affiliations.
Department of Computer Science, University of North Carolina at Charlotte, Charlotte, NC, 28223, USA
Srinivas Akella
You can also search for this author in PubMed Google Scholar
Corresponding author
Correspondence to Srinivas Akella .
Editor information
Editors and affiliations.
Industrial Engineering and Operations Research, University of California, Berkeley, CA, USA
Ken Goldberg
Electrical Engineering and Computer Sciences, University of California, Berkeley, CA, USA
Pieter Abbeel
Rutgers University, Piscataway, NJ, USA
Kostas Bekris
University of California, Berkeley, CA, USA
Lauren Miller
Rights and permissions
Reprints and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Akella, S. (2020). Assignment Algorithms for Variable Robot Formations. In: Goldberg, K., Abbeel, P., Bekris, K., Miller, L. (eds) Algorithmic Foundations of Robotics XII. Springer Proceedings in Advanced Robotics, vol 13. Springer, Cham. https://doi.org/10.1007/978-3-030-43089-4_58
Download citation
DOI : https://doi.org/10.1007/978-3-030-43089-4_58
Published : 07 May 2020
Publisher Name : Springer, Cham
Print ISBN : 978-3-030-43088-7
Online ISBN : 978-3-030-43089-4
eBook Packages : Intelligent Technologies and Robotics Intelligent Technologies and Robotics (R0)
Share this chapter
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Publish with us
Policies and ethics
- Find a journal
- Track your research
Distributed Algorithm Design for Constrained Multi-robot Task Assignment
The task assignment problem is one of the fundamental combinatorial optimization problems. It has been extensively studied in operation research, management science, computer science and robotics. Task assignment problems arise in various applications of multi-robot systems (MRS), such as environmental monitoring, disaster response, extraterrestrial exploration, sensing data collection and collaborative autonomous manufacturing. In these MRS applications, there are realistic constraints on robots and tasks that must be taken into account both from the modeling perspective and the algorithmic perspective. From the modeling aspect, such constraints include (a) Task group constraints: where tasks form disjoint groups and each robot can be assigned to at most one task in each group. One example of the group constraints comes from tightly-coupled tasks, where multiple micro tasks form one tightly-coupled macro task and need multiple robots to perform each simultaneously. (b) Task deadline constraints: where tasks must be assigned to meet their deadlines. (c) Dynamically-arising tasks: where tasks arrive dynamically and the payoffs of future tasks are unknown. Such tasks arise in scenarios like searchrescue, where new victims are found dynamically. (d) Robot budget constraints: where the number of tasks each robot can perform is bounded according to the resource it possesses (e.g., energy). From the solution aspect, there is often a need for decentralized solution that are implemented on individual robots, especially when no powerful centralized controller exists or when the system needs to avoid single-point failure or be adaptive to environmental changes. Most existing algorithms either do not consider the above constraints in problem modeling, are centralized or do not provide formal performance guarantees. In this thesis, I propose methods to address these issues for two classes of problems, namely, the constrained linear assignment problem and constrained generalized assignment problem. Constrained linear assignment problem belongs to P, while constrained generalized assignment problem is NP-hard. I develop decomposition-based distributed auction algorithms with performance guarantees for both problem classes. The multi-robot assignment problem is decomposed into an optimization problem for each robot and each robot iteratively solving its own optimization problem leads to a provably good solution to the overall problem. For constrained linear assignment problem, my approaches provides an almost optimal solution. For constrained generalized assignment problem, I present a distributed algorithm that provides a solution within a constant factor of the optimal solution. I also study the online version of the task allocation problem with task group constraints. For the online problem, I prove that a repeated greedy version of my algorithm gives solution with constant factor competitive ratio. I include simulation results to evaluate the average-case performance of the proposed algorithms. I also include results on multi-robot cooperative package transport to illustrate the approach.
Degree Type
- Dissertation
- Robotics Institute
Degree Name
- Doctor of Philosophy (PhD)
Usage metrics
- Adaptive Agents and Intelligent Robotics
Help | Advanced Search
Computer Science > Multiagent Systems
Title: a conflict-aware optimal goal assignment algorithm for multi-robot systems.
Abstract: The fundamental goal assignment problem for a multi-robot application aims to assign a unique goal to each robot while ensuring collision-free paths, minimizing the total movement cost. A plausible algorithmic solution to this NP-hard problem involves an iterative process that integrates a task planner to compute the goal assignment while ignoring the collision possibilities among the robots and a multi-agent path-finding algorithm to find the collision-free trajectories for a given assignment. This procedure involves a method for computing the next best assignment given the current best assignment. A naive way of computing the next best assignment, as done in the state-of-the-art solutions, becomes a roadblock to achieving scalability in solving the overall problem. To obviate this bottleneck, we propose an efficient conflict-guided method to compute the next best assignment. Additionally, we introduce two more optimizations to the algorithm -- first for avoiding the unconstrained path computations between robot-goal pairs wherever possible, and the second to prevent duplicate constrained path computations for multiple robot-goal pairs. We extensively evaluate our algorithm for up to a hundred robots on several benchmark workspaces. The results demonstrate that the proposed algorithm achieves nearly an order of magnitude speedup over the state-of-the-art algorithm, showcasing its efficacy in real-world scenarios.
| Subjects: | Multiagent Systems (cs.MA); Artificial Intelligence (cs.AI); Robotics (cs.RO) |
| Cite as: | [cs.MA] |
| (or [cs.MA] for this version) | |
| Focus to learn more arXiv-issued DOI via DataCite |
Submission history
Access paper:.
- HTML (experimental)
- Other Formats
References & Citations
- Google Scholar
- Semantic Scholar
BibTeX formatted citation
Bibliographic and Citation Tools
Code, data and media associated with this article, recommenders and search tools.
- Institution
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .
IEEE Account
- Change Username/Password
- Update Address
Purchase Details
- Payment Options
- Order History
- View Purchased Documents
Profile Information
- Communications Preferences
- Profession and Education
- Technical Interests
- US & Canada: +1 800 678 4333
- Worldwide: +1 732 981 0060
- Contact & Support
- About IEEE Xplore
- Accessibility
- Terms of Use
- Nondiscrimination Policy
- Privacy & Opting Out of Cookies
A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.
Solving the Restricted Assignment Problem to Schedule Multi-get Requests in Key-Value Stores
New citation alert added.
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
New Citation Alert!
Please log in to your account
Information & Contributors
Bibliometrics & citations, view options, index terms.
Information systems
Data management systems
Database management system engines
Parallel and distributed DBMSs
Theory of computation
Design and analysis of algorithms
Approximation algorithms analysis
Online algorithms
Online learning algorithms
Theory and algorithms for application domains
Recommendations
An efficient memory-mapped key-value store for flash storage.
Persistent key-value stores have emerged as a main component in the data access path of modern data processing systems. However, they exhibit high CPU and I/O overhead. Today, due to power limitations it is important to reduce CPU overheads for data ...
Hector: A Framework to Design and Evaluate Scheduling Strategies in Persistent Key-Value Stores
Key-value stores distribute data across several storage nodes to handle large amounts of parallel requests. Proper scheduling of these requests impacts the quality of service, as measured by achievable throughput and (tail) latencies. In addition to ...
Building Efficient Key-Value Stores via a Lightweight Compaction Tree
Log-Structure Merge tree (LSM-tree) has been one of the mainstream indexes in key-value systems supporting a variety of write-intensive Internet applications in today’s data centers. However, the performance of LSM-tree is seriously hampered by ...
Information
Published in.
University Carlos III of Madrid, Madrid, Madrid, Spain
University of Oregon, Eugene, OR, USA
https://ror.org/03ths8210University Carlos III of Madrid, Madrid, Spain
https://ror.org/04d836q62TU Wien, Vienna, Austria
https://ror.org/02p0gd045Universidad Complutense de Madrid, Madrid, Spain
https://ror.org/02rx3b187Université Grenoble Alpes, Saint Martin d'Hères, France
Springer-Verlag
Berlin, Heidelberg
Publication History
Author tags.
- Key-Value Stores
- Restricted Assignment
- Approximation
Contributors
Other metrics, bibliometrics, article metrics.
- 0 Total Citations
- 0 Total Downloads
- Downloads (Last 12 months) 0
- Downloads (Last 6 weeks) 0
View options
Login options.
Check if you have access through your login credentials or your institution to get full access on this article.
Full Access
Share this publication link.
Copying failed.
Share on social media
Affiliations, export citations.
- Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download, a status dialog will open to start the export process. The process may take a few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download
- Download citation
- Copy citation
We are preparing your search results for download ...
We will inform you here when the file is ready.
Your file of search results citations is now ready.
Your search export query has expired. Please try again.
IMAGES
VIDEO
COMMENTS
Abstract—Executing time-sensitive multi-robot missions in- volves two distinct problems: Multi-Robot Task Assignment (MRTA) and Multi-Agent Path Finding (MAPF). Computing safe paths that complete every task and minimize the time to mission completion, or makespan, is a significant computational challenge even for small teams.
Assigning tasks to a set of robots is a fundamental problem in robotics. It consists in finding the best task assignment to the available robots. In this paper, we present two distributed market-based algorithms to solve the assignment problem where n robots compete for n tasks with the assumption that each robot can be assigned to only one task.
Motivating applications: The multi-robot assignment problem for variable goal formations is motivated by applications including the following examples. 1.Multiple-robot assignment: The assignment and planning of teams of robots, drones, and spacecraft often requires motion between formations. Exam-
The rescue robot assignment problem is modeled as a multi-objective optimization problem with a discrete search space. When each group of robots is assigned to a task area, the values of multiple optimization indicators can be obtained. Hence we can refer to literature related to multi-robot task allocation and multi-objective optimization ...
This paper addresses a multiple agricultural spraying robots task assignment problem in the greenhouse environment. The objective of the problem is to obtain a set of Pareto solutions that simultaneously optimize the total travel distance and maximum completion time of all robots. To solve this problem, an effective multi-objective evolutionary ...
Assignment Algorithms for Variable Robot Formations. Chapter. First Online: 07 May 2020. pp 912-927. Cite this chapter. Download book PDF. Srinivas Akella. Part of the book series: Springer Proceedings in Advanced Robotics ( (SPAR,volume 13)) 1542 Accesses.
This problem is an extension of the deterministic generalized assignment problem, which is a NP-hard problem. We design an iterative algorithm for solving CC-GAP in which each robot maximizes its own objective by solving a chance-constrained knapsack problem in an iterative manner.
We present a novel algorithm for the multi-robot generalized assignment problem (GAP) with stochastic resource consumption. In this problem, each robot has a resource (e.g., battery life) constraint and it consumes a certain amount of resource to perform a task. In practice, the resource consumed for performing a task can be uncertain. Therefore, we assume that the resource consumption is a ...
the time resource assignment. We show that the problem can be reduced to a problem of assigning tasks to robots, where the tasks are organized in overlapping sets, and each robot has a limit on the number of tasks it can perform from each set, which is a variant of multi-robot assignment problem with set precedence constraint (SPC-MAP ...
Abstract: Due to the widespread application of multi-robot systems, the efficient task assignment for a team of robots has become particularly critical for performing complex tasks. This paper studies the task assignment problem for multiple robots to visit a group of target locations with precedence constraints, which determine the order/sequence in which certain target locations need to be ...
With the emergence of the artificial intelligence era, all kinds of robots are traditionally used in agricultural production. However, studies concerning the robot task assignment problem in the agriculture field, which is closely related to the cost and efficiency of a smart farm, are limited. Therefore, a Multi-Weeding Robot Task Assignment (MWRTA) problem is addressed in this paper to ...
The task assignment problem is one of the fundamental combinatorial optimization problems. It has been extensively studied in operation research, management science, computer science and robotics. Task assignment problems arise in various applications of multi-robot systems (MRS), such as environmental monitoring, disaster response, extraterrestrial exploration, sensing data collection and ...
Multi-robot task assignment (MRTA) is a particularly intriguing problem within the realm of multi-robot systems. The MRTA problem involves assigning a set of given tasks to multiple mobile robots, aiming to optimize one or more objective functions [5]. Presently, there has been little focus on the task allocation of agricultural spraying robots ...
The fundamental goal assignment problem for a multi-robot application aims to assign a unique goal to each robot while ensuring collision-free paths, minimizing the total movement cost. A plausible algorithmic solution to this NP-hard problem involves an iterative process that integrates a task planner to compute the goal assignment while ignoring the collision possibilities among the robots ...
satisfying solutions to the task assignment problem compared with several baseline methods. The rest of this paper is organized as follows. Section II presents the related work on the studied task assignment problem. In Section III, the formulation of the multi-robot package delivery task assignment problem is given. Section IV
assignment and to demonstrate its competitive performance with other meth-ods. More broadly, we aim to provide an additional tool for solving multi-robot optimization problems. The remainder of this work is organized as follows. Section 2 introduces the multi-robot task assignment problem and a general optimization statement. We
This problem is an extension of a special generalized assignment problem (where each task consumes the same time resource and must be finished), with additional deadline constraints for the time resource assignment. We show that the problem can be reduced to a problem of assigning tasks to robots, where the tasks are organized in overlapping ...
This paper introduces an extended cooperative multi-task assignment problem (ECMTAP), which involves deploying heterogeneous UAVs from different base stations to accomplish specific missions, with a focus on minimizing overall mission completion time. ... How, Uav task assignment, IEEE Robot. Autom. Mag. 15 (1) (2008) 39-44. Google Scholar [8 ...
The goal is to assign and route robots to transport objects between stations so that the project makespan—the time from start to completion—is minimized. We call this problem precedence-constrained multi-agent task assignment and path-finding (PC-TAPF). PC-TAPF generalizes the multi agent pathfinding (MAPF) problem with task assignment ...
In this paper, we consider the problem of concurrent assignment and planning of trajectories (which we denote C apt) for a team of robots.This problem involves simultaneously addressing two challenges: (1) the combinatorially complex problem of finding a suitable assignment of robots to goal locations, and (2) the generation of collision-free, time parameterized trajectories for every robot.
A coordinated robot-target assignment is required to direct robots to different zones when using robot teams for the discovery of an unknown environment. However, the computational cost of a robot-target assignment problem is high, as the distance of each robot to each target must be calculated for effective coordination.
Among these problems, task-assignment and robot-motion planning problems have been studied extensively [5][6][7] [8] [9], but fewer studies have been conducted on order-batching problems and ...
Multiple Robot Point Set Coverage under Geometric Constraints We focus on the assignment of discrete points among K robots and determining the order in which the points should be processed by the robots, in the presence of geometric and kinematic constraints between the robots. This is a path planning problem that arises as a subproblem in the decoupled approach to solving the motion planning ...
This paper studies the multi-robot task assignment problem in which a fleet of dispersed robots needs to efficiently transport a set of dynamically appearing packages from their initial locations to corresponding destinations within prescribed time-windows. Each robot can carry multiple packages simultaneously within its capacity. Given a sufficiently large robot fleet, the objective is to ...
However, partitioning these requests for appropriate storage server distribution is non-trivial and may result in imbalances. This study addresses this optimization challenge as the Restricted Assignment problem on Intervals (RAI). We propose an efficient (2-1 / m)-approximation algorithm, where m is the number of machines.