Paper deep dive
Relaxing Constraints in Anonymous Multi Agent Path Finding for Large Agents
Stepan Dergachev, Dmitry Avdeev
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 97%
Last extracted: 3/26/2026, 1:27:59 AM
Summary
This paper presents a modification to the Anonymous Multi-Agent Path-Finding for Large Agents (AMAPF-LA) algorithm, which operates in continuous space. The original algorithm required a minimum separation of 4 agent radii between start/goal positions. The authors propose a relaxation of this constraint to 2โ3, while theoretically proving that the modified algorithm preserves safety, collision avoidance, and goal reachability properties.
Entities (5)
Relation Signals (3)
Stepan Dergachev โ authored โ Relaxing Constraints in Anonymous Multi Agent Path Finding for Large Agents
confidence 100% ยท Relaxing Constraints in Anonymous Multi Agent Path Finding for Large Agents Stepan Dergachev
Modified AMAPF-LA โ relaxesconstraint โ 4 agent radii
confidence 98% ยท Proposed a modification aimed at relaxing the constraints and reduce this limit from 4 to 2โ3.
AMAPF-LA โ solves โ Anonymous Multi-Agent Path-Finding
confidence 95% ยท In this work, we focus on one of the algorithms[7] of so-called AMAPF for Large Agents (AMAPF-LA)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:The study addressed the problem of Anonymous Multi-Agent Path-finding (AMAPF). Unlike the classical formulation, where the assignment of agents to goals is fixed, in the anonymous MAPF setting it is irrelevant which agent reaches specific goal, provided that all goals are occupied. Most existing multi-agent pathfinding algorithms rely on a discrete representation of the environment (e.g., square grids) and do not account for the sizes of agents. This limits their applicability in real-world scenarios, such as trajectory planning for mobile robots in warehouses. Conversely, methods operating in continuous space typically impose substantial restrictions on the input data, such as constraints on the distances between initial and goal positions or between start/goal positions and obstacles. In this work, we considered one of the AMAPF algorithms designed for continuous space, where agents are modeled as disks of equal size. The algorithm requires a strict minimum separation of $4$ agent radii between any start/goal positions. Proposed a modification aimed at relaxing the constraints and reduce this limit from $4$ to $2\sqrt{3}$. We theoretically demonstrated that the proposed enhancements preserve original theoretical properties, including the guarantee that all agents will eventually achieve their goals safely and without collisions.
Tags
Links
- Source: https://arxiv.org/abs/2603.24442v1
- Canonical: https://arxiv.org/abs/2603.24442v1
Trouble viewing inline? Open PDF directly โ
Full Text
30,394 characters extracted from source content.
Expand or collapse full text
Relaxing Constraints in Anonymous Multi Agent Path Finding for Large Agents Stepan Dergachev 1,2[0000-0001-8858-2831] and Avdeev Dmitry 1[0009-0009-7833-7838] 1 HSE University, Moscow, Russia 2 FRC CSC RAS, Moscow, Russia Abstract. The study addressed the problem of Anonymous Multi-Agent Path- finding (AMAPF). Unlike the classical formulation, where the assignment of agents to goals is fixed, in the anonymous MAPF setting it is irrelevant which agent reaches specific goal, provided that all goals are occupied. Most existing multi-agent pathfinding algorithms rely on a discrete representation of the envi- ronment (e.g., square grids) and do not account for the sizes of agents. This limits their applicability in real-world scenarios, such as trajectory planning for mobile robots in warehouses. Conversely, methods operating in continuous space typi- cally impose substantial restrictions on the input data, such as constraints on the distances between initial and goal positions or between start/goal positions and obstacles. In this work, we considered one of the AMAPF algorithms designed for continuous space, where agents are modeled as disks of equal size. The algo- rithm requires a strict minimum separation of 4 agent radii between any start/goal positions. Proposed a modification aimed at relaxing the constraints and reduce this limit from 4 to 2โ3. We theoretically demonstrated that the proposed en- hancements preserve original theoretical properties, including the guarantee that all agents will eventually achieve their goals safely and without collisions. Keywords: Multi Agent Path-Finding, Anonymous Multi Agent Path-Finding, Multi Agent Path-Finding for Large Agents, Geometry, Navigation. 1 Introduction The multi-agent pathfinding (MAPF) is a challenging problem in the field of artificial intelligence that arises in numerous practical domains, including multi-robot systems, logistics, video game development and etc. In the classical formulation, agents are as- signed to predetermined, fixed goals. However, in many real-world scenarios, such as automated warehouses, agents are interchangeable, and it is irrelevant which agent reaches a particular goal, as long as all goals are eventually achieved. This variant of the problem is commonly referred to as Anonymous Multi-agent pathfinding (AMAPF) [1]. Many algorithms for both classical MAPF and its anonymous variant are built upon discrete representation of the environment, such as grids, and typically ignore the sizes of agents [2โ5]. These assumptions limit their applicability in real-world scenarios. On the other hand, existing AMAPF methods that operate directly in continuous spaces 2 usually impose a number of strict input constraints to ensure correctness [6โ8] such as minimum separation requirements between start and goal positions or between these positions and static obstacles. Such constraints further limit the applicability of these approaches in practice. In this work, we focus on one of the algorithms[7] of so-called AMAPF for Large Agents (AMAPF-LA), that is, an approach designed for continuous environments while explicitly accounting for agent size. In this formulation, obstacles are modeled as pol- ygons, whereas agents are represented as disks of unit radius. The algorithm has two main requirements: (i) the distance between the start/goal positions of any two agents must be at least 4, and (i) the distance between any start/goal position and obstacles must be at least โ 5. When we first examined the paper, we noted that it uses a specific theorem to ensure correct operation. In this paper we relax the first condition from 4 to 2 โ 3. At the same time, we theoretically demonstrate that this modification preserves the fundamental properties of the original algorithm, including the guarantee that all agents reach assigned goals. 2 Related work The MAPF problem formulations can be subdivided into several categories. The classic formulation of the problem is one where agents are assigned to specific goals, meaning it is crucial that a particular agent reaches a particular goal. Another important variant is the Anonymous Multi-Agent Path Finding (AMAPF) problem, where agents are not assigned to specific goals[9]. If the agents' dimensions are also taken into account, the problem is referred to as (Anonymous) Multi-Agent Path Finding for Large Agents. Finding optimal solution for MAPF problem, where each agent is assigned to a spe- cific goal, has been shown to be NP-hard [10]. However, much research has concen- trated on developing either optimal [11] or bounded-suboptimal [12] algorithms. In ad- dition, several algorithms without formal optimality guarantees have been proposed, including MAPP [13], Push and Swap [14], Bibox [15], and Push and Rotate [16]. In contrast to MAPF, the Anonymous MAPF problem under the makespan metric admits a polynomial-time optimal solution, using algorithms for finding maximum flow in a graph [10]. However, applying these algorithms directly to large-scale problems is often impractical. In [17], the authors introduce the suboptimal and efficient algorithm TSWAP. Several AMAPF algorithms also operate in continuous spaces, but most of them ne- glect either the presence of obstacles [6, 18] or the physical size of agents[19]. Methods that do consider obstacles typically impose restrictive assumptions, such as requiring obstacles of special structure [8], enforcing minimum separation between start and goal locations [20], and constraining the distance between these positions and obstacles [7]. Finally, several works have explored learning-based methods for AMAPF (e.g., re- inforcement learning and imitation learning approaches) [21โ24]. While these methods often demonstrate promising empirical performance, they generally lack theoretical guarantees of safety and goal reachability. 3 3 Problem Statement Consider a set ํ=1,2,...,ํ of agents in a common workspace ํโโ 2 . Each agent is represented by an open disk of unit radius, and its state is defined by the position of the disk's center. We define a set of starting positions for the agents as ํฎ=ํ 1 ,...,ํ ํ , where each ํ ํ โโ 2 . Similarly, let ํฏ=ฯ 1 ,...,ฯ ํ be a set of goal points, with ฯ ํ โโ 2 . The workspace contains traversable areas and obstacle regions. The subset of the workspace occupied by obstacles is denoted by ํโํ. The traversable area is denoted as ํ ํํํ =ํโํ. Furthermore, we define the set of collision-free positions, where agents do not collide with any obstacles, as โฑ โฑ=ํฅโํ ํํํ | โฌ 1 ( ํ ) โฉํ=โ ( 1 ) Where โฌ 1 ( ํ ) is an open unit disk. We consider ํ to be the continuous time set, ํ= ํ + โช0. A path is a continuous mapping over time, ฯ:ํโโฑ. Furthermore, a pair of paths ฯ and ฯ โฒ is said to be non-conflicting if the agents moving along these paths do not collide. โํกโํ : โฌ 1 (ํ ( ํก ) )โฉโฌ 1 (ํ โฒ ( ํก ) )โ โ ( 2 ) Thus, the problem is to find a set of paths for all agents, ฮ =ฯ 1 ,...,ฯ ํ , such that all paths are pairwise non-conflicting, each agent's path starts at its respective initial position ฯ ํ ( 0 ) =ํ ํ , and ends at a unique goal position. โํกโํ : โ ฯ ํ ( ํก ) ํโํ =ํฏ. We consider a set of paths ฮ =ฯ ํ ํโํ to be a solution to the problem. We define the length of a path ฯ as | ฯ | . Thus, the cost of a solution is the sum of the lengths of the paths: ํ ํขํ_ํํ_ํํํ ํกํ ( ฮ ) =โ | ํ ํ | ํ ํ=1 ( 3 ) In this research, we imposed no requirements that optimize the cost of the solution; however, solutions with a lower cost are more relevant. 4 Anonymous Multi-Agent Pathfinding for Large Agents To provide a foundation for the proposed improvement, we first outline the base algo- rithm [7]. This description highlights its core principles and the limitations that arise from its assumptions regarding the input data. In the subsequent section, we introduce a modified version of the algorithm designed to mitigate these limitations. The sug- gested method relaxes the constraints imposed on the initial and goal configurations while preserving the theoretical properties of the original approach. 4 4.1 Background The main idea of the algorithm consists in the sequential selection and movement of individual agents from their start to their goal positions with a guarantee of collision avoidance. At the first step, the shortest paths are computed for each agentโgoal pair, after which the optimal assignment of goals to agents is found to minimize the total path length. As a result, a current set of paths is formed: ฮ=ฮณ 1 ,...,ฮณ ํ , where ฮณ ํ : [ 0,1 ] โโฑ,ฮณ ํ ( 0 ) = ํ ํ , โ ฮณ ํ ( 1 ) ํโํ =ฯ ํ . Then, a single goal ฯ is identified, which does not block the move- ment of other agents along the paths from ฮ. Next, a start position s is selected from which the goal ฯ can be reached without collisions with other agents stationed at their start positions. The agent corresponding to position s moves to the goal ฯ, after which the area โฌ 1 ( ฯ ) occupied by this agent is marked as an obstacle. The positions s and ฯ are removed from the sets of start and goal positions ํฎ and ํฏ, respectively. The proce- dure is repeated until all agents reach their goals. For the correct operation of the algorithm, a number of requirements regarding the start and goal positions must be satisfied: 1. The pairwise distance between any two start or goal positions is at least 4. โํฃ,ํฃ โฒ โํฎโชํฏ, โํฃโํฃโฒโโโฅ4 ( 4 ) 2. The distance between any start or goal position and any obstacle is at least โ 5 โํฃโํฎโชํฏ and โํฅโํ, โํฃโํฅโโโฅ โ 5 ( 5 ) For a more rigorous treatment of the algorithm, we introduce several definitions and statements. The proofs for these can be found in the original work [7]. Theorem 1. A goal ฯ ํ โํฏ is called standalone if, given the current set of paths ฮ, it satisfies the following condition: โํพ ํ โฮ, ํโ ํ, 1โคํ,ํโคํ, โํฅโํพ ํ โฌ 1 ( ํฅ ) โฉโฌ 1 ( ํ ํ ) =โ . ( 6 ) In other words, a standalone goal does not conflict with the vicinity of any other path and, consequently, does not obstruct the movement of the agents. Lemma 1. Let ํฃโํฎโชํฏ,ํฅโโฑ, and suppose โฌ 1 ( ํฃ ) โฉโฌ 1 ( ํฅ ) โ โ . Then the path ฮณ connecting v to x ( ฮณ ( 0 ) =ํฃ,ฮณ ( 1 ) =ํฅ ) is a line segment that lies entirely within โฑ. Theorem 2. Consider a set of paths ฮ=ฮณ ํ ํโํ such that โํโํ, ฮณ ํ ( 0 ) = ํ ํ , โ ฮณ ํ ( 1 ) ํโํ =ํฏ, and the value ํ ํขํ_ํํ_ํํํ ํกํ ( ฮ ) is minimal among all such path sets. Then, for this set of paths, a standalone goal always exists. Let us consider a detailed step-by-step description of the algorithm. 1. For each agent ํ, we construct a set of shortest paths ฮ ํ โฒ =ฮณ ํ,ํ โฒ from its start position ํ ํ to all goal positions ฯ ํ . 2. Using the sets ฮ ํ โฒ , we find a set of paths ฮ=ฮณ ํ ํโํ such that โํโ ํ, ฮณ ํ ( 0 ) =ํ ํ , โ ฮณ ํ ( 1 ) ํโํ =ํฏ, and the value of ํ ํขํ_ํํ_ํํํ ํกํ ( ฮ ) is 5 minimized. In this case, the Hungarian algorithm [25] can be used to find the optimal assignment of goals. 3. Let us find a standalone goal ฯ for the set of paths ฮ. Theorem 1 states that such a goal always exists. Let j be the index of the agent that are assigned to the goal ฯ, i.e., ฮณ ํ ( 1 ) =ฯ. 4. We define the last agent ํ that blocks path ฮณ ํ , i.e.: โ ํกโ [ 0,1 ] : โฌ 1 (ํพ ํ ( ํก ) )โฉโฌ 1 ( ํ ํ ) โ โ โ ํโํ,ํก โฒ >ํก: โฌ 1 (ํพ ํ ( ํก โฒ ) )โฉโฌ 1 ( ํ ํ ) โ โ .(7) 5. If this agent ํ does not exist, we move agent ํ by path ฮณ ํ to goal ฯ, add the path to the total set ฮ , remove ํ ํ and ฯ from ํฎ and ํฏ, and add โฌ 1 ( ฯ ) to the set of obstacles (ํ ํํํ =ํ ํํํ โโฌ 1 ( ฯ ) , โฑ=โฑโโฌ 2 ( ฯ ) ). 6. Otherwise, agent ํ is assigned a path constructed from the straight-line seg- ment [ํ ํ ,ฮณ ํ ( ํก ) ] and the remaining part of the path from ฮณ ํ ( ํก ) to ฯ. We move the agent along the new path, after which we add this path to ฮ , re- move the start position ํ ํ and goal ฯ from their respective sets, and block the area โฌ 1 ( ฯ ) . 7. Repeat steps 1-6 until all agents are assigned goals. Figure 1 illustrates one step of the algorithm's operation. Agents ํ and ํ (green disks) need to be assigned goals ํก ํ and ํก ํ (violet disks). An optimal set of paths was con- structed. Goal ํก ํ was considered as a standalone goal; however, the path of agent k conflicted with the start position of agent ํ. Agent ํ is assigned goal ํก ํ , and a new path is constructed for it (red dashed line). Fig. 1. Illustration of the basic conflict resolution method. The figure is taken from paper [7] 6 4.2 Suggested Method This section will describe a modification of the algorithm previously considered from the paper [7]. For the subsequent discussion and proofs, we will leverage the previously introduced theorems and formulations. Let us describe the modified algorithm. The modified algorithm proposes a different approach to handle the movement of agents when the theorems from the original algorithm in paper [7] are violated. When constraints are weakened, the conditions for these theorems may no longer hold. Con- sequently, a situation may occur where the distance between point ฮณ ํ ( ํก ) and goal ํ becomes less than 2, which could potentially lead to conflicts in the future. Therefore, in such cases, the algorithm selects a point located exactly at a distance of 2 from ํ instead of ฮณ ํ ( ํก ) . Let us consider a detailed step-by-step description of the modified algorithm. 1. For each agent ํ, we construct a set of shortest paths ฮ ํ โฒ =ํพ ํ,ํ โฒ from its start position ํ ํ to all goal positions ํ ํ . 2. Using the sets ฮ ํ โฒ , we find a set of paths ฮ=ํพ ํ ํโํ such that โํโ ํ, ํพ ํ ( 0 ) =ํ ํ , โ ํพ ํ ( 1 ) ํโํ =ํฏ, and the value of ํ ํขํ_ํํ_ํํํ ํกํ ( ฮ ) is min- imized. In this case, the Hungarian algorithm [25] can be used to find the optimal assignment of goals. 3. Let us find a standalone goal ฯ for the set of paths ฮ. Theorem 1 states that such a goal always exists. Let j be the index of the agent that are assigned to the goal ํ, i.e., ํพ ํ ( 1 ) =ํ. 4. We define the last agent ํ that blocks path ํพ ํ , i.e.: โํกโ [ 0,1 ] :โฌ 1 (ํพ ํ ( ํก ) )โฉโฌ 1 ( ํ ํ ) โ โ โํโํ, ํก โฒ >ํก: โฌ 1 (ํพ ํ ( ํก โฒ ) )โฉโฌ 1 ( ํ ํ ) โ โ .(8) 5. If this agent ํ does not exist, we move agent ํ by path ํพ ํ to goal ํ, add the path to the total set ฮ , remove ํ ํ and ํ from ํฎ and ํฏ, and add โฌ 1 ( ํ ) to the set of obstacles (ํ ํํํ =ํ ํํํ โโฌ 1 ( ํ ) , โฑ=โฑโโฌ 2 ( ํ ) ). 6. Otherwise: a) If the distance to ฮณ ํ ( ํก ) is at least 2, agent ํ is assigned a path that con- sists of the straight-line segment [ํ ํ ,ฮณ ํ ( ํก ) ] and the remaining part of the path from ฮณ ํ ( ํก ) to ฯ. We move the agent along the new path, after which this path is added to ฮ , the start position ํ ํ and goal ฯ are re- moved from their respective sets, and the area โฌ 1 ( ฯ ) is blocked (see Figure 2) b) If the distance to ฮณ ํ ( ํก ) is less than 2, a single point ฮณ ํ ( ํก โฒ ) at a distance of 2 from ฯ is chosen, i.e.: โ! ํก โฒ โ [ 0,1 ] :โํพ ํ ( ํก โฒ ) ,ํโโ=2. ( 9 ) Agent ํ is assigned a path constructed from the straight-line segment [ํ ํ ,ํพ ํ ( ํกโฒ ) ] and the remaining part of the path from ฮณ ํ ( ํก โฒ ) 7 to ฯ. We move the agent along the new path, after which we add this path to ฮ , remove the start position ํ ํ and goal ฯ from their respective sets, and block the area โฌ 1 ( ฯ ) (see Figure 3). 7. Repeat steps 1-6 until all agents are assigned goals. Fig. 2. Movement of agents in case of sufficient distance between ฮณ ํ ( ํก ) and ฯ. Fig. 3. Movement of agents in case of violation of the distance condition between ํพ ํ ( ํก ) and ํ. Next, we provide a proof of the algorithm's theoretical properties. 4.3 Theoretical Analysis Lemma 2. Given a triangle ABC with | ํดํต | =2, | AC | โฅ2, | BC | โฅ2 โ 3, prove that the distance from point C to the segment AB is at least 2. Proof. Drop a perpendicular CH to the line AB. If | ํถํป | โฅ2, then the distance to the segment is clearly at least 2, and the statement is proven. Now suppose | ํถํป | โค2. 8 Assume that H lies on the segment AB. Then, by the Pythagorean theorem, 2 โ 3โค | ํถํต | =โ | ํถํป | 2 + | ํปํต | 2 โคโ | ํถํป | 2 + | ํดํต | 2 โค โ 2 2 +2 2 =2 โ 2, which is a contra- diction. Hence, H does not lie on the segment AB, meaning the distance from C to the segment AB in this case is the distance to either point A or point B. By the given con- ditions, |ํดํถ|,|ํตํถ|โฅ2, which completes the proof. Theorem 3. When executing step 6(a), the movement of the conflicting agent does not cause conflicts with other agents Proof. When executing step 6(a), the agent moves a distance of 2 toward point ฮณ ํ ( ํก ) , and by assumption, the path starting from this point is conflict-free. Therefore, it re- mains only to verify that the movement over the distance of 2 is valid; the remainder of the path is valid by the definition of the chosen point. Note that there are no agents within a distance of 2 from point ฮณ ํ ( ํก ) , as otherwise this point would not be the last conflict point. Moreover, if there are no agents/goals within a distance of 2 โ 3 from the conflicting agent, then these two circles, inside which no agents are present, entirely cover the movement of the conflicting agent. Indeed, if these two circles did not cover the movement of the conflicting agent, then there would exist some point ํค on the boundary of the union of these two circles such that the distance from w to the segment [ํ ํ ,ฮณ ํ ( ํก ) ] would be less than 2, i.e., ํํํ ํก(ํค,[ํ ํ ,ฮณ ํ ( ํก ) ])<2. However, by assumption, the following conditions hold simultaneously: ํํํ ํก ( ํ ํ ,ํค ) โฅ2 โ 3,ํํํ ํก(ฮณ ํ ( ํก ) ,ํค)โฅ2, and ํํํ ํก(ฮณ ํ ( ํก ) ,ํ ํ )=2. This leads to a geometry problem, the proof of which is given in Lemma 2. An illustration of the proof is shown in Fig. 4. The conflicting agent is marked as a green disk centered at B. The movement occurs from point B to point A. By definition, no agents can be inside the blue circles. Furthermore, during the move- ment from B to A, the distance from the center of the agent to the boundary of one of the two blue circles is always at least 2, as can be seen from the two nested circles of radius 2. Fig. 4. Illustration of the proof of the correctness of movement along the new path 9 Lemma 3. During the execution of the algorithm, โํ,1โคํโคํ,โ!ํก โฒ โ [ 0,1 ] :ํํํ ํก(ํพ ํ ( ํก โฒ ) ,ํก ํ )=2. Furthermore, ํพ ํ ( ํก โฒ ,1 ) =[ํพ ํ ( ํก โฒ ) ,ํก ํ ]. In other words, the point ํพ ํ ( ํก โฒ ) defined in step 6(b) is unique, and the path between ํพ ํ ( ํก โฒ ) and ํก ํ is a straight line segment. Proof. Consider the assignment ฮ โฒ obtained during step 1. From Lemma 1 it follows that for any such point ํพ ํ ( ํก โฒ ) in step 6(b), the path between ํพ ํ ( ํก โฒ ) and ํก ํ is obstacle- free. Consequently, the algorithm will assign the optimal route as a straight line seg- ment. Moreover, if there were multiple such points, the algorithm would have con- structed a segment to the goal from the earliest such point, again contradicting the op- timality of the path assignment. Lemma 4. Given a triangle ABC with | ํดํต | =2, | ํตํถ | โค2, | ํดํถ | โฅ2 โ 3. Also given a point ํท such that | ํถํท | โฅ2 โ 3, | ํดํท | โฅ2 โ 3. Prove that ํํํ ํก ( ํตํถ,ํท ) โฅ2 and ํํํ ํก ( ํดํต,ํท ) โฅ2. Proof. Let us prove that ํํํ ํก ( ํตํถ,ํท ) โฅ2. Drop a perpendicular ํทํป to the line ํตํถ. If | ํทํป | โฅ2, then this point is proven. Now suppose | ํทํป | <2. Note that in this case |ํถํป|=โ | ํถํท | 2 โ | ํปํท | 2 โฅ2 โ 2. In this case, |ํถํป|>|ํตํถ|, meaning ํป does not lie on ํตํถ, so the distance to the segment ํตํถ is the distance to either point ํต or ํถ. Point ํถ already has a distance greater than 2 to point ํท due to the constraint 2 โ 3. It remains to prove that |ํตํท|โฅ2| and then the problem is solved. Suppose this is not true. Then, due to the length constraints, angles โ ํดํตํถโฅ 2ํ 3 ,โ ํถํตํท> 2ํ 3 ,โ ํดํตํท> 2ํ 3 , by the Law of Cosines. But then it turns out that โ ํดํตํถ+โ ํถํตํท+โ ํดํตํท>2ํ. If so, then point ํต cannot be inside or on the boundary (possibly degenerate) of triangle ํดํถํท, since then the sum of angles would be 2ํ. However, since all sides of triangle ํดํถํท are greater than 2 โ 3 and ํต is outside this triangle, then one of the points ํด,ํถ,ํท is at a distance greater than 2 from point ํต, which contradicts the constraints on the lengths of segments ํดํต,ํถํต,ํทํต. Indeed, one of the sides must be greater than 2, because otherwise triangle ํดํถํท would lie strictly inside a semicircle of radius 2, which is impossible, since the perimeter of the triangle is less than the perimeter of the semicircle (4+2ํ), due to convexity and the nesting of con- vex figures, and since all sides are at least 2 โ 3, the perimeter of the triangle is at least 6 โ 3 > 4+2ํ, a contradiction. Therefore, the distance to point ํต in this case is also at least 2, so the problem for segment ํตํถ is solved. The case for segment AB is analogous. 10 Fig. 5. The area in which the agent is located in case 6(b) Theorem 4. When executing step 6(b), the movement of the conflicting agent does not cause conflicts with other agents. Proof. First, note that when executing step 6(b), there exists a specific 'small' bounded region, which is formed by the intersection of the circle of radius 2 centered at ฮณ ํ ( ํก โฒ ) and the set of all points that are at least 2 โ 3 away from ํก ํ . An illustration of such region is provided in Figure 5. It can be seen that the conflicting agent is always inside such region. If the conflict- ing agent were outside, step 6(a) would be executed instead. Indeed, if the conflicting agent ํ is outside of this region, then ํํํ ํก([ฮณ ํ ( ํก โฒ ) ,ํก ํ ],ํ ํ )>2โน[ฮณ ํ ( ํก โฒ ) ,ํก ํ ]โฉ ํต 1 ( ํ ํ ) =โ , meaning the point ฮณ ํ ( ํก ) defined in step 6(a) would be at least at distance 2 from the standalone goal ํก ํ by Lemma 3, so step 6(a) would be executed. Therefore, only the case where the conflicting agent ํ is inside such region remains. We now prove that the path from any inner point to the point ฮณ ํ ( ํก โฒ ) from step 6(b) does not conflict with other agents. This requires solving a geometric problem, which is ad- dressed in Lemma 4. In the geometric interpretation, points ํด,ํต, and ํถ correspond to ํก ํ ,ํพ ํ ( ํก โฒ ) , and ํ ํ , respectively. Moreover, point ํท represents some other agent. Accordingly, Lemma 4 shows that the polyline ํถํตํด is at least at distance 2 from point ํท, which in our case implies that no conflicts occur during the movement. An illustration is provided in Fig.6. 11 Fig. 6. Illustration of the proof of the correctness of movement along the new path Theorem 5. The standalone goal always exists. Proof. We base the beginning of the proof on the work from [7]. Note that if there is no standalone goal, then there exists a cycle of goals that conflict with each other. With- out loss of generality, assume that for agent ํ, the start position is ํ ํ and the goal is ํก ํ , and goal ํก ํ+1 intersects the path of agent ํ for each ํ from 1 to ํโ1 inclusive, and goal ํก 1 intersects the path of agent 1. Now we need to prove that there exists a set of paths assigning each agent ํ to goal ํก ํ+1 (for ํ=ํ, the goal is ํก 1 ), for ํ from 1 to ํ, such that the total length of the new paths is better than the original. However, note that in the described modified algorithm, the conflicting agent moved less than 2 towards a point on the path that was at least 2 away from the standalone goal. We apply the algorithm to the path from ํ ํ to ํก ํ , where the conflicting agent in this case is goal ํก ํ+1 . Applying all the above proofs to the modified algorithm, we conclude that the new assignment is strictly better than the old one, contradicting the initial assignment choice. Theorem 6. The algorithm is complete and finds a solution that is at most worse than the optimal solution by 4m radius of disk, provided the following conditions hold: 1. The pairwise distance between the centers of agents/goals is at least 2 โ 3 2. The distance between the centers of agents/goals and obstacles is at least โ 5 Proof. To prove the algorithm's completeness, we must verify that during its execu- tion, no collisions occur with obstacles, and no collisions occur between agents. Con- flicts with obstacles are prevented by Lemma 1. Theorems 3 and 4 prove that when executing these steps, no conflicts between agents arise during movement. Therefore, no conflicts occur, meaning the algorithm always finds some solution. Moreover, when executing one of the sub-steps in step 6, the additional movement adds at most 4 to the cost, as noted in Theorems 3 and 4. Hence, the found solution is at most worse than the optimal solution by 4ํ. Furthermore, after each algorithm iteration, ํต 1 (ํก ํ ) is added to 12 the obstacles. Due to the 2 โ 3 constraint between agents and goals, the distance between agents and obstacles remains at least โ 5, since โ 5<2 โ 3. The 2 โ 3 constraint also persists, as the algorithm proceeds to a subset of the set for which this constraint held. Thus, the algorithm's constraints are preserved after each iteration. 5 Conclusion In this work, we considered the problem of constructing a set of conflict-free paths for moving a group of agents from initial positions to a set of target positions, where it is not important which agent occupies which target. We examined an algorithm proposed in [7], which allows solutions to be found on a plane while accounting for the sizes of the agents. However, the original algorithm imposes constraints on the relative arrange- ment of the initial and target positions. In this work, we proposed a modification that relaxes these constraints by 13% while preserving the theoretical properties of the orig- inal algorithm. This improvement can help find solutions in problems with a higher density of agents. In cases where the original algorithm was inapplicable due to its con- straints, the modified algorithm can successfully solve the problem. An important direction for future research is to conduct experimental testing of the proposed method and compare it with existing alternatives, as well as to further relax the constraints on possible input data for multi-agent path planning algorithms. 6 References 1. Stern R, Sturtevant NR, Felner A, et al (2019) Multi-Agent Pathfinding: Defini- tions, Variants, and Benchmarks. In: Proceedings of the 12th Annual Symposium on Combinatorial Search (SoCS 2019). p 151โ158 2. De Wilde B, Ter Mors AW, Witteveen C (2014) Push and rotate: a complete multi-agent pathfinding algorithm. Journal of Artificial Intelligence Research 51:443โ 492 3. Sharon G, Stern R, Felner A, Sturtevant NR (2015) Conflict-Based Search for Optimal Multi-Agent Pathfinding. Artificial Intelligence 219:40โ66 4. Yu J, LaValle SM (2013) Multi-agent path planning and network flow. In: Algo- rithmic Foundations of Robotics X: Proceedings of the Tenth Workshop on the Algo- rithmic Foundations of Robotics. Springer, p 157โ173 5. Okumura K, Dรฉfago X (2023) Solving simultaneous target assignment and path planning efficiently with time-independent execution. Artificial Intelligence 321:103946 6. Turpin M, Michael N, Kumar V (2014) Capt: Concurrent assignment and plan- ning of trajectories for multiple robots. The International Journal of Robotics Research 33:98โ112 7. Solovey K, Yu J, Zamir O, Halperin D (2015) Motion planning for unlabeled discs with optimality guarantees. arXiv preprint arXiv:150405218 13 8. Banyassady B, de Berg M, Bringmann K, et al (2022) Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. In: 38th International Symposium on Computational Geometry (SoCG 2022) 9. Stern R, Sturtevant NR, Felner A, et al (2019) Multi-Agent Pathfinding: Defini- tions, Variants, and Benchmarks. In: Proceedings of the 12th Annual Symposium on Combinatorial Search (SoCS 2019). p 151โ158 10. Yu J, LaValle SM (2013) Multi-agent path planning and network flow. In: Al- gorithmic Foundations of Robotics X: Proceedings of the Tenth Workshop on the Al- gorithmic Foundations of Robotics. Springer, p 157โ173 11. Sharon G, Stern R, Felner A, Sturtevant NR (2015) Conflict-Based Search for Optimal Multi-Agent Pathfinding. Artificial Intelligence 219:40โ66 12. Li J, Ruml W, Koenig S (2021) EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021). p 12353โ12362 13. Wang K, Botea A (2011) MAPP: a scalable multi-agent path planning algo- rithm with tractability and completeness guarantees. Journal of Artificial Intelligence Research 42:55โ90 14. Luna R, Bekris KE (2011) Push and swap: Fast cooperative path-finding with completeness guarantees. In: IJCAI. p 294โ300 15. Surynek P (2009) A novel approach to path planning for multiple robots in bi- connected graphs. In: 2009 IEEE international conference on robotics and automation. IEEE, p 3613โ3619 16. De Wilde B, Ter Mors AW, Witteveen C (2014) Push and rotate: a complete multi-agent pathfinding algorithm. Journal of Artificial Intelligence Research 51:443โ 492 17. Okumura K, Dรฉfago X (2023) Solving simultaneous target assignment and path planning efficiently with time-independent execution. Artificial Intelligence 321:103946 18. Panagou D, Turpin M, Kumar V (2019) Decentralized Goal Assignment and Safe Trajectory Generation in Multirobot Networks via Multiple Lyapunov Functions. IEEE Transactions on Automatic Control 65:3365โ3380 19. Adler A, De Berg M, Halperin D, Solovey K (2015) Efficient multi-robot mo- tion planning for unlabeled discs in simple polygons. In: Algorithmic Foundations of Robotics XI: Selected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics. Springer, p 1โ17 20. Turpin M, Mohta K, Michael N, Kumar V (2014) Goal Assignment and Tra- jectory Planning for Large Teams of Interchangeable Robots. Autonomous Robots 37:401โ415 21. Lowe R, Wu YI, Tamar A, et al (2017) Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments. Proceedings of the Advances in neural infor- mation processing systems (NIPS 2017) 30: 22. Ji X, Li H, Pan Z, et al (2021) Decentralized, Unlabeled Multi-Agent Naviga- tion in Obstacle-Rich Environments Using Graph Neural Networks. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2021). p 8936โ8943 14 23. Khan A, Kumar V, Ribeiro A (2021) Large Scale Distributed Collaborative Unlabeled Motion Planning with Graph Policy Gradients. IEEE Robotics and Automa- tion Letters 6:5340โ5347 24. Chu W, Yu A, Zhang W, et al (2024) Perception Field Based Imitation Learn- ing for Unlabeled Multi-Agent Pathfinding. Science China Information Sciences 67:152107 25. Kuhn HW (1955) The Hungarian method for the assignment problem. Naval research logistics quarterly 2:83โ97