一种基于负载均衡的多Agent路径规划算法

Load Balancing Alogrithm for Multi-Agent Itinerary Planning

在分布式信息查询系统中,使用多个Agent协作完成查询任务是一种有效的方法,所有Agent的总行程影响网络的通信流量,单个Agent的最大负载决定了查询任务的完成时间。现有方法大多研究如何减少Agent的总行程,未考虑Agent的负载均衡问题。本文提出一种基于负载均衡的多Agent迁移路线规划(Load balanced mul-ti-agent planning,LBMAP)算法首先寻找图中一条包含所有节点的TSP回路,然后使用动态规划算法将该回路分为多段,每个Agent访问其中一段,算法兼顾了两个优化目标:最小化Agent的总行程、最小化Agent的关键负载。仿真实验表明:随着Agent平均访问节点数的增大,LBMAP算法的性能趋近于理论最优值。

In the agent-based distributed information systems, it is ordinary to use multiple agents to complete the task. The total trip impact on the network communications traffic, and the largest single workload determines the time to cornplete the task of inquiry. Existing methods focus primarily on reducing mobile Agent＇s total trip, while does not considering the load balancing problem. In this paper, a load balancing alogrithrn for multi-agent itinerary planning is proposed. Firstly, the algorithm finds a TSP circuit, and then divide the circuit into segments, each Agent visits a segment separately. The algorithm considers two objectives when planning the Agent＇s travel path： minimizing the total trip and minimizing the critical workload. Simulation results show that LBMAP alogrithm produces near-optimal performance with increasing average number of visiting nodes.