With the application of multi-robot systems in various scenarios, the task assignment problem of multiple robots with precedence constraints has become a hot research topic, where a robot can perform a task only when all the predecessor tasks of the task have been completed. In response to this issue, this paper proposes an effective task assignment method to minimize the total time for a fleet of robots to perform multiple tasks with precedence constraints. Firstly, a greedy algorithm is used to generate the initial task assignments for multiple robots. Subsequently, the simulated annealing and adaptive large neighborhood search algorithms are integrated to improve the initial solution, where a novel insertion operator is introduced. Finally, numerous experiments show that the proposed method has superior performance for solving the precedence-constrained multi-robot task assignment problem compared with several existing popular heuristic methods.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Improved Adaptive Large Neighborhood Search Algorithm for Multi-robot Task Assignment with Precedence Constraints

  • Xiaoshan Bai,
  • Jiahao Zou,
  • Bo Zhang,
  • Zongze Wu

摘要

With the application of multi-robot systems in various scenarios, the task assignment problem of multiple robots with precedence constraints has become a hot research topic, where a robot can perform a task only when all the predecessor tasks of the task have been completed. In response to this issue, this paper proposes an effective task assignment method to minimize the total time for a fleet of robots to perform multiple tasks with precedence constraints. Firstly, a greedy algorithm is used to generate the initial task assignments for multiple robots. Subsequently, the simulated annealing and adaptive large neighborhood search algorithms are integrated to improve the initial solution, where a novel insertion operator is introduced. Finally, numerous experiments show that the proposed method has superior performance for solving the precedence-constrained multi-robot task assignment problem compared with several existing popular heuristic methods.