基于改进贪婪式算法的AMR任务分配

AMR task allocation based on improved greedy algorithm

摘要:

采用自主移动机器人AMR（Autonomous Mobile Robot）集群智能、高效处理机场行李时，为了解决机场环境中AMR集群的分配调度问题，提出一种改进贪婪式算法的任务调度策略. 根据随机行李数量，分配合适的AMR数量执行处理任务. 该算法综合考虑在机场环境下行李任务的到达规律和AMR特性，据此改进贪婪选择策略，使其较其他算法更好体现行李任务与AMR之间的调度分配关系. 首先, 采用A*算法计算代价，能够获得更加符合实际环境的代价值；其次, 对AMR进行类型划分和使用预先出发的策略，减小了任务分配时间和系统运行时间. 仿真结果表明，该算法与相关文献算法相比, 能够获得更小的任务分配时间和系统运行时间.

Abstract:

When using Autonomous Mobile Robot (AMR) cluster to process airport baggage intelligently and efficiently, in order to solve the allocation and scheduling problem of AMR cluster in the airport environment, a task scheduling strategy with an improved greedy algorithm is proposed. According to the random baggage quantity, the appropriate AMR quantity is allocated to perform the processing task. The proposed algorithm comprehensively considers the arrival rules and AMR characteristics of baggage tasks in an airport environment, and accordingly improves the greedy selection strategy, which making it better than other algorithms to reflect the scheduling and allocation relationship between baggage tasks and AMR. Firstly, the A* algorithm is used to calculate the cost, which can obtain a substitute value that is more in line with the actual environment. Secondly, the type division of AMR and the use of advance departure strategies reduce the task allocation time and system runtime. Simulation results show that the algorithm can obtain at least 8.9% improvement in system runtime compared with the greedy algorithm.