Search

Search Results

• DEVELOPMENT OF A METHOD FOR SOLVING THE PROBLEM OF TASK ALLOCATION IN A MULTI-AGENT SYSTEM

  V.А. Kostyukov , F.А. Houssein

  144-155

  2025-10-01

  Abstract ▼

  This paper considers the problem of task distribution within a multi-agent system, where each agent is an autonomous robot, and each task corresponds to a point in a two-dimensional environment that one of the agents must visit. This problem is essentially similar to a multi-agent version of the classical traveling salesman problem, where several agents are involved instead of one participant. Each of them must go through a unique route covering a certain set of points. In this regard, a study of the multi-agent traveling salesman problem is conducted as one of the formats for setting the problem of distributing goals among agents. This problem is of great importance in the field of routing and optimal task distribution. Its solution includes two closely related subproblems: determining the set of points assigned to each agent and constructing the optimal route for visiting them. There are three main approaches to solving this problem in the scientific literature: Optimization approach, where both subproblems are solved jointly; Cluster-First, Route-Second model, where tasks are first distributed among agents, and then routes are built;
  The Route-First, Cluster-Second model assumes initial optimization of the route for all points with its subsequent division between agents without changing the order of visits. In this paper, a hybrid method is proposed that combines elements of the Cluster-First, Route-Second and Route-First, Cluster-Second approaches. The goal is to combine the strengths of both concepts and minimize their drawbacks. To test the effectiveness of the developed method, a comparative study was conducted. The evaluation was carried out according to three main metrics: the time spent on constructing a solution, the total length of all routes, and the maximum route length among all agents. The experimental results showed that the use of the proposed method allows for a reduction in the maximum route length (thereby reducing the load imbalance between agents) by an average of 26%.

• HYBRID METHOD FOR SOLVING THE MULTI-AGENT TRAVELING SALESMAN PROBLEM

  V.А. Kostyukov, F.А. Houssein

  2025-04-27

  Abstract ▼

  In this research work, the problem of task allocation in a multi-agent system is considered, where
  each agent is a robot, and each task is represented by a position, which should be visited by one agent.
  This problem is very similar to the multi-agent traveling salesman problem, which, unlike the famous traveling
  salesman problem, involves several traveling salesmen who visit a given number of cities exactly
  once and return to the starting position with minimal travel costs. Therefore, the multi-agent traveling
  salesman problem is analyzed as a representative of the task allocation problem. The multi-traveling
  salesman problem is important for the field of route optimization and task allocation between several
  agents. It includes two different, but interrelated subproblems: distribute cities among agents and determine
  the order in which each agent visits cities. In the literature, there are 3 concepts for solving this
  problem with respect to solving its two constituent subproblems: the optimization concept, where both
  subproblems are solved simultaneously; The Cluster-First, Route-Second concept is where the question of
  which tasks to assign to which salesman is first decided, and then the question of the order in which each
  salesman solves his tasks is decided; The Route-First, Cluster-Second concept is where the question of the
  order in which tasks should be visited is first decided, and then this cycle is divided between agents without
  changing the order of visits in order to answer the question of which tasks each agent takes on. This
  paper proposes a hybrid approach to solving the multiple traveling salesman problem (mTSP), which
  combines the ideas of two well-known concepts: "First clustering, then routing" and "First routing, then
  clustering" in order to obtain their positive aspects and get rid of their weaknesses. To evaluate the effectiveness
  of the developed method, a comparative study was conducted using the classical method for solving
  the multi-traveling salesman problem. The results were evaluated based on three key criteria: the
  computational time to obtain a solution to the multi-travelling salesman problem, the total length of the
  routes travelled by the salesmen, and the maximum route length among them. The analysis of the experimental
  data showed that when using the proposed method, the maximum path length among the routes
  travelled by the agents (load imbalance) is reduced by an average of 26%.