Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Cluster-based Multi-Robot Task Assignment, Planning, and Control
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Signals and Systems.ORCID iD: 0000-0001-6762-7172
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Signals and Systems.ORCID iD: 0000-0003-3922-1735
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Signals and Systems.ORCID iD: 0000-0002-1046-0305
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Signals and Systems.ORCID iD: 0000-0001-8870-6718
Show others and affiliations
2024 (English)In: International Journal of Control, Automation and Systems, ISSN 1598-6446, E-ISSN 2005-4092, Vol. 22, no 8, p. 2537-2550Article in journal (Refereed) Published
Abstract [en]

This paper presents a complete system architecture for multi-robot coordination for unbalanced task assignments, where a number of robots are supposed to visit and accomplish missions at different locations. The proposed method first clusters tasks into clusters according to the number of robots, then the assignment is done in the form of one-cluster-to-one-robot, followed by solving the traveling salesman problem (TSP) to determine the visiting order of tasks within each cluster. A nonlinear model predictive controller (NMPC) is designed for robots to navigate to their assigned tasks while avoiding colliding with other robots. Several simulations are conducted to evaluate the feasibility of the proposed architecture. Video examples of the simulations can be viewed at https://youtu.be/5C7zTnv2sfo and https://youtu.be/-JtSg5V2fTI?si=7PfzZbleOOsRdzRd. Besides, we compare the cluster-based assignment with a simulated annealing (SA) algorithm, one of the typical solutions for the multiple traveling salesman problem (mTSP), and the result reveals that with a similar optimization effect, the cluster-based assignment demonstrates a notable reduction in computation time. This efficiency becomes increasingly pronounced as the task-to-agent ratio grows.

Place, publisher, year, edition, pages
Springer Nature, 2024. Vol. 22, no 8, p. 2537-2550
Keywords [en]
Autonomous robots, Hungarian algorithm, multi-robot systems, task assignment
National Category
Robotics
Research subject
Robotics and Artificial Intelligence
Identifiers
URN: urn:nbn:se:ltu:diva-103890DOI: 10.1007/s12555-023-0745-4ISI: 001282795800023Scopus ID: 2-s2.0-85200365780OAI: oai:DiVA.org:ltu-103890DiVA, id: diva2:1830545
Projects
Autonomous Drones for Underground Mining Operations
Funder
Swedish Energy AgencyEU, Horizon 2020, 101003591
Note

Validerad;2024;Nivå 2;2024-08-12 (hanlid);

Funder: LKAB

Available from: 2024-01-23 Created: 2024-01-23 Last updated: 2025-02-05Bibliographically approved
In thesis
1. Synergistic Strategies in Multi-Robot Systems: Exploring Task Assignment and Multi-Agent Pathfinding
Open this publication in new window or tab >>Synergistic Strategies in Multi-Robot Systems: Exploring Task Assignment and Multi-Agent Pathfinding
2024 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Robots are increasingly utilized in industry for their capability to perform repetitive,complex tasks in environments unsuitable for humans. This surge in robotic applicationshas spurred research into Multi-Robot Systems (MRS), which aim to tackle complex tasksrequiring collaboration among multiple robots, thereby boosting overall efficiency. However,MRS introduces multifaceted challenges that span various domains, including robot perception,localization, task assignment, communication, and control. This dissertation delves into theintricate aspects of task assignment and path planning within MRS.The first area of focus is on multi-robot navigation, specifically addressing the limitationsinherent in current Multi-Agent Path Finding (MAPF) models. Traditional MAPF solutionstend to oversimplify, treating robots as holonomic units on grid maps. While this approachis impractical in real-world settings where robots have distinct geometries and kinematicrestrictions, it is important to note that even in its simplified form, MAPF is categorized as anNP-hard problem. The complexity inherent in MAPF becomes even more pronounced whenextending these models to non-holonomic robots, underscoring the significant computationalchallenges involved. To address these challenges, this thesis introduces a novel MAPF solverdesigned for non-holonomic, heterogeneous robots. This solver integrates the hybrid A*algorithm, accommodating kinematic constraints, with a conflict-based search (CBS) for efficientconflict resolution. A depth-first search approach in the conflict tree is utilized to accelerate theidentification of viable solutions.The second research direction explores synergizing task assignment with path-finding inMRS. While there is substantial research in both decentralized and centralized task assignmentstrategies, integrating these with path-finding remains underexplored. This dissertation evaluatesdecoupled methods for sequentially resolving task assignment and MAPF challenges. Oneproposed method combines the Hungarian algorithm and a Traveling Salesman Problem (TSP)solver for swift, albeit suboptimal, task allocation. Subsequently, robot paths are generatedindependently, under the assumption of collision-free navigation. During actual navigation, aNonlinear Model Predictive Controller (NMPC) is deployed for dynamic collision avoidance. Analternative approach seeks optimal solutions by conceptualizing task assignment as a MultipleTraveling Salesman Problem (MTSP), solved using a simulated annealing algorithm. In tandem,CBS is iteratively applied to minimize the cumulative path costs of the robots.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2024. p. 94
Series
Licentiate thesis / Luleå University of Technology, ISSN 1402-1757
Keywords
Autonomous robots, Multi-robot systems, Task assignment, Multi-agent path-finding
National Category
Robotics
Research subject
Robotics and Artificial Intelligence
Identifiers
urn:nbn:se:ltu:diva-103895 (URN)978-91-8048-474-9 (ISBN)978-91-8048-475-6 (ISBN)
Presentation
2024-02-28, A117, Luleå University of Technology, Luleå, 09:00 (English)
Opponent
Supervisors
Available from: 2024-01-23 Created: 2024-01-23 Last updated: 2025-02-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Bai, YifanLindqvist, BjörnNordström, SamuelKanellakis, ChristoforosNikolakopoulos, George

Search in DiVA

By author/editor
Bai, YifanLindqvist, BjörnNordström, SamuelKanellakis, ChristoforosNikolakopoulos, George
By organisation
Signals and Systems
In the same journal
International Journal of Control, Automation and Systems
Robotics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 467 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf