US-12619257-B2 - Waypoint graph generation for route planning using semantic map information

Abstract

In various examples, a technique for generating a route plan is disclosed that includes receiving a semantic map that represents a physical environment. The technique further includes generating a route graph based at least on the semantic map, where the route graph includes one or more route graph edges, wherein each route graph edge has an associated location in one or more map regions of the semantic map and an associated cost. The technique also includes determining a cost of a particular graph edge based at least on a region type, where the region type is determined based at least on a map region in which the particular route graph edge is located. The technique further includes generating, using the route graph, a route plan for a mobile robot to move from a given start location on the semantic map to a given destination location on the semantic map.

Inventors

• Ju-Hsuan HUA
• Soha POUYA

Assignees

• NVIDIA CORPORATION

Dates

Publication Date

20260505

Application Date

20240126

Claims (20)

1. 1 . A method, comprising: receiving, at a computing device, a semantic map that represents a physical environment; generating a route graph based at least on the semantic map, the route graph including one or more route graph edges each including an associated location in one or more map regions of the semantic map; determining a cost of a particular route graph edge of the route graph edges based at least on a region type of the particular route graph edge, the region type being determined based at least on a map region in which the particular route graph edge is located; determining, using the route graph, a plurality of edges that form a route plan for a mobile robot to move from a first location on the semantic map to a second location on the semantic map, the plurality of edges including the particular route graph edge and selected based at least on a cumulative cost computed as a weighted sum based at least on region types of map regions traversed by the plurality of edges and corresponding edge lengths, the mobile robot configured to navigate through at least a portion of the physical environment based on at least the route plan.
2. 2 . The method of claim 1 , wherein each point of a plurality of points on the particular route graph edge is located at a respective determined distance from each of two or more boundary lines of the map region in which the particular route graph edge is located.
3. 3 . The method of claim 2 , wherein the respective determined distance is an equal distance from each of the two or more boundary lines of the map region in which the particular route graph edge is located.
4. 4 . Method of claim 1 , wherein the region type of the particular route graph edge corresponds to a numeric value, and the cost of the particular route graph edge is determined based at least on the numeric value.
5. 5 . The method of claim 4 , wherein the cost of the particular route graph edge is further determined based at least on a product of the numeric value of the region type and a length associated with the particular route graph edge.
6. 6 . The method of claim 5 , wherein the length associated with the particular route graph edge corresponds to a length represented by the particular route graph edge in the map region in which the particular route graph edge is located.
7. 7 . The method of claim 4 , wherein the numeric value is proportional to a speed limit associated with the region type.
8. 8 . The method of claim 1 , further comprising determining a cost of a path that includes a plurality of route graph edges by: determining a weighted sum of a plurality of edge lengths, wherein each respective edge length is a length of a respective route graph edge of the plurality of route graph edges, and each respective edge length is weighted in the weighted sum by a respective numeric value determined based at least on a respective region type associated with the respective route graph edge.
9. 9 . The method of claim 1 , wherein the route graph represents one or more routes through the map regions of the semantic map.
10. 10 . The method of claim 1 , wherein each route graph edge is at least a threshold distance from each boundary of each map region of the semantic map, and the threshold distance corresponds to a predetermined distance between the location of the mobile robot and the location of the boundary.
11. 11 . The method of claim 1 , wherein each map region represents a portion of the environment that is reachable by the mobile robot.
12. 12 . The method of claim 1 , wherein the route graph further includes a plurality of route graph vertices, wherein each route graph edge connects a respective first route graph vertex located at a respective first endpoint of the respective route graph edge to a respective second route graph vertex located at a respective second endpoint of the respective route graph edge.
13. 13 . The method of claim 1 , further comprising: generating a waypoint graph that includes a plurality of waypoint graph edges and a plurality of waypoint graph vertices, each waypoint graph edge corresponding to a respective route graph edge of the one or more route graph edges, and each waypoint graph vertex corresponding to a respective route graph vertex.
14. 14 . One or more processors comprising: processing circuitry to perform operations comprising: receiving a semantic map that represents a physical environment; generating a route graph based at least on the semantic map, the route graph including one or more route graph edges including associated locations in one or more map regions of the semantic map and associated costs; determining a cost of a particular route graph edge of the route graph edges based at least on a region type of the particular route graph edge, the region type being determined based at least on a map region in which the particular route graph edge is located; determining, using the route graph, a plurality of edges that form a route plan for a mobile robot to move from a first location on the semantic map to a second location on the semantic map, the plurality of edges including the particular route graph edge and selected based at least on a cumulative cost computed as a weighted sum based at least on region types of map regions traversed by the plurality of edges and corresponding edge lengths, the mobile robot configured to navigate through at least a portion of the physical environment based on at least the route plan.
15. 15 . The one or more processors of claim 14 , wherein each point of a plurality of points on the particular route graph edge is located at a respective determined distance from each of two or more boundary lines of the map region in which the particular route graph edge is located.
16. 16 . The one or more processors of claim 15 , wherein the respective determined distance is an equal distance from each of the two or more boundary lines of the map region in which the particular route graph edge is located.
17. 17 . The one or more processors of claim 14 , wherein the one or more processors is comprised in at least one of: a control system for an autonomous or semi-autonomous machine; a perception system for an autonomous or semi-autonomous machine; a system for performing simulation operations; a system for performing digital twin operations; a system for performing light transport simulation; a system for performing collaborative content creation for 3D assets; a system for performing deep learning operations; a system implemented using an edge device; a system for generating or presenting at least one of virtual reality content, augmented reality content, or mixed reality content; a system implemented using a robot; a system for performing conversational AI operations; a system for performing one or more generative AI operations; a system implementing one or more large language models (LLMs); a system for generating synthetic data; a system incorporating one or more virtual machines (VMs); a system implemented at least partially in a data center; or a system implemented at least partially using cloud computing resources.
18. 18 . A system comprising: one or more processors to perform operations comprising: receiving a semantic map that represents a physical environment; generating a route graph based at least on the semantic map, the route graph including one or more route graph edges, and each route graph edge including an associated location in one or more map regions of the semantic map and an associated cost; determining a cost of a particular route graph edge of the route graph edges based at least on a region type of the particular route graph edge, the region type being determined based at least on a map region in which the particular route graph edge is located; and determining, using the route graph, a plurality of edges that form a route plan for a mobile robot to move from a first location on the semantic map to a second location on the semantic map, the plurality of edges including the particular route graph edge and selected based at least on a cumulative cost computed as a weighted sum based at least on region types of map regions traversed by the plurality of edges and corresponding edge lengths, the mobile robot configured to navigate through at least a portion of the physical environment based on at least the route plan.
19. 19 . The system of claim 18 , wherein each point of a plurality of points on the particular route graph edge is located at a respective determined distance from each of two or more boundary lines of the map region in which the particular route graph edge is located.
20. 20 . The system of claim 18 , wherein the system is comprised in at least one of: a control system for an autonomous or semi-autonomous machine; a perception system for an autonomous or semi-autonomous machine; a system for performing simulation operations; a system for performing digital twin operations; a system for performing light transport simulation; a system for performing collaborative content creation for 3D assets; a system for performing deep learning operations; a system implemented using an edge device; a system for generating or presenting at least one of virtual reality content, augmented reality content, or mixed reality content; a system implemented using a robot; a system for performing conversational AI operations; a system for performing one or more generative AI operations; a system implementing one or more large language models (LLMs); a system for generating synthetic data; a system incorporating one or more virtual machines (VMs); a system implemented at least partially in a data center; or a system implemented at least partially using cloud computing resources.

Description

BACKGROUND To traverse an environment, many autonomous or semi-autonomous mobile robots move through the environment to a given destination according to a route determined by a route planner. The route planner may use a waypoint graph to determine routes, where the waypoint graph represents areas in a physical environment through which the robot can move. The waypoint graph also represents areas through which the robot cannot move, such as physical obstacles. The physical environment can be a building, such as a warehouse, and the waypoint graph can be a map of the floor areas of the building, for example. As another example, the waypoint graph can represent a road network for vehicle traffic, and the given destination can be a street address. In existing approaches, the route planner uses an occupancy map to generate a waypoint graph. The occupancy map represents the physical environment as a grid of cells and indicates whether each cell is occupied by an obstacle. The route planner uses the waypoint graph to determine routes through the environment. The waypoint graph includes a set of vertices that represent locations in the environment and a set of edges that connect the vertices. The edges represent navigable surfaces that a robot can physically occupy. The edges are associated with costs, which can correspond to travel time between vertices. However, there can be different types of navigable surfaces in an environment, and the different types of navigable surfaces can have different effects on route planning. In existing approaches, the waypoint graph does not include information about characteristics of the navigable surfaces that are relevant to how a robot moves through the environment. Thus, for example, the edge costs do not accurately represent travel time for surfaces on which the robot slows down, such as ramps. The use of inaccurate edge costs can cause the route planner to generate sub-optimal route plans. As an example, a robot moves at a reduced speed on a particular ramp, but edge cost for the ramp is not adjusted to reflect the reduced speed in existing techniques. Accordingly, the real-world navigation cost of the ramp is greater than the cost used by the route planner, and the real-world travel time for a route that crosses the ramp is greater than the expected travel time used by the route planner. Route plans generated based on inaccurate costs can be sub-optimal, since such route plans are likely to be chosen instead of other route plans that have lower true costs. As such, a need exists for more effective techniques for generating route plans in environments having multiple different types of navigable surfaces that have different effects on route planning in autonomous or semi-autonomous systems. SUMMARY Embodiments of the present disclosure relate to generating a route plan based on a waypoint graph in which edge costs are determined from a semantic map. The techniques described herein include generating a route plan by, at least, receiving, at a computing device, a semantic map that represents a physical environment. The techniques may further include generating a route graph based on the semantic map, where the route graph includes one or more route graph edges, wherein each route graph edge has an associated location in one or more map regions of the semantic map and an associated cost. The techniques may also include determining a cost of a particular route graph edge based on a region type, where the region type is determined based on a map region in which the particular route graph edge is located. The techniques may further include generating, using the route graph, a route plan for a mobile robot to move from a given start location on the semantic map to a given destination location on the semantic map. One technical advantage of the disclosed techniques relative to the prior approaches is the ability to generate route plans based on semantic information associated with waypoint graph edges, so that the route plan accurately reflects the cost of navigation in each area represented by a waypoint graph edge. For example, the cost of each edge is based on the type of navigable surface represented by the edge. Using edge costs based on the type of navigable surface allows the disclosed graph generator to accurately identify optimal paths between given locations. These technical advantages represent one or more technological improvements over prior approaches. BRIEF DESCRIPTION OF THE DRAWINGS The present systems and methods for generating a route plan based on a waypoint graph for robotics systems and applications are described in detail below with reference to the attached drawing figures, wherein: FIG. 1 illustrates a computing device configured to implement one or more aspects of various embodiments; FIG. 2 is a more detailed illustration of the waypoint graph generator of FIG. 1, according to various embodiments; FIG. 3A illustrates an example Voronoi diagram on an exampl