Path planning

• US 9,784,586 B2
• Filed: 07/04/2014
• Issued: 10/10/2017
• Est. Priority Date: 07/15/2013
• Status: Active Grant

• Current Assignee: BAE Systems Plc
• Original Assignee: BAE Systems Plc
• Inventors: Deittert, Markus
• Primary Examiner(s): Shafi, Muhammad
• Application Number:
  US14/905,194
• Publication Number:
  US 20160153791A1
• Time in Patent Office: 1,194 Days
• Field of Search: 701 25, 701 26- 49
• CPC Class Codes: B60W 30/146 Speed limiting
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• 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/0217 in accordance with energy consumption, time reduction or distance reduction criteria
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

Disclosed are methods and apparatus for determining a path (4) for a vehicle (2). The method comprises providing starting and final positions for the vehicle (2), and using the provided positions, determining an ordered sequence of points, thereby providing the path (4) for the vehicle (2). Performing the optimisation process comprises: minimising a distance between the final position and a last point in the sequence; for each point other than a last point in the sequence, constraining a distance between that point and the next point to be equal to a predefined distance; and, for each path point other than the first and last points, constraining an angle between a line that connects that point to the point that precedes it and a line that connects that point to the next point to be greater than or equal to a predefined angle.

Claims

1. An apparatus for determining a path for a vehicle, the apparatus comprising:

one or more processors configured, using a starting position for the vehicle and a desired terminal position for the vehicle, to perform an optimisation process to determine a position for each path point in an ordered sequence of path points (P1-Pn), the ordered sequence of path points (P1-Pn) defining the path for the vehicle;

wherein performing the optimisation process comprises;

minimising a distance between the desired final position for the vehicle and a last path point (P_n) in the sequence of path points (P₁-P_n);

for each path point other than a last path point (Pn) in the sequence of path points (P1-Pn), constraining a distance between that path point and the next path point in the ordered sequence (P₁-P_n) to be equal to a predefined distance; and

for each path point other than the first path point (P₁) in the ordered sequence (P₁-P_n) and the last path point (P_n) in the ordered sequence (P₁-P_n), constraining an angle between a line that connects that path point to the path point that precedes that path point in the ordered sequence (P₁-P_n) and a line that connects that path point to the next path point in the ordered sequence (P₁-P_n) to be greater than or equal to a predefined angle.

2. The apparatus according to claim 1, wherein the apparatus further comprises a vehicle controller operatively coupled to the one or more processors and configured to control the vehicle such that the vehicle follows the determined path.

3. The apparatus according to claim 1, wherein performing the optimisation process further comprises controlling, by a vehicle controller operatively coupled to the one or more processors, the vehicle such that the vehicle follows the determined path.

4. The apparatus according to claim 1, wherein performing the optimisation process further comprises:

for each path point, projecting a vector between that path point and the next path point in the ordered sequence (P₁-P_n) onto each of a plurality of base vectors, thereby providing a plurality of projections; and

for each path point, constraining the plurality of projections for that path point to be less than or equal to the predefined distance.

5. The apparatus according to claim 1, wherein performing the optimisation process further comprises:

for each path point, projecting a vector between that path point and the next path point in the ordered sequence (P₁-P_n) onto each of a plurality of base vectors, thereby providing a plurality of projections; and

for each path point, constraining one of the projections for that path point to be greater than or equal to some proportion of the predefined distance.

6. The apparatus according to claim 1, wherein performing the optimisation process further comprises, for each path point other than the first path point (P₁) in the ordered sequence (P₁-P_n) and the last path point (P_n) in the ordered sequence (P₁-P_n), constraining a distance between that path point and a line that connects the path point that precedes that path point in the ordered sequence (P₁-P_n) to the path point that follows that path point in the ordered sequence (P₁-P_n) to be less than or equal to a further predefined distance.

7. The apparatus according to claim 6, wherein the further predefined distance is some function of an angle, the angle being dependent upon a minimum turning radius of the vehicle.

8. The apparatus according to claim 6, wherein the further predefined distance is some function of the predefined distance.

9. The apparatus according to claim 1, wherein performing the optimisation process further comprises constraining a position of the second path point in the ordered sequence (P₁-P_n) to be dependent upon a position of the first path point (P₁) in the ordered sequence and a vector that points in substantially the same direction as an initial velocity of the vehicle.

10. The apparatus according to claim 1, wherein the vehicle is operable so as to be switched between operating in a forward gear and a reverse gear;

and performing the optimisation process further comprises determining a switch profile for the vehicle, the switch profile specifying, for each path point, whether or not the vehicle is switched between operating in the forward gear and the reverse gear.

11. The apparatus according to claim 1, wherein performing the optimisation process further comprises determining a velocity profile for the vehicle, the velocity profile specifying a velocity for the vehicle at each path point in the ordered sequence of path points (P₁-P_n).

12. The apparatus according to claim 11, wherein performing the optimisation process further comprises constraining a speed of the vehicle at the last path point (P_n) in the ordered sequence (P₁-P_n) to be less than or equal to a predefined threshold speed.