Multi-agent path planning method and device, and storage medium
US12045939B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | May 27, 2022 |
| Grant date | Jul 23, 2024 |
| Priority date | — |
| Expiry date | Jan 12, 2043 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T2210/21
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A multi-agent path planning method is provided. The method includes: generating an initial mesh of a 2D floor plan of a space; optimizing the initial mesh to find a target mesh maximizing a value of a metric function, the metric function including a term reflecting a number of agents that a graph corresponding to a candidate mesh can hold and a term reflecting a number of agents in a largest connected component of the graph corresponding to the candidate mesh, the candidate mesh being a mesh; converting the target mesh into a target graph, each vertex of the target graph representing a position that an agent can reside at, and each edge of the target graph representing a path that an agent can travel on; and planning paths for the plurality of agents according to origins and destinations of the agents and the graph, wherein the agents traveling on the planned paths do not collide with each other.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.