Graph construction and execution ML techniques

Patent metadata

Field	Value
Publication number	US-12326732-B2
Application number	US-202117232818-A
Country	US
Kind code	B2
Filing date	Apr 16, 2021
Priority date	Apr 16, 2020
Publication date	Jun 10, 2025
Grant date	Jun 10, 2025

Abstract

Discussed herein are devices, systems, and methods for autonomous, dynamic navigation of scenarios. A method can include implementing a path generation machine learning (ML) technique to determine paths between a device and a goal, determining a node of the paths as an intersection of at least two of the paths, and implementing an executive ML technique to determine which of the at least two paths to take at a node of the graph to reach the goal.

First claim

What is claimed is:

1. A device comprising:
at least one memory storing data of a path generation machine learning (ML) technique, an executive multi-agent reinforcement learning (MARL) ML technique, a motion ML technique, and a goal associated with a target; and
processing circuitry configured to:
implement the path generation ML technique to determine multiple, distinct paths between the device and a target resulting in pre-determined paths that jointly form a graph, the path generation ML technique is constrained to generate a path of the pre-determined paths that is achievable based on a physics-based model of a vehicle and minimizes usage of a resource and then blocking that path to find an alternative path of the pre-determined paths that minimizes the usage of the resource;
determine a node of the pre-determined paths as an intersection of at least two paths of the pre-determined paths;
implement the executive MARL ML technique to determine which of the at least two pre-determined paths to take at a node of the graph to achieve the goal and reach the target resulting in a selected path; and
implement the motion ML technique to cause the device to traverse the selected path.

2. The device of claim 1 , wherein the memory includes data representing a three-dimensional (3D) point cloud of an environment around the device, wherein a density of the points in the 3D point cloud represent severity of risk to the device in traversing through that portion of the environment represented by the 3D point cloud.

3. The device of claim 1 , wherein the executive ML technique includes a Markov Decision Process (MDP) and operates only to determine which path of the pre-determined paths to take at the node.

4. The device of claim 3 , wherein the executive ML technique determines the selected path to take based on a defined goal and a reinforcement learning (RL) reward.

5. The device of claim 4 , wherein the executive ML technique determines the selected path to take based further on a reinforcement learning (RL) reward of a second device and respective capabilities constraints of the device and the second device; and
the goal is common to the first and second devices.

6. The device of claim 1 , wherein the path generation ML technique operates using a neural planner.

7. The device of claim 1 , wherein the path generation ML technique is one of a plurality of path generation ML techniques, each of the path generation ML techniques trained based on a different constraints.

8. The device of claim 7 , wherein the different constraints include two or more of least fuel used in traversing the path, least time to traverse the path, or least damage to the device in traversing the path.

9. A method of navigating to a goal, the method comprising:
implementing a path generation machine learning (ML) technique to determine multiple, distinct paths between a device and the goal resulting in pre-determined paths that jointly form a graph, the path generation ML technique is constrained to generate a path of the pre-determined paths that is achievable based on a physics-based model of a vehicle and minimizes usage of a resource and then blocking that path to find an alternative path of the pre-determined paths that minimizes the usage of the resource;
determining a node of the pre-determined paths as an intersection of at least two paths of the pre-determined paths; and
implementing an executive ML technique to determine which of the at least two pre-determined paths to take at a node of the graph to achieve the goal resulting in a selected path.

10. The method of claim 9 , wherein the executive ML technique determines which pre-determined path to take based on data representing a three-dimensional (3D) point cloud of an environment around the device as input, wherein a density of the points in the 3D point cloud represent severity of risk to the device in traversing through that portion of the environment represented by the 3D point cloud.

11. The method of claim 9 , wherein the executive ML technique includes a Markov Decision Process (MDP) and operates only to determine which path of the pre-determined paths to take at the node.

12. The method of claim 11 , wherein the executive ML technique determines the pre-determined path of the pre-determined paths to take based the goal and a reinforcement learning (RL) reward for reaching the goal.

13. The method of claim 11 , wherein the executive ML technique determines the pre-determined path of the pre-determined paths to take based further on an RL reward of a second device and respective capabilities constraints of the device and the second device and the goal is shared between the device and the second device.

14. The method of claim 9 , wherein the path generation ML technique operates using a neural planner.

15. A machine-readable medium including instructions that, when executed by a machine, cause the machine to perform operations for navigating to a goal, the operations comprising:
implementing a path generation machine learning (ML) technique to determine multiple, distinct paths between a device and the goal resulting in pre-determined paths that jointly form a graph, the path generation ML technique is constrained to generate a path of the pre-determined paths that is achievable based on a physics-based model of a vehicle and minimizes usage of a resource and then blocking that path to find an alternative path of the pre-determined paths that minimizes the usage of the resource;
determining a node of the pre-determined paths as an intersection of at least two paths of the pre-determined paths; and
implementing an executive ML technique to determine which of the at least two pre-determined paths to take at a node of the graph to achieve the goal resulting in a selected path.

16. The machine-readable medium of claim 15 , wherein the executive ML technique determines which pre-determined path to take based on data representing a three-dimensional (3D) point cloud of an environment around the device as input, wherein a density of the points in the 3D point cloud represent severity of risk to the device in traversing through that portion of the environment represented by the 3D point cloud.

17. The machine-readable medium of claim 16 , wherein the executive ML technique includes a Markov Decision Process (MDP) and the path generation ML technique includes a neural planner and operates only to determine which path of the pre-determined paths to take at the node.

18. The machine-readable medium of claim 15 , wherein the executive ML technique determines the selected path of the pre-determined paths to take based the goal and a reinforcement learning (RL) reward for reaching the goal.

19. The machine-readable medium of claim 15 , wherein the path generation ML technique is one of a plurality of path generation ML techniques, each of the path generation ML techniques trained based on a different constraints.

20. The machine-readable medium of claim 19 , wherein the different constraints include two or more of least fuel used in traversing the path, least time to traverse the path, or least damage to the device in traversing the path.

Assignees

• Raytheon Co

Inventors

• Young Darrell L
• Eccles Christopher A
• Tanner Franklin

Classifications

• G06N3/09

  Supervised learning · CPC title

• G06N3/0455

  Auto-encoder networks; Encoder-decoder networks · CPC title

• G06N3/092

  Reinforcement learning · CPC title

• G06N3/0499

  Feedforward networks · CPC title

• G06N3/08

  Learning methods · CPC title