CN120406463A

CN120406463A - Multi-robot path planning method, system and electronic equipment

Info

Publication number: CN120406463A
Application number: CN202510557774.2A
Authority: CN
Inventors: 徐光运; 张小艺; 吴耀华; 马文凯; 宗广灯; 岳明; 尚现伟; 邹霞; 史璐玉; 孙甲浩
Original assignee: Lanjian Intelligent Technology Co ltd
Current assignee: Lanjian Intelligent Technology Co ltd
Priority date: 2025-04-29
Filing date: 2025-04-29
Publication date: 2025-08-01

Abstract

The invention provides a multi-robot path planning method, a multi-robot path planning system and electronic equipment, and relates to the technical field of robots, wherein the method comprises the steps of firstly constructing a target map of a physical space environment where a robot is positioned; the target map is an interference result of a SLAM map and a point location map, obstacles in the physical space environment are marked in the target map, task parameters of tasks to be distributed and robot state information of a plurality of robots are obtained, the target tasks distributed by each robot are determined according to the task parameters and the robot state information, and a target path for executing the target tasks is planned for each robot respectively based on the target map marked with the obstacles. The method and the system can improve the adaptability and the robustness of the AGV system in a complex dynamic environment.

Description

Multi-robot path planning method, system and electronic equipment

Technical Field

The present invention relates to the field of robots, and in particular, to a method, a system, and an electronic device for planning paths of multiple robots.

Background

In the field of automated guided vehicles (Automated Guided Vehicle, AGVs), autonomous multi-robot systems are receiving great attention for their rich and varied functionality and higher efficiency. In a Multi-robot system, many application scenarios require coordinated navigation of the mobile robot in a complex environment, which requires generation of collision-free trajectories from the initial position to the final position of the robot, a problem called a labeled Multi-robot path search (Multi-AGENT PATH FINDING, MAPF) problem.

At present, the multi-robot path search is mainly performed based on a topological map, but the method is difficult to adapt to the conditions of large map scale, complex and dynamic environment, and has various problems such as long implementation period, inaccurate path drawing, difficult quick response and dynamic change. Therefore, how to improve the adaptability and robustness of the AGV system in a complex dynamic environment is a problem to be solved.

Disclosure of Invention

In view of the above, the present invention aims to provide a multi-robot path planning method, system and electronic device, which can improve the adaptability and robustness of an AGV system in a complex dynamic environment.

In a first aspect, an embodiment of the present invention provides a method for planning a path of a plurality of robots, the method including the steps of:

Constructing a target map of a physical space environment where the robot is located, wherein the target map is an interference result of an SLAM map and a point location map, and obstacles in the physical space environment are marked in the target map;

acquiring task parameters of tasks to be distributed and robot state information of a plurality of robots;

determining a target task allocated to each robot according to the task parameters and the robot state information;

and planning a target path for executing the target task for each robot based on the target map marked with the obstacle.

In some embodiments, the obstacle comprises a static obstacle and a dynamic obstacle, and the constructing the target map of the physical space environment of the robot comprises:

Modeling a physical space environment where a robot is located through a laser radar to obtain a rasterized SLAM map, wherein static obstacles in the physical space environment are marked in the SLAM map;

analyzing platform metadata of a platform map corresponding to the physical space environment, and constructing a point location map based on the platform metadata, wherein in the point location map, a platform is marked as a dynamic obstacle;

And carrying out interference processing on the SLAM map and the point location map to obtain a target map, wherein the interference processing comprises coordinate alignment and space discretization, the target map is stored in a key value pair form, a key represents grid coordinates, and a value represents the occupation state of the grid and the distance between the grid and an obstacle nearest to the grid mark.

In some embodiments, the determining the target task allocated by each robot according to the task parameter and the robot state information includes:

acquiring the starting point and the end point of the task to be distributed in the task parameters,

Judging whether a passable path from the starting point to the ending point exists in the target map according to the obstacle marked in the target map;

And if so, determining the target task distributed by each robot according to the preset task distribution strategy and the state information of the robot and the task parameters.

In some embodiments, the planning, for each robot, a target path for performing the target task based on the target map marked with the obstacle includes:

Acquiring a target starting point and a target ending point of the target task to be executed by each robot;

searching for a discrete path from a target start point to the target end point for each of the robots within the range of the target map marked with obstacles according to an enhanced collision-based search ECBS algorithm;

nonlinear optimization is carried out on the discrete paths of each robot, so that discrete track points are obtained;

and dividing and fitting the discrete track points of each robot to obtain a target path for executing the target task.

In some embodiments, the non-linearly optimizing the discrete path of each of the robots, resulting in an optimized path, includes:

Determining a robot triplet closest in time step based on the discrete path of each of the robots;

Grouping and distributing priorities of the robots according to the occurrence frequency of the robot triplets to obtain a plurality of robot combinations with priorities;

according to the order of the priorities, each robot combination is used as a current robot combination one by one;

taking an optimized path corresponding to the optimized high-priority robot combination as collision constraint, and performing nonlinear optimization on the discrete paths of the robots in the current robot combination to obtain an optimized path.

In some embodiments, the dividing and fitting the discrete trajectory points of each robot to obtain a target path for performing the target task includes:

Acquiring track information of the discrete track points for each robot, wherein the track information at least comprises positions;

dividing a plurality of continuous discrete track points with the same positions into a segmentation group;

dividing the discrete track points with different positions in the discrete track points into a plurality of subsections based on an error self-adaptive segmentation algorithm;

fitting each subsection respectively to obtain a track section;

and constructing the sequence and the dependency relationship among the track segments to obtain a target path for executing the target task.

In some embodiments, the method further comprises:

Constructing an action dependency graph, wherein vertexes in the action dependency graph are used for representing actions of the robot, and edges in the action dependency graph are used for representing dependency relations among the actions;

And controlling each robot to sequentially execute actions according to the action dependency graph in the process that each robot moves according to the respective target path.

In some embodiments, the method further comprises:

Acquiring expected actions of the robot in a current target task under the condition that the robot is simultaneously distributed with a plurality of target tasks, wherein the residual execution time of the expected actions is longer than a preset planning time;

Constructing a reverse action dependency graph, and executing reachability search on the expected action in the reverse action dependency graph to obtain an action set to be completed between the robot and a new target task;

determining a stopping action executed last by the robot in the action set;

And the robot continues to execute the action in the current target task until the stopping action is completed, and starts to execute the new target task.

In a second aspect, an embodiment of the present invention provides a multi-robot path planning system, the system including:

The system comprises a map construction module, a control module and a control module, wherein the map construction module is used for constructing a target map of a physical space environment where the robot is, and obstacles in the physical space environment are marked in the target map;

The information acquisition module is used for acquiring task parameters of the tasks to be distributed and robot state information of a plurality of robots;

the task allocation module is used for determining a target task allocated by each robot according to the task parameters and the robot state information;

And the path planning module is used for planning a target path for executing the target task for each robot based on the target map marked with the obstacle.

In a third aspect, an embodiment of the present invention further provides an electronic device, including a memory, and a processor, where the memory stores a computer program that can be executed on the processor, where the processor executes the steps of the method for planning a path of multiple robots according to the first aspect.

The embodiment of the invention has at least the following beneficial effects:

The invention provides a multi-robot path planning method, a system and electronic equipment, wherein the method comprises the steps of constructing a target map of a physical space environment where a robot is located; the target map is an interference result of the SLAM map and the point location map, obstacles in a physical space environment are marked in the target map, task parameters of tasks to be distributed and robot state information of a plurality of robots are obtained, the target tasks distributed by each robot are determined according to the task parameters and the robot state information, and a target path for executing the target tasks is planned for each robot respectively based on the target map marked with the obstacles.

The scheme can realize task allocation and path planning in a complex environment. The target task distributed by each robot is determined, and then, a target path specially executing the target task is planned for the robot, so that the planned target path and the target task have higher matching degree, the implementation cost of the target task is reduced, and the execution efficiency of the task is improved. And aiming at path planning, the target map utilized by the path planning method is an interference result of a SLAM map and a point location map, wherein the SLAM map is a finer obstacle grid map, can more accurately represent the physical space environment, and the point location map is convenient for path planning of multiple robots through the topological result among sites. Furthermore, based on the target map marked with the obstacle, the target path for executing the target task is planned for each robot respectively, so that the accuracy of path planning can be remarkably improved, the method and the system can be rapidly applied to the environment with frequent change, and the adaptability and the robustness of the AGV system in the complex dynamic environment can be effectively improved.

Additional features and advantages of the invention will be set forth in the description which follows, or in part will be obvious from the description, or may be learned by practice of the invention.

In order to make the above objects, features and advantages of the present invention more comprehensible, preferred embodiments accompanied with figures are described in detail below.

Drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings that are needed in the description of the embodiments or the prior art will be briefly described, and it is obvious that the drawings in the description below are some embodiments of the present invention, and other drawings can be obtained according to the drawings without inventive effort for a person skilled in the art.

FIG. 1 is a flow chart of a multi-robot path planning method provided by an embodiment of the present invention;

FIG. 2 is a schematic diagram of a system architecture according to an embodiment of the present invention;

FIG. 3 is a schematic diagram of a task management layer and a robot management layer according to an embodiment of the present invention;

FIG. 4 is a flowchart of a task allocation method according to an embodiment of the present invention;

fig. 5 is a flowchart of a path planning method according to an embodiment of the present invention;

FIG. 6 is a schematic diagram of a multi-robot path planning test scenario provided by an embodiment of the present invention;

FIG. 7 is a schematic diagram of another multi-robot path planning test scenario provided by an embodiment of the present invention;

FIG. 8 is a schematic diagram of a multi-robot path planning system according to an embodiment of the present invention;

fig. 9 is a schematic structural diagram of an electronic device according to an embodiment of the present invention.

Icon:

The system comprises a map construction module 501, an information acquisition module 502, a task allocation module 503 and a path planning module 504;

101-processor, 102-memory, 103-bus, 104-communication interface.

Detailed Description

For the purpose of making the objects, technical solutions and advantages of the embodiments of the present invention more apparent, the technical solutions of the present invention will be clearly and completely described below with reference to the accompanying drawings, and it is apparent that the described embodiments are some embodiments of the present invention, but not all embodiments. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.

Currently, in an autonomous multi-robot system in the field of automatic AGVs, multi-robot path searching is mainly performed based on a topological map. Wherein, the robot needs to safely and efficiently navigate from a starting point to a target point in a complex environment where dynamic moving objects such as personnel, obstacles and the like exist. This process requires the ability of the robot to predict future dynamic obstacle trajectories to plan short-term target paths while ensuring that path planning does not pose a hazard or inconvenience to personnel. In addition, the robot needs to have a fast path planning capability, and when the actual track of the dynamic obstacle does not accord with the predicted track, a new path plan can be quickly generated so as to avoid collision. The effective path planning capability will significantly improve the adaptability and robustness of the robot to the dynamic environment.

In a multi-robot system, many application scenarios require coordinated navigation of mobile robots in a complex environment, i.e. face multi-robot path search problems.

The related multi-robot path search method mainly depends on the following two ways:

1. The path planning method based on marking the station positions is that the AGV robot is driven to move to the station positions one by one to mark, namely, marking is completed once when one station position is reached. However, this approach is particularly time consuming when the number of stations is large, greatly reducing the efficiency of path planning.

2. The method takes a map constructed by instant positioning and map construction (Simultaneous Localization AND MAPPING, SLAM) as a background, and the topology map of a platform and a route is planned manually in advance, so that the AGV robot runs strictly according to the manually planned route. However, this method limits the flexibility of the AGV, and can only operate according to a preset route, which is difficult to adapt to complex and changeable dynamic environments.

Therefore, the current technology for searching multiple robot paths based on the topological map has a plurality of problems under the conditions of large map scale and complex environment, such as long implementation period, insufficient path drawing precision, often need to be adjusted for multiple times, and in the environment with frequent dynamic changes, the method based on the topological map is difficult to quickly respond and adjust the paths in time.

In order to effectively alleviate at least one of the problems, the method, the system and the electronic equipment for planning the paths of the multiple robots, provided by the embodiment of the invention, realize task allocation and path planning in a complex environment through multi-layer cooperative control, wherein a target map utilized in the path planning process is an interference result of an SLAM map and a point location map, the SLAM map is a finer barrier grid map, the physical space environment can be represented more accurately, and the point location map is convenient for path planning of the multiple robots through a topological result among sites of the point location map. Therefore, the method not only can reduce the implementation cost of multi-robot path planning, but also can improve the accuracy of path planning, and can be rapidly applied to the environment with frequent change, thereby effectively improving the adaptability and the robustness of the AGV system in the complex dynamic environment.

For the sake of understanding the present embodiment, first, a method for planning paths of multiple robots disclosed in the present embodiment is described in detail, where the method is applied to a scenario where multiple robots execute tasks. As shown in fig. 1, a multi-robot path planning method includes the following steps.

And S110, constructing a target map of the physical space environment where the robot is located, wherein the target map is an interference result of the SLAM map and the point location map, and the target map is marked with obstacles in the physical space environment.

Step S120, acquiring task parameters of the task to be allocated and robot state information of a plurality of robots.

Step S130, determining the target task distributed by each robot according to the task parameters and the state information of the robot.

Step S140, planning a target path for executing the target task for each robot based on the target map marked with the obstacle.

For a better understanding of the scheme, the following detailed description of the steps is developed separately.

Referring to fig. 2, the present embodiment provides a system architecture for implementing a multi-robot path planning method, where the system architecture may include a map building layer, an RCS (RobatControl System, robot control system) server, a vehicle-mounted end, and a scheduling system.

In this embodiment, the map building layer is a core base of the system, is a core component of environmental awareness and space modeling in the AGV navigation system, and adopts a single-instance mode to ensure a globally unique instance, and provides unified map data service for processes such as path planning, task scheduling, and the like. The map construction layer can be used for constructing a target map of the physical space environment where the robot is located and sending the target map to the RCS server.

Correspondingly, in one embodiment, the marked obstacles in the target map comprise static obstacles and dynamic obstacles, and the implementation process of constructing the target map of the physical space environment of the robot in step S110 may be divided into construction of a SLAM map, construction of a point location map and interference processing, which are described below.

The construction of the SLAM map comprises the steps of modeling a physical space environment where a robot is located through a laser radar to obtain a rasterized SLAM map, wherein static barriers in the physical space environment are marked in the SLAM map.

In a specific embodiment, a laser radar SLAM technology is used for carrying out rasterization modeling on a physical space environment where a robot is located and static obstacles in the physical space environment, and a SLAM map comprising a distance map and a static obstacle map is generated. The static obstacle refers to an obstacle with a fixed position in a physical space environment, such as a wall, equipment and the like.

In addition, the SLAM map can be processed based on the path planning tool marked by the obstacle, and a more accurate SLAM map is generated through point cloud point complement and denoising operations.

The distance map contained in the SLAM map characterizes the spatial distance (such as euclidean distance in particular) between the robot and the static obstacle in the physical space environment through pixel values, so that the path safety is estimated rapidly. The passable area in the physical space environment can be accurately represented by the distance map.

The static obstacle map contained in the SLAM map is used for identifying a two-dimensional occupation grid of the static obstacle in the physical space environment, and is used as a basic constraint condition of path searching. The distribution of the static barriers in the physical space environment can be accurately represented through the static barrier map

Based on the above, the rasterized SLAM map constructed by the laser radar in this embodiment can accurately represent the distribution and passable area of static obstacles in the physical space environment.

And constructing a point location map, namely analyzing the platform metadata of the platform map corresponding to the physical space environment, and constructing the point location map based on the platform metadata, wherein the platform is marked as a dynamic obstacle in the point location map.

In particular embodiments, the point location map relates primarily to processing of station related data. The embodiment can load a platform map corresponding to a physical space environment, analyze platform metadata in the platform map, and the platform metadata can comprise a plurality of data such as platform ID, type (such as loading and unloading stations and charging stations), geometric dimension and operation rules (such as a dockable vehicle body model and allowed docking time).

Modeling the entrance line of the platform as a virtual path segment according to the platform metadata, storing the starting point coordinates and the end point coordinates of the platform as path nodes, and storing the topological connection relation between the current platform and other platforms, thereby constructing a point location map. Meanwhile, in the point location map, the station is marked as a dynamic obstacle. A dynamic obstacle may be understood as a region occupied by a current station being considered non-passable in a non-task state and passable in a task state, and in particular, when a robot receives a task (e.g., dock handling) involving the current station, an occupancy flag of the region occupied by the current station may be temporarily released by a dynamic obstacle masking mechanism, thereby allowing path planning into the region occupied by the current station.

Through the point location map constructed in the mode, the passable area of the robot can be defined, and the passable area comprises stations, path nodes and topological connection relations. It should be noted that the point map of the present embodiment is only used for planning "point" structures such as platforms, and is not used for directly limiting the driving track of the robot.

And the interference processing is carried out on the SLAM map and the point map to obtain a target map, wherein the interference processing comprises coordinate alignment and space discretization, the target map is stored in a key value pair mode, a key represents grid coordinates, and a value represents the occupation state of a grid and the distance between the key and an obstacle nearest to the grid coordinates.

In this embodiment, the point location map (for logical path network optimization) and the SLAM map (for physical space environment modeling) together constitute a "dual map" infrastructure for multi-robot traversable path search based on obstacle markers.

Based on this, in a specific embodiment, coordinates and obstacles of the SLAM map and the point map are aligned first, and then the aligned SLAM map and point map are converted into an interference map through a spatial discretization algorithm, so as to obtain a target map.

The target map is stored in a hash table. In the hash table, the Key (Key) is a hash Value of the grid coordinates, and the Value (Value) includes the occupancy state of the grid (e.g., free, obstacle) and its distance from the nearest obstacle.

When the robot performs path searching, each path node is expanded, the grid occupation state of the path node needs to be queried from the hash table of the target map. If the occupied state of the grid is marked as an 'obstacle', the expansion of the direction is stopped, and if the occupied state of the grid is marked as a 'free', the distance between the grid and the nearest obstacle is further calculated, and a safety buffer area is generated by combining the radius of the robot body so as to ensure that the path has no collision.

By constructing the target map of the physical space environment where the robot is located through the embodiment, the target map is combined with the SLAM map, so that the physical space environment can be more accurately represented, and meanwhile, the point location map is combined, so that the path planning of multiple robots can be optimized. The accuracy of subsequent path planning can be improved based on the target map, so that the robot can be rapidly applied to the environment with frequent change, and the adaptability and the robustness of the AGV system in the complex dynamic environment are effectively improved.

In conjunction with fig. 2, in this embodiment, the RCS server may be configured to obtain task parameters of a task to be allocated from the scheduling system, and obtain robot state information of a plurality of robots from the vehicle-mounted end.

The RCS server serves as a central control hub of the system and bears the core functions of data integration and instruction distribution. The RCS server may continuously receive real-time robot state information of the robot uploaded by the vehicle-mounted terminal, such as a position of the robot, an electric quantity, sensor data, and the like. And the RCS server can continuously receive the tasks and task parameters thereof issued by the scheduling system, wherein the task parameters comprise the starting point, the ending point, the priority and the like of the tasks. The RCS server receives the robot state information of the vehicle-mounted terminal and the task parameters of the dispatching system, so that the synchronization of global information can be maintained.

The RCS server comprises a state monitoring layer. The state monitoring layer is used for ensuring that the communication reliability of the RCS server side, the scheduling system and the vehicle-mounted side is maintained through a heartbeat mechanism, tracking the running state of the scheduling system (such as abnormal alarm, task progress update and the like) in real time, and feeding back the preset key running state (such as solution loading completion) to the downstream module.

In the embodiment of fig. 2, the scheduling system serves as a global optimizer, and may acquire a target map, task parameters and robot state information from the RCS server, then determine a target task allocated to each robot according to the task parameters and the robot state information, and plan a target path for executing the target task for each robot based on the target map marked with the obstacle, respectively.

After the dispatching system completes the allocation between the tasks and the robots and the planning of the target paths, the target tasks and the target paths are issued to the robots of the vehicle-mounted end through the RCS server. The RCS server side sends instructions on the target tasks and the target paths downwards (i.e. the vehicle-mounted side) and sends the target map to be marked based on the obstacle upwards (i.e. the dispatching system) by the two-way communication closed loop.

In this embodiment, the vehicle-mounted terminal is used as an execution terminal, receives the target task and the target path issued by the RCS server, and drives the robot to move along the target path and execute the target task. Meanwhile, the robot at the vehicle-mounted end senses the change of the physical space environment (such as sudden obstacle) in real time through multi-sensor fusion. Once the path deviation is detected or the target map is updated, the vehicle-mounted terminal immediately triggers local re-planning, and the corrected robot state is returned to the RCS server terminal to form a real-time control loop of perception-decision-execution-feedback.

And along with tasks such as tasks and map updating performed by the robot at the vehicle-mounted end, the scheduling system can also receive feedback information such as task completion or interruption, map updating and the like fed back by the vehicle-mounted end through the RCS server side, so as to form a closed loop optimization mechanism of map updating, strategy generation, task execution and state backtracking.

Through the system architecture comprising the map construction layer, the RCS server side, the vehicle-mounted side and the scheduling system, the data flow process of the whole AGV system when the multi-robot task is executed is described, and the action mechanism of the multi-robot passable path searching algorithm based on the obstacle mark in the whole system is described. And the path planned by the dispatching system is issued to the vehicle-mounted terminal through the RCS server terminal, so that the cooperative task execution of a plurality of robots is realized. The system architecture realizes efficient task scheduling and path planning in a dynamic environment through multi-layer cooperative control, and remarkably improves the adaptability and robustness of the AGV system in a complex dynamic environment.

Next, on the basis of the above system architecture, the present embodiment focuses on the task allocation described in step S130 and the path planning described in step S140.

In the embodiment, the scheduling system is responsible for optimizing global task scheduling and path planning, and the system can comprise a task management layer, a robot management layer, a task distribution layer, a path planning layer, a post-optimization processing layer and a track fitting layer, wherein all the layers are in cooperative work to realize efficient task distribution and path planning.

Referring to fig. 3, the task management layer is a task scheduling center of the scheduling system and is responsible for full life cycle management of tasks, including receiving, canceling, state management, archiving and the like of the tasks. The task management layer can receive a task creation instruction from the RCS server, analyze task parameters in the task creation instruction, and store the task in a task cache area in a scheduling custom format. The task buffer area stores all unfinished tasks and supports quick search and dynamic update. Meanwhile, the task management layer also receives a task cancel instruction, and positions the task according to a task identifier (task_id). If the task is in an 'unprocessed' state, deleting the task from the buffer directly, and if the task is allocated to the robot, informing a robot management layer to release relevant resources of the task and rolling back the task state to an unprocessed state.

The task management layer is also responsible for defining task states including "unprocessed," "allocated," "executing," and "completed," among others. The circulation of tasks at different stages is driven by the state labels. For example, after a task transitions from an "unprocessed" state to an "allocated" state, its associated path information (maintained by shared_ptr shared pointers) will be bound to the target robot. When the task is completed, the task is marked as 'completed' according to feedback information (such as reaching an end point and having zero speed) of the robot, and the task is deleted from the task cache area and archived to a history record.

The robot management layer can be used for monitoring and dynamically scheduling the resources of the AGV cluster, and ensures the efficient utilization of the robot resources and the smooth execution of tasks. The robot management layer can flexibly allocate the robot clusters, such as dynamically robots, deleting robots, managing the robots online or offline, and updating the robot resource pool in real time. When the robot goes offline, the occupied path lock and task resources are released, and reasonable allocation of the resources is ensured. Meanwhile, the robot management layer records real-time robot state information of each robot, such as task path information (such as currently executed path sequence, residual mileage, obstacle avoidance points and the like), task loads (such as ID (identification), priority and execution progress of an allocated task and the like) and running states (such as electric quantity, sensor data and communication states, on-line/off-line states detected through a heartbeat mechanism and the like). The robot management layer monitors and dynamically schedules the resources of the AGV cluster to ensure the efficient utilization of the robot resources and the smooth execution of tasks.

The robot management layer is also used for performing closed-loop management on the tasks. The robot management layer receives the 'allocated task' issued by the task management layer, adds the 'allocated task' into the executing task list, and modifies the task state into 'executing'. When the robot reaches the target point and meets the completion conditions (such as speed return to zero and no instruction to be executed), the task is marked as 'completed', and the task is fed back to the task management layer.

In this embodiment, the task allocation layer may determine, according to the task parameter and the robot state information, a target task allocated to each robot.

Referring to fig. 4, the present embodiment includes:

s301, acquiring a starting point and an ending point of a task to be distributed in the task parameters.

The task allocation layer is a decision engine for matching tasks with the robots and is responsible for intelligent matching and allocation according to the state information and task parameters of the robots. The task allocation layer pulls robot state information of all online robots from the robot management layer, extracts an 'unprocessed' task list from the task management layer, and acquires task parameters of each task to be allocated of the task list, wherein the task parameters at least comprise a starting point and an ending point of the task.

S302, judging whether a passable path from a starting point to an ending point exists in the target map according to the obstacle marked in the target map.

The present embodiment may first verify the reachability of a task from a start point to an end point based on a target map by a dual pre-screening mechanism. If all paths from the start point to the end point are blocked by the obstacle marked in the target map, it is determined that there is no passable path from the start point to the end point in the target map, in which case the status of the task is marked as "unreachable".

If there is a passable path from the start point to the end point in the target map, the following step S303 is performed.

S303, if the target task exists, determining the target task distributed by each robot according to the preset task distribution strategy and the state information and the task parameters of the robot.

Under the condition that a passable path from a starting point to a terminal point exists in a target map, robots matched with the tasks can be screened for the tasks according to the preset task allocation strategy and the state information and the task parameters of the robots, and the screened robots can meet the requirements of the current tasks in the aspects of loading capacity, size limitation, current load and the like. Further, the target task assigned to each robot is determined, or the target robot assigned to each task is determined.

In specific implementation, the task allocation layer may combine the state information (such as idle degree and position) of the robot with the task parameters (such as emergency degree), and allocate the optimal robot to the task through a greedy algorithm or a task allocation strategy such as a load balancing strategy. After successful allocation, the status of the updated task is "allocated", and the task information is written into the execution task list of the vehicle management layer. If task allocation fails (e.g., no robots or paths are available), an alarm is triggered and the upstream system is notified of the intervention.

In addition, the task allocation layer also supports a task preemption mechanism, and the high-priority task can interrupt the execution of the low-priority task.

In the above embodiment, the task management layer, the robot management layer and the task allocation layer cooperate to form a complete task scheduling process. After the task management layer receives the new task, the task allocation layer is responsible for matching a proper robot, and the robot management layer is responsible for binding the task and modifying the state, and then the path is issued to the vehicle-mounted terminal for execution.

Referring to fig. 5, in the present embodiment, a target path for performing a target task may be individually planned for each robot based on a target map marked with an obstacle through a path planning layer, a post-optimization processing layer, and a trajectory fitting layer. The present embodiment includes the following steps S401 to S404.

S401, acquiring a target starting point and a target ending point of a target task to be executed by each robot.

S402, according to ECBS algorithm, a discrete path from a target start point to a target end point is searched for each robot within a range of the target map marked with the obstacle.

In this embodiment, the path planning layer is a core decision layer of the multi-robot system, and is responsible for generating a running track with no space-time conflict, feasible kinematics and optimal efficiency in a dynamic multi-robot environment. The workflow integrates the collaborative search of multiple robots, the action-dependent modeling and the real-time exception handling mechanism.

In embodiments where path preprocessing is implemented through the path planning layer, the full-scale robot state information, including but not limited to pose, speed, kinematic model, and sequence of remaining trajectory points for the current path, may be pulled in real-time from the robot management layer. Meanwhile, the existing path information is extracted and the space-time occupation label (such as a time window of a path segment) is analyzed, so that basic data is provided for subsequent conflict detection.

To facilitate understanding of the scheme, a ECBS (Enhanced Conflict-Based Search, enhanced collision-Based Search) algorithm in this embodiment is first described.

Given a graph g= (V, E) and a set of robots a ₁,a₂,…,a_k, each robot a _i has a start point s _i E V and a target point G _i E V. The task is to plan a path from the start point to the target point for each robot so that there is no collision on the path, i.e. at the same point in time, two robots cannot occupy the same position. At the same time, the total cost of the path is minimized as much as possible.

In this embodiment, a ECBS algorithm is used to perform path planning, and this algorithm is a two-layer search algorithm, where a high layer is responsible for generating Constraint Trees (CT), and a low layer is responsible for searching an optimal path for each robot under Constraint. However, the optimality guarantee of CBS algorithms results in higher computational complexity when the number of robots is high. The ECBS (Enhanced CBS) algorithm allows for sacrificing optimality of solutions over a range by introducing bounded suboptimal search mechanisms in the higher and lower level searches in exchange for faster solution speeds. Specifically, the ECBS algorithm shares a bounded suboptimal factor at the upper and lower layers, thereby dynamically adjusting the flexibility of the upper and lower layers. The design enables ECBS algorithm to obviously improve the solving efficiency of the algorithm on the premise of ensuring that the quality of the solution is different from the optimal solution by not more than omega times.

In high level searches, ECBS algorithm controls the scope of the search by maintaining a FOCAL list, and the nodes in FOCAL list meet the following conditions:

FOCAL={n|n∈OPEN,n.cost≤LB·ω}

where LB is the lowest cost estimate for all nodes in the current OPEN list, ω is a bounded suboptimal factor. In this way, ECBS algorithm ensures that the optimal solution is not deviated too far in the higher level search.

In the lower-layer search, ECBS algorithm also introduces a bounded suboptimal search mechanism, allowing the lower layer to return a path with a cost not exceeding ω times of the optimal solution under constraint. In this way, the ECBS algorithm realizes bounded suboptimal performance in both high-level and low-level searches, so that the solution quality is ensured and the solution efficiency of the algorithm is greatly improved.

Based on the above embodiment, according to ECBS algorithm, a discrete path from the target start point to the target end point is searched for each robot within the range of the target map marked with the obstacle.

S403, performing nonlinear optimization on the discrete paths of each robot to obtain discrete track points.

In multi-robot trajectory planning, nonlinear optimization is a key step in refining discrete paths into smooth and dynamically viable trajectories. The discrete path generated by the discrete path planning stage in step S402, while capable of avoiding obstacles, is typically piecewise linear, including corners, which is not kinetically feasible for mobile robots that are not fully constrained. Thus, nonlinear optimization is used to further refine the path to smooth and conform to the dynamics of the robot.

Wherein the nonlinear optimization problem is defined as follows:

Where N represents the number of robots, H represents the number of sampling points of the discrete path, AndThe state (such as including position and orientation) and control input (such as including linear velocity and angular velocity) of the ith robot at the jth sampling point are represented, respectively. s _i and g _i are the start state and target state, respectively, of the ith robot, f is the nonlinear dynamics model of the robot,Is the safety corridor of the ith robot at the jth sampling point, U _i is the control input constraint of the ith robot, R _i is the collision model radius of the ith robot, and P and Q are weight matrices for adjusting the weights of smoothness and trajectory bias in the optimization objective.

The optimization objective consists of two parts. The first part is to control the difference between the inputs continuously by constraintTo ensure that the control input changes to the trajectory are smooth. The second part is to restrain the deviation between the actual track and the reference track of the robotTo maintain the feasibility of the path. Constraints include boundary conditions, dynamics constraints, safety corridor constraints, control input constraints, and inter-robot collision avoidance constraints. These constraints ensure that the trajectory of each robot starts from a starting state, ends with a target state, and conforms to its nonlinear dynamics model while avoiding collisions with obstacles and other robots in the environment.

In this case, in order to solve the problem of track optimization of a large-scale robot, the present embodiment may perform nonlinear optimization on the discrete path of each robot by using a priority track optimization method to obtain discrete track points, with reference to the following specific details:

The method comprises the steps of determining a robot triplet closest to each robot in a time step based on a discrete path of each robot, grouping the robots according to the occurrence frequency of the robot triplet and distributing priorities to obtain a plurality of robot combinations with priorities, taking each robot combination as a current robot combination one by one according to the priority order, taking an optimized path corresponding to the optimized high-priority robot combination as a collision constraint, and carrying out nonlinear optimization on the discrete path of each robot in the current robot combination to obtain discrete track points.

Specifically, by analyzing the discrete path of each robot, the robot triples which are closer in time step are identified, and the robots are grouped and assigned with priority according to the occurrence frequency of the triples, so as to obtain a plurality of robot combinations with priority.

And optimizing the robot combination with higher priority according to the order of the priorities. In optimizing the trajectory of the current robot combination, the collision avoidance constraints of the combination with the optimized high priority robot need to be considered. Then, the optimized path corresponding to the optimized high-priority robot combination is used as collision constraint, nonlinear optimization is performed on the discrete path of each robot in the current robot combination, IPOPT (Interior Point OPTimizer) can be used as a solver of the nonlinear optimization problem in the process, and the optimized discrete path is refined into smooth and dynamically feasible track point discrete track points, so that collision avoidance and dynamics constraint can be met.

S404, dividing and fitting the discrete track points of each robot to obtain a target path for executing the target task.

The track after nonlinear optimization is composed of a series of discrete track points with fixed time intervals, and in order to further process the discrete track points so as to generate a smoother track which is easy to execute, the embodiment can segment and fit the discrete track points of each robot so as to obtain a target path for executing a target task. The implementation process of the step can comprise the following steps (1) - (3):

(1) Track information of discrete track points is acquired for each robot. Specifically, a set { point ₁,point₂,…,point_n } of discrete track points may be obtained from the nonlinear optimization process, and track information of each discrete track point includes a position, a timestamp, a speed, an angular speed, and the like.

(2) Dividing a plurality of continuous discrete track points with the same positions in the discrete track points into a segmentation group, dividing the discrete track points with different positions in the discrete track points into a plurality of subsections based on an error self-adaptive segmentation algorithm, and fitting each subsection respectively to obtain a track section.

Specifically, when the positions of a plurality of continuous discrete track points are completely identical, the discrete track points are forcedly divided into a divided group. In this case, the robot may be in a waiting state or perform in-situ rotation.

Reasonably dividing discrete track points with inconsistent positions, and performing straight line or Bezier curve fitting on each divided sub-segment to obtain a track segment. In order to achieve smooth fitting of the trajectories, the present embodiment may employ an error-based adaptive segmentation method.

The error-based adaptive segmentation method is to set an error threshold epsilon and gradually increase the fit data points from one end of the set of discrete trajectory points. For each sub-segment, the error of fitting a straight line or a third order Bezier curve is calculated. If the error exceeds the threshold epsilon, the current discrete trajectory point is marked as a segmentation point and the fitting of a new sub-segment is restarted. And determining the optimal starting and ending positions of each sub-segment by gradually increasing the fitted discrete track points, so that the self-adaptive segmentation of the track is realized, and a plurality of sub-segments are obtained. And then, fitting each sub-segment into a straight line or a third-order Bezier curve to obtain a track segment, thereby providing more accurate track description for subsequent path planning and control.

Through the above processing procedure, in this embodiment, the discrete track point after nonlinear optimization is divided into a plurality of subsections, and fitting is performed through a straight line or a bezier curve. The method not only improves the smoothness of the track, but also provides more accurate track description for subsequent path planning and control, thereby obviously improving the navigation performance of the multi-robot system.

(3) And constructing the sequence and the dependency relationship among the track segments to obtain a target path for executing the target task.

In this embodiment, after the segmentation and fitting of the discrete track points are completed, a track dependency graph (Action DEPENDENCY GRAPH, ADG) is further constructed. The track dependency graph is used for describing the sequence and the dependency between track segments and provides important references for subsequent path planning and control. The optimized target path can be effectively managed and issued through the track dependency graph, and the robot can accurately track the preset path in the task execution process.

In one embodiment, the multi-robot path planning method may further include:

And constructing an action dependency graph, wherein the vertexes in the action dependency graph are used for representing actions of the robots, the edges in the action dependency graph are used for representing the dependency relationships among the actions, and controlling the robots to sequentially execute the actions according to the action dependency graph in the process that the robots move according to the respective target paths.

In this embodiment, the action dependency graph may be employed to capture dependencies between robot actions. The action dependency graph is a directed graph in which vertices represent actions of a robot and edges represent dependency relationships between the actions.

Constructing the action dependency graph includes creating a vertex and a first directed edge, adding a second directed edge.

Wherein in embodiments where vertices and first directed edges are created, each action of each robot (including moving, turning, lifting shelves, etc.) is represented as one vertex in the action dependency graph. For each robot, the continuous actions are connected by adopting a first directed edge, and the first directed edge represents the action sequence of the same robot, so that the robot can execute the next action after one action is completed.

In embodiments where a second directed edge is added, the second directed edge is used to represent the action dependency between different robots. If the action of one robot needs to be started after the action of the other robot is completed, a second directed edge is added between the two actions. For example, if robot a needs to pass through a channel and robot B is moving in the channel, the entering action of robot a needs to be performed after the exiting action of robot B is completed, so a second directed edge is added between the entering action of robot a and the exiting action of robot B.

In the action execution stage, each vertex (i.e., action) of the action dependency graph has three states, namely:

Staged, representing that the action is ready but has not yet joined the execution queue;

enqueued indicating that the action has been added to the execution queue and waiting for execution;

Finish indicates that the action has been completed.

The execution process of the action dependency graph manages the execution order of actions by tracking the state of each vertex. An action is added to the execution queue only after all dependent actions of the action (predecessor actions connected by the first directed edge and the second directed edge) are completed. In this way, the action dependency graph can ensure that the robot completes actions according to the planned sequence in the actual execution task, and collision can be avoided even if time delay or dynamic change exists.

In order to achieve seamless connection of planning and execution in a dynamic environment, the embodiment can introduce a Commit Cut mechanism. The Commit Cut mechanism is a mechanism for determining the last action set that the robot must complete before switching to a new target task, and the core idea is to allow the robot to continue to execute part of actions in the current target task when re-planning, so as to avoid stagnation caused by waiting for the new target task.

Based on the Commit Cut mechanism, the multi-robot path planning method provided by the embodiment may further include:

firstly, under the condition that the robot is simultaneously distributed with a plurality of target tasks, the expected action of the robot in the current target task is obtained, wherein the residual execution time of the expected action is longer than the preset planning time.

And secondly, constructing a reverse action dependency graph, and executing reachability search on the expected action in the reverse action dependency graph to obtain an action set to be completed by the robot before switching to a new target task. Illustratively, a reachability search is performed in the reverse-action dependency graph to find all reachable actions that constitute the set of actions Committed Vertices that the robot must complete before switching to the new target task.

Next, a last stop action performed by the robot is determined in action set Committed Vertices, which forms a command Cut.

After determining the stop action Commit Cut, the robot continues to execute the action in the current target task until the stop action Commit Cut is completed, and starts to execute a new target task. Specifically, after the robot finishes the stop action Commit Cut, a new target task is started according to the state after the stop action Commit Cut is finished.

Through the Commit Cut mechanism in the embodiment, the robot can start a new target task in advance while executing a current target task, thereby realizing the durability of the system.

Based on the action dependency graph and the Commit Cut mechanism adopted by the embodiment, the method provides a guarantee of robustness and durability for practical application of multi-robot path planning. The action dependency graph ensures that the robot completes actions according to the planned sequence in actual execution by capturing the dependency among actions, and the Commit Cut mechanism ensures the continuous operation capability of the AGV system in a dynamic environment by allowing the overlapping of planning and execution. The method not only improves the robustness and efficiency of the AGV system, but also reduces the communication requirement between robots, and provides important technical support for the actual deployment of the multi-robot system.

In order to verify the adaptability and robustness of the multi-robot path planning method provided by the embodiment in a complex dynamic environment, the embodiment performs a test in an actual scene. As shown in fig. 6 and 7, the present embodiment takes a long corridor area and multiple robots (e.g., < 15) as examples of a test scenario.

As can be observed from fig. 6, in a test scenario of a long corridor area, two robots initially travel in the same direction along the same path. When the first robot reaches a predetermined lane change point and performs lane change operation, it does not block the travel route of the second robot any more, so that the two robots can continue to travel in the same direction on different paths. The path planning strategy effectively avoids direct collision among robots and improves the running efficiency. As the first robot approaches the target point, it travels along a bezier curve, a smooth curve commonly used for path planning, which ensures that the robot reaches the end point smoothly. At the same time, the second robot continues to travel along a straight path without being affected by the first robot lane change or curved travel.

The whole test process shows the effectiveness of the path planning algorithm in processing the dynamic path planning problem in the multi-robot environment. Through reasonable planning of the lane change points and the running tracks, the algorithm can ensure that the robot runs safely and efficiently in a limited space, and meanwhile, potential traffic collision is reduced. This test result is significant for optimizing path planning strategies in a multi-robot system.

Referring to the multi-robot path planning test shown in fig. 7, it can be observed from fig. 7 that the present embodiment performs multi-robot passable path search based on obstacle markers in the case of 10 robots, and the 10 robots work cooperatively, demonstrating path planning capability in a complex environment. The test scenario simulates the collaborative work situation of multiple robots that may be encountered in practical applications, including the running of robots in long aisles, intersections, and narrow aisles.

In the test process, the robot needs to effectively avoid static obstacles and dynamic obstacles while keeping a safe distance. In fig. 7, the robot successfully realizes navigation and obstacle avoidance in different areas through accurate path planning. Particularly in long corridor areas, the robots avoid collision among the robots by coordinating respective running routes, and ensure the smoothness of traffic flow. In addition, fig. 7 also shows the path adjustment capability of the robot when approaching the target point. By dynamically adjusting the travel path, the robot can adapt to changes in the environment, such as movements of other robots or suddenly appearing obstacles, so as to safely and accurately reach the destination.

These test results verify the effectiveness and robustness of the multi-robot path planning method proposed by the present embodiment in handling high density traffic flows. The method not only improves the path planning efficiency, but also enhances the adaptability of the robot in a dynamic environment, and provides technical support for practical deployment of the multi-robot system.

In summary, the multi-robot path planning method provided by the embodiment of the invention comprises the steps of firstly constructing a target map of a physical space environment where a robot is located, wherein the target map is an interference result of a SLAM map and a point map, wherein obstacles in the physical space environment are marked in the target map, secondly acquiring task parameters of tasks to be distributed and robot state information of a plurality of robots, determining a target task distributed by each robot according to the task parameters and the robot state information, and then planning a target path for executing the target task for each robot based on the target map marked with the obstacles.

The embodiment of the present invention provides a multi-robot path planning system, as shown in fig. 8, corresponding to the above embodiment of the method, the system includes the following modules:

The map construction module 501 is used for constructing a target map of a physical space environment where the robot is located, wherein obstacles in the physical space environment are marked in the target map;

the information acquisition module 502 is configured to acquire task parameters of a task to be allocated and robot state information of a plurality of robots;

A task allocation module 503, configured to determine, according to the task parameters and the robot state information, a target task allocated by each robot;

A path planning module 504, configured to plan, for each robot, a target path for executing the target task based on the target map marked with the obstacle.

In some embodiments, the obstacles include static obstacles and dynamic obstacles, and the map construction module 501 includes:

In some embodiments, the task allocation module 503 includes:

In some embodiments, the path planning module 504 includes:

The acquisition unit is used for acquiring a target starting point and a target ending point of the target task to be executed by each robot;

A search unit for searching for a discrete path from a target start point to the target end point for each of the robots within a range of the target map marked with an obstacle according to an enhanced collision-based search ECBS algorithm;

The optimizing unit is used for carrying out nonlinear optimization on the discrete paths of each robot to obtain discrete track points;

and the segmentation and fitting unit is used for carrying out segmentation and fitting on the discrete track points of each robot to obtain a target path for executing the target task.

In some embodiments, the optimization unit comprises:

In some embodiments, the segmentation and fitting unit comprises:

fitting each subsection respectively to obtain a track section;

In some embodiments, the system further comprises a first action execution control module for:

In some embodiments, the system further comprises a second action execution control module for:

determining a stopping action executed last by the robot in the action set;

The multi-robot path planning system provided by the embodiment has the same technical characteristics as the multi-robot path planning method provided by the embodiment, so that the same technical problems can be solved, and the same technical effects can be achieved. For a brief description, reference may be made to the corresponding content of the aforementioned embodiments of the multi-robot path planning method, where the embodiments are not mentioned.

The embodiment also provides an electronic device, the schematic structural diagram of which is shown in fig. 9, where the device includes a processor 101 and a memory 102, where the memory 102 is configured to store one or more computer instructions, and the one or more computer instructions are executed by the processor, so as to implement the multi-robot path planning method.

The electronic device shown in fig. 9 further comprises a bus 103 and a communication interface 104, the processor 101, the communication interface 104 and the memory 102 being connected by the bus 103.

The memory 102 may include a high-speed random access memory (RAM, random Access Memory), and may further include a non-volatile memory (non-volatile memory), such as at least one disk memory. Bus 103 may be an ISA bus, a PCI bus, an EISA bus, or the like. The buses may be classified as address buses, data buses, control buses, etc. For ease of illustration, only one bi-directional arrow is shown in fig. 9, but not only one bus or one type of bus.

The communication interface 104 is configured to connect with at least one user terminal and other network units through a network interface, and send the encapsulated IPv4 message or the IPv4 message to the user terminal through the network interface.

The processor 101 may be an integrated circuit chip with signal processing capabilities. In implementation, the steps of the above method may be performed by integrated logic circuits of hardware in the processor 101 or instructions in the form of software. The Processor 101 may be a general-purpose Processor, including a central processing unit (Central Processing Unit, CPU), a network Processor (Network Processor, NP), a digital signal Processor (DIGITAL SIGNAL Processor, DSP), an Application Specific Integrated Circuit (ASIC), a Field-Programmable gate array (FPGA) or other Programmable logic device, discrete gate or transistor logic device, or discrete hardware components. The various methods, steps and logic blocks of the disclosure in the embodiments of the disclosure may be implemented or performed. A general purpose processor may be a microprocessor or the processor may be any conventional processor or the like. The steps of a method disclosed in connection with the embodiments of the present disclosure may be embodied directly in hardware, in a decoded processor, or in a combination of hardware and software modules in a decoded processor. The software modules may be located in a random access memory, flash memory, read only memory, programmable read only memory, or electrically erasable programmable memory, registers, etc. as well known in the art. The storage medium is located in the memory 102, and the processor 101 reads information in the memory 102, and in combination with its hardware, performs the steps of the method of the previous embodiment.

The embodiment of the invention also provides a readable storage medium, wherein a computer program is stored on the readable storage medium, and the computer program executes the steps of the multi-robot path planning method in the previous embodiment when being executed by a processor.

In the several embodiments provided by the present application, it should be understood that the disclosed systems, devices, and methods may be implemented in other manners. The above-described apparatus embodiments are merely illustrative, for example, the division of the units is merely a logical function division, and there may be other manners of division in actual implementation, and for example, multiple units or components may be combined or integrated into another system, or some features may be omitted, or not performed. Alternatively, the coupling or direct coupling or communication connection shown or discussed with each other may be through some communication interface, indirect coupling or communication connection of devices or units, electrical, mechanical, or other form.

The units described as separate units may or may not be physically separate, and units shown as units may or may not be physical units, may be located in one place, or may be distributed on a plurality of network units. Some or all of the units may be selected according to actual needs to achieve the purpose of the solution of this embodiment.

In addition, each functional unit in the embodiments of the present invention may be integrated in one processing unit, or each unit may exist alone physically, or two or more units may be integrated in one unit.

The functions, if implemented in the form of software functional units and sold or used as a stand-alone product, may be stored in a non-volatile computer readable storage medium executable by a processor. Based on this understanding, the technical solution of the present invention may be embodied essentially or in a part contributing to the prior art or in a part of the technical solution in the form of a software product stored in a storage medium, comprising several instructions for causing a computer device (which may be a personal computer, a server, a network device, etc.) to perform all or part of the steps of the method according to the embodiments of the present invention. The storage medium includes a U disk, a removable hard disk, a Read-Only Memory (ROM), a random access Memory (RAM, random Access Memory), a magnetic disk, an optical disk, or other various media capable of storing program codes.

It should be noted that the foregoing embodiments are merely illustrative embodiments of the present invention, and not restrictive, and the scope of the invention is not limited to the embodiments, and although the present invention has been described in detail with reference to the foregoing embodiments, it should be understood by those skilled in the art that any modification, variation or substitution of some of the technical features of the embodiments described in the foregoing embodiments may be easily contemplated within the scope of the present invention, and the spirit and scope of the technical solutions of the embodiments do not depart from the spirit and scope of the embodiments of the present invention. Therefore, the protection scope of the present invention shall be subject to the protection scope of the claims.

Claims

1. A multi-robot path planning method, characterized in that the method comprises the following steps:

Constructing a target map of the physical space environment where the robot is located; wherein the target map is the interference result of the SLAM map and the point map, and obstacles in the physical space environment are marked in the target map;

Obtaining task parameters of tasks to be assigned and robot status information of multiple robots;

Determining a target task assigned to each of the robots according to the task parameters and the robot status information;

Based on the target map with obstacles marked, a target path for each robot to perform the target task is planned respectively.

2. The method according to claim 1, wherein the obstacles include static obstacles and dynamic obstacles; and constructing a target map of the physical space environment in which the robot is located comprises:

Modeling the physical space environment where the robot is located by using a laser radar to obtain a rasterized SLAM map; wherein the static obstacles in the physical space environment are marked in the SLAM map;

Parsing the platform metadata of the platform map corresponding to the physical space environment, and constructing a point map based on the platform metadata; wherein the platform is marked as a dynamic obstacle in the point map;

Interference processing is performed on the SLAM map and the point map to obtain a target map; wherein the interference processing includes: coordinate alignment and spatial discretization; the target map is stored in the form of key-value pairs, where the key represents the grid coordinate and the value represents the occupancy state of the grid and the distance to the nearest obstacle to the grid mark.

3. The method according to claim 1, wherein determining the target task assigned to each robot based on the task parameters and the robot status information comprises:

Get the starting point and end point of the task to be assigned in the task parameters,

Determining whether there is a navigable path from the starting point to the end point in the target map according to the obstacles marked in the target map;

If so, the target task assigned to each robot is determined through a preset task assignment strategy and according to the robot state information and the task parameters.

4. The method according to claim 1, wherein planning a target path for each robot to perform the target task based on the target map marked with obstacles comprises:

Obtaining a target starting point and a target end point of the target task to be performed by each robot;

According to the enhanced collision-based search (ECBS) algorithm, within the range of the target map marked with obstacles, searching for a discrete path from the target starting point to the target end point for each of the robots;

performing nonlinear optimization on the discrete path of each robot to obtain discrete trajectory points;

The discrete trajectory points of each robot are segmented and fitted to obtain a target path for executing the target task.

5. The method according to claim 4, wherein the performing nonlinear optimization on the discrete path of each robot to obtain an optimized path comprises:

Based on the discrete path of each robot, determining a robot triplet with the shortest distance within a time step;

Grouping and assigning priorities to the robots according to the frequencies of occurrence of the robot triples to obtain a plurality of robot combinations with priorities;

According to the order of priority, each of the robot combinations is used as the current robot combination;

The optimized path corresponding to the optimized high-priority robot combination is used as a collision constraint, and nonlinear optimization is performed on the discrete paths of the robots in the current robot combination to obtain an optimized path.

6. The method according to claim 4, wherein the segmenting and fitting of the discrete trajectory points of each robot to obtain a target path for executing the target task comprises:

For each of the robots, obtaining trajectory information of the discrete trajectory points; wherein the trajectory information at least includes: position;

Dividing multiple continuous discrete trajectory points with the same position among the discrete trajectory points into a segmentation group;

An error-based adaptive segmentation algorithm is used to divide discrete trajectory points with different positions among the discrete trajectory points into a plurality of sub-segments;

Fitting each of the sub-segments respectively to obtain a trajectory segment;

The sequence and dependency relationship between the trajectory segments are constructed to obtain a target path for executing the target task.

7. The method according to claim 1, further comprising:

Constructing an action dependency graph; wherein the vertices in the action dependency graph are used to represent the actions of the robot, and the edges in the action dependency graph are used to represent the dependency relationships between the actions;

During the process of each robot moving along its own target path, each robot is controlled to perform actions sequentially according to the action dependency graph.

8. The method according to claim 1, further comprising:

When the robot is assigned a plurality of target tasks at the same time, obtaining an expected action of the robot in the current target task; wherein the remaining execution time of the expected action is greater than a preset planning time;

Constructing a reverse action dependency graph, and performing a reachability search on the desired action in the reverse action dependency graph to obtain a set of actions to be completed by the robot before switching to a new target task;

Determining the last stop action performed by the robot in the action set;

The robot continues to execute the actions in the current target task until the stop action is completed, and then starts to execute the new target task.

9. A multi-robot path planning system, characterized in that the system includes the following modules:

A map construction module is used to construct a target map of the physical space environment where the robot is located; wherein obstacles in the physical space environment are marked in the target map;

An information acquisition module, used to obtain task parameters of the task to be assigned and robot status information of multiple robots;

A task assignment module, configured to determine a target task assigned to each robot based on the task parameters and the robot status information;

A path planning module is used to plan a target path for each robot to perform the target task based on the target map marked with obstacles.

10. An electronic device, characterized in that it comprises: a processor and a storage device; the storage device stores a computer program, and when the computer program is executed by the processor, it implements the steps of the multi-robot path planning method according to any one of claims 1 to 8.