公开(公告)号：US20250103653A1

公开(公告)日：2025-03-27

申请号：US18494671

申请日：2023-10-25

Applicant: POSTECH Research and Business Development Foundation

Inventor： Hee Kap AHN ,  Hyo Jeong AN ,  Mook Kwon JUNG ,  Tae Kang EOM ,  Hwi KIM

IPC: G06F16/901

Abstract: Disclosed are embodiments of shortest path search in an obstacle environment. Provided is a shortest path search method including: creating an epsilon graph; and determining k closest points from a query point on the basis of the graph, wherein the creating of the graph includes: creating a node group of nodes on the basis of a point group of arrival points; creating an edge group of edges on the basis of the created nodes; setting, on the basis of an obstacle group of at least one obstacle, whether each of the nodes is a valid node or a non-valid node; setting, on the basis of the obstacle group, whether each of the edges is a valid or non-valid edge; and including, for each of the arrival points, a particular arrival point on an anchor list of a valid node closest from the particular arrival point among the valid nodes.