Path planning for mobile machine in large scale navigation

Patent metadata

Field	Value
Publication number	US-2025224235-A1
Application number	US-202418407494-A
Country	US
Kind code	A1
Filing date	Jan 9, 2024
Priority date	Jan 9, 2024
Publication date	Jul 10, 2025
Grant date	—

Abstract

Path planning for mobile machine in large scale navigation disclosed. A path for moving a mobile machine is planned by: determining a start map node in a map graph based on a start point in the path and a goal map node in the map graph based on a goal point in the path; determining whether the start map node and the goal map node correspond to the same submap; and if so, planning the path between the start point and the goal point using a real-time path planning method; otherwise, obtaining the path between the start point and the goal point by merging a node path between the start map node and the goal map node, a first real-time path between the start point and a first stop point, and a second real-time path between the goal point and a last stop point.

First claim

What is claimed is:

1 . A method for planning a path between a start point and a goal point for a mobile machine, comprising:
determining, based on a current position of the mobile machine, the start point in the path; determining a start map node among a plurality of map nodes in a map graph based on the start point in the path and a goal map node among the plurality of map nodes in the map graph based on the goal point in the path, wherein each of the map nodes corresponds to each of a plurality of submaps partitioned from a facility map; determining whether the start map node and the goal map node correspond to the same submap; planning the path between the start point and the goal point using a real-time path planning method, in response to the start map node and the goal map node corresponding to the same submap; and obtaining the path between the start point and the goal point by merging a node path between the start map node and the goal map node, a first real-time path between the start point and a first stop point connecting the adjacent submaps between the start point and the goal point, and a second real-time path between the goal point and a last stop point connecting the adjacent submaps between the goal point and the start point, in response to the start map node and the goal map node not corresponding to the same submap.

2 . The method of claim 1 , wherein the node path is planned using a graph search algorithm and the real-time path is planned using the real-time path planning method.

3 . The method of claim 1 , wherein obtaining the path between the start point and the goal point includes:
planning, using a graph search algorithm, the node path between the start map node and the goal map node.

4 . The method of claim 3 , wherein obtaining the path between the start point and the goal point further includes:
planning, based on a pre-planned path, the node path in each of the submaps except the submap corresponding to the start point and the submap corresponding to the goal point.

5 . The method of claim 4 , wherein obtaining the path between the start point and the goal point further includes:
planning, using the real-time path planning method, the first real-time path between the start point and the first stop point; planning, using the real-time path planning method, the second real-time path between the goal point and the last stop point; and obtaining the path between the start point and the goal point by merging the node path, the first real-time path, and the second real-time path.

6 . The method of claim 1 , wherein an edge is established between the map nodes corresponding to the same stop point.

7 . The method of claim 6 , wherein each of the edge has a cost representing one of connectivity, physical distance, and traffic density.

8 . The method of claim 1 , wherein the stop point corresponds to one of an entrance, a corridor, an elevator, and a nurse station.

9 . The method of claim 1 , wherein the facility map is for a health care institution, and the submaps are partitioned from the facility map based on departmental medical functions.

10 . A method for navigating a mobile machine according to a path between a start point and a goal point, comprising:
determining, based on a current position of the mobile machine, the start point in the path; determining a start map node among a plurality of map nodes in a map graph based on the start point in the path and a goal map node among the plurality of map nodes in the map graph based on the goal point in the path, wherein each of the map nodes corresponds to each of a plurality of submaps partitioned from a facility map; determining whether the start map node and the goal map node correspond to the same submap; planning the path between the start point and the goal point using a real-time path planning method, in response to the start map node and the goal map node corresponding to the same submap; obtaining the path between the start point and the goal point by merging a node path between the start map node and the goal map node, a first real-time path between the start point and a first stop point connecting the adjacent submaps between the start point and the goal point, and a second real-time path between the goal point and a last stop point connecting the adjacent submaps between the goal point and the start point, in response to the start map node and the goal map node not corresponding to the same submap; moving the mobile machine according to the path; determining whether the mobile machine has arrived the goal point or not; and returning to determining, based on the current position of the mobile machine, the start point in the path between the start point and the goal point, in response to the robot having not arrived the goal point.

11 . The method of claim 10 , wherein the node path is planned using a graph search algorithm and the real-time path is planned using the real-time path planning method.

12 . The method of claim 10 , wherein obtaining the path between the start point and the goal point includes:
planning, using a graph search algorithm, the node path between the start map node and the goal map node.

13 . The method of claim 12 , wherein obtaining the path between the start point and the goal point further includes:
planning, based on a pre-planned path, the node path in each of the submaps except the submap corresponding to the start point and the submap corresponding to the goal point.

14 . The method of claim 13 , wherein obtaining the path between the start point and the goal point further includes:
planning, using the real-time path planning method, the first real-time path between the start point and the first stop point; planning, using the real-time path planning method, the second real-time path between the goal point and the last stop point; and obtaining the path between the start point and the goal point by merging the node path, the first real-time path, and the second real-time path.

15 . A mobile machine, comprising:
one or more processors; and one or more memories storing one or more programs configured to be executed by the one or more processors, wherein the one or more programs comprise instructions to: determine, based on a current position of the mobile machine, a start point in a path; determine a start map node among a plurality of map nodes in a map graph based on the start point in the path and a goal map node among the plurality of map nodes in the map graph based on a goal point in the path, wherein each of the map nodes corresponds to each of a plurality of submaps partitioned from a facility map; determine whether the start map node and the goal map node correspond to the same submap; plan the path between the start point and the goal point using a real-time path planning method, in response to the start map node and the goal map node corresponding to the same submap; obtain the path between the start point and the goal point by merging a node path between the start map node and the goal map node, a first real-time path between the start point and a first stop point connecting the adjacent submaps between the start point and the goal point, and a second real-time path between the goal point and a last stop point connecting the adjacent submaps between the goal point and the start point, in response to the start map node and the goal map node not corresponding to the same submap; move the mobile machine according to the path; determine whether the mobile machine has arrived the goal point or not; and return to determining, base

Assignees

• Futronics Na Corp
• Ubtech Robotics Corp Ltd

Inventors

• Du Huaguang
• Liu Zhipeng
• Zhao Fangyun
• Zhang Chengkun
• Tan Huan

Classifications

• G01C21/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/343 Primary

  Calculating itineraries (travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047) · CPC title

• G01C21/383

  Indoor data · CPC title

• G01C21/206 Primary

  specially adapted for indoor navigation · CPC title

• G01C21/38

  Electronic maps specially adapted for navigation; Updating thereof · CPC title