US Patent Application 17827602. MULTI-AGENT PATH PLANNING METHOD AND DEVICE, AND STORAGE MEDIUM simplified abstract

From WikiPatents
Jump to navigation Jump to search

MULTI-AGENT PATH PLANNING METHOD AND DEVICE, AND STORAGE MEDIUM

Organization Name

Tencent America LLC

Inventor(s)

Xifeng Gao of TALLAHASSEE FL (US)

Zherong Pan of Palo Alto CA (US)

MULTI-AGENT PATH PLANNING METHOD AND DEVICE, AND STORAGE MEDIUM - A simplified explanation of the abstract

This abstract first appeared for US patent application 17827602 titled 'MULTI-AGENT PATH PLANNING METHOD AND DEVICE, AND STORAGE MEDIUM

Simplified Explanation

- The patent application describes a method for multi-agent path planning. - The method involves generating a 2D floor plan of a space and optimizing it to find a target mesh that maximizes a metric function. - The metric function takes into account the number of agents that the mesh can hold and the number of agents in the largest connected component of the graph corresponding to the mesh. - The target mesh is then converted into a target graph, where each vertex represents a position for an agent and each edge represents a possible path for an agent to travel on. - Paths are planned for multiple agents based on their origins, destinations, and the graph, ensuring that the agents do not collide with each other.


Original Abstract Submitted

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.