• shareshare
  • link
  • cite
  • add
auto_awesome_motion View all 5 versions
Other research product . Article . 2021

Hierarchical Task Assignment and Path Finding with Limited Communication for Robot Swarms

Dario Albani; Wolfgang Hönig; Daniele Nardi; Nora Ayanian; Vito Trianni;
Open Access
Published: 31 Mar 2021 Journal: Applied Sciences, volume 11, page 3,115 (eissn: 2076-3417, Copyright policy )
Publisher: Multidisciplinary Digital Publishing Institute
Country: Italy
Complex service robotics scenarios entail unpredictable task appearance both in space and time. This requires robots to continuously relocate and imposes a trade-off between motion costs and efficiency in task execution. In such scenarios, multi-robot systems and even swarms of robots can be exploited to service different areas in parallel. An efficient deployment needs to continuously determine the best allocation according to the actual service needs, while also taking relocation costs into account when such allocation must be modified. For large scale problems, centrally predicting optimal allocations and movement paths for each robot quickly becomes infeasible. Instead, decentralized solutions are needed that allow the robotic system to self-organize and adaptively respond to the task demands. In this paper, we propose a distributed and asynchronous approach to simultaneous task assignment and path planning for robot swarms, which combines a bio-inspired collective decision-making process for the allocation of robots to areas to be serviced, and a search-based path planning approach for the actual routing of robots towards tasks to be executed. Task allocation exploits a hierarchical representation of the workspace, supporting the robot deployment to the areas that mostly require service. We investigate four realistic environments of increasing complexity, where each task requires a robot to reach a location and work for a specific amount of time. The proposed approach improves over two different baseline algorithms in specific settings with statistical significance, while showing consistently good results overall. Moreover, the proposed solution is robust to limited communication and robot failures.
Subjects by Vocabulary

Microsoft Academic Graph classification: Swarm robotics Asynchronous communication Motion planning Distributed computing Process (computing) Artificial intelligence business.industry business Workspace Robotics Task (project management) Robot Computer science

Library of Congress Subject Headings: lcsh:Technology lcsh:T lcsh:Engineering (General). Civil engineering (General) lcsh:TA1-2040 lcsh:Biology (General) lcsh:QH301-705.5 lcsh:Physics lcsh:QC1-999 lcsh:Chemistry lcsh:QD1-999


Fluid Flow and Transfer Processes, Computer Science Applications, Process Chemistry and Technology, General Engineering, Instrumentation, General Materials Science, swarm robotics, decision-making, task allocation, path finding, decision making, service robotics

Funded by
Foundations of Trustworthy AI - Integrating Reasoning, Learning and Optimization
  • Funder: European Commission (EC)
  • Project Code: 952215
  • Funding stream: H2020 | RIA
Validated by funder
Related to Research communities
Rural Digital Europe