CBS (Conflict-Based Search) is a branch-and-bound method used for multi-agent path planning problems. Its main goal is to allow multiple agents to find the optimal collision-free path in a shared environment. The characteristic of CBS is that it adopts a hierarchical structure, which is divided into high-level conflict resolution and low-level path planning. Path conflict detection and conflict resolution are considered separately to achieve a balance between search efficiency and solution quality.
01 High-level conflict resolution
High-level conflict resolution is mainly responsible for detecting conflicts between multiple agents and decomposing the problem into smaller sub-problems by generating different constraints for conflicting agents.Whenever a conflict is detected, CBS creates constraints for the conflicting agents to prevent them from appearing in the same location at the same time. By recursively decomposing conflicts and giving priority to solutions with lower path costs, until a conflict-free path for all agents is found.
Steps:
1. Initial state:Assume that each agent AiThere is an initial shortest path Pi, which is the optimal path without considering conflicts.
2. Conflict detection:The algorithm checks all paths P1,P2,...Pn, find the conflict. For example, if two agents Aiand AjIf t appears at the same position (x, y) at the same time, this is a conflict, recorded as (Ai, Aj, (x, y), t)。
3. Conflict resolution:For each conflict (Ai, Aj, (x, y), t), CBS generates two child nodes, each child node corresponds to the constraints of an agent:
(1) Child node 1: is agent AiAdd a constraint to restrict it from entering the position (x, y) at time t, marked as Ci=(x, y, t)。
(2) Child node 2: is agent AjAdd a constraint like Cj=(x, y, t)。
In this way, CBS decomposes the conflict into two possible path planning problems, in which at least one agent must change its path to avoid the conflict.
4. Priority queue:Store these two child nodes in the priority queue, sort them by the total cost (such as the total path length), and select the solution with the smallest total cost each time for processing. The cost can be expressed as cost(P1, P2, ..., Pn), that is, the total length of all agent paths.
5. Iteration:Remove the node with the smallest current total cost from the priority queue and repeat conflict detection and decomposition until a conflict-free solution is found.
In this way, the higher level is only responsible for constraint generation and conflict management, constantly reducing the solution space by generating constraints.
02 Low-level path planning
Low-level path planning focuses on calculating the optimal path for a single agent that satisfies high-level constraints.Whenever the higher layer generates new constraints, the lower layer will re-plan the path for the constrained agent to ensure that it avoids conflict points. The lower layer uses a classic path search algorithm (such as the A* algorithm) to calculate the shortest path of the agent, and maintains the overall search efficiency while locally adjusting the agent path.
Steps:
1. Single-agent path planning:When the high level is an intelligent agent AiConstraint C is generatedi(such as avoiding position (x, y) at time t), the lower layer will use a path search algorithm (such as A* algorithm) AiTo calculate the new path Pi, the following conditions must be met:
-
Path P i Avoid all high-level constraints C i , that is, P i Does not contain any prohibited states such as (x, y, t).
-
Path P i Be as short as possible while satisfying the constraints.
2. Path search:Suppose agent AiThe starting point of the current path is si, the target is gi, the task of path planning is to find a path from sito giThe shortest path Pi, making:
And satisfy the constraint C at all times ti(i.e. Aiwill not appear at the constrained time and location).
3. Partial update:The low-level layer will only recalculate paths for constrained agents, and other unconstrained agents keep their original paths unchanged, which greatly reduces computational overhead.
4. Feedback to senior management:When the lower layer plans a new path P for the agentiFinally, it will be fed back to senior management. If the low-level path calculation does not violate new constraints and there are no conflicts, the algorithm terminates; if there are still conflicts, the high-level continues to generate new constraints and recursively decompose.
Summary
High-Level Conflict Resolution:Manages constraint generation and conflict detection, generating constraints whenever a conflict is found and decomposing the problem into sub-problems until a conflict-free solution is found. Its core lies in the branch-and-bound method and conflict recursive decomposition.
Low-level path planning:Based on high-level constraints, re-plan the shortest path for the affected agents to ensure that the path complies with the constraints. It uses a classic path search algorithm to independently calculate the path of a single agent.
The CBS algorithm already has a Python-based library. You can use it in Python projects by running "pip install cbs-mapf" to install this library.
References
[1] Sharon G, Stern R, Felner A, et al. Conflict-based search for optimal multi-agent pathfinding[J]. Artificial intelligence, 2015, 219: 40-66.
[2] Hönig W, Kiesel S, Tinka A, et al. Conflict-based search with optimal task assignment[C]//Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. 2018.
[3] Huang T, Koenig S, Dilkina B. Learning to resolve conflicts for multi-agent path finding with conflict-based search[C]//Proceedings of the AAAI conference on artificial intelligence. 2021, 35(13): 11246-11253.
[4] CBS algorithm Python library website: https://pypi.org/project/cbs-mapf/
Machine-translated from the Chinese original CBS 算法介绍 (published 2024-10-20). WeChat original ↗