Computer-implemented method and a system for guiding a vehicle within a scenario with obstacles

• US 10,352,711 B2
• Filed: 08/25/2017
• Issued: 07/16/2019
• Est. Priority Date: 10/06/2016
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Diaz, Lucas Rodriguez, Querejeta, Carlos, Hernandez, Ernesto Valls
• Primary Examiner(s): Antonucci, Anne M
• Assistant Examiner(s): LaRose, Renee
• Application Number:
  US15/686,974
• Publication Number:
  US 20180100743A1
• Time in Patent Office: 690 Days
• CPC Class Codes: B64C 39/024 of the remote controlled vehicle type, i.e. RPV
• CPC Class Codes: B64U 2201/10 autonomous, i.e. by navigating independently from ground or air stations, e.g. by using inertial navigation systems [INS]
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3469 Fuel consumption; Energy use; Emission aspects
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0202 specially adapted to aircraft
• CPC Class Codes: G05D 1/0212 with means for defining a desired trajectory involving a plurality of land vehicles G05D1/0287
• CPC Class Codes: G05D 1/0217 in accordance with energy consumption, time reduction or distance reduction criteria

Abstract

A method and a system for guiding a vehicle from a source to a target within a scenario with obstacles are disclosed. The source is established as a starting point and a subpath to the target is computed. When an obstacle is detected that crosses the computed subpath, a plurality of obstacle-free subpaths are computed to connect the starting point to a waypoint of an outer boundary of a detected obstacle. Priorities for each waypoint are computed and ordered accordingly in a list of potential waypoints to select the highest priority waypoint in the list as a new starting point. Previous operations are repeated until the target is reached, thus the path is obtained by backtracking waypoints to the source. The vehicle can be then guided and the target reached via the obtained path.

Claims

1. A computer-implemented method for guiding a vehicle from a source (S) to a target (T) within a scenario with obstacles, the method comprising:

establishing the source (S) as a starting point (S′

);

computing a subpath from the starting point (S′

) to the target (T);

detecting if an obstacle (O) crosses the computed subpath;

repeatedly, for a detected obstacle (O), computing a plurality of obstacle-free subpaths avoiding the detected obstacle (O), each obstacle-free subpath connecting the starting point (S′

) to a waypoint (W) of an outer boundary of a detected obstacle (O);

computing a priority value for each waypoint (W), wherein the priority value is computed based on;

the distance between the waypoint (W) and the target (T) regardless of eventual obstacles and

the accumulated distance from the source to the waypoint (W), wherein accumulated distance comprises at least the distance between the starting point and the ending point of at least one computed obstacle-free subpath from the source to the waypoint (W), the distance being defined according to a pre-established metric;

storing each waypoint (W) and its corresponding priority in a list of potential waypoints (LPW);

selecting the highest priority waypoint (W) in the list as a starting point (S′

) and repeating the previous steps until the target (T) is reached;

obtaining an optimal path by backtracking waypoints (W) from the target (T) to the source (S); and

guiding the vehicle according to the optimal path.

2. The computer-implemented method of claim 1, wherein the outer boundary of an obstacle (O) is modelled by a geometrical figure.

3. The computer-implemented method of claim 2, wherein the waypoint (W) is obtained as an intersection of a common tangent segment to the geometrical figure corresponding to the obstacle (O).

4. The computer-implemented method of claim 3, wherein the waypoint is a vertex of a polygon.

5. The computer-implemented method of claim 1, wherein the metric is selected among the following:

Euclidean, less fuel consumption, less altitude, Geodesic distance.

6. The computer-implemented method of claim 1, wherein the obstacle is represented by a no-incursion zone.

7. The computer-implemented method of claim 1, wherein the vehicle is selected among a UAV, an aircraft, a ground robot and an autonomous car.

8. A system for guiding a vehicle from a source (S) to a target (T) within a scenario with obstacles comprising:

a path computing unit (10) configured to;

establish the source (S) as a starting point (S′

);

compute a subpath from the starting point (S′

) to the target (T);

a detecting unit (20) configured to detect if an obstacle (O) crosses a computed subpath;

the path computing unit (10) further configured to repeatedly compute a plurality of obstacle-free subpaths avoiding the detected obstacle (O), each obstacle-free subpath connecting the starting point (S′

) to a waypoint (W) of an outer boundary of an obstacle (O) detected in a computed path;

a selecting unit (30) configured to;

compute a priority value for each waypoint (W), wherein the priority value is computed based on the distance between the waypoint (W) and the target (T) regardless of eventual obstacles and the accumulated distance from the source to the waypoint (W), wherein accumulated distance comprises at least the distance between the starting point and the ending point of at least one generated obstacle-free path from the source to the waypoint (W), the distance being defined according to a pre-established metric;

store each waypoint (W) and its corresponding priority in a list of potential waypoints (LPW) to check;

select the highest priority waypoint (W) in the list as a starting point (S′

) and repeating the previous steps until the target (T) is reached;

the path computing unit (10) further configured to;

obtain an optimal path by backtracking waypoints (W) from the target (T) to the source (S); and

a guiding unit (40) configured to guide the vehicle according to the optimal path.

9. The system of claim 8, wherein the outer boundary of an obstacle (O) is modelled by a geometrical figure.

10. The system of claim 9, wherein the waypoint (W) is obtained as an intersection of a common tangent segment to the geometrical figure corresponding to the obstacle (O).

11. The system of claim 10, wherein the waypoint is a vertex of a polygon.

12. The system of claim 8, wherein the metric is selected among the following:

Euclidean, less fuel consumption, less altitude, Geodesic distance.

13. The system of claim 8, wherein the obstacle is represented by a no-incursion zone.

14. The system of claim 8, wherein the vehicle is selected among a UAV, an aircraft, a ground robot and an autonomous car.

15. A computer program product for guiding a vehicle from a source to a target within a scenario with obstacles comprising computer code instructions that, when executed by a processor, causes the processor to perform functions comprising:

establishing the source (S) as a starting point (S′

);

computing a subpath from the starting point (S′

) to the target (T);

detecting if an obstacle (O) crosses the computed subpath;

repeatedly, for a detected obstacle (O), computing a plurality of obstacle-free subpaths avoiding the detected obstacle (O), each obstacle-free subpath connecting the starting point (S′

) to a waypoint (W) of an outer boundary of a detected obstacle (O);

computing a priority value for each waypoint (W), wherein the priority value is computed based on;

the distance between the waypoint (W) and the target (T) regardless of eventual obstacles and

the accumulated distance from the source to the waypoint (W), wherein accumulated distance comprises at least the distance between the starting point and the ending point of at least one computed obstacle-free subpath from the source to the waypoint (W), the distance being defined according to a pre-established metric;

storing each waypoint (W) and its corresponding priority in a list of potential waypoints (LPW);

selecting the highest priority waypoint (W) in the list as a starting point (S′

) and repeating the previous steps until the target (T) is reached;

obtaining an optimal path by backtracking waypoints (W) from the target (T) to the source (S); and

guiding the vehicle according to the optimal path.

16. The computer program product of claim 15, wherein the outer boundary of an obstacle (O) is modelled by a geometrical figure.

17. The computer program product of claim 16, wherein the waypoint (W) is obtained as an intersection of a common tangent segment to the geometrical figure corresponding to the obstacle (O).

18. The computer program product of claim 17, wherein the waypoint is a vertex of a polygon.

19. The computer program product of claim 15, wherein the metric is selected among the following:

Euclidean, less fuel consumption, less altitude, Geodesic distance.

20. The computer program product of claim 15, wherein the obstacle is represented by a no-incursion zone.