Dynamic Multi-Robot Task Allocation in Semi-Dynamic Environment
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Sähkötekniikan korkeakoulu |
Master's thesis
Authors
Date
2023-10-09
Department
Major/Subject
Control, Robotics and Autonomous Systems
Mcode
ELEC3025
Degree programme
AEE - Master’s Programme in Automation and Electrical Engineering (TS2013)
Language
en
Pages
59
Series
Abstract
Multi-robot task allocation has gained significant focus from the research community for its efficiency in utilizing the multi-robot system to allocate complex tasks to different robots. While it would be useful to deploy the system in a dynamic environment, only a few previous research have focused specifically on developing allocation algorithms optimized for dynamic environments. Although dynamic-agnostic MRTA algorithms, which have received the most research attention from the community, can efficiently achieve task allocation in a static environment, they can not take into account dynamic information in an environment. This can lead to behavior such as robots being stuck or needing detours to achieve tasks, which can significantly affect the effectiveness of the algorithm. Therefore, this thesis proposes a decentralized market-based multi-robot task allocation algorithm which can be used in an environment with semi-dynamic objects. In the algorithm, the robots constantly observe the status of the doors in an environment, whether they are opened or closed, and use LBP to make predictions of the status of all the doors in the environment using the previous observations from each robot. The predictions are then used to bid for tasks by each robot. The improved bidding procedure can help robots avoid tasks that have a high possibility of being blocked by a closed door and thus decrease the need for detours. The proposed algorithm is tested in a simulated environment to compare the time used for task allocation, time used for task execution, and the number of failed tasks with a baseline algorithm that is not able to observe doors in the environment and make corresponding predictions to evaluate the efficiency of the proposed algorithm. The evaluation shows that the proposed algorithm outperforms the baseline algorithm in making better task allocations to reduce the time needed for task executions and the number of failed tasks while only slightly increasing the time needed for task allocation. Experiments on the proposed algorithm and two state-of-the-art task allocation algorithms also show that the predictions can be used effectively to boost the performance of task allocation by reducing the time needed for task executions.Description
Supervisor
Kucner, TomaszThesis advisor
Kucner, TomaszKeywords
mobile robots, multi-robot task allocation, market-based task allocation, loopy belief propagation