Graph exploration forward search

Patent metadata

Field	Value
Publication number	US-12560447-B2
Application number	US-202318152047-A
Country	US
Kind code	B2
Filing date	Jan 9, 2023
Priority date	Oct 14, 2022
Publication date	Feb 24, 2026
Grant date	Feb 24, 2026

Abstract

Provided are methods for graph forward search exploration, which can include detecting a plurality of obstacles along a first trajectory of a vehicle. Some methods described also include determining a plurality of valid combinations of a plurality of trajectories to handle the plurality of obstacles. Some methods described also include generating a reduced decision tree based at least on the valid combinations of the plurality of trajectories by at least excluding a second trajectory of the plurality of trajectories associated with an obstacle of a plurality of obstacles based on a position of the obstacle being outside of a corridor defined by a spatial range and/or a temporal range. Some methods described also include selecting an optimal trajectory of the vehicle from the plurality of trajectories of the reduced decision tree. Systems and computer program products are also provided.

First claim

What is claimed is:

1 . A system comprising:
at least one processor; and at least one memory storing instructions thereon that, when executed by the at least one processor, result in operations comprising: detecting a plurality of obstacles along a first trajectory of a vehicle; determining a plurality of valid combinations of a plurality of trajectories representing a passing maneuver and a lateral maneuver to navigate through an environment including the plurality of obstacles and the vehicle, wherein a combination of the passing maneuver and the lateral maneuver is valid when the combination is physically possible based on a position of the vehicle relative to a position of at least one obstacle; generating a reduced decision tree based at least on the plurality of valid combinations by at least excluding a second trajectory of the plurality of trajectories based on a position of a corresponding obstacle being outside of a corridor defined by a spatial range and/or a temporal range, wherein the spatial range and/or the temporal range is adjusted to limit a quantity of valid combinations remaining in the reduced decision tree; and controlling operation of the vehicle according to an optimal trajectory of the vehicle selected from the plurality of trajectories of the reduced decision tree.

2 . The system of claim 1 , wherein the reduced decision tree is further generated by at least including, in the reduced decision tree, at least one trajectory of the plurality of trajectories associated with at least one obstacle of the plurality of obstacles based on a position of the at least one obstacle being within the corridor.

3 . The system of claim 1 , wherein determining the plurality of valid combinations comprises: independently validating the passing maneuver and/or the lateral maneuver for each obstacle of the plurality of obstacles.

4 . The system of claim 3 , wherein determining the plurality of valid combinations further comprises: removing, based on the independently validating the passing maneuver and/or the lateral maneuver for each obstacle, the passing maneuver from a plurality of passing maneuvers and/or the lateral maneuver from a plurality of lateral maneuvers.

5 . The system of claim 4 , wherein determining the plurality of valid combinations further comprises: generating a plurality of combinations of the independently validated passing maneuver and the lateral maneuver.

6 . The system of claim 5 , wherein determining the plurality of valid combinations further comprises: independently validating the plurality of combinations to define the plurality of valid combinations.

7 . The system of claim 6 , wherein determining the plurality of valid combinations further comprises: removing, based on the independently validating the plurality of combinations, a combination of the plurality of combinations.

8 . The system of claim 1 , wherein determining the plurality of valid combinations further comprises ordering the plurality of obstacles in the decision tree based on a distance between the vehicle and the plurality of obstacles.

9 . A method comprising:
detecting a plurality of obstacles along a first trajectory of a vehicle; determining a plurality of valid combinations of a plurality of trajectories representing a passing maneuver and a lateral maneuver to navigate through an environment including the plurality of obstacles and the vehicle, wherein a combination of the passing maneuver and the lateral maneuver is valid when the combination is physically possible based on a position of the vehicle relative to a position of at least one obstacle; generating a reduced decision tree based at least on the plurality of valid combinations by at least excluding a second trajectory of the plurality of trajectories based on a position of a corresponding obstacle being outside of a corridor defined by a spatial range and/or a temporal range, wherein the spatial range and/or the temporal range is adjusted to limit a quantity of valid combinations remaining in the reduced decision tree; and controlling operation of the vehicle according to an optimal trajectory of the vehicle selected from the plurality of trajectories of the reduced decision tree.

10 . The method of claim 9 , wherein the reduced decision tree is further generated by at least including, in the reduced decision tree, at least one trajectory of the plurality of trajectories associated with at least one obstacle of the plurality of obstacles based on a position of the at least one obstacle being within the corridor.

11 . The method of claim 9 , wherein determining the plurality of valid combinations comprises: independently validating the passing maneuver and/or the lateral maneuver for each obstacle of the plurality of obstacles.

12 . The method of claim 11 , wherein determining the plurality of valid combinations further comprises: removing, based on the independently validating the passing maneuver and/or the lateral maneuver for each obstacle, the passing maneuver from a plurality of passing maneuvers and/or the lateral maneuver from a plurality of lateral maneuvers.

13 . The method of claim 12 , wherein determining the plurality of valid combinations further comprises: generating a plurality of combinations of the independently validated passing maneuver and the lateral maneuver.

14 . The method of claim 13 , wherein determining the plurality of valid combinations further comprises: independently validating the plurality of combinations to define the plurality of valid combinations.

15 . The method of claim 14 , wherein determining the plurality of valid combinations further comprises: removing, based on the independently validating the plurality of combinations, a combination of the plurality of combinations.

16 . The method of any one of claim 9 , wherein determining the plurality of valid combinations further comprises ordering the plurality of obstacles in the decision tree based on a distance between the vehicle and the plurality of obstacles.

17 . At least one non-transitory storage media storing instructions that, when executed by at least one processor, cause the at least one processor to:
detect a plurality of obstacles along a first trajectory of a vehicle; determine a plurality of valid combinations of a plurality of trajectories representing a passing maneuver and a lateral maneuver to navigate through an environment including the plurality of obstacles and the vehicle, wherein a combination of the passing maneuver and the lateral maneuver is valid when the combination is physically possible based on a position of the vehicle relative to a position of at least one obstacle; generate a reduced decision tree based at least on the plurality of valid combinations by at least excluding a second trajectory of the plurality of trajectories based on a position of a corresponding obstacle being outside of a corridor defined by a spatial range and/or a temporal range, wherein the spatial range and/or the temporal range is adjusted to limit a quantity of valid combinations remaining in the reduced decision tree; and controlling operation of the vehicle according to an optimal trajectory of the vehicle selected from the plurality of trajectories of the reduced decision tree.

18 . The at least one non-transitory storage media of claim 17 , wherein the plurality of trajectories comprises a passing maneuver and/or a lateral maneuver for each obstacle of the plurality of obstacles; and wherein the instructions that cause the at least one processor to determi

Assignees

• Motional Ad Llc

Inventors

• Andersen Hans
• Cserna Bence

Classifications

• G06N5/022

  Knowledge engineering; Knowledge acquisition · CPC title

• G01C21/3446

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

• G08G1/166

  for active traffic, e.g. moving vehicles, pedestrians, bikes · CPC title

• B60W30/0956

  the prediction being responsive to traffic or environmental parameters · CPC title

• B60W60/0011

  involving control alternatives for a single driving scenario, e.g. planning several paths to avoid obstacles · CPC title