A Distributed Approach to the Multi-Robot Task Allocation Problem Using the Consensus-Based Bundle Algorithm and Ant Colony System
We propose a distributed approach to solve the multi-robot task allocation problem. This problem consists of two distinct sets: robots and tasks. The objective is to assign tasks to robots while optimizing a given criterion. This problem is known to be NP-hard even with small numbers of robots and t...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8981979/ |
| _version_ | 1818932144461840384 |
|---|---|
| author | Farouq Zitouni Saad Harous Ramdane Maamri |
| author_facet | Farouq Zitouni Saad Harous Ramdane Maamri |
| author_sort | Farouq Zitouni |
| collection | DOAJ |
| description | We propose a distributed approach to solve the multi-robot task allocation problem. This problem consists of two distinct sets: robots and tasks. The objective is to assign tasks to robots while optimizing a given criterion. This problem is known to be NP-hard even with small numbers of robots and tasks. The field of survivors' search and rescue is adopted: i.e. some Unmanned Aerial Vehicles are used to rescue a number of survivors. We choose this problem, given its importance in everyday life: (a) survivors are the tasks; (b) Unmanned Aerial Vehicles are the robots; and (c) the objective is to rescue the maximum number of survivors while minimizing the makespan (time elapsed between rescuing the first and last survivors) and traveled distances. The approach is composed of two phases: inclusion and consensus. During the inclusion phase, each Unmanned Aerial Vehicle builds a bundle of survivors using the Ant Colony System. During the consensus phase, Unmanned Aerial Vehicles resolve conflicts in their bundles of survivors (i.e. a survivor is being chosen by more than two Unmanned Aerial Vehicles), using an adequate coordination mechanism. The approach is implemented using Java programming language and JADE multi-agent Framework. The performance of our approach is compared to five state-of-the-art multi-robot task allocation solutions. Simulation results show that the proposed approach outperforms these solutions, in terms of: (i) makespans; (ii) traveled distances; and (iii) exchanged messages. |
| first_indexed | 2024-12-20T04:27:49Z |
| format | Article |
| id | doaj.art-3ba87a81a86442e7abaf5ba79ea6e8c5 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-20T04:27:49Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-3ba87a81a86442e7abaf5ba79ea6e8c52022-12-21T19:53:28ZengIEEEIEEE Access2169-35362020-01-018274792749410.1109/ACCESS.2020.29715858981979A Distributed Approach to the Multi-Robot Task Allocation Problem Using the Consensus-Based Bundle Algorithm and Ant Colony SystemFarouq Zitouni0https://orcid.org/0000-0003-2566-1457Saad Harous1https://orcid.org/0000-0001-6524-7352Ramdane Maamri2https://orcid.org/0000-0001-7962-6775Department of Computer Science, Kasdi Merbah University, Ouargla, AlgeriaDepartment of Computer Science and Software Engineering, United Arab Emirates University, Abu Dhabi, United Arab EmiratesLIRE Laboratory, Abdelhamid Mehri University, Constantine, AlgeriaWe propose a distributed approach to solve the multi-robot task allocation problem. This problem consists of two distinct sets: robots and tasks. The objective is to assign tasks to robots while optimizing a given criterion. This problem is known to be NP-hard even with small numbers of robots and tasks. The field of survivors' search and rescue is adopted: i.e. some Unmanned Aerial Vehicles are used to rescue a number of survivors. We choose this problem, given its importance in everyday life: (a) survivors are the tasks; (b) Unmanned Aerial Vehicles are the robots; and (c) the objective is to rescue the maximum number of survivors while minimizing the makespan (time elapsed between rescuing the first and last survivors) and traveled distances. The approach is composed of two phases: inclusion and consensus. During the inclusion phase, each Unmanned Aerial Vehicle builds a bundle of survivors using the Ant Colony System. During the consensus phase, Unmanned Aerial Vehicles resolve conflicts in their bundles of survivors (i.e. a survivor is being chosen by more than two Unmanned Aerial Vehicles), using an adequate coordination mechanism. The approach is implemented using Java programming language and JADE multi-agent Framework. The performance of our approach is compared to five state-of-the-art multi-robot task allocation solutions. Simulation results show that the proposed approach outperforms these solutions, in terms of: (i) makespans; (ii) traveled distances; and (iii) exchanged messages.https://ieeexplore.ieee.org/document/8981979/Ant colony systemconsensus-based bundle algorithmcoordinationmulti-robot systemsmulti-robot task allocation problemresolution of conflicts |
| spellingShingle | Farouq Zitouni Saad Harous Ramdane Maamri A Distributed Approach to the Multi-Robot Task Allocation Problem Using the Consensus-Based Bundle Algorithm and Ant Colony System IEEE Access Ant colony system consensus-based bundle algorithm coordination multi-robot systems multi-robot task allocation problem resolution of conflicts |
| title | A Distributed Approach to the Multi-Robot Task Allocation Problem Using the Consensus-Based Bundle Algorithm and Ant Colony System |
| title_full | A Distributed Approach to the Multi-Robot Task Allocation Problem Using the Consensus-Based Bundle Algorithm and Ant Colony System |
| title_fullStr | A Distributed Approach to the Multi-Robot Task Allocation Problem Using the Consensus-Based Bundle Algorithm and Ant Colony System |
| title_full_unstemmed | A Distributed Approach to the Multi-Robot Task Allocation Problem Using the Consensus-Based Bundle Algorithm and Ant Colony System |
| title_short | A Distributed Approach to the Multi-Robot Task Allocation Problem Using the Consensus-Based Bundle Algorithm and Ant Colony System |
| title_sort | distributed approach to the multi robot task allocation problem using the consensus based bundle algorithm and ant colony system |
| topic | Ant colony system consensus-based bundle algorithm coordination multi-robot systems multi-robot task allocation problem resolution of conflicts |
| url | https://ieeexplore.ieee.org/document/8981979/ |
| work_keys_str_mv | AT farouqzitouni adistributedapproachtothemultirobottaskallocationproblemusingtheconsensusbasedbundlealgorithmandantcolonysystem AT saadharous adistributedapproachtothemultirobottaskallocationproblemusingtheconsensusbasedbundlealgorithmandantcolonysystem AT ramdanemaamri adistributedapproachtothemultirobottaskallocationproblemusingtheconsensusbasedbundlealgorithmandantcolonysystem AT farouqzitouni distributedapproachtothemultirobottaskallocationproblemusingtheconsensusbasedbundlealgorithmandantcolonysystem AT saadharous distributedapproachtothemultirobottaskallocationproblemusingtheconsensusbasedbundlealgorithmandantcolonysystem AT ramdanemaamri distributedapproachtothemultirobottaskallocationproblemusingtheconsensusbasedbundlealgorithmandantcolonysystem |