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

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 claim 10 , further comprising a navigation unit to obtain the first source as a position of the vehicle and provide the obtained information to the computer unit.

18. A non-transitory computer program product for generating a path for a vehicle from a first source to a target within a 2D environment with one or more obstacles, the non-transitory computer program product comprising computer code instructions that, when executed by a processor, cause the processor to perform a 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 ( 106 ) 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; and

composing a valid path connecting the first source to the target based on the plurality of conflict-free sub-paths.

19. The non-transitory computer program product of claim 18 , 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.

20. The non-transitory computer program product of claim 19 , 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.