This article is about the MAPF problem in AGV scheduling and path planning problems, including the MAPF problem background, description, type and conflict type, solution algorithm type, etc.
01 Background of the MAPF problem
The traditional Vehicle Routing Problem (VRP) is the most common type of path planning problem in the logistics field. It requires designing paths for multiple vehicles under certain conditions and completing tasks at the lowest cost, such as delivering goods to multiple customer points. The complexity of VRP mainly stems from global task allocation, scheduling optimization and resource constraints. It is a classic combinatorial optimization problem. Global optimization algorithms are usually used, such as genetic algorithms, tabu search, simulated annealing, hybrid heuristics, etc., to find an optimal solution or a near-optimal solution that satisfies all constraints.
However, with the continuous development of logistics automation and intelligent robot technology, especially the widespread application of autonomous vehicles (AGVs), the challenge of path planning is no longer just the optimization of global tasks, but how to coordinate the actions of multiple autonomous agents in a complex and dynamic environment. This means that not only the optimal path of the vehicle must be considered, but also ensuring that multiple agents do not conflict when moving in the same space. Real-time collaboration has become a new problem.
It is against this background that a more microscopic path planning problem comes into our lives:Multi-Agent Path Finding (MAPF). Multi-agent path planning (MAPF) is a problem of planning collision-free paths for multiple agents in a shared environment. In recent years, research on MAPF has flourished, and its applications include automated warehouses and self-driving vehicles. Agents move in a shared space, and every time point and every path may collide with other agents or static obstacles. Therefore, MAPF is more of a real-time coordination problem. The key constraint is that multiple agents travel along the planned path at the same time without conflict. Its complexity comes from the collaboration of agents in the space-time dimension. Especially in a large-scale agent environment, how to design a conflict-free path for each agent in limited space and time is the main difficulty.
02 Description of MAPF problem
With k agentsClassic MAPF problemThe description is:
Define a tuple (G,s,t). Among them, G=(V,E) is an undirected graph. The node v ∈V in the undirected graph is the position that the agent can occupy, and the edge (n,n’) ∈ E represents the line connecting the agent from node n to n’. s is a set of initial positions, and each agent has a starting position si ∈ s; t is a set of target positions, and each agent has a target position ti∈ t . It is assumed that time and space are discretized into fixed step sizes and grids, and it is also assumed that the actions of the agent are also discrete. In each time step, each agent is located in one of the graph nodes and can perform an action. There are generally five types of actions: up, down, left, right and wait. The movement action can only move from the current node v to the adjacent node v’ (( v, v’ ) ∈ E) in the graph. The movement speed of the agent and physical consumption and other influencing factors are not considered when moving. Define the action as the function a : V → V, that is, a(v)=v’ means that if the agent is located at the vertex v and performs the action a, then it will be located at the vertex v’ in the next time step. The path planning of a single agent is a set of a series of actions from the starting position to the target position π= (a1, a2, ... , an), the path planning problem of k agents is the set of k paths Π={π1,π2, ... ,πk}, where the i-th agent corresponds to the path πi。
03 Conflict types of MAPF
The MAPF solution is said to be valid if and only if there is no conflict between the path plans of any two single agents.Common conflict types in classic MAPF problems are:
side conflict：πi and πj An edge conflict occurs if and only if agent i and agent j traverse the same edge in the same direction at the same time step.
Vertex conflict:πi and πj A vertex conflict occurs if and only if agent i and agent j occupy the same vertex at the same time step.
Follow the conflict:If an agent plans to occupy a vertex occupied by another agent at the previous time step, then πi and πj Follow-up conflicts will occur.
Circular conflict:A set of single-agent paths πi,πi+1, ... ,πjA cycle conflict occurs if and only if each agent moves to the vertex occupied by another agent in the previous time step and forms a "rotating cycle" pattern.
Exchange conflict:πi and πjAn exchange conflict occurs if and only if agent i and agent j exchange positions within a single time step.
Figure 1: Illustration of common conflict types. From left to right: edge conflict, vertex conflict, following conflict, cycle conflict, exchange conflict.
04 Types of MAPF
In the classic MAPF problem, each agent knows the starting point and target end point according to the assigned task.According to different task allocations, the classic MAPF problem can be expanded into the following three categories:
Anonymous MAPF:In this variant of MAPF, the goal is to move an agent to a set of goal vertices, but it does not matter which agent reaches which goal, i.e. each of these agents can be assigned to any goal, but it must satisfy a one-to-one mapping between the agent and the goal. Similar to the Didi taxi scene.
Group MAPF:In this variant of MAPF, agents are grouped into teams, each team has a set of goal vertices, and the agents in each team need to be moved to their goal vertices, where each agent can only be assigned to goals from the set of goal vertices assigned to its team. Similar to the regional order dispatching scenario for takeout.
Dynamic MAPF:In this variant of MAPF, the agent receives a new task when it reaches the target vertex, and new agents can appear in the graph over time. All agents will continue to receive new tasks and continue to act. Planning is not just for a single task, but for lifelong optimization.
05 Types of MAPF solving algorithms
According to different planning methods, the MAPF algorithm is divided intocentralized planning algorithmanddistributed planning algorithm. The centralized planning algorithm needs to know the starting position, target position, obstacle location and other information of all agents. In centralized scheduling, map information is stored by a central server that communicates with each agent. The central server masters the status and path information of all agents and is responsible for assigning tasks to each agent, issuing task instructions and planning a collision-free optimal path for each agent.Centralized planning algorithms can be divided into four categories: A*-based search, Conflict Based Search (CBS), cost-growing tree-based, and protocol-based. They pay more attention to the quality of the solution during the solution process.。In the following, we will introduce in detail two multi-agent path planning algorithms based on A* search and conflict search.
The distributed planning algorithm is a MAPF algorithm based on reinforcement learning that emerged in the field of artificial intelligence. It adopts the idea of decentralization. During the interaction between the agent and the environment, each agent can communicate with other agents within a certain range. The premise is that each agent only masters information such as the location of the agent and obstacles within the field of view. The agent continuously interacts with the environment according to the current strategy, obtains the state of the environment at the next moment and updates its action strategy. Distributed planning algorithms can be divided into three categories according to different improvement technologies: expert demonstration type, improved communication type and task decomposition type. They are suitable for high-density and dynamic partially observable environments and can efficiently solve real-time re-planning problems.
References
[1] R. Stern et al., “Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks,” SOCS, vol. 10, no. 1, pp. 151–158, Sep. 2021, doi: 10.1609/socs.v10i1.18510.
Machine-translated from the Chinese original MAPF 问题介绍 (published 2024-10-20). WeChat original ↗