Path planning for mobile machine in large scale navigation

Patent metadata

Field	Value
Publication number	US-12474171-B2
Application number	US-202418407494-A
Country	US
Kind code	B2
Filing date	Jan 9, 2024
Priority date	Jan 9, 2024
Publication date	Nov 18, 2025
Grant date	Nov 18, 2025

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 computer-implemented method for planning a path between a start point and a goal point for a mobile machine, comprising:
determining, by a processor of the mobile machine, based on a current position of the mobile machine, the start point in the path; determining, by the processor, 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, by the processor, whether the start map node and the goal map node correspond to the same submap; planning, by the processor, 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, by the processor, 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; and controlling, by the processor, the mobile machine to move according to the path; wherein obtaining, by the processor, the path between the start point and the goal point includes: planning, by the processor using a graph search algorithm, the node path between the start map node and the goal map node; and wherein obtaining, by the processor, the path between the start point and the goal point further includes: planning, by the processor, 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.

2 . The method of claim 1 , wherein the real-time path is planned using the real-time path planning method.

3 . The method of claim 1 , wherein obtaining, by the processor, the path between the start point and the goal point further includes:
planning, by the processor using the real-time path planning method, the first real-time path between the start point and the first stop point; planning, by the processor using the real-time path planning method, the second real-time path between the goal point and the last stop point; and obtaining, by the processor, 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.

4 . The method of claim 1 , wherein, before obtaining, by the processor, the path between the start point and the goal point, the method further comprises:
establishing, by the processor, an edge between the map nodes corresponding to the same stop point.

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

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

7 . 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.

8 . The method of claim 1 , wherein the method further comprises:
providing the mobile machine, wherein the mobile machine further includes an inertial measurement unit electrically coupled to the processor; and wherein determining, by the processor of the mobile machine, based on the current position of the mobile machine, the start point in the path includes: collecting, by the inertial measurement unit, data; and obtaining, by the processor, the current position of the mobile machine by estimating using the data collected by the inertial measurement unit, and using the current position of the mobile machine as the start point in the path.

9 . 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; 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; and
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.

10 . The method of claim 9 , wherein the real-time path is planned using the real-time path planning method.

11 . The method of claim 9 , 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.

12 . The method of claim 9 , wherein determining, based on the current position of the mobile machine, the start point in the path includes:
obtaining the current position of the mobile machine by estimating using data collected by an inertial measurement unit of the mobile machine, and using the current position of the mobile machine as the start point in the path.

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

14 . The method of claim 13 , wherein the method further comprises:
dividing the facility map into areas based on the departmental medic

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/38

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

• G01C21/383

  Indoor data · CPC title

• G01C21/206 Primary

  specially adapted for indoor navigation · CPC title