Computer-implemented method and a system for defining a path for a vehicle within an environment with obstacles

Patent metadata

Field	Value
Publication number	US-11262764-B2
Application number	US-201916570979-A
Country	US
Kind code	B2
Filing date	Sep 13, 2019
Priority date	Sep 14, 2018
Publication date	Mar 1, 2022
Grant date	Mar 1, 2022

Abstract

A computer-implemented method and a system for generating a path for a vehicle from a source to a target within a two-dimensional (2D) environment with one or more obstacles is disclosed. The obstacles may be dynamic, static or both. The method comprises generating, in a two dimensions-plus-time space, a velocity cone that represents a set of potential waypoints reachable from a first source for the vehicle moving at a speed, providing a polytope, obtaining at least one interception polygon by intersecting and projecting the velocity cone with the polytope on the 2D region; generating a 2D scene comprising interception polygons to avoid, computing a visibility graph algorithm for the 2D scene and obtaining a plurality of conflict-free sub-paths, and composing a valid path connecting the source to the target based on the plurality of conflict-free sub-paths.

First claim

The invention claimed is:

1. A computer-implemented method for generating a path for a vehicle from a first source to a target within a two-dimensional (2D) environment with one or more obstacles, the method comprising:
generating, in a two dimensions plus time (2D+t) space, a velocity cone having a slope corresponding to a first speed and an apex at the first source at an initial time, wherein the velocity cone represents a set of potential waypoints reachable from the first source for the vehicle moving at the first speed;
for each obstacle present in the 2D environment, wherein the obstacle is a static obstacle or a dynamic obstacle, providing a polytope in the 2D+t space, wherein the polytope represents a 2D polygon modeling an obstacle at an initial time with its evolution over time;
obtaining one or more interception polygons by intersecting the velocity cone with the polytope in the 2D+t space, thereby forming a non-planar surface, and projecting the non-planar surface on the 2D environment;
generating a first 2D scene comprising the one or more interception polygons to avoid;
computing a visibility graph algorithm for the first 2D scene based on a first number of vertices associated with the one or more interception polygons and obtaining a plurality of conflict-free sub-paths for the vehicle to traverse that avoids each obstacle;
composing a valid path connecting the first source to the target based on the plurality of conflict-free sub-paths;
producing instructions for guiding the vehicle among the obstacles according to the valid path; and
controlling movement of the vehicle in accordance with the instructions.

2. The method of claim 1 , wherein the visibility graph algorithm applies a vertex reduction heuristic based on checking visibility of a segment from the first source to the target among the one or more interception polygons.

3. The method of claim 2 , wherein the vertex reduction heuristic is further based on:
computing a common tangent segment to each interception polygon being crossed and adding to a list endpoints of the common tangent segment as potential waypoints; and
backtracking the potential waypoints from the target to the first source.

4. The method of claim 1 , wherein once a waypoint is included in a sub-path, said added included waypoint becomes a second source to construct a subsequent velocity cone until the target is reached.

5. The method of claim 4 , further comprising:
generating a second 2D scene according to the subsequent velocity cone, wherein the subsequent velocity cone is constructed having a slope corresponding to a second speed and an apex at the second source, the second speed being different than the first speed.

6. The method of claim 5 , further comprising:
computing, in parallel, a visibility graph algorithm for the second 2D scene, thereby obtaining a plurality of conflict-free sub-paths associated with the second speed; and
composing an alternative valid path based on the plurality of conflict-free sub-paths for the vehicle to traverse at the second speed.

7. The method of claim 5 , further comprising:
computing, in parallel, a visibility graph algorithm for the second 2D scene, thereby obtaining a plurality of conflict-free sub-paths associated with the first speed or the second speed; and
composing an alternative valid path based on the plurality of conflict-free sub-paths, wherein at least one conflict-free sub-path is traversed at the second speed.

8. The method of claim 6 , further comprising selecting the first speed or the second speed for the vehicle to traverse an obstacle according to a selection criterion based on at least one of the following: estimated arrival time, computation time and traversed distance from the first source to the target.

9. The method of claim 1 , wherein computing the visibility graph algorithm further comprises producing at least one offset polygon, wherein the offset polygon is produced by a buffer area surrounding at least one of the one or more interception polygons.

10. A system for generating a path for a vehicle from a first source to a target within a 2D environment with one or more obstacles, the system comprising:
a computing unit comprising a memory storing computer readable code and at least one processor to execute the computer readable code to cause the at least one processor to:
generate, in a 2D+t space, a velocity cone having a slope corresponding to a first speed and an apex at the first source at an initial time, wherein the velocity cone represents a set of potential waypoints reachable from the first source for the vehicle moving at the first speed;
provide a polytope in the 2D+t space for each obstacle present in the 2D environment, wherein the obstacle is a static obstacle or a dynamic obstacle, wherein the polytope represents a 2D polygon modeling an obstacle at an initial time with its evolution over time;
obtain one or more interception polygons by intersecting the velocity cone with the polytope in the 2D+t space thereby forming a non-planar surface, and project the non-planar surface on the 2D environment;
generate a 2D scene comprising the one or more interception polygons to avoid;
compute a visibility graph algorithm for the 2D scene based on a first number of vertices associated with the one or more interception polygons and obtaining a plurality of conflict-free sub-paths for the vehicle to traverse that avoids each obstacle; and
compose a valid path connecting the first source to the target based on the plurality of conflict-free sub-paths,
wherein the processor is further configured to produce instructions for guiding the vehicle among the one or more obstacles according to the valid path, the system further comprising a control system on-board the vehicle configured for controlling movement of the vehicle in accordance with the instructions.

11. The system of claim 10 , wherein the visibility graph algorithm applies a vertex reduction heuristic based on checking visibility of a segment from the first source to the target among the one or more interception polygons.

12. The system of claim 11 , wherein the vertex reduction heuristic is further based on:
computing a common tangent segment to each interception polygon being crossed and adding to a list endpoints of the common tangent segment as potential waypoints; and
backtracking the potential waypoints from the target to the first source.

13. The system of claim 10 , wherein once a waypoint is included in a sub-path, said added included waypoint becomes a second source to construct a subsequent velocity cone until the target is reached.

14. The system of claim 13 , wherein the processor is further configured to generate a second 2D scene according to the subsequent velocity cone, wherein the subsequent velocity cone is constructed having a slope corresponding to a second speed and an apex at the second source, the second speed being different than the first speed.

15. The system of claim 10 , wherein computing the visibility graph algorithm further comprises producing at least one offset polygon, wherein the offset polygon is produced by a buffer area surrounding at least one of the one or more interception polygons present in the 2D scene.

16. The system of claim 10 , further comprising a plurality of sensors for gathering information about obstacles present in the 2D environment, wherein the computing unit receives the information from the plurality of sensors and provides a polytope in the 2D+t space for each obstacle based on the received information.

17. The system of cla

Assignees

• Boeing Co

Inventors

• Navarro Francisco A
• Rodriguez Diaz Lucas
• Valls Hernandez Ernesto

Classifications

• B64U2201/10

  autonomous, i.e. by navigating independently from ground or air stations, e.g. by using inertial navigation systems [INS] · CPC title

• G01C21/3407

  specially adapted for specific applications · CPC title

• G01C21/20 Primary

  Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) · CPC title

• G06Q10/047

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• G05D2201/0213

  Physics · mapped topic